View publication
| Title | Quasi-Delaunay Triangulations Using GPU-Based Edge-Flips |
| Authors | Cristobal Navarro, Eliana Scheihing, Nancy Hitschfeld |
| Publication date | September 2014 |
| Abstract |
The edge-flip technique has been widely used for transforming any existing triangular mesh into a Delaunay mesh. Although several tools for generating Delaunay triangulations are known, there is no one that offers a realtime solution capable of maintaining the Delaunay condition on dynamically changing triangulations and, in particular, one integrable with the OpenGL rendering pipeline. In this paper we present an iterative GPGPU-based method capable of improving triangulations under the Delaunay criterion. Since the algorithm uses an e value to handle co-circular or close to co-circular point configurations, a low percentage of triangles do not fulfill the Delaunay condition. We have compared the triangulations generated by our method with the ones generated by the Triangle software and by the CGAL library and we obtained less than 0.05 % different triangles for full random meshes and less than 1 % for noise based ones. Based on our experimental results, we report speedups from 14x to 50x against Lawson's sequential algorithm and of approximately 3x against the CGAL's and Triangle's constructive algorithms when processing full random triangulations. In our noise based tests we report up to 36x and 27x of speedup against CGAL and Triangle, respectively. |
| Pages | 36-49 |
| Reference URL |
|