high performance computing on graphics processing units: hgpu.org

The Delaunay edge-flip algorithm is a practical method for transforming any existing triangular mesh S into a mesh T(S) that satisfies the Delaunay condition. Although several implementations of this algorithm are known, to the best of our knowledge no parallel GPU-based implementation has been reported yet. In the present work, we propose a quadriphasic and iterative GPU-based algorithm that transforms 2D triangulations and 3D triangular surface meshes into Delaunay triangulations and improves strongly the performance with respect to a sequential CPU-implementation in large meshes. For 3D surface triangulations, we use a threshold value to prevent edge-flips in triangles that could deform the original geometry. On each phase, we address the main challenges that arise when adapting the problem to a parallel architecture and we present a GPU-based solution for each high CPU-consuming time step, reducing drastically the number sequential operations needed.