A minimalistic approach for fast computation of geodesic distances on triangular meshes
Resumo
The computation of geodesic distances is an important research topic in Geometry Processing and 3D Shape Analysis as it is a basic component of many methods used in these areas. In this work, we present a minimalistic parallel algorithm based on front propagation to compute approximate geodesic distances on meshes. Our method is practical and simple to implement, and does not require any heavy pre-processing. The convergence of our algorithm depends on the number of discrete level sets around the source points from which distance information propagates. To appropriately implement our method on GPUs taking into account memory coalescence problems, we take advantage of a graph representation based on a breadth-first search traversal that works harmoniously with our parallel front propagation approach. We report experiments that show how our method scales with the size of the problem. We compare the mean error and processing time obtained by our method with such measures computed using other methods. Our method produces results in competitive times with almost the same accuracy, especially for large meshes. We also demonstrate its use for solving two classical geometry processing problems: the regular sampling problem and the Voronoi tessellation on meshes.
Palavras-chave:
Geodesic distance, Fast marching, Triangular meshes, Parallel programming, Breadth-first search
Referências
S. Kurtek, E. Klassen, Z. Ding, M.J. Avison, A. Srivastava. Parameterization-invariant shape statistics and probabilistic classification of anatomical surfaces. Springer Berlin Heidelberg, Berlin, Heidelberg (2011), pp. 147-158
J. Rabin, G. Peyré, L.D. Cohen. Geodesic shape retrieval via optimal mass transport. Springer Berlin Heidelberg, Berlin, Heidelberg (2010), pp. 771-784
A.M. Bronstein, M.M. Bronstein, R. Kimmel. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proc Natl Acad Sci (PNAS), 103 (5) (2006), pp. 1168-1172
J. Bennour, J. l. Dugelay. Protection of 3D object visual representations. Proceedings of the IEEE international conference on multimedia and expo (2006), pp. 1113-1116
A.B. Hamza, H. Krim. Geodesic Object representation and recognition. Springer Berlin Heidelberg, Berlin, Heidelberg (2003), pp. 378-387
G.N. Oliveira, R.P. Torchelsen, J.L.D. Comba, M. Walter, R. Bastos. Geodesic-driven visual effects over complex surfaces. Vis Comput, 27 (10) (2011), pp. 917-928
P.-P.J. Sloan, C.F. Rose III, M.F. Cohen. Shape by example. Proceedings of the symposium on interactive 3D graphics, ACM, New York, NY, USA (2001), pp. 135-143
J.S.B. Mitchell, D.M. Mount, C.H. Papadimitriou. The discrete geodesic problem. SIAM J Comput, 16 (4) (1987), pp. 647-668
V. Surazhsky, T. Surazhsky, D. Kirsanov, S.J. Gortler, H. Hoppe. Fast exact and approximate geodesics on meshes
Proceedings of the ACM SIGGRAPH Papers, ACM, New York, NY, USA (2005), pp. 553-560
J.A. Sethian. Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science. Cambridge University Press, Cambridge, GB (1999)
Premiére édition parue sous le titre: Level set methods, 1996.
R. Kimmel, J.A. Sethian. Computing geodesic paths on manifolds. Proceedings of the National Academy Science USA (1998), pp. 8431-8435
K. Crane, C. Weischedel, M. Wardetzky. Geodesics in heat: a new approach to computing distance based on heat flow. ACM Trans Graph, 32 (5) (2013), pp. 1-11
H. Zhu, L. He, S. Fu, R. Li, X. Han, Z. Fu, et al. Wolfpath: accelerating iterative traversing-based graph processing algorithms on GPU. Int J Parallel Program (2017)
Y. Eldar, M. Lindenbaum, M. Porat, Y.Y. Zeevi. The farthest point strategy for progressive image sampling
Proceedings of the 12th IAPR International Conference on Pattern Recognition Vol. 3 - Conference C: Signal Processing (1994), pp. 93-97 vol.3
J. Qian, Y. Zhang, H. Zhao. Fast sweeping methods for eikonal equations on triangular meshes. SIAM J Numer Anal, 45 (1) (2007), pp. 83-107
K. Polthier, M. Schmies. Straightest geodesics on polyhedral surfaces. Springer Berlin Heidelberg, Berlin, Heidelberg (1998), pp. 135-150
D. Martínez, L. Velho, P.C. Carvalho. Computing geodesics on triangular meshes. Comput Graph, 29 (5) (2005), pp. 667-675
O. Weber, Y.S. Devir, A.M. Bronstein, M.M. Bronstein, R. Kimmel. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Trans Graph, 27 (4) (2008), pp. 104:1-104:16
P.-E. Danielsson. Euclidean distance mapping. Comput Graph Image Process, 14 (3) (1980), pp. 227-248
Z. Fu, W.-K. Jeong, Y. Pan, R.M. Kirby, R.T. Whitaker. A fast iterative method for solving the Eikonal equation on triangulated surfaces. SIAM J Sci Comput, 33 (5) (2011), pp. 2468-2488
X. Ying, X. Wang, Y. He. Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem. ACM Trans Graph, 32 (6) (2013), pp. 170:1-170:12
X. Wang, Z. Fang, J. Wu, S.-Q. Xin, Y. He. Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces. Comput Aided Geom Des, 52–53 (2017), pp. 262-284
Geometric Modeling and Processing 2017.
K. Crane, C. Weischedel, M. Wardetzky. The heat method for distance computation. Commun ACM, 60 (11) (2017), pp. 90-99
J. Tao, J. Zhang, B. Deng, Z. Fang, Y. Peng, Y. He. Parallel and scalable heat methods for geodesic distance computation. IEEE Trans Pattern Anal Mach Intell, 8 (2019), p. 1-1, 10.1109/TPAMI.2019.2933209
Litman R., Bronstein A.M. Spectrometer: amortized sublinear spectral approximation of distance on graphs. CoRR 2016; arXiv: 1609.05715
A. Bronstein, M. Bronstein, R. Kimmel. Numerical geometry of non-rigid shapes (1 ed.), Springer Publishing Company, Incorporated (2008)
M. Lage, T. Lewiner, L. Velho. CHE: a scalable topological data structure for triangular meshes. Technical Report (2005) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.523.7580.
Peyré G. Fm toolbox matlab (fibonacci heap). 2014. https://github.com/gpeyre/numerical-tours.
Sun J. Meshlp package. 2008a. https://github.com/areslp/matlab/tree/master/MeshLP/MeshLP.
Sun J. Multiple source/target exact geodesic (shortest path) algorithm for triangular mesh (triangulated 2d surface in 3d). 2008b. http://code.google.com/p/geodesic/.
Crane K. Heat method: CHOLMOD implementation. 2013. https://github.com/dgpdec/course.
S.C. Rennich, D. Stosic, T.A. Davis. Accelerating sparse Cholesky factorization on GPUs. Proceedings of the 4th workshop on irregular applications: architectures and algorithms, IA3, IEEE Press, Piscataway, NJ, USA (2014), pp. 9-16
J. Rabin, G. Peyré, L.D. Cohen. Geodesic shape retrieval via optimal mass transport. Springer Berlin Heidelberg, Berlin, Heidelberg (2010), pp. 771-784
A.M. Bronstein, M.M. Bronstein, R. Kimmel. Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching. Proc Natl Acad Sci (PNAS), 103 (5) (2006), pp. 1168-1172
J. Bennour, J. l. Dugelay. Protection of 3D object visual representations. Proceedings of the IEEE international conference on multimedia and expo (2006), pp. 1113-1116
A.B. Hamza, H. Krim. Geodesic Object representation and recognition. Springer Berlin Heidelberg, Berlin, Heidelberg (2003), pp. 378-387
G.N. Oliveira, R.P. Torchelsen, J.L.D. Comba, M. Walter, R. Bastos. Geodesic-driven visual effects over complex surfaces. Vis Comput, 27 (10) (2011), pp. 917-928
P.-P.J. Sloan, C.F. Rose III, M.F. Cohen. Shape by example. Proceedings of the symposium on interactive 3D graphics, ACM, New York, NY, USA (2001), pp. 135-143
J.S.B. Mitchell, D.M. Mount, C.H. Papadimitriou. The discrete geodesic problem. SIAM J Comput, 16 (4) (1987), pp. 647-668
V. Surazhsky, T. Surazhsky, D. Kirsanov, S.J. Gortler, H. Hoppe. Fast exact and approximate geodesics on meshes
Proceedings of the ACM SIGGRAPH Papers, ACM, New York, NY, USA (2005), pp. 553-560
J.A. Sethian. Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science. Cambridge University Press, Cambridge, GB (1999)
Premiére édition parue sous le titre: Level set methods, 1996.
R. Kimmel, J.A. Sethian. Computing geodesic paths on manifolds. Proceedings of the National Academy Science USA (1998), pp. 8431-8435
K. Crane, C. Weischedel, M. Wardetzky. Geodesics in heat: a new approach to computing distance based on heat flow. ACM Trans Graph, 32 (5) (2013), pp. 1-11
H. Zhu, L. He, S. Fu, R. Li, X. Han, Z. Fu, et al. Wolfpath: accelerating iterative traversing-based graph processing algorithms on GPU. Int J Parallel Program (2017)
Y. Eldar, M. Lindenbaum, M. Porat, Y.Y. Zeevi. The farthest point strategy for progressive image sampling
Proceedings of the 12th IAPR International Conference on Pattern Recognition Vol. 3 - Conference C: Signal Processing (1994), pp. 93-97 vol.3
J. Qian, Y. Zhang, H. Zhao. Fast sweeping methods for eikonal equations on triangular meshes. SIAM J Numer Anal, 45 (1) (2007), pp. 83-107
K. Polthier, M. Schmies. Straightest geodesics on polyhedral surfaces. Springer Berlin Heidelberg, Berlin, Heidelberg (1998), pp. 135-150
D. Martínez, L. Velho, P.C. Carvalho. Computing geodesics on triangular meshes. Comput Graph, 29 (5) (2005), pp. 667-675
O. Weber, Y.S. Devir, A.M. Bronstein, M.M. Bronstein, R. Kimmel. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Trans Graph, 27 (4) (2008), pp. 104:1-104:16
P.-E. Danielsson. Euclidean distance mapping. Comput Graph Image Process, 14 (3) (1980), pp. 227-248
Z. Fu, W.-K. Jeong, Y. Pan, R.M. Kirby, R.T. Whitaker. A fast iterative method for solving the Eikonal equation on triangulated surfaces. SIAM J Sci Comput, 33 (5) (2011), pp. 2468-2488
X. Ying, X. Wang, Y. He. Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem. ACM Trans Graph, 32 (6) (2013), pp. 170:1-170:12
X. Wang, Z. Fang, J. Wu, S.-Q. Xin, Y. He. Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces. Comput Aided Geom Des, 52–53 (2017), pp. 262-284
Geometric Modeling and Processing 2017.
K. Crane, C. Weischedel, M. Wardetzky. The heat method for distance computation. Commun ACM, 60 (11) (2017), pp. 90-99
J. Tao, J. Zhang, B. Deng, Z. Fang, Y. Peng, Y. He. Parallel and scalable heat methods for geodesic distance computation. IEEE Trans Pattern Anal Mach Intell, 8 (2019), p. 1-1, 10.1109/TPAMI.2019.2933209
Litman R., Bronstein A.M. Spectrometer: amortized sublinear spectral approximation of distance on graphs. CoRR 2016; arXiv: 1609.05715
A. Bronstein, M. Bronstein, R. Kimmel. Numerical geometry of non-rigid shapes (1 ed.), Springer Publishing Company, Incorporated (2008)
M. Lage, T. Lewiner, L. Velho. CHE: a scalable topological data structure for triangular meshes. Technical Report (2005) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.523.7580.
Peyré G. Fm toolbox matlab (fibonacci heap). 2014. https://github.com/gpeyre/numerical-tours.
Sun J. Meshlp package. 2008a. https://github.com/areslp/matlab/tree/master/MeshLP/MeshLP.
Sun J. Multiple source/target exact geodesic (shortest path) algorithm for triangular mesh (triangulated 2d surface in 3d). 2008b. http://code.google.com/p/geodesic/.
Crane K. Heat method: CHOLMOD implementation. 2013. https://github.com/dgpdec/course.
S.C. Rennich, D. Stosic, T.A. Davis. Accelerating sparse Cholesky factorization on GPUs. Proceedings of the 4th workshop on irregular applications: architectures and algorithms, IA3, IEEE Press, Piscataway, NJ, USA (2014), pp. 9-16
Publicado
28/10/2019
Como Citar
CALLA, Luciano Arnaldo Romero; PEREZ, Lizeth J. Fuentes ; MONTENEGRO, Anselmo A. .
A minimalistic approach for fast computation of geodesic distances on triangular meshes. In: CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 32. , 2019, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
DOI: https://doi.org/10.5753/sibgrapi.2019.9816.
