I am working on some path finding code, I have a triangle navigation mesh, i have two points (either end of the green line), my code then finds the least amount of triangles to get between the two (the blue triangles). Now after that, i iterate through all triangles to generate the shortest path while staying inside the triangles. The red line is what my current algorithm does. http://www.adam.com.au/mathews64/shortestPath.jpg the problem i'm having is, you can see a little kink in my red line, so its not actually the shortest line. this is more of an algorithm problem than a math problem, but it seems to most suitable area to post. so i want to remove the kink so i have the actual shortest line, and i'd like to do this with only a single pass over the triangles. Im thinking this may not be possible and i may need to take my now optimised points (from the red line) and keep running an algorithm over them to eliminate points until i have the shortest path :-/ so now for my algorithm: the green line shall be called the best line the points that make up the red line shall be called the point list for each triangle: if (the best line intersects the polygon) skip this polygon (ie. continue) get closest point from triangle to the best line and add it to a the point list end for each

Hi!

I'm not sure I understand what you are doing correctly, but how about adjusting the best line when you add a new point to the point list? The new point would be the starting point of the new best line, since up to that point the path should already be optimal.*

* I don't think your 'best line' approach can find the globally optimal path (if there are two 'corridors' in the navmesh leading to the same destination, it could select the longer one depending on the shape of the first triangles), but it's locally optimal at least.

ive thought of adjust the best line, but that would also result in a similar line (the same in the above case).
I've also thought of working forwards till i hit a point, then work backwards till i hit a point rinse and repeat, but again, it wouldnt be the optimal line

Hmm, I think we're misunderstanding each other at some point. The way I understand it, using your algorithm + adjusting the best line should lead to the optimal result in the example you provided.

Step-by-step it would look like this:
- 1. triangle is skipped
- 2. triangle - add the upper vertex to the point list, set starting point of the best line to this point
- all subsequent triangles skipped

If you instead look for the shortest path on the mesh (distance wise and not count the tris), there is an algorithm that finds the exact shortest path between any points on a manifold mesh.

It's called MMP and there's a good paper on it here:
http://research.microsoft.com/~hoppe/geodesics.pdf

Be warned though, it's a lot of work to implement.

Quote:Original post by Morrandir
Step-by-step it would look like this:
- 1. triangle is skipped
- 2. triangle - add the upper vertex to the point list, set starting point of the best line to this point
- all subsequent triangles skipped

this will only work from bottom to top, doing it the other way the result will be the same

An easily stated problem that you would hope has a simple solution, but as the Hoppe paper shows, this is not the case. I have a PDF that shows my (probably naive) approach to this problem: Geodesics on Triangle Meshes. Unfortunately, I am just shy of finishing the source code for this, so no concrete code samples to show yet.

There is also an newer paper: http://cg.cs.tsinghua.edu.cn/papers/degenerate.pdf which describes how do deal with degenerate cases.

Implementing either of these methods is quite hard, so I suggest this open implementation of the original (non degenerate handling) paper with MIT license: http://code.google.com/p/geodesic/