2015
Conference article
Open Access
Compression and querying of arbitrary geodesic distances
Aiello R., Banterle F., Pietroni N., Malomo L., Cignoni P., Scopigno R.
Geodesics
In this paper, we propose a novel method for accelerating the computation of geodesic distances over arbitrary manifold triangulated surfaces. The method is based on a preprocessing step where we build a data structure. This allows to store arbitrary complex distance metrics. We show that, by exploiting the precomputed data, the proposed method is significantly faster than the classical Dijkstra algorithm for the computation of point to point distances. Moreover, as we precompute exact geodesic distances, the proposed approach can be more accurate than state-of-the-art approximations.
Source: Image Analysis and Processing. 18th International Conference, ICIAP 2015, pp. 282–293, Genoa, Italy, 7-11/09/2015
Publisher: Springer, Berlin , Germania
1. L. Bertelli, B. Sumengen, and B.S. Manjunath. Redundancy in all pairs fast marching method. In Image Processing, 2006 IEEE Int. Conf. on, October 2006.
2. Marcel Campen and Leif Kobbelt. Walking on broken mesh: Defect-tolerant geodesic distances and parameterizations. Computer Graphics Forum, 30(2), 2011.
3. Jindong Chen and Yijie Han. Shortest paths on a polyhedron. In Proc. of the Sixth Annual Symp. on Computational Geometry, SCG '90, New York, NY, USA, 1990. ACM.
4. Massimiliano Corsini, Paolo Cignoni, and Roberto Scopigno. E cient and exible sampling with blue noise properties of triangular meshes. IEEE Trans. on Visualization and Computer Graphics, 18(6), 2012.
5. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. Geodesics in heat: A new approach to computing distance based on heat ow. ACM Trans. Graph., 32(5), October 2013.
6. Rina Dechter and Judea Pearl. Generalized best- rst search strategies and the optimality of a*. J. ACM, 32(3), July 1985.
7. R. Kimmel and J. A. Sethian. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. USA, 1998.
8. Danil Kirsanov. Minimal Discrete Curves and Surfaces. PhD thesis, The Division of Engineering and Applied Sciences, Harvard University, September 2004.
9. Dimas Mart nez, Luiz Velho, and Paulo C. Carvalho. Computing geodesics on triangular meshes. Comput. Graph., 29(5), October 2005.
10. Facundo Memoli and Guillermo Sapiro. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces: 730. J. Comput. Phys., 173(2), November 2001.
11. Facundo Memoli and Guillermo Sapiro. Distance functions and geodesics on submanifolds of r and point clouds. Journal on Applied Mathematics, 65(4), August 2005.
12. Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. The discrete geodesic problem. SIAM J. Comput., 16(4), August 1987.
13. Stanley Osher and James A. Sethian. Fronts propagating with curvature dependent speed: Algorithms based on hamilton-jacobi formulations. JOURNAL OF COMPUTATIONAL PHYSICS, 79(1), 1988.
14. Dao T. P. Quynh, Ying He, Shi-Qing Xin, and Zhonggui Chen. An intrinsic algorithm for computing geodesic distance elds on triangle meshes with holes. Graph. Models, 74(4), July 2012.
15. J. A. Sethian. A fast marching level set method for monotonically advancing fronts. In Proc. Nat. Acad. Sci, 1995.
16. Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler, and Hugues Hoppe. Fast exact and approximate geodesics on meshes. ACM Trans. Graph., 24(3), July 2005.
17. Sebastien Valette and Jean-Marc Chassery. Approximated centroidal voronoi diagrams for uniform polygonal mesh coarsening. In Computer Graphics Forum, volume 23, 2004.
18. O r Weber, Yohai S. Devir, Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Trans. Graph., 27(4), November 2008.
19. Shi-Qing Xin and Guo-Jin Wang. Improving chen and han's algorithm on the discrete geodesic problem. ACM Trans. Graph., 28(4), September 2009.
20. Shi-Qing Xin, Xiang Ying, and Ying He. Constant-time all-pairs geodesic distance query on triangle meshes. In Proc. of the ACM SIGGRAPH Symp. on Interactive 3D Graphics and Games, I3D '12, New York, NY, USA, 2012. ACM.
21. Xiang Ying, Xiaoning Wang, and Ying He. Saddle vertex graph (svg): A novel solution to the discrete geodesic problem. ACM Trans. Graph., 32(6), November 2013.
22. Xiang Ying, Shi-Qing Xin, and Ying He. Parallel chen-han (pch) algorithm for discrete geodesics. ACM Trans. Graph., 33(1), February 2014.
23. W. Zeng and R. L. Church. Finding shortest paths on real road networks: The case for a*. Int. J. Geogr. Inf. Sci., 23(4), April 2009.
2. Marcel Campen and Leif Kobbelt. Walking on broken mesh: Defect-tolerant geodesic distances and parameterizations. Computer Graphics Forum, 30(2), 2011.
3. Jindong Chen and Yijie Han. Shortest paths on a polyhedron. In Proc. of the Sixth Annual Symp. on Computational Geometry, SCG '90, New York, NY, USA, 1990. ACM.
4. Massimiliano Corsini, Paolo Cignoni, and Roberto Scopigno. E cient and exible sampling with blue noise properties of triangular meshes. IEEE Trans. on Visualization and Computer Graphics, 18(6), 2012.
5. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. Geodesics in heat: A new approach to computing distance based on heat ow. ACM Trans. Graph., 32(5), October 2013.
6. Rina Dechter and Judea Pearl. Generalized best- rst search strategies and the optimality of a*. J. ACM, 32(3), July 1985.
7. R. Kimmel and J. A. Sethian. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. USA, 1998.
8. Danil Kirsanov. Minimal Discrete Curves and Surfaces. PhD thesis, The Division of Engineering and Applied Sciences, Harvard University, September 2004.
9. Dimas Mart nez, Luiz Velho, and Paulo C. Carvalho. Computing geodesics on triangular meshes. Comput. Graph., 29(5), October 2005.
10. Facundo Memoli and Guillermo Sapiro. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces: 730. J. Comput. Phys., 173(2), November 2001.
11. Facundo Memoli and Guillermo Sapiro. Distance functions and geodesics on submanifolds of r and point clouds. Journal on Applied Mathematics, 65(4), August 2005.
12. Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. The discrete geodesic problem. SIAM J. Comput., 16(4), August 1987.
13. Stanley Osher and James A. Sethian. Fronts propagating with curvature dependent speed: Algorithms based on hamilton-jacobi formulations. JOURNAL OF COMPUTATIONAL PHYSICS, 79(1), 1988.
14. Dao T. P. Quynh, Ying He, Shi-Qing Xin, and Zhonggui Chen. An intrinsic algorithm for computing geodesic distance elds on triangle meshes with holes. Graph. Models, 74(4), July 2012.
15. J. A. Sethian. A fast marching level set method for monotonically advancing fronts. In Proc. Nat. Acad. Sci, 1995.
16. Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler, and Hugues Hoppe. Fast exact and approximate geodesics on meshes. ACM Trans. Graph., 24(3), July 2005.
17. Sebastien Valette and Jean-Marc Chassery. Approximated centroidal voronoi diagrams for uniform polygonal mesh coarsening. In Computer Graphics Forum, volume 23, 2004.
18. O r Weber, Yohai S. Devir, Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Trans. Graph., 27(4), November 2008.
19. Shi-Qing Xin and Guo-Jin Wang. Improving chen and han's algorithm on the discrete geodesic problem. ACM Trans. Graph., 28(4), September 2009.
20. Shi-Qing Xin, Xiang Ying, and Ying He. Constant-time all-pairs geodesic distance query on triangle meshes. In Proc. of the ACM SIGGRAPH Symp. on Interactive 3D Graphics and Games, I3D '12, New York, NY, USA, 2012. ACM.
21. Xiang Ying, Xiaoning Wang, and Ying He. Saddle vertex graph (svg): A novel solution to the discrete geodesic problem. ACM Trans. Graph., 32(6), November 2013.
22. Xiang Ying, Shi-Qing Xin, and Ying He. Parallel chen-han (pch) algorithm for discrete geodesics. ACM Trans. Graph., 33(1), February 2014.
23. W. Zeng and R. L. Church. Finding shortest paths on real road networks: The case for a*. Int. J. Geogr. Inf. Sci., 23(4), April 2009.
Metrics
Back to previous page
BibTeX entry
@inproceedings{oai:it.cnr:prodotti:340210,
title = {Compression and querying of arbitrary geodesic distances},
author = {Aiello R. and Banterle F. and Pietroni N. and Malomo L. and Cignoni P. and Scopigno R.},
publisher = {Springer, Berlin , Germania},
doi = {10.1007/978-3-319-23231-7_26},
booktitle = {Image Analysis and Processing. 18th International Conference, ICIAP 2015, pp. 282–293, Genoa, Italy, 7-11/09/2015},
year = {2015}
}
0000-0003-1357-7637CNR ExploRA
ISTI Repository
DOIAlso available from
ISTI Repository
DOIAlso available from
