Geodesic computation on triangle meshes? [closed]

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)

Gael

Take a look on this implementation. – Dharma

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.

Herschelherself

Answer 2

Just to add to the previous answer by wxnfifth that Fast marching method can be applied not alone, but as the first step to receive a good approximation of geodesic path, which is iteratively improved as follows:

1. Compose the strip of triangles containing existing approximation of the path.
2. Find the shortest path in the strip, which is a task that can be solved exactly in a linear time, for example by Shortest Paths in Polygons method by Wolfgang Mulzer.
3. If that path passes via a vertex on the boundary of triangle strip then the path along the other side of the vertex is considered, and if it is shorter then the strip is updated and the algorithm is restarted from step 2.

As to the libraries, where it is implemented, one can consider open-source MeshLib and specifically the function computeSurfacePath. And there is even a short video showing its work on some sample mesh.

---

Opulence