Efficient construction and simplification of Delaunay meshes
| Autor: | Chunxu Xu, Ying He, Dian Fan, Yong-Jin Liu |
|---|---|
| Přispěvatelé: | School of Computer Science and Engineering |
| Rok vydání: | 2015 |
| Předmět: |
Pitteway triangulation
Constrained Delaunay triangulation Delaunay triangulation Delaunay Mesh Delaunay Triangulation Topology Chew's second algorithm Computer Graphics and Computer-Aided Design Bowyer–Watson algorithm Triangle mesh Polygon mesh Ruppert's algorithm ComputingMethodologies_COMPUTERGRAPHICS Mathematics |
| Zdroj: | ACM Transactions on Graphics. 34:1-13 |
| ISSN: | 1557-7368 0730-0301 |
| DOI: | 10.1145/2816795.2818076 |
| Popis: | Delaunay meshes (DM) are a special type of triangle mesh where the local Delaunay condition holds everywhere. We present an efficient algorithm to convert an arbitrary manifold triangle mesh M into a Delaunay mesh. We show that the constructed DM has O ( Kn ) vertices, where n is the number of vertices in M and K is a model-dependent constant. We also develop a novel algorithm to simplify Delaunay meshes, allowing a smooth choice of detail levels. Our methods are conceptually simple, theoretically sound and easy to implement. The DM construction algorithm also scales well due to its O ( nK log K ) time complexity. Delaunay meshes have many favorable geometric and numerical properties. For example, a DM has exactly the same geometry as the input mesh, and it can be encoded by any mesh data structure. Moreover, the empty geodesic circumcircle property implies that the commonly used cotangent Laplace-Beltrami operator has non-negative weights. Therefore, the existing digital geometry processing algorithms can benefit the numerical stability of DM without changing any codes. We observe that DMs can improve the accuracy of the heat method for computing geodesic distances. Also, popular parameterization techniques, such as discrete harmonic mapping, produce more stable results on the DMs than on the input meshes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|