Sign in to follow this  
supagu

shortest path between two points on tri mesh

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
You can recursively try to shorten the path you have. for example, the kink could be shortened by skipping over the offending vertex. If that path is not obstructed, then it is more optimal.

Similarly, what you can do is take the absolute shortest path (the green direct line). The link intersects with the mesh, so you would have to stop there, then walk up along the first edge to the first vertex on your red path.

From there, is is a direct line of sight to the destination, with no obstruction. So that is the end of the path.

Then the next step would be to go over that path you have computed, and try to see if it is possible to shortcut corners, until none can be removed.



there's even a 5th step I missed...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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/

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this