Geodesic distance

Newbie & Debugging Questions
#1

Hi guys,

For a project I’m supposed to implement sth called the geodesic distance into my program. What I have until now is a model-loader which takes an .obj. file and displays it on screen. now i’m supposed to click and put 2 points on the mesh and calculate the shortest geodesic distance between those points. From what I understand, this can be done with the dijkstra-algorithm, but I am not too sure.

What I basically wanted to ask for is, if somebody could point me into the right direction to implement this functionality to compute the shortest geodesic distance between 2 points or even help me out with some tutorials / other helpful websites :slight_smile:

Thank you in advance!

#2

On a arbitrary “surface” the Geodesic distance is not so easy to calculate. Look up tensors and tensor calculus… well you can do it with variational calculus or whatever its called if you have a nice metric (way to measure distance).

However if you only care about the distance on a mesh, as in that you don;t care that this is approximating some surface, then yes, any standard min path algos will work with a fine mesh. (assuming normal distance metrics).

So dijkstra-algorithm or A* with the correct heuristic estimator should work fine. Just think of each polygon as a node with weighted edges to other nodes (polys) and you have a graph structure that these algorithms work on. (google for details, or even use search here).

Note however this is an approximation, and there are some details like the fact that the points could be much “smaller” than a polygon in which case adjustments would need to me made. In other words the mesh needs to be very fine because the error will be on the order of the largest poly in the mesh.

On a course mesh where you want accuracy much higer than the largest poly size, you would need to do it geometrically, with paths on the surface defined with cutting planes and if you don’t have a simple mesh (aka you have holes) its gets really tricky.

#3

If this isn’t a university assignment then you could port the BSD MatLab implementation available from Mathworks.