Parallel window propagation on mesh surfaces

https://doi.org/10.31130/ud-jst.2023.208ICT

##plugins.themes.academic_pro.article.main##

Author

  • Le Tien Hung
    Military Technical Academy, Hanoi, Vietnam
    Do Quoc Trinh
    Military Technical Academy, Hanoi, Vietnam
    Nguyen Huu Tho
    Military Technical Academy, Hanoi, Vietnam

Từ khóa:

Geodesics;
MMP algorithm
windows propogation
parallel computing

Tóm tắt

The task of calculating the shortest distance with minimal curvature between two points on a mesh surface is a well-known problem in computational geometry. This paper aims to develop a effective algorithm for computing geodesics on large, complex models with fast processing times to facilitate interactive applications. Our contribution is developing of the parallel window propagation (PWP) algorithm, which divides the sequential MMP algorithm into four phases: front node selection, window list propagation, window list merging, and vertex update. We use two separate buffers for incoming windows on each edge to avoid data dependency and conflicts in each phase, allowing for parallel processing on a CPU. As a result, our PWP algorithm can propagate a large number of windows simultaneously and independently, leading to significant improvements in performance for real-world models.

Tài liệu tham khảo

    [1] Martınez, L. Velho, and P. C. Carvalho, “Computing geodesics on triangular meshes”, Computers & Graphics, vol. 29, no. 5, pp. 667–675, 2005. https://doi.org/10.1016/j.cag.2005.08.003
    [2] Polthier and M. Schmies, “Straightest geodesics on polyhedral surfaces”, in Proc. ACM SIGGRAPH 2006 Courses (SIGGRAPH '06), pp. 30-38, 2006. DOI:10.1145/1185657.1185664
    [3] -Q. Xin and G.-J. Wang, “Efficiently determining a locally exact shortest path on polyhedral surfaces”, Computer-Aided Design, vol. 39, no. 12, pp. 1081–1090, 2007. DOI: 10.1016/j.cad.2007.08.001
    [4] S. Mitchell, D. M. Mount, and C. H. Papadimitriou, “The discrete geodesic problem”, SIAM Journal on Computing, vol. 16, no. 4, pp. 647–668, 1987.
    [5] Chen and Y. Han, “Shortest paths on a polyhedron”, in Proceedings of the 6th Annual symposium on Computational geometry, 1990, pp. 360–369. https://doi.org/10.1145/98524.98601
    [6] Novotni and R. Klein, “Computing geodesic distances on triangular meshes”, in Proceedings of WSCG'2002, vol. 11, 2002, pp. 341-347.
    [7] Surazhsky, T. Surazhsky, D. Kirsanov, S. J. Gortler, and H. Hoppe, “Fast exact and approximate geodesics on meshes”, ACM Transactions on Graphics (TOG), vol. 24, no. 3, pp. 553–560, 2005. DOI: 10.1145/1073204.1073228
    [8] R. Varadarajan and P. K. Agarwal, “Approximating shortest paths on a nonconvex polyhedron”, SIAM Journal on Computing, vol. 30, no. 4, pp. 1321–1340, 2000.
    [9] Har-Peled, “Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions”, Discrete & Computational Geometry, vol. 21, no. 2, pp. 217–231, 1999.
    [10] Har-Peled, “Constructing approximate shortest path maps in three dimensions”, in Proceedings of the 44th Annual symposium on Computational geometry, 1998, pp. 383–391. Doi: 10.1145/276884.276927
    [11] Aleksandrov, A. Maheshwari, and J.-R. Sack, “An improved approximation algorithm for computing geometric shortest paths”, Fundamentals of Computation Theory, Springer, Vol. 2751, pp. 246–257, 2003. DOI:10.1007/978-3-540-45077-1_23
    [12] -Q. Xin and G.-J. Wang, “Improving Chen and Han’s algorithm on the discrete geodesic problem”, ACM Transactions on Graphics (TOG), vol. 28, no. 4, pp. 1-8, 2009. DOI: 10.1145/1559755.1559761.
    [13] Ying, S. Xin, and Y. He, “Parallel Chen-Han (PCH) algorithm for discrete geodesics”, ACM Transactions on Graphics (TOG), vol. 33, no. 1, pp. 1-11, 2014. DOI: 10.1145/1559755.1559761.
    [14] A. Sethian, “Fast marching methods”, SIAM Review, vol. 41, no. 2, pp. 199–235, 1999. DOI: 10.1137/S0036144598347059
    [15] Crane, C. Weischedel and M. Wardetzky, “Geodesics in heat: a new approach to computing distance based on heat flow”, ACM Transactions on Graphics (TOG), vol. 32, no. 5, pp. 1-11, 2013. DOI: 10.1145/2516971.2516977.
    [16] Ying, X. Wang, and Y. He, “Saddle vertex graph (SVG): A novel solution to the discrete geodesic problem”, ACM Transactions on Graphics (TOG), vol. 32, no. 6, pp. 1-12, 2013. DOI: 10.1145/2508363.2508379.
    [17] Qin, X. Han, H. Yu, Y. Yu, and J. Zhang, “Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation”, ACM Transactions on Graphics (Proc. SIGGRAPH), vol. 35, no. 4, pp. 1-13, 2016. DOI: 10.1145/2897824.2925930.
Xem thêm

##plugins.themes.academic_pro.article.sidebar##

Đã Xuất bản

Dec 31, 2023
Download
PDF (English)
Cách trích dẫn
Hung, L. T., D. Q. Trinh, và N. H. Tho. “Parallel Window Propagation on Mesh Surfaces”. Tạp Chí Khoa học Và Công nghệ - Đại học Đà Nẵng, vol 21, số p.h 12.1, Tháng Chạp 2023, tr 101-6, doi:10.31130/ud-jst.2023.208ICT.

##plugins.themes.academic_pro.article.details##