Efficient Construction and Simplification of Delaunay Meshes

Yong-Jin Liu Tsinghua University Chun-Xu Xu Tsinghua University Dian Fan Tsinghua University Ying He Nanyang technological University

Geometric Modeling and Processing mathscidoc:1608.16001

ACM Transactions on Graphics, 34, (6), 174, 2015.12
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 logK) 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.
Delaunay triangulation, Delaunay mesh, geodesic Voronoi diagram, Delaunay mesh simplification
[ Download ] [ 2016-08-19 10:51:32 uploaded by liuyj ] [ 568 downloads ] [ 0 comments ] [ Cited by 3 ]
  title={Efficient Construction and Simplification of Delaunay Meshes },
  author={Yong-Jin Liu, Chun-Xu Xu, Dian Fan, and Ying He},
  booktitle={ACM Transactions on Graphics},
Yong-Jin Liu, Chun-Xu Xu, Dian Fan, and Ying He. Efficient Construction and Simplification of Delaunay Meshes . 2015. Vol. 34. In ACM Transactions on Graphics. pp.174. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819105132820131255.
Please log in for comment!
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved