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"

Gyp

Could you be more precise about the problem with using dijkstras algorithm? Especially where the inaccuracies come from? Are the edges of the mesh somehow approximations of some other structure? Using multiple starting points should be no problem for dijkstras algorithm and if the matroid condition holds it will find the best solution, so I am not seeing a problem here. – Bywaters

the apporximation comes from the fact that Dijkstra is very mesh-dependent.. considering a plane made of tris, and a single seed point in the center, the correct distance between each grid vertex and the seed vertex is equal to the Euclidean distance, while Dijkstra would report such a correct value only for the vertices lying along edges at PI/4 steps from the seed. Wheat i mean is that insted of giving a correct euclidean distance, you would end up with a simple sum of the distances. – Gyp

Wait... you want Euclidean distance between a given point and the nearest seed point? That's trivial. – Superimposed

no, I need the geodesic, that is, the distance between a point and a set of seeds point in the same surface. If the surface is folded on itself (u shaped for instance) the geodesic distance & the euclidean distance are way different – Gyp

I was talking about euclidean distances on the comment before because I stated the example involved a plane, in which case euclidean distance equals the shortest path on a flattened surface – Gyp

Have you told us what surface is interpolated over one of your quads? I understand it does not lie in one plane, but computing the geodesic distance requires a concrete definition of the surface. With triangles the faces can be flat and geodesic distance is comparatively easy. Perhaps you are looking for a way to interpolate the quad surface that makes distance calculation as easy as possible? – Foret

I would suggest to split this problem into a few, but more specific sub-problems, that might help you to find a right way. As an example, you might like to ask what people think about applying "this&that" to "such..." problem. In other way, I am afraid, this question is too long to get answer without bounty, for which you do not have yet points. – Jahdal

Sounds like you want distance on the surface defined by your mesh, but you don't necessarily need to go through the vertices of the mesh. I agree with the references you found that a triangular mesh makes this much easier, as you can approximate your surface by piecewise flat patches. Maybe you could split up your quads into a few triangles? As long as your surface curvature isn't too extreme that should get you an accurate result. – Serve

The seed set thing is confusing. By stating that it is closed, do you mean all of you seed vertices are connected? Why not merge them into one vertex? Does the distance within the seed set matter? Honestly I am still not a 100% sure I understand the problem, and illustration would really help. As I see it, doing a fill algorithm and using that as a heuristic for regular path finding should work. I think approaching it as an optimization problem instead of an algorithm problem will help. – Antipole

Answer 1

There is a new paper that discusses exactly how to solve your problem: Geodesics in Heat by Keenan Crane, Clarisse Weischedel and Max Wardetzky. (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.

Nablus

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.

Gobert