Hello,
so recently I've jumped out of graphics and tried some path finding and navmesh generation. My workflow works as following:
- take set of models that are going to form NavMesh, and voxelize them
- triangulate isosurface on the voxels using Marching Cubes (or similar) algorithm -> this is my navmesh (now in my example it is something closely resembling sphere)
- generate navmesh (e.g. a graph when nodes are triangles and edges are connecting always 2 neighboring triangles).
- take 2 random points and find a set of nodes (triangles) between them (A-star)
Up to this point, it is quite simple and fast (and working). Now I've decided to implement some sort of path smoothing - I've examined the algorithm at http://digestingduck.blogspot.cz/2010/03/simple-stupid-funnel-algorithm.html - which is actually quite good and it will work well, but not for generic 3D navmesh (it will work well only for navmesh that is actually 2-dimensional).
So I tried to come up with something similar that would work for 3D navmesh - I obtain "portals" (edges that are between neighboring triangles along the path). So far I'm good (also I already know that the portals are always stored as left-right pair, using path as a reference). And now the hard part:
Extending the algorithm on the linked site to 3D I can actually calculate quite good path, yet with one problem - my path isn't going over the surface of triangles (which is obvious) - but basically going straight to either another apex point, or goal. Now my idea was to project back the path to each portal edge (by just calculating 2 closest points on both lines), and adding this into the path.
I'm still in the phase where I'm testing this (sio, but if anyone found similar problem, please explain how you solved it.
Results (good path):
Results (wrong path - see bottom):
It looks like I'm nor properly ignoring some portals I actually could (because 1st, 2nd and 3rd portal from the bottom actually share vertex).
I'm not going to spam source here right away, I'm still checking whether there aren't any typos that could cause this. But if anyone is interested I might link it somewhere.
