Geodesic computation on triangle meshes?

Question

I am trying to find the distance between two points on a triangulated surface (geodesic distance). It looks like a basic operation and is not trivial. So I am wondering if there are any libraries that do this? My google fo failed, so I would greatly appreciate any pointers.

(I am aware of CGAL, scipy.spatial, but I couldn't find anything in the docs, let me know if I missed something there)

Answer 1

There are many implementation for computing geodesic distance on triangle mesh. Some are approximate and some are exact.

1.Fast Marching method. This method is approximate and in practice the average error is below 1%. You can refer to Gabriel Peyre's implementation of fast marching method in matlab. http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching

2. MMP method proposed by [1] and implemented in [2]. This method is exact and the code is in https://code.google.com/p/geodesic/ . Same as the comment by Ante. A disadvantage is that when the mesh is larege, MMP method will consume a lot of memory, O(n^2), n is the number of vertices.

3. CH method proposed in [3] and improved and implemented in [4]. This method is exact and consume less memory than MMP method. The code is in https://sites.google.com/site/xinshiqing/knowledge-share

4. Heat method proposed in [5]. One implementation is in https://github.com/dgpdec/course This method is approximated and require a preprocessing process. It's faster than Fast Marching method.

[1] Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (August 1987), 647-668.

[2] Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven Gortler, Hugues Hoppe. Fast exact and approximate geodesics on meshes. ACM Trans. Graphics (SIGGRAPH), 24(3), 2005.

[3] Chen, J. and Han, Y.1990. Shortest paths on a polyhedron. InSCG '90: Proceedings of the sixth annual symposium on Computational geometry. ACM Press, New York, NY, USA, 360{369

[4] Shi-Qing Xin and Guo-Jin Wang. 2009. Improving Chen and Han's algorithm on the discrete geodesic problem. ACM Trans. Graph. 28, 4, Article 104 (September 2009), 8 pages.

[5] Crane K, Weischedel C, Wardetzky M. Geodesics in heat: a new approach to computing distance based on heat flow[J]. ACM Transactions on Graphics (TOG), 2013, 32(5): 152.