GPolylla: Fully GPU-accelerated polygonal mesh generator

Abstract

This work presents a fully GPU-accelerated algorithm for the polygonal mesh generator known as Polylla. Polylla is a tri-to-polygon mesh generator, which benefits from the half-edge data structure to manage any polygonal shape. The proposed parallel algorithm introduces a novel approach to modify triangulations to get polygonal meshes using the half-edge data structure in parallel on the GPU. By changing the adjacency values of each half-edge, the algorithm accomplishes to unlink half-edges that are not used in the new polygonal mesh without the need neither removing nor allocating new memory in the GPU. The experimental results show a speedup, reaching up to ×83.2 when compared to the CPU sequential implementation. Additionally, the speedup is ×746.8 when the cost of copying the data structure from the host device and back is not included.

Sergio Salinas-Fernández

Professor PEX at the Universidad de Chile

My research interests include Data science, Computational geometry and GPU computing.

Nancy Hitschfeld Kahler

+Lab founder | Full Professor Universidad de Chile

Full Professor at the Department of Computer Science, University of Chile. Her main research interests include geometric modeling, geometric meshes, and parallel algorithms (GPU computing), focused in computational science, and engineering applications.

Roberto Carrasco

GPU filters for accelerating the convex hull

My research interests include Asados, Empanadas, and Choripanes.