Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/80803
Title: Efficient construction and simplification of Delaunay meshes
Authors: Liu, Yong-Jin
Xu, Chun-Xu
Fan, Dian
He, Ying
Keywords: Delaunay Triangulation
Delaunay Mesh
Issue Date: 2015
Source: Liu, Y.-J., Xu, C.-X., Fan, D., & He, Y. (2015). Efficient construction and simplification of Delaunay meshes. ACM Transactions on Graphics, 34(6), 174-.
Series/Report no.: ACM Transactions on Graphics
Abstract: 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.
URI: https://hdl.handle.net/10356/80803
http://hdl.handle.net/10220/45017
ISSN: 0730-0301
DOI: 10.1145/2816795.2818076
Rights: © 2015 Association for Computing Machinery (ACM). This is the author created version of a work that has been peer reviewed and accepted for publication by ACM Transactions on Graphics, Association for Computing Machinery . It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1145/2816795.2818076].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
Efficient Construction and Simplification of Delaunay Meshes.pdf18.27 MBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 10

40
Updated on Dec 2, 2022

Web of ScienceTM
Citations 10

31
Updated on Dec 1, 2022

Page view(s)

323
Updated on Dec 9, 2022

Download(s) 20

254
Updated on Dec 9, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.