“Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem” by Ying, Wang and He
Conference:
Type(s):
Title:
- Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem
Session/Category Title: Geometry Ops
Presenter(s)/Author(s):
Abstract:
This paper presents the Saddle Vertex Graph (SVG), a novel solution to the discrete geodesic problem. The SVG is a sparse undirected graph that encodes complete geodesic distance information: a geodesic path on the mesh is equivalent to a shortest path on the SVG, which can be solved efficiently using the shortest path algorithm (e.g., Dijkstra algorithm). The SVG method solves the discrete geodesic problem from a local perspective. We have observed that the polyhedral surface has some interesting and unique properties, such as the fact that the discrete geodesic exhibits a strong local structure, which is not available on the smooth surfaces. The richer the details and complicated geometry of the mesh, the stronger such local structure will be. Taking advantage of the local nature, the SVG algorithm breaks down the discrete geodesic problem into significantly smaller sub-problems, and elegantly enables information reuse. It does not require any numerical solver, and is numerically stable and insensitive to the mesh resolution and tessellation. Users can intuitively specify a model-independent parameter K, which effectively balances the SVG complexity and the accuracy of the computed geodesic distance. More importantly, the computed distance is guaranteed to be a metric. The experimental results on real-world models demonstrate significant improvement to the existing approximate geodesic methods in terms of both performance and accuracy.
References:
1. Campen, M., and Kobbelt, L. 2011. Walking on broken mesh: Defect-tolerant geodesic distances and parameterizations. Comput. Graph. Forum 30, 2, 623–632.
2. Chen, J., and Han, Y. 1990. Shortest paths on a polyhedron. In Proceedings of the Symposium on Computational Geometry (SCG ’90), 360–369.
3. Crane, K., Weischedel, C., and Wardetzky, M. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transactions on Graphics.
4. Davis, T. A., and Hager, W. W. 2009. Dynamic supernodes in sparse cholesky update/downdate and triangular solves. ACM Trans. Math. Softw. 35, 4, 27:1–27:23.
5. Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 1, 269–271.
6. Goldberg, A. V., and Harrelson, C. 2005. Computing the shortest path: A search meets graph theory. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA ’05), 156–165.
7. Kimmel, R., and Sethian, J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci., 8431–8435.
8. Liu, Y.-J., Zhou, Q.-Y., and Hu, S.-M. 2007. Handling degenerate cases in exact geodesic computation on triangle meshes. The Visual Computer 23, 9–11, 661–668.
9. Liu, Y.-J., Chen, Z., and Tang, K. 2011. Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces. IEEE Trans. Pattern Anal. Mach. Intell. 33, 8, 1502–1517.
10. Mémoli, F., and Sapiro, G. 2001. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. J. Comput. Phys. 173, 2, 730–764.
11. Mémoli, F., and Sapiro, G. 2005. Distance functions and geodesics on submanifolds of Rd and point clouds. SIAM Journal of Applied Mathematics 65, 4, 1227–1260.
12. Mitchell, J. S. B., Mount, D. M., and Papadimitriou, C. H. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4, 647–668.
13. Novotni, M., and Klein, R. 2002. Computing geodesic distances on triangular meshes. In Proc. WSCG ’02.
14. Pohl, I. 1971. Bi-directional search. Machine Intelligence 6, 124–140.
15. Polthier, K., and Schmies, M. 1998. Mathematical Visualization, ch. Straightest Geodesics on Polyhedral Surfaces, 391.
16. Schreiber, Y., and Sharir, M. 2006. An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. In Proceedings of the Symposium on Computational Geometry (SCG ’06), 30–39.
17. Schreiber, Y. 2007. Shortest paths on realistic polyhedra. In Proceedings of the Symposium on Computational Geometry (SCG ’07), 74–83.
18. Sethian, J. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Nat. Acad. Sci 93, 4, 1591–1595.
19. Sharir, M., and Schorr, A. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 1, 193–215.
20. 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, 553–560.
21. Weber, O., Devir, Y. S., Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2008. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Trans. Graph. 27, 4, 104:1–104:16.
22. Xin, S.-Q., and Wang, G.-J. 2009. Improving Chen and Han’s algorithm on the discrete geodesic problem. ACM Trans. Graph. 28, 4, 104:1–104:8.
23. Xin, S.-Q., Quynh, D. T. P., Ying, X., and He, Y. 2012. A global algorithm to compute defect-tolerant geodesic distance. In SIGGRAPH Asia 2012 Technical Briefs, SA ’12, 23:1–23:4.
24. 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 (I3D ’12), 31–38.
25. Ying, X., Xin, S.-Q., and He, Y. 2013. Parallel Chen-Han (PCH) algorithm for discrete geodesics. arXiv:1305.1293.
