View publication
| Title | A GPU-based Method for Generating Quasi-Delaunay Triangulations based on Edge-Flips |
| Authors | Cristobal Navarro, Nancy Hitschfeld, Eliana Scheihing |
| Publication date | 2013 |
| Abstract | The Delaunay edge-flip technique is a practical method for transforming any existing triangular mesh S into a mesh T (S) that satisfies the Delaunay condition. In this paper we present an iterative GPU-based method capable of improving triangulations under the Delaunay criteria. This method is based on the edge-flip tech-nique and its implementation is fully integrable with the OpenGL rendering pipeline. Since the algorithm uses an epsilon value to handle co-circular or close to co-circular point configurations, we can not guarantee that all triangles fulfill the Delaunay condition. However, 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. Based on our experimental results, we report speedups from 14x to 50x against Lawson's sequential algorithm and of approximately 3x against the O(nlog n) CGAL's and Triangle's constructive algorithms while processing bad quality triangulations. |
| Downloaded | 8 times |
| Pages | 27-34 |
| Conference name | International Conference on Computer Graphics Theory and Applications |
| Publisher | SCITEPress: Science and Technology Publicatios |
|