Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một thuật toán hiệu quả để xây dựng sơ đồ Voronoi xấp xỉ trên bề mặt tam giác hóa
Tóm tắt
Sơ đồ Voronoi trên các bề mặt tam giác hóa dựa trên địa chính tĩnh có vai trò quan trọng trong nhiều ứng dụng của đồ họa máy tính. Các phương pháp trước đây để xây dựng sơ đồ Voronoi như vậy thường phụ thuộc vào việc có một khoảng cách địa chính chính xác. Tuy nhiên, việc tính toán địa chính chính xác tốn thời gian và tiêu tốn nhiều bộ nhớ, hạn chế ứng dụng rộng rãi của sơ đồ Voronoi địa chính (GVD). Để khắc phục vấn đề này, thay vì sử dụng các phương pháp chính xác, chúng tôi đã xây dựng lại một phương pháp đồ thị dựa trên việc chèn điểm Steiner, như một cách hiệu quả để thu được khoảng cách địa chính. Hơn nữa, vì phân đoạn chia tách bao gồm cả hyperbolic và các đoạn thẳng, chúng tôi sử dụng sơ đồ Apollonius để mã hóa các cấu trúc phức tạp, cho phép sơ đồ Voronoi mã hóa một bề mặt trục giữa cho một tập hợp các mẫu biên dày đặc. Dựa trên những chiến lược này, chúng tôi trình bày một thuật toán xấp xỉ để xây dựng sơ đồ Voronoi một cách hiệu quả trên các bề mặt tam giác hóa. Chúng tôi cũng đề xuất một tiêu chí để đánh giá sự tương đồng của kết quả của chúng tôi với GVD chính xác. Mặc dù kết quả GVD của chúng tôi được xây dựng bằng cách sử dụng khoảng cách địa chính xấp xỉ, chúng tôi có thể đạt được kết quả GVD tương tự như kết quả chính xác bằng cách chèn các điểm Steiner trên các cạnh tam giác. Kết quả thử nghiệm trên nhiều mô hình 3D chỉ ra tốc độ cải thiện và yêu cầu bộ nhớ so với các phương pháp hàng đầu trước đây.
Từ khóa
#Voronoi diagrams; geodesic metric; computer graphics; Steiner point insertion; triangulated surfacesTài liệu tham khảo
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.
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.
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.
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.
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.
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.
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.
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.
Boissonnat, J. D.; Wormser, C.; Yvinec, M. Curved Voronoi diagrams. In: Effective Computational Geometry for Curves and Surfaces. Berlin Heidelberg: Springer, 67–116, 2006.
Aurenhammer, F. Voronoi diagrams—A survey of a fundamental geometric data structure. ACM Computing Surveys Vol. 23, No. 3, 345–405, 1991.
Liu, J.; Liu, S. A survey on applications of Voronoi diagrams. Journal of Engineering Graphics Vol. 22, No. 2, 125–132, 2004.
Kunze, R.; Wolter, F. E.; Rausch, T. Geodesic Voronoi diagrams on parametric surfaces. Proceedings Computer-Graphics International Vol. 16, No. 3, 230–237, 1997.
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.
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.
Na, H. S.; Lee, C. N.; Cheong, O. Voronoi diagrams on the sphere. Computational Geometry Vol. 23, No. 2, 183–194, 2002.
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.
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.
Peyré, G.; Cohen, L. D. Geodesic remeshing using front propagation. International Journal of Computer Vision Vol. 69, No. 1, 145–156, 2006.
Peethambaran, J.; Muthuganapathy, R. Reconstruction of water-tight surfaces through Delaunay sculpting. Computer-Aided Design Vol. 58, 62–72, 2015.
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.
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.
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.
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.
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.
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.
Crane, K.; Livesu, M.; Puppo, E.; Qin, Y. P. A survey of algorithms for geodesic paths and distances. arXiv preprint arXiv:2007.10430, 2020.
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.
Chen, J. D.; Han, Y. J. Shortest paths on a polyhedron. In: Proceedings of the 6th Annual Symposium on Computational Geometry, 360–369, 1990.
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.
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.
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.
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.
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.
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.
Crane, K.; Weischedel, C.; Wardetzky, M. Geodesics in heat. ACM Transactions on Graphics Vol. 32, No. 5, Article No. 152, 2013.
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.
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.
Ying, X.; Wang, X. N.; He, Y. Saddle vertex graph (SVG). ACM Transactions on Graphics Vol. 32, No. 6, Article No. 170, 2013.
Lanthier, M.; Maheshwari, A.; Sack, J.-R. Approximating shortest paths on weighted polyhedral surfaces. Algorithmica Vol. 30, No. 4, 527–562, 2001.
Lanthier, M.; Maheshwari, A.; Sack, J. R. Approximating weighted shortest paths on polyhedral surfaces. In: Proceedings of the 13th Annual Symposium on Computational Geometry, 274–283, 1997.
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.
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.
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.
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.
Aleksandrov, L.; Maheshwari, A.; Sack, J. R. Approximation algorithms for geometric shortest path problems. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 286–295, 2000.
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.
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.
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.
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.
Boissonnat, J. D.; Dyer, R.; Ghosh, A. Constructing intrinsic Delaunay triangulations of submanifolds. arXiv preprint arXiv:1303.6493, 2013.
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.
Senechal, M. Spatial tessellations: Concepts and applications of Voronoi diagrams. Science Vol. 260, No. 5111, 1170–1173, 1993.
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.
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.
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.
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.
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.
Aurenhammer, F. Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing Vol. 16, No. 1, 78–96, 1987.
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.
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.
Karavelas, M. I.; Emiris, I. Z. Predicates for the planar additively weighted Voronoi diagram. Technical Report ECG-TR-122201-01. INRIA Sophia-Antipolis, 2002.
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.
Fortune, S. A sweepline algorithm for Voronoi diagrams. Algorithmica Vol. 2, Nos. 1–4, 153–174, 1987.
Zhou, Q. N.; Jacobson, A. Thingi10K: A dataset of 10,000 3D-printing models. arXiv preprint arXiv:1605.04797, 2016.
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.
Rote, G. Computing the Fréchet distance between piecewise smooth curves. Computational Geometry Vol. 37, No. 3, 162–174, 2007.
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.
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.