Yong-Jin Liu
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.
Supplemental Material
Available for Download
Supplemental files.
- Amenta, N., and Bern, M. 1999. Surface reconstruction by Voronoi filtering. Discrete & Computational Geometry 22, 4, 481--504.Google Scholar
Cross Ref
- Bobenko, A. I., and Springborn, B. A. 2007. A discrete laplace-beltrami operator for simplicial surfaces. Discrete & Computational Geometry 38, 4, 740--756. Google ScholarDigital Library
- Burago, Y. D., and Zallgaller, V. A. 1960. Polyhedral embedding of a net. Vestnik Leningrad. Univ. 15, 66--80.Google Scholar
- Cheng, S.-W., Dey, T. K., and Shewchuk, J. R. 2012. Delaunay Mesh Generation. CRC Press. Google ScholarDigital Library
- Chew, L. P. 1987. Constrained Delaunay triangulations. In Proceedings of ACM SoCG '87, 215--222. Google ScholarDigital Library
- Chew, L. P. 1993. Guaranteed-quality mesh generation for curved surfaces. In Proceedings of ACM SoCG '93, 274--280. Google ScholarDigital Library
- Cignoni, P., Rocchini, C., and Scopigno, R. 1998. Metro: measuring error on simplified surfaces. Computer Graphics Forum 17, 2, 167--174.Google ScholarCross Ref
- Crane, K., Weischedel, C., and Wardetzky, M. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Trans. Graph. 32, 5, 152. Google ScholarDigital Library
- de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6, 171:1--171:11. Google ScholarDigital Library
- de Goes, F., Alliez, P., Owhadi, H., and Desbrun, M. 2013. On the equilibrium of simplicial masonry structures. ACM Trans. Graph. 32, 4, 93:1--93:10. Google ScholarDigital Library
- de Goes, F., Memari, P., Mullen, P., and Desbrun, M. 2014. Weighted triangulations for geometry processing. ACM Trans. Graph. 33, 3, 28:1--28:13. Google ScholarDigital Library
- Dey, T. K., Edelsbrunner, H., Guha, S., and Nekhayev, D. V. 1999. Topology preserving edge contraction. Publ. Inst. Math.(Beograd) (N.S) 66, 80, 23--45.Google Scholar
- Du, Q., and Wang, D. 2005. Anisotropic centroidal Voronoi tessellations and their applications. SIAM J. Scientific Computing 26, 3, 737--761. Google ScholarDigital Library
- Dyer, R., Zhang, H., and Möller, T. 2007. Delaunay mesh construction. In Proceedings of SGP '07, 273--282. Google ScholarDigital Library
- Dyer, R., Zhang, H., and Möller, T. 2008. Surface sampling and the intrinsic Voronoi diagram. In Proceedings of SGP'08, 1393--1402. Google ScholarDigital Library
- Edelsbrunner, H., and Shah, N. R. 1997. Triangulating topological spaces. International Journal of Computational Geometry and Applications 7, 4, 365--378.Google ScholarCross Ref
- Fisher, M., Springborn, B., Bobenko, A. I., and Schröder, P. 2007. An algorithm for the construction of intrinsic Delaunay triangulations with applications to digital geometry processing. Computing 82, 2-3, 199--213. Google ScholarDigital Library
- Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In ACM SIGGRAPH '97, 209--216. Google ScholarDigital Library
- Glickenstein, D. 2005. Geometric triangulations and discrete Laplacians on manifolds. arXiv:math/0508188.Google Scholar
- Guibas, L. J., Knuth, D. E., and Sharir, M. 1992. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7, 1--6, 381--413.Google ScholarCross Ref
- Indermitte, C., Liebling, T., Troyanov, M., and Clémençon, H. 2001. Voronoi diagrams on piecewise flat surfaces and an application to biological growth. Theoretical Computer Science 263, 1--2. Google ScholarDigital Library
- Lévy, B., and Liu, Y. 2010. Lp centroidal Voronoi tessellation and its applications. ACM Trans. Graph. 29, 4, 119:1--119:11. Google ScholarDigital Library
- Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D.-M., Lu, L., and Yang, C. 2009. On centroidal Voronoi tessellation - energy smoothness and fast computation. ACM Trans. Graph. 28, 4, 101:1--101:17. Google ScholarDigital Library
- Liu, Y.-J., Chen, Z., and Tang, K. 2011. Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 8, 1502--1517. Google ScholarDigital Library
- Liu, Y., Pan, H., Snyder, J., Wang, W., and Guo, B. 2013. Computing self-supporting surfaces by regular triangulation. ACM Trans. Graph. 32, 4, 92:1--92:10. Google ScholarDigital Library
- Lloyd, S. 1982. Least squares quantization in PCM. IEEE Trans. Inform. Theory. 28, 2, 129--137. Google ScholarDigital Library
- Lu, L., Sun, F., Pan, H., and Wang, W. 2012. Global optimization of centroidal Voronoi tessellation with Monte Carlo approach. IEEE Transactions on Visualization and Computer Graphics 18, 11, 1880--1890. Google ScholarDigital Library
- Maehara, H. 2011. On a proper acute triangulation of a polyhedral surface. Discrete Mathematics 311, 17, 1903--1909. Google ScholarDigital Library
- Mullen, P., Memari, P., de Goes, F., and Desbrun, M. 2011. HOT: Hodge-optimized triangulations. ACM Trans. Graph. 30, 4, 103:1--103:12. Google ScholarDigital Library
- Okabe, A., Boots, B., Sugihara, K., and Chiu, S.-N. 2000. Spatial Tessellations: Concept and Applications of Voronoi Diagrams. Wiley. Google ScholarDigital Library
- Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experiment. Math. 2, 1, 15--36.Google ScholarCross Ref
- Rippa, S. 1990. Minimal roughness property of the Delaunay triangulation. Computer Aided Geometric Design 7, 6, 489--497. Google ScholarDigital Library
- Rivin, I. 1994. Euclidean structures on simplicial surfaces and hyperbolic volume. Annals of Mathematics 139, 3, 553--580.Google ScholarCross Ref
- Saraf, S. 2009. Acute and nonobtuse triangulations of polyhedral surfaces. European Journal of Combinatorics 30, 4, 833--840. Google ScholarDigital Library
- VanderZee, E., Hirani, A. N., Guoy, D., and Ramos, E. 2007. Well-centered planar triangulation-an iterative approach. In Proceedings of IMR '07, 121--138.Google Scholar
- Wardetzky, M., Mathur, S., Kälberer, F., and Grinspun, E. 2007. Discrete laplace operators: No free lunch. In Proceedings of SGP '07, 33--37. Google ScholarDigital Library
- Yan, D.-M., Lévy, B., Liu, Y., Sun, F., and Wang, W. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. In Proceedings of SGP '09, 1445--1454. Google ScholarDigital Library
- Zamfirescu, T. 2002. Acute triangulations: a short survey. In Proceedings of the Sixth Annual Conference of the Romanian Society of Mathematical Sciences, 9--17.Google Scholar
Index Terms
- Efficient construction and simplification of Delaunay meshes
Recommendations
Delaunay mesh simplification with differential evolution
Delaunay meshes (DM) are a special type of manifold triangle meshes --- where the local Delaunay condition holds everywhere --- and find important applications in digital geometry processing. This paper addresses the general DM simplification problem: ...
Voronoi-Delaunay duality and Delaunay meshes
SPM '07: Proceedings of the 2007 ACM symposium on Solid and physical modelingWe define a Delaunay mesh to be a manifold triangle mesh whose edges form an intrinsic Delaunay triangulation or iDT of its vertices, where the triangulated domain is the piecewise flat mesh surface. We show that meshes constructed from a smooth surface ...
Gabriel meshes and Delaunay edge flips
SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical ModelingWe undertake a study of the local properties of 2-Gabriel meshes: manifold triangle meshes each of whose faces has an open Euclidean diametric ball that contains no mesh vertices. We show that, under mild constraints on the dihedral angles, such meshes ...
Comments