Jump to content
  • Advertisement
Sign in to follow this  
Vilem Otte

Funnel algorithm on actual 3D data

This topic is 747 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts



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.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!