“Efficient construction and simplification of Delaunay meshes” by Liu, Xu, Fan and He
Conference:
Type(s):
Title:
- Efficient construction and simplification of Delaunay meshes
Session/Category Title: Geometry Processing
Presenter(s)/Author(s):
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.
References:
1. Amenta, N., and Bern, M. 1999. Surface reconstruction by Voronoi filtering. Discrete & Computational Geometry 22, 4, 481–504.
2. Bobenko, A. I., and Springborn, B. A. 2007. A discrete laplace-beltrami operator for simplicial surfaces. Discrete & Computational Geometry 38, 4, 740–756.
3. Burago, Y. D., and Zallgaller, V. A. 1960. Polyhedral embedding of a net. Vestnik Leningrad. Univ. 15, 66–80.
4. Cheng, S.-W., Dey, T. K., and Shewchuk, J. R. 2012. Delaunay Mesh Generation. CRC Press.
5. Chew, L. P. 1987. Constrained Delaunay triangulations. In Proceedings of ACM SoCG ’87, 215–222.
6. Chew, L. P. 1993. Guaranteed-quality mesh generation for curved surfaces. In Proceedings of ACM SoCG ’93, 274–280.
7. Cignoni, P., Rocchini, C., and Scopigno, R. 1998. Metro: measuring error on simplified surfaces. Computer Graphics Forum 17, 2, 167–174.
8. 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.
9. 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.
10. 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.
11. 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.
12. 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.
13. Du, Q., and Wang, D. 2005. Anisotropic centroidal Voronoi tessellations and their applications. SIAM J. Scientific Computing 26, 3, 737–761.
14. Dyer, R., Zhang, H., and Möller, T. 2007. Delaunay mesh construction. In Proceedings of SGP ’07, 273–282.
15. Dyer, R., Zhang, H., and Möller, T. 2008. Surface sampling and the intrinsic Voronoi diagram. In Proceedings of SGP’08, 1393–1402.
16. Edelsbrunner, H., and Shah, N. R. 1997. Triangulating topological spaces. International Journal of Computational Geometry and Applications 7, 4, 365–378.
17. 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.
18. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In ACM SIGGRAPH ’97, 209–216.
19. Glickenstein, D. 2005. Geometric triangulations and discrete Laplacians on manifolds. arXiv:math/0508188.
20. Guibas, L. J., Knuth, D. E., and Sharir, M. 1992. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7, 1–6, 381–413.
21. 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.
22. Lévy, B., and Liu, Y. 2010. Lp centroidal Voronoi tessellation and its applications. ACM Trans. Graph. 29, 4, 119:1–119:11.
23. 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.
24. 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.
25. 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.
26. Lloyd, S. 1982. Least squares quantization in PCM. IEEE Trans. Inform. Theory. 28, 2, 129–137.
27. 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.
28. Maehara, H. 2011. On a proper acute triangulation of a polyhedral surface. Discrete Mathematics 311, 17, 1903–1909.
29. Mullen, P., Memari, P., de Goes, F., and Desbrun, M. 2011. HOT: Hodge-optimized triangulations. ACM Trans. Graph. 30, 4, 103:1–103:12.
30. Okabe, A., Boots, B., Sugihara, K., and Chiu, S.-N. 2000. Spatial Tessellations: Concept and Applications of Voronoi Diagrams. Wiley.
31. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experiment. Math. 2, 1, 15–36.
32. Rippa, S. 1990. Minimal roughness property of the Delaunay triangulation. Computer Aided Geometric Design 7, 6, 489–497.
33. Rivin, I. 1994. Euclidean structures on simplicial surfaces and hyperbolic volume. Annals of Mathematics 139, 3, 553–580.
34. Saraf, S. 2009. Acute and nonobtuse triangulations of polyhedral surfaces. European Journal of Combinatorics 30, 4, 833–840.
35. 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.
36. Wardetzky, M., Mathur, S., Kälberer, F., and Grinspun, E. 2007. Discrete laplace operators: No free lunch. In Proceedings of SGP ’07, 33–37.
37. 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.
38. Zamfirescu, T. 2002. Acute triangulations: a short survey. In Proceedings of the Sixth Annual Conference of the Romanian Society of Mathematical Sciences, 9–17.
