Efficient construction and simplification of Delaunay meshes
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/80803 http://hdl.handle.net/10220/45017 |
| _version_ | 1824456422950174720 |
|---|---|
| author | Liu, Yong-Jin Xu, Chun-Xu Fan, Dian He, Ying |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Liu, Yong-Jin Xu, Chun-Xu Fan, Dian He, Ying |
| author_sort | Liu, Yong-Jin |
| collection | NTU |
| description | 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. |
| first_indexed | 2025-02-19T03:53:51Z |
| format | Journal Article |
| id | ntu-10356/80803 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:53:51Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/808032020-03-07T11:48:54Z Efficient construction and simplification of Delaunay meshes Liu, Yong-Jin Xu, Chun-Xu Fan, Dian He, Ying School of Computer Science and Engineering Delaunay Triangulation Delaunay Mesh 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. MOE (Min. of Education, S’pore) Accepted version 2018-06-21T02:54:58Z 2019-12-06T13:59:17Z 2018-06-21T02:54:58Z 2019-12-06T13:59:17Z 2015 Journal Article 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-. 0730-0301 https://hdl.handle.net/10356/80803 http://hdl.handle.net/10220/45017 10.1145/2816795.2818076 en ACM Transactions on Graphics © 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]. 13 p. application/pdf |
| spellingShingle | Delaunay Triangulation Delaunay Mesh Liu, Yong-Jin Xu, Chun-Xu Fan, Dian He, Ying Efficient construction and simplification of Delaunay meshes |
| title | Efficient construction and simplification of Delaunay meshes |
| title_full | Efficient construction and simplification of Delaunay meshes |
| title_fullStr | Efficient construction and simplification of Delaunay meshes |
| title_full_unstemmed | Efficient construction and simplification of Delaunay meshes |
| title_short | Efficient construction and simplification of Delaunay meshes |
| title_sort | efficient construction and simplification of delaunay meshes |
| topic | Delaunay Triangulation Delaunay Mesh |
| url | https://hdl.handle.net/10356/80803 http://hdl.handle.net/10220/45017 |
| work_keys_str_mv | AT liuyongjin efficientconstructionandsimplificationofdelaunaymeshes AT xuchunxu efficientconstructionandsimplificationofdelaunaymeshes AT fandian efficientconstructionandsimplificationofdelaunaymeshes AT heying efficientconstructionandsimplificationofdelaunaymeshes |