I implemented Djikstra's shortest path algorithm to approximate Geodesics on arbitrary meshes. Djikstra's works, but I noticed a problem inherent to the discretization of my meshes.
Consider the following figure squence:
This is my current refinement algorithm which is the easiest/standard face subdivision. Now consider the approximation of a geodesic in 2 points:
The blue point is where I think the actual geodesic intersects that edge, which is quite far from where the approximated geodesic passes. However that path ISN'T wrong.
Consider a square grid. The distance between any 2 points in the grid is the manhattan distance |x| + |y|.
So as far as Djikstra's is concerned, a path that goes all the way down and then to the left has the same length as a path that goes diagonally in a staircase pattern. Refining the mesh won't change the distance either. In other words, the limit of the shortest path found by Djikstra in a regular square grid as the size of the squares goes to 0 is NOT the straigtht line connecting 2 points.
Now the actual question, does anyone know of a way to subdivide my surface that is fairly straightforward but will actually converge to the geodesic?