“Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation”

  • ©Yipeng Wang, Xiaoguang Han, Hongchuan Yu, Yizhou Yu, and Jian Jun Zhang

Conference:


Type:


Title:

    Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation

Session/Category Title: MESHES

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Computing discrete geodesic distance over triangle meshes is one of the fundamental problems in computational geometry and computer graphics. In this problem, an effective window pruning strategy can significantly affect the actual running time. Due to its importance, we conduct an in-depth study of window pruning operations in this paper, and produce an exhaustive list of scenarios where one window can make another window partially or completely redundant. To identify a maximal number of redundant windows using such pairwise cross checking, we propose a set of procedures to synchronize local window propagation within the same triangle by simultaneously propagating a collection of windows from one triangle edge to its two opposite edges. On the basis of such synchronized window propagation, we design a new geodesic computation algorithm based on a triangle-oriented region growing scheme. Our geodesic algorithm can remove most of the redundant windows at the earliest possible stage, thus significantly reducing computational cost and memory usage at later stages. In addition, by adopting triangles instead of windows as the primitive in propagation management, our algorithm significantly cuts down the data management overhead. As a result, it runs 4–15 times faster than MMP and ICH algorithms, 2-4 times faster than FWP-MMP and FWP-CH algorithms, and also incurs the least memory usage.

References:


    1. Balasubramanian, M., Polimeni, J., and Schwartz, E. L. 2009. Exact geodesics and shortest paths on polyhedral surfaces. IEEE Trans. Pattern Anal. Mach. Intell. 31, 6, 1006–1016. Google ScholarDigital Library
    2. Bose, P., Maheshwari, A., Shu, C., and Wuhrer, S. 2011. A survey of geodesic paths on 3d surfaces. Comput. Geom. Theory Appl. 44, 9 (Nov.), 486–498. Google ScholarDigital Library
    3. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2006. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proceedings of the National Academy of Sciences 103, 5, 1168–1172.Google ScholarCross Ref
    4. Chen, J., and Han, Y. 1990. Shortest paths on a polyhedron. In Proceedings of the Sixth Annual Symposium on Computational Geometry, ACM, New York, NY, USA, SCG ’90, 360–369. Google ScholarDigital Library
    5. 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 (Oct.), 152:1–152:11. Google ScholarDigital Library
    6. Kimmel, R., and Sethian, J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. USA, 8431–8435.Google Scholar
    7. Liu, Y. J., Chen, Z., and Tang, K. 2011. Construction of iso-contours, bisectors, and voronoi diagrams on triangulated surfaces. Pattern Analysis and Machine Intelligence, IEEE Transactions on 33, 8, 1502–1517. Google ScholarDigital Library
    8. Liu, Y.-J., Xu, C.-X., Fan, D., and He, Y. 2015. Efficient construction and simplification of delaunay meshes. ACM Transactions on Graphics (TOG) 34, 6, 174. Google ScholarDigital Library
    9. Liu, Y.-J. 2013. Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures. Computer-Aided Design 45, 3, 695–704. Google ScholarDigital Library
    10. Mémoli, F., and Sapiro, G. 2001. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. Journal of computational Physics 173, 2, 730–764. Google ScholarDigital Library
    11. Mémoli, F., and Sapiro, G. 2005. Distance functions and geodesics on submanifolds of rd and point clouds. SIAM Journal on Applied Mathematics 65, 4, 1227–1260.Google ScholarCross Ref
    12. Mitchell, J. S. B., Mount, D. M., and Papadimitriou, C. H. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (Aug.), 647–668. Google ScholarDigital Library
    13. Peyré, G., and Cohen, L. D. 2006. Geodesic remeshing using front propagation. International Journal of Computer Vision 69, 1, 145–156. Google ScholarDigital Library
    14. Schreiber, Y., and Sharir, M. 2009. An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. In Twentieth Anniversary Volume:. Springer, 1–80.Google Scholar
    15. Sethian, J. A. 1996. A fast marching level set method for monotonically advancing fronts. Proceedings of the National Academy of Sciences 93, 4, 1591–1595.Google ScholarCross Ref
    16. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3 (July), 553–560. Google ScholarDigital Library
    17. Xin, S.-Q., and Wang, G.-J. 2009. Improving chen and han’s algorithm on the discrete geodesic problem. ACM Trans. Graph. 28, 4 (Sept.), 104:1–104:8. Google ScholarDigital Library
    18. Xin, S.-Q., Ying, X., and He, Y. 2012. Constant-time all-pairs geodesic distance query on triangle meshes. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM, New York, NY, USA, I3D ’12, 31–38. Google ScholarDigital Library
    19. Xu, C., Wang, T. Y., Liu, Y., Liu, L., and He, Y. 2015. Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes. IEEE Trans. Vis. Comput. Graph. 21, 7, 822–834.Google ScholarDigital Library
    20. Yatziv, L., Bartesaghi, A., and Sapiro, G. 2005. O(n) implementation of the fast marching algorithm. Journal of Computational Physics 212, 393–399. Google ScholarDigital Library
    21. Ye, J., and Yu, Y. 2016. A fast modal space transform for robust nonrigid shape retrieval. The Visual Computer 32, 5 (May), 553–568. Google ScholarDigital Library
    22. Ye, J., Yan, Z., and Yu, Y. 2013. Fast nonrigid 3d retrieval using modal space transform. In 3rd ACM International Conference on Multimedia Retrieval (ICMR), 121–126. Google ScholarDigital Library
    23. Ying, X., Wang, X., and He, Y. 2013. Saddle vertex graph (svg): A novel solution to the discrete geodesic problem. ACM Trans. Graph. 32, 6 (Nov.), 170:1–170:12. Google ScholarDigital Library
    24. Ying, X., Xin, S.-Q., and He, Y. 2014. Parallel chen-han (pch) algorithm for discrete geodesics. ACM Trans. Graph. 33, 1 (Feb.), 9:1–9:11. Google ScholarDigital Library
    25. Zhong, Z., Guo, X., Wang, W., Lvy, B., Sun, F., Liu, Y., and Mao, W. 2013. Particle-based anisotropic surface meshing. ACM Transactions on Graphics (SIGGRAPH conference proceedings). Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page: