Ideas on calculating geodesic distance and shortest path.

[Mario]

Hello everybody, I've been reading the forums regularly in the past, but this is my first post.

I'm trying to find a way to calculate shortest path between two points on a surface to calculate it's geodesic distance, but I can't find a proper way. I managed to get an aproximation, but the moment the surfaces gets too convex, I loose track. Anyone has done this before or knows some good tips to get into the right track, please? I've checked a few technical papers but some of them are way ahead my understanding and other I can't find a way to translate them to ICE.

I case it helps, what I've done until now is: I get the starting point on the surface and the vector that goes towards the target point on the surface, then I start crawling equidistant points over the surface in that direction and I sum up their distances. The problem is that when I reach very curved parts of the surface, I loose track and besides that, I'm not sure I'm really following the shortest path.

Thank you!

[grahamef]

I hate to disappoint, but in general this is a very hard problem and the subject of ongoing research e.g. http://www.cs.technion.ac.il/~bron/research_fmm.html.

You might want to try to simplify the problem, e.g. define what's "good enough" for a specific case and just solve that. Or perhaps you could sample the surface fairly regularly and adapt something like the A* pathfinding algorithm.

[Mario]

Well, I have been working on it a bit more and I think I have something which is 'kinda' aproximate... But I don't think it's as close as the methods described in those technical papers, I mean, it finds a path and measures it, but I'm still not sure it's the absolute shortest patch. I case someone is curious I could share a compound even just for the sake of exchanging some ideas. ;-)

Cheers.

[Letterbox]

You might find this easier, and you can do the same thing in mathematica too, if you prefer that. http://www.ceremade.dauphine.fr/~peyre/teaching/manifold/tp3.html

Depending on your mesh and its density and whats exactly required you might find that one icetree that sets the weights to the edge lengths and then solve the shortest path (http://en.wikipedia.org/wiki/Shortest_path_problem) via something like Dijkstra's might be sufficient. You should find code out there for that.

Both to some degree require some understanding of graph theory (typically found in books with "Discrete mathematics" in the title), but depending on exactly your needs the readings required may not be that much at all. You might even look for some youtube videos on the subject.

[Mario]

Thanks for your replies @grahamef and @Letterbox!

To be honest, it's far enough for what I needed for my actual project. But I took it as an exercise to squeeze my brain and learn some ICE. It's working pretty well on simple primitives like spheres or cones, but in much more complex meshes (like characters) I could'nt tell if it's really choosing the shortest path... maybe it is. It would be great to know some "Mathematica" just to check how biased this method is, hehe...

Cheers.

PS.- Here's the compound in case someone feels like testing it. It's a bit messy inside... sorry.

[Letterbox]

If you have what you need, then you've done a great job.

Often the way is find a solution based on needs, not always on mathematical first principles and generalized cases. That my friend takes time. Lots of time. But tools like Mathematica & Matlab surely do help, good to know, just in case you ever go down this path again ( i hope it's the shortest ).

[Mario]

... definitely it's not finding the shortest path. I underestimated the magnitude of the problem...

[Daniel Brassard]

What if you shrink-wrap a geodesic sphere onto your surface, what would be the result?
Increase the geodesic subdivision and try to gain more details?
Does it approximate well or is it off, way off?

Sometime a simple solution is only what we need!

Dan

[Mario]

Hey Dan, thanks for your reply!

I'll have to give it a try. Will that be using Dijkstra's algorythm to traverse the edges of the shrinked sphere?

Cheers