Journal Home > Volume 9 , Issue 3

Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics. Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric. However, exact geodesic computation is time-consuming and has high memory usage, limiting wider application of geodesic Voronoi diagrams (GVDs). In order to overcome this issue, instead of using exact methods, we reformulate a graph method based on Steiner point insertion, as an effective way to obtain geodesic distances. Further, since a bisector comprises hyperbolic and line segments, we utilize Apollonius diagrams to encode complicated structures, enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples. Based on these strategies, we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces. We also suggest a measure for evaluating similarity of our results to the exact GVD. Although our GVD results are constructed using approximate geodesic distances, we can get GVD results similar to exact results by inserting Steiner points on triangle edges. Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods.


menu
Abstract
Full text
Outline
Electronic supplementary material
About this article

An efficient algorithm for approximate Voronoi diagram constructionon triangulated surfaces

Show Author's information Wenlong Meng1Pengbo Bo1Xiaodong Zhang1Jixiang Hong2Shiqing Xin2( )Changhe Tu2( )
School of Computer Science and Technology, Harbin Instituteof Technology, Weihai 264209, China
School of Computer Science and Technology, Shandong University, Qingdao 266237, China

Abstract

Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics. Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric. However, exact geodesic computation is time-consuming and has high memory usage, limiting wider application of geodesic Voronoi diagrams (GVDs). In order to overcome this issue, instead of using exact methods, we reformulate a graph method based on Steiner point insertion, as an effective way to obtain geodesic distances. Further, since a bisector comprises hyperbolic and line segments, we utilize Apollonius diagrams to encode complicated structures, enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples. Based on these strategies, we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces. We also suggest a measure for evaluating similarity of our results to the exact GVD. Although our GVD results are constructed using approximate geodesic distances, we can get GVD results similar to exact results by inserting Steiner points on triangle edges. Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods.

Keywords: geodesic Voronoi diagrams (GVDs), trian-gular surfaces, mesh surfaces, approximate geodesics, Apollonius diagrams

References(68)

[1]
Tsai, J.; Gerstein, M.; Levitt, M. Simulating the minimum core for hydrophobic collapse in globular proteins. Protein Science Vol. 6, No. 12, 2606–2616, 1997.
[2]
Liu, Y. J.; Yu, M. J.; Li, B. J.; He, Y. Intrinsic manifold SLIC: A simple and efficient method for computing content-sensitive superpixels. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 40, No. 3, 653–666, 2018.
[3]
Dong, X.; Chen, Z. G.; Liu, Y. J.; Yao, J. F.; Guo, X. H. GPU-based supervoxel generation with a novel anisotropic metric. IEEE Transactions on Image Processing Vol. 30, 8847–8860, 2021.
[4]
Liu, Y.; Wang, W. P.; Lévy, B.; Sun, F.; Yan, D. M.; Lu, L.; Yang, C. On centroidal Voronoi tessellation—Energy smoothness and fast computation. ACM Transactions on Graphics Vol. 28, No. 4, Article No. 101, 2009.
[5]
Liu, Y. J.; Xu, C. X.; Yi, R.; Fan, D.; He, Y. Manifold differential evolution (MDE). ACM Transactions on Graphics Vol. 35, No. 6, Article No. 243, 2016.
[6]
Wang, X. N.; Ying, X.; Liu, Y. J.; Xin, S. Q.; Wang, W. P.; Gu, X. F.; Mueller-Wittig, W.; He, Y. Intrinsic computation of centroidal voronoi tessellation (CVT) on meshes. Computer-Aided Design Vol. 58, 51–61, 2015.
[7]
Stanković T.; Shea, K. Investigation of a Voronoi diagram representation for the computational design of additively manufactured discrete lattice structures. Journal of Mechanical Design Vol. 142, No. 11, 111704, 2020.
[8]
Dai, G. Y.; Lv, H. X.; Chen, L. Y.; Zhou, B. B.; Xu, P. A novel coverage holes discovery algorithm based on Voronoi diagram in wireless sensor networks. International Journal of Hybrid Information Technology Vol. 9, No. 3, 273–282, 2016.
[9]
Boissonnat, J. D.; Wormser, C.; Yvinec, M. Curved Voronoi diagrams. In: Effective Computational Geome-try for Curves and Surfaces. Berlin Heidelberg: Springer, 67–116, 2006.
DOI
[10]
Aurenhammer, F. Voronoi diagrams—A survey of a fundamental geometric data structure. ACM Computing Surveys Vol. 23, No. 3, 345–405, 1991.
[11]
Liu, J.; Liu, S. A survey on applications of Voronoi diagrams. Journal of Engineering Graphics Vol. 22, No. 2, 125–132, 2004.
[12]
Kunze, R.; Wolter, F. E.; Rausch, T. Geodesic Voronoi diagrams on parametric surfaces. Proceedings Computer Graphics International Vol. 16, No. 3, 230–237, 1997.
[13]
Liu, Y. J.; Chen, Z. Q.; Tang, K. Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 33, No. 8, 1502–1517, 2011.
[14]
Qin, Y. P.; Yu, H. C.; Zhang, J. J. Fast and memory-efficient Voronoi diagram construction on triangle meshes. Computer Graphics Forum Vol. 36, No. 5, 93–104, 2017.
[15]
Na, H. S.; Lee, C. N.; Cheong, O. Voronoi diagrams on the sphere. Computational Geometry Vol. 23, No. 2, 183–194, 2002.
[16]
Onishi, K.; Takayama, N. Construction of Voronoi diagram on the upper half-plane. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences Vol. E79-A, No. 4, 533–539, 1996.
[17]
Medimegh, N.; Belaid, S.; Werghi, N. A survey of the 3D triangular mesh watermarking techniques. International Journal of Multimedia Vol. 1, No. 1, 33–39, 2015.
[18]
Peyré, G.; Cohen, L. D. Geodesic remeshing using front propagation. International Journal of Computer Vision Vol. 69, No. 1, 145–156, 2006.
[19]
Peethambaran, J.; Muthuganapathy, R. Reconstruction of water-tight surfaces through Delaunay sculpting. Computer-Aided Design Vol. 58, 62–72, 2015.
[20]
Kimmel, R.; Kiryati, N.; Bruckstein, A. M. Multivalued distance maps for motion planning on surfaces with moving obstacles. IEEE Transactions on Robotics and Automation Vol. 14, No. 3, 427–436, 1998.
[21]
Lu, L.; Lévy, B.; Wang, W. P. Centroidal Voronoi tessellation of line segments and graphs. Computer Graphics Forum Vol. 31, No. 2pt4, 775–784, 2012.
[22]
Mitchell, J. S. B.; Mount, D. M.; Papadimitriou, C. H. The discrete geodesic problem. SIAM Journal on Computing Vol. 16, No. 4, 647–668, 1987.
[23]
Qin, Y. P.; Han, X. G.; Yu, H. C.; Yu, Y. Z.; Zhang, J. J. Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation. ACM Transactions on Graphics Vol. 35, No. 4, Article No. 125, 2016.
[24]
Xu, C. X.; Liu, Y. J.; Sun, Q.; Li, J. Y.; He, Y. Polyline-sourced geodesic Voronoi diagrams on triangle meshes. Computer Graphics Forum Vol. 33, No. 7, 161–170, 2014.
[25]
Bose, P.; Maheshwari, A.; Shu, C.; Wuhrer, S. A survey of geodesic paths on 3D surfaces. Computational Geometry Vol. 44, No. 9, 486–498, 2011.
[26]
Crane, K.; Livesu, M.; Puppo, E.; Qin, Y. P. A survey of algorithms for geodesic paths and distances. arXiv preprint arXiv:2007.10430, 2020.
[27]
Surazhsky, V.; Surazhsky, T.; Kirsanov, D.; Gortler, S. J.; Hoppe, H. Fast exact and approximate geodesics on meshes. ACM Transactions on Graphics Vol. 24, No. 3, 553–560, 2005.
[28]
Chen, J. D.; Han, Y. J. Shortest paths on a polyhedron. In: Proceedings of the 6th Annual Symposium on Computational Geometry, 360–369, 1990.
DOI
[29]
Xin, S. Q.; Wang, G. J. Improving Chen and Han’s algorithm on the discrete geodesic problem. ACM Transactions on Graphics Vol. 28, No. 4, Article No. 104, 2009.
[30]
Ying, X.; Xin, S. Q.; He, Y. Parallel Chen–Han (PCH) algorithm for discrete geodesics. ACM Transactions on Graphics Vol. 33, No. 1, Article No. 9, 2014.
[31]
Xu, C. X.; Wang, T. Y.; Liu, Y. J.; Liu, L. G.; He, Y. Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes. IEEE Transactions on Visualization and Computer Graphics Vol. 21, No. 7, 822–834, 2015.
[32]
Du, J.; He, Y.; Fang, Z.; Meng, W. L.; Xin, S. Q. On the vertex-oriented triangle propagation (VTP) algorithm: Parallelization and approximation. Computer-Aided Design Vol. 130, 102943, 2021.
[33]
Kimmel, R.; Sethian, J. A. Computing geodesic paths on manifolds. Proceedings of the National Academy of Sciences of the United States of America Vol. 95, No. 15, 8431–8435, 1998.
[34]
Weber, O.; Devir, Y. S.; Bronstein, A. M.; Bronstein, M. M.; Kimmel, R. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Transactions on Graphics Vol. 27, No. 4, Article No. 104, 2008.
[35]
Crane, K.; Weischedel, C.; Wardetzky, M. Geodesics in heat. ACM Transactions on Graphics Vol. 32, No. 5, Article No. 152, 2013.
[36]
Solomon, J.; Rustamov, R.; Guibas, L.; Butscher, A. Earth mover’s distances on discrete surfaces. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 67, 2014.
[37]
Xin, S. Q.; Ying, X.; He, Y. Constant-time all-pairs geodesic distance query on triangle meshes. In: Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 31–38, 2012.
DOI
[38]
Ying, X.; Wang, X. N.; He, Y. Saddle vertex graph (SVG). ACM Transactions on Graphics Vol. 32, No. 6, Article No. 170, 2013.
[39]
Lanthier, M.; Maheshwari, A.; Sack, J.-R. Approxi-mating shortest paths on weighted polyhedral surfaces. Algorithmica Vol. 30, No. 4, 527–562, 2001.
[40]
Lanthier, M.; Maheshwari, A.; Sack, J. R. Approxi-mating weighted shortest paths on polyhedral surfaces. In: Proceedings of the 13th Annual Symposium on Computational Geometry, 274–283, 1997.
DOI
[41]
Aleksandrov, L.; Lanthier, M.; Maheshwari, A.; Sack, J. R. An ε-approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Algorithm Theory — SWAT’98. Lecture Notes in Computer Science, Vol. 1432. Arnborg, S.; Ivansson, L. Eds. Springer Berlin Heidelberg, 11–22, 1998.
DOI
[42]
Aleksandrov, L.; Maheshwari, A.; Sack, J. R. Determining approximate shortest paths on weighted polyhedral surfaces. Journal of the ACM Vol. 52, No. 1, 25–53, 2005.
[43]
Adikusuma, Y. Y.; Du, J.; Fang, Z.; He, Y. An accuracy controllable and memory efficient method for computing high-quality geodesic distances on triangle meshes. Computer-Aided Design Vol. 150, 103333, 2022.
[44]
Adikusuma, Y. Y.; Fang, Z.; He, Y. Fast construction of discrete geodesic graphs. ACM Transactions on Graphics Vol. 39, No. 2, Article No. 14, 2020.
[45]
Aleksandrov, L.; Maheshwari, A.; Sack, J. R. Approximation algorithms for geometric shortestpath problems. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 286–295, 2000.
DOI
[46]
Meng, W. L.; Xin, S. Q.; Tu, C. H.; Chen, S. M.; He, Y.; Wang, W. P. Geodesic tracks: Computing discrete geodesics with track-based Steiner point propagation. IEEE Transactions on Visualization and Computer Graphics Vol. 28, No. 12, 4887–4901, 2022.
[47]
Lee, D. T. Medial axis transformation of a planar shape. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. PAMI-4, No. 4, 363–369, 1982.
[48]
Giblin, P.; Kimia, B. B. A formal classification of 3D medial axis points and their local geometry. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 26, No. 2, 238–251, 2004.
[49]
Leibon, G.; Letscher, D. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In: Proceedings of the 16th Annual Symposium on Computational Geometry, 341–349, 2000.
DOI
[50]
Boissonnat, J. D.; Dyer, R.; Ghosh, A. Constructing intrinsic Delaunay triangulations of submanifolds. arXiv preprint arXiv:1303.6493, 2013.
[51]
Augenbaum, J. M.; Peskin, C. S. On the construction of the Voronoi mesh on a sphere. Journal of Computational Physics Vol. 59, No. 2, 177–192, 1985.
[52]
Senechal, M. Spatial tessellations: Concepts and applications of Voronoi diagrams. Science Vol. 260, No. 5111, 1170–1173, 1993.
[53]
Kimmel, R.; Sethian, J. A. Fast Voronoi diagrams and offsets on triangulated surfaces. Technical Report. Technion-Israel Inst of Tech Haifa Dept of Computer Science, 2000.
[54]
Liu, Y. J.; Tang, K. The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces. Information Processing Letters Vol. 113, No. 4, 132–136, 2013.
[55]
Liu, Y. J.; Fan, D.; Xu, C. X.; He, Y. Constructing intrinsic Delaunay triangulations from the dual of geodesic Voronoi diagrams. ACM Transactions on Graphics Vol. 36, No. 2, Article No. 15, 2017.
[56]
Van Kreveld, M.; Schwarzkopf, O.; de Berg, M.; Overmars, M. Computational geometry algorithms and applications. Computer Graphics Forum Vol. 13, No. 3, 12–16, 2000.
[57]
Rong, G. D.; Liu, Y.; Wang, W. P.; Yin, X. T.; Gu, D.; Guo, X. H. GPU-assisted computation of centroidal Voronoi tessellation. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 3, 345–356, 2011.
[58]
Aurenhammer, F. Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing Vol. 16, No. 1, 78–96, 1987.
[59]
Gavrilova, M.; Rokne, J. An efficient algorithm for construction of the power diagram from the Voronoi diagram in the plane. International Journal of Computer Mathematics Vol. 61, Nos. 1–2, 49–61, 1996.
[60]
Karavelas, M. I.; Yvinec, M. Dynamic additively weighted Voronoi diagrams in 2D. In: Algorithms — ESA 2002. Lecture Notes in Computer Science, Vol. 2461. Möhring, R.; Raman, R. Eds. Springer Berlin Heidelberg, 586–598, 2002.
DOI
[61]
Karavelas, M. I.; Emiris, I. Z. Predicates for the planar additively weighted Voronoi diagram. Technical Report ECG-TR-122201-01. INRIA Sophia-Antipolis, 2002.
[62]
Wang, P. H.; Yuan, N.; Ma, Y. W.; Xin, S. Q.; He, Y.; Chen, S. M.; Xu, J.; Wang, W. Robust computation of 3D Apollonius diagrams. Computer Graphics Forum Vol. 39, No. 7, 43–55, 2020.
[63]
Fortune, S. A sweepline algorithm for Voronoi diagrams. Algorithmica Vol. 2, Nos. 1–4, 153–174, 1987.
[64]
Zhou, Q. N.; Jacobson, A. Thingi10K: A dataset of 10,000 3D-printing models. arXiv preprint arXiv:1605.04797, 2016.
[65]
Alt, H.; Godau, M. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications Vol. 5, Nos. 01n02, 75–91, 1995.
[66]
Rote, G. Computing the Fréchet distance between piecewise smooth curves. Computational Geometry Vol. 37, No. 3, 162–174, 2007.
[67]
Eiter, T.; Mannila, H. Computing discrete Fréchet distance. Technical Report. 1994. Available at http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf.
[68]
Lo, S. H. A new mesh generation scheme for arbitrary planar domains. International Journal for Numerical Methods in Engineering Vol. 21, No. 8, 1403–1426, 1985.
Video
41095_0326_ESM.mp4
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 16 September 2022
Accepted: 21 November 2022
Published: 05 March 2023
Issue date: September 2023

Copyright

© The Author(s) 2023.

Acknowledgements

The authors would like to thank the reviewers for their valuable suggestions. This work was supported in part by the Youth Teacher Development Foundation of Harbin Institute of Technology (IDGA10002143), the National Natural Science Foundation of China (62072139, 62272277, 62072284), the National Key R&D Program of China (2021YFB1715900), and the Joint Funds of the National Natural Science Foundation of China (U22A2033).

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduc-tion in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return