Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams
Intrinsic Delaunay triangulation (IDT) naturally generalizes Delaunay triangulation from R2 to curved surfaces. Due to many favorable properties, the IDT whose vertex set includes all mesh vertices is of particular interest in polygonal mesh processing. To date, the only way for constructing such ID...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/87052 http://hdl.handle.net/10220/45219 |
| _version_ | 1824454881590640640 |
|---|---|
| author | Liu, Yong-Jin Fan, Dian Xu, Chun-Xu He, Ying |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Liu, Yong-Jin Fan, Dian Xu, Chun-Xu He, Ying |
| author_sort | Liu, Yong-Jin |
| collection | NTU |
| description | Intrinsic Delaunay triangulation (IDT) naturally generalizes Delaunay triangulation from R2 to curved surfaces. Due to many favorable properties, the IDT whose vertex set includes all mesh vertices is of particular interest in polygonal mesh processing. To date, the only way for constructing such IDT is the edge-flipping algorithm, which iteratively flips non-Delaunay edges to become locally Delaunay. Although this algorithm is conceptually simple and guarantees to terminate in finite steps, it has no known time complexity and may also produce triangulations containing faces with only two edges. This article develops a new method to obtain proper IDTs on manifold triangle meshes. We first compute a geodesic Voronoi diagram (GVD) by taking all mesh vertices as generators and then find its dual graph. The sufficient condition for the dual graph to be a proper triangulation is that all Voronoi cells satisfy the so-called closed ball property. To guarantee the closed ball property everywhere, a certain sampling criterion is required. For Voronoi cells that violate the closed ball property, we fix them by computing topologically safe regions, in which auxiliary sites can be added without changing the topology of the Voronoi diagram beyond them. Given a mesh with n vertices, we prove that by adding at most O(n) auxiliary sites, the computed GVD satisfies the closed ball property, and hence its dual graph is a proper IDT. Our method has a theoretical worst-case time complexity O(n2 + tnlog n), where t is the number of obtuse angles in the mesh. Computational results show that it empirically runs in linear time on real-world models. |
| first_indexed | 2025-02-19T03:29:21Z |
| format | Journal Article |
| id | ntu-10356/87052 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:29:21Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/870522020-03-07T11:48:51Z Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams Liu, Yong-Jin Fan, Dian Xu, Chun-Xu He, Ying School of Computer Science and Engineering Intrinsic Delaunay Triangulation Geodesic Voronoi Diagram Intrinsic Delaunay triangulation (IDT) naturally generalizes Delaunay triangulation from R2 to curved surfaces. Due to many favorable properties, the IDT whose vertex set includes all mesh vertices is of particular interest in polygonal mesh processing. To date, the only way for constructing such IDT is the edge-flipping algorithm, which iteratively flips non-Delaunay edges to become locally Delaunay. Although this algorithm is conceptually simple and guarantees to terminate in finite steps, it has no known time complexity and may also produce triangulations containing faces with only two edges. This article develops a new method to obtain proper IDTs on manifold triangle meshes. We first compute a geodesic Voronoi diagram (GVD) by taking all mesh vertices as generators and then find its dual graph. The sufficient condition for the dual graph to be a proper triangulation is that all Voronoi cells satisfy the so-called closed ball property. To guarantee the closed ball property everywhere, a certain sampling criterion is required. For Voronoi cells that violate the closed ball property, we fix them by computing topologically safe regions, in which auxiliary sites can be added without changing the topology of the Voronoi diagram beyond them. Given a mesh with n vertices, we prove that by adding at most O(n) auxiliary sites, the computed GVD satisfies the closed ball property, and hence its dual graph is a proper IDT. Our method has a theoretical worst-case time complexity O(n2 + tnlog n), where t is the number of obtuse angles in the mesh. Computational results show that it empirically runs in linear time on real-world models. Accepted version 2018-07-25T03:04:07Z 2019-12-06T16:34:05Z 2018-07-25T03:04:07Z 2019-12-06T16:34:05Z 2017 Journal Article Liu, Y.-J., Fan, D., Xu, C.-X., & He, Y. (2017). Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams. ACM Transactions on Graphics, 36(2), 15-. 0730-0301 https://hdl.handle.net/10356/87052 http://hdl.handle.net/10220/45219 10.1145/2999532 en ACM Transactions on Graphics © 2017 Association for Computing Machinery. 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/2999532]. 15 p. application/pdf |
| spellingShingle | Intrinsic Delaunay Triangulation Geodesic Voronoi Diagram Liu, Yong-Jin Fan, Dian Xu, Chun-Xu He, Ying Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams |
| title | Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams |
| title_full | Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams |
| title_fullStr | Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams |
| title_full_unstemmed | Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams |
| title_short | Constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams |
| title_sort | constructing intrinsic delaunay triangulations from the dual of geodesic voronoi diagrams |
| topic | Intrinsic Delaunay Triangulation Geodesic Voronoi Diagram |
| url | https://hdl.handle.net/10356/87052 http://hdl.handle.net/10220/45219 |
| work_keys_str_mv | AT liuyongjin constructingintrinsicdelaunaytriangulationsfromthedualofgeodesicvoronoidiagrams AT fandian constructingintrinsicdelaunaytriangulationsfromthedualofgeodesicvoronoidiagrams AT xuchunxu constructingintrinsicdelaunaytriangulationsfromthedualofgeodesicvoronoidiagrams AT heying constructingintrinsicdelaunaytriangulationsfromthedualofgeodesicvoronoidiagrams |