A Quasi-Parallel GPU-Based Algorithm for Delaunay Edge-Flips

Cristobal A. Navarro, Nancy Hitschfeld-Kahler, Eliana Scheihing
Informatics Institute, Austral University of Chile, Valdivia, Chile
Austral University of Chile, 2011


   title={A Quasi-Parallel GPU-Based Algorithm for Delaunay Edge-Flips},

   author={Navarro, C.A. and Hitschfeld-Kahler, N. and Scheihing, E.},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: