shortest paths & geodesics

Question

given a mesh made entirely of quads, where every vertex has valence n (with n >= 3), and does not lie on the same plane, I need to find the distance of every vertex in the mesh from a closed set of seed vertices. That is, given one or more mesh vertices (a seed set), I need to build a distance map that stores the distance of each mesh vertex from the seed set (which will have distance 0 from themselves).

after spending some time searching for possible solutions, I got the following picture:

1) it is not trivial, and different approaches have been developed during the last 20 years or so

2) every algorithm that takes into account a 3d domain is restricted to a triangular domain

said that, this is the picture I got:

Dijkstra algorithm may be used as a way to find the shortest path between 2 vertices, following the edges of the mesh, but it is very inaccurate and will lead to an erroneous geodesic. Lanthier (LA) proposed an improvement, but the error is still quite high.

Kimmel and Sethian (KS) proposed a Fast Marching Method -FMM- to solve the Eikonal equation, addressing the issue calculating the propagation of a wave starting at the seed points and recording the time the wave crosses every vertex. Unfortunately this algorithm, while simple enough to implement, still brings a quite inaccurate result, and care has to be taken to avoid obtuse triangles, or treat them in a very special way. Novotni (NV) addressed the problem of (KS) precision in a single seed scenario, but it is unclear to me if:

a) it still suffers from the obtuse angle problem

b) when used in a multiple seed points scenario, a single FMM has to be implemented for every single seed in order to find the minimum distance for each mesh vertex from each seed (that is, in a 10 seed points scenario, FMM would have to be run 10 times per each mesh vertex)

On the other side, an exact algorithm -MMP- that leads to 0 error has been presented by Mitchell & al. (MI) in 87, and AFAIK has never been really implmeneted (probably due to the computing power required). On the same exact approach, Surazhsky & al. (SU) provided an alternative exact algorithm based on MMP that should outperform the latter in terms of speed, still leading to a correct result. Unfortunately the computing power required for the calculation, even if much less than the original MMP, is still high enough so that realtime interactive implementation is not feasible at this time. (SU) also proposed an approximation of their exact algorithm, what they called flat-exact. It should take the same computational time of FMM, while bringing only 1/5th of the error, but:

c) it is unclear to me if it can be used in a multiple seeds scenario.

Other exact shortest path algorithms have been proposed by Chen & Han (CH) and Kapoor (KP), but while the first is absolutely slow, the second is just too complicated to be implemented in practice.

so.. the bottom line is: I need a distance from a set, not the shortest path between 2 points.

if I got it right,

either I use FMM to get a distance of each vertex from a set in a single pass,

-or-

use another algorithm to calulate the geodesic from every mesh vertex to every seed point and find the shortest one (and If I got it right that would mean calling that algorithm on every seed point for every mesh vertex, that is, on a 10,000 vertex mesh and a seed set of 50 points, I would have to calculate 500,000 geodesics in order to get the 10,000 shortest one)

Am I missing something? is FMM the only way to deal with multiple seeds distances in a single pass? Someone knows if the flat-exact algorithm may be used in a multiple seed points scenario?

thnx

Notes:

(LA): Lanthier & al. "Approximating weighted shortest paths on polyhedral surfaces"

(KS): Kimmel, Sethian "Computing geodesic paths on manifolds"

(NV): Novotni "Computing geodesic distances on triangular meshes"

(MI): Mitchell & al. "The discrete geodesic problem"

(SU): Surazhsky, Kirsanov & al. "Fast exact and approximate geodesics on meshes"

(CH): Chen, Han, "Shortest paths on polyhedron"

(KP): Kapoor "Efficient computation of geodeisc shortest paths"

Answer 1

There is a new paper that discusses exactly how to solve your problem: Geodesics in Heat. (Just spotted it and it reminded me of your question.) The idea is that the heat equation can be thought of as describing the diffusion of particles from some central point. Although it models random diffusion, if you run the heat equation for a short enough time then any particles that get from A to B must have followed the shortest path so mathematically you can get an estimate of distance.

The catch is that the proportion of particles that follow a path close to the shortest path is tiny so you have to solve a differential equation that starts large at some region and rapidly ends up small elsewhere. That's not likely to be well behaved numerically. The trick is that for larger t, even though it doesn't measure distance correctly, it does give the gradient of the distance function and this can be used with other methods to get the distance.

TL;DR The linked paper solves distance from every point in a mesh to any subdomain, including finite sets of seed points.

Oh...and I haven't tested it myself.

Answer 2

"a) it still suffers from the obtuse angle problem"

Yes, the original FMM suffers from the obtuse angle problem, but researchers have solved this problem. This link is Gabriel Peyre's implementation of fast marching method in matlab. http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching

"b) when used in a multiple seed points scenario, a single FMM has to be implemented for every single seed in order to find the minimum distance for each mesh vertex from each seed (that is, in a 10 seed points scenario, FMM would have to be run 10 times per each mesh vertex)"

If you mean multi-source shortest path problem, fast marching method don't need to run multiple times. For example, for seed s1 and s2, and destination v, and shortest distance between s1 and v is d(s1,v), distance between s2 and v is d(s2,v). To find the shortest distance between v and s1,s2, min(d(s1,v),d(s2,v)), run one time fast marching method is enough. But if you want to know both d(s1,v) and d(s2,v), you need to run FMM multiple times.

"On the other side, an exact algorithm -MMP- that leads to 0 error has been presented by Mitchell & al. (MI) in 87, and AFAIK has never been really implmeneted (probably due to the computing power required). On the same exact approach, Surazhsky & al. (SU) provided an alternative exact algorithm based on MMP that should outperform the latter in terms of speed, still leading to a correct result. Unfortunately the computing power required for the calculation, even if much less than the original MMP, is still high enough so that realtime interactive implementation is not feasible at this time. (SU) also proposed an approximation of their exact algorithm, what they called flat-exact. It should take the same computational time of FMM, while bringing only 1/5th of the error, but:"

comments: MMP has an implementation in 2005, the implementation is published in [1]. The link to the code is in https://code.google.com/p/geodesic/

"c) it is unclear to me if it can be used in a multiple seeds scenario."

It can be used in multi seeds scenario and the above code implemented it.

"Other exact shortest path algorithms have been proposed by Chen & Han (CH) and Kapoor (KP), but while the first is absolutely slow, the second is just too complicated to be implemented in practice."

comments: The first one is slow, but in [2] the author improved the CH algorithm and give an practical implementation which is exact and faster than MMP. The code is in sites.google.com/site/xinshiqing/knowledge-share

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

[2]Improving Chen & Han’s Algorithm on the Discrete Geodesic Problem. Shiqing Xin and Guo-Jin Wang. ACM Transactions on Graphics (TOG): 28(4), pp. 1–8, August 2009.

Answer 3

Another option: Euclidean Shortest Path Algorithm This is a recent (2012) generic implementation of shortest path.

Answer 4

This may be better suited for the theoretical computer science stack exchange. See this post on shortest edge paths.

https://cstheory.stackexchange.com/questions/6822/shortest-paths-disallowing-each-edge

and perhaps

https://cstheory.stackexchange.com/questions/4034/complexity-of-computing-shortest-paths-in-the-plane-with-polygonal-obstacles