AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Computational Visual Media Article
PDF (6.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

An efficient algorithm for approximate Voronoi diagram constructionon triangulated surfaces

School of Computer Science and Technology, Harbin Instituteof Technology, Weihai 264209, China
School of Computer Science and Technology, Shandong University, Qingdao 266237, China
Show Author Information

Graphical Abstract

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 surfacesmesh surfacesapproximate geodesicsApollonius diagrams

Electronic Supplementary Material

Video
41095_0326_ESM.mp4

References

[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[10]
Aurenhammer, F. Voronoi diagrams—A survey of a fundamental geometric data structure. ACM Computing Surveys Vol. 23, No. 3, 345–405, 1991.
Crossref Google Scholar
[11]
Liu, J.; Liu, S. A survey on applications of Voronoi diagrams. Journal of Engineering Graphics Vol. 22, No. 2, 125–132, 2004.
Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[15]
Na, H. S.; Lee, C. N.; Cheong, O. Voronoi diagrams on the sphere. Computational Geometry Vol. 23, No. 2, 183–194, 2002.
Crossref Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[18]
Peyré, G.; Cohen, L. D. Geodesic remeshing using front propagation. International Journal of Computer Vision Vol. 69, No. 1, 145–156, 2006.
Crossref Google Scholar
[19]
Peethambaran, J.; Muthuganapathy, R. Reconstruction of water-tight surfaces through Delaunay sculpting. Computer-Aided Design Vol. 58, 62–72, 2015.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[35]
Crane, K.; Weischedel, C.; Wardetzky, M. Geodesics in heat. ACM Transactions on Graphics Vol. 32, No. 5, Article No. 152, 2013.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[38]
Ying, X.; Wang, X. N.; He, Y. Saddle vertex graph (SVG). ACM Transactions on Graphics Vol. 32, No. 6, Article No. 170, 2013.
Crossref Google Scholar
[39]
Lanthier, M.; Maheshwari, A.; Sack, J.-R. Approxi-mating shortest paths on weighted polyhedral surfaces. Algorithmica Vol. 30, No. 4, 527–562, 2001.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[50]
Boissonnat, J. D.; Dyer, R.; Ghosh, A. Constructing intrinsic Delaunay triangulations of submanifolds. arXiv preprint arXiv:1303.6493, 2013.
Google Scholar
[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.
Crossref Google Scholar
[52]
Senechal, M. Spatial tessellations: Concepts and applications of Voronoi diagrams. Science Vol. 260, No. 5111, 1170–1173, 1993.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[58]
Aurenhammer, F. Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing Vol. 16, No. 1, 78–96, 1987.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Google Scholar
[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.
Crossref Google Scholar
[63]
Fortune, S. A sweepline algorithm for Voronoi diagrams. Algorithmica Vol. 2, Nos. 1–4, 153–174, 1987.
Crossref Google Scholar
[64]
Zhou, Q. N.; Jacobson, A. Thingi10K: A dataset of 10,000 3D-printing models. arXiv preprint arXiv:1605.04797, 2016.
Google Scholar
[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.
Crossref Google Scholar
[66]
Rote, G. Computing the Fréchet distance between piecewise smooth curves. Computational Geometry Vol. 37, No. 3, 162–174, 2007.
Crossref Google Scholar
[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.
Crossref Google Scholar
Computational Visual Media
Volume 9 Issue 3,
September 2023
Pages 443-459
DOI: 10.1007/s41095-022-0326-0
Cite this article:
Meng W, Bo P, Zhang X, et al. An efficient algorithm for approximate Voronoi diagram constructionon triangulated surfaces. Computational Visual Media, 2023, 9(3): 443-459. https://doi.org/10.1007/s41095-022-0326-0

903

Views

44

Downloads

4

Crossref

2

Web of Science

3

Scopus

0

CSCD

Altmetrics
Received: 16 September 2022
Accepted: 21 November 2022
Published: 05 March 2023
© The Author(s) 2023.

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