Advertisement Jump to content
Sign in to follow this  

Subdividing Navigation Meshes

This topic is 3820 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

I have 2 questions, 1) When we speak about navigation mesh, is it supposed to be the ground mesh? If it is not, do we put a navigation mesh that overlaps the original ground mesh? but hide it in the game? 2) How do you cut and merge polygons of the nav mesh? For example, when a wall cuts across a polygon of the nav mesh, how do you cut the nav mesh from a "certain" point of one edge to another point who belongs to the opposite edge? What i mean by "certain" is that I don't know where it should be starting (leftmost, center or rightmost)... What Direct3D functions are helpful in my case? Can't explain.... but hope that you would understand what I am talking about. Thanks Jack [Edited by - lucky6969b on August 2, 2008 4:00:26 AM]

Share this post

Link to post
Share on other sites
Usually a navigation mesh will be a different mesh from the geometry that is used to render the ground. There are a couple of reasons. First, the idea is that the nav mesh would be simpler, e.g., fewer vertices and triangles, so that operations that use it, such as ray tracing to find the ground height and path finding operations, can run much faster than if you used a ground mesh that had more detail. It won't be the case for every game that the ground mesh needs more detail, but it can be. Another reason for having a separate navigation mesh is that you may not want the character to be able to walk everywhere on the ground. By making a different navigation mesh, you can limit the walkable area, to keep the character within the main gameplay areas.

As for cutting a navigation can be tricky to automatically generate navigation meshes. The techniques for doing this include polygon clipping and Boolean set operations. It can be done with BSP trees or other approaches. I would say that in a typical game production pipeline, navigation meshes are probably usually custom built by an artist. An artist might use the ground mesh as a starting point, making a copy to be the nav mesh, then use tools inside a digital content creation (DCC) tool such as 3ds max or Maya to trim the nav mesh copy appropriately.

Note that if you do automatically generate your nav meshes by trimming a ground mesh against a wall, now you have the possibility that your character can walk directly into a wall (unless you have another collision response operation also), while if you manually created the nav mesh you could trim it somewhat away from the wall to prevent the character from walking into the wall without doing a separate character/wall collision response procedure.

I hope that helps!

Share this post

Link to post
Share on other sites
You should also note that depending on how your navmesh code is written, there may be other limitations to the mesh that dictate a custom drawn mesh, or even several seperate meshes that overlap where they connect.
Since some navmesh stuff is just a lookup table with n^2 entries for n triangles, you need to keep your meshes small or else have a huge memory footprint. And the way that table is created means that you can't have any internal verticies in the mesh.

Share this post

Link to post
Share on other sites
Thank you for replying.
I have a strong desire to automate this process, as this is not a chore for me.
I am using Direct9c, and I've heard of adjacency but I am not sure how to manipulate edges and vertices of a mesh with Direct9c...
Any examples that I can take a look at?
I have bought 2 books namely AI Programming Wisdoms 3+4? which are quite dear :) but I still haven't quite mastered the techniques yet...

Share this post

Link to post
Share on other sites
I think one of the earlier AI Wisdom books may have had more coverage of navigation meshes. If I recall correctly, the first book may have had a fairly comprehensive example, though I can't vouch for the quality of the technique or code.

Share this post

Link to post
Share on other sites
Actually, it was Greg Snook's article on navigation meshes in the original Game Programming Gems that I was thinking about, not the earlier AI Wisdom books.

If you have a separate mesh for your ground geometry, then here is an approach I would suggest might be workable:

*** Part 1 - Find contours of world geometry ***

for each item in the world other than the ground plane
// Project points into xy plane, creating a 2D point
// cloud.
add each vertex into an array of 2D points, setting Z = 0

// determine a convex shape that approximates the item's
// projection shape on the ground
find convex contour of the 2D point cloud using any
convenient technique

// cleanup contour and add to array of contours
weld points together to make sure the contour is a single
closed loop of line segments

// optionally increase size of the contours to push
// nav mesh away from geometry. here's an easy way.
find centroid of all points that make up the contour.
scale all the points about the centroid by some uniform
scale factor x that is greater than 1.0.

*** Part 2 - Cut holes in the ground mesh ***

make a copy of the ground mesh, but disconnect the triangles
so you have 3 unique vertices per triangle....this "triangle
soup" approach is not fully optimal for performance or memory
but can make things quite a bit easier to code.

for each contour above
Mark all the triangles as unvisited, e.g., assign a flag = false
on a per triangle basis.

For each triangle in the ground mesh copy
if visited = true, skip the triangle,
if the triangle doesn't overlap the contour
mark the triangle as visited = true
clip the triangle against the convex contour using
(for example) the Sutherland-Hodgeman algorithm. But
remember that you want to keep the part that is
outside the contour, not inside... The result
may not be a triangle, and in fact a given triangle
could be completely clipped away or could be cut into
two independent pieces.

When you do the clip, you'll compute the clip points
in 2D (xy plane), but when inserting new vertices
remember to compute the z coordinate as well, since
you'll need the z point in your final clipped nav
ground mesh.

triangulate the clipped result, marking each
new triangle visited = true, and adding all
new triangles into the copied mesh

delete the original, unclipped triangle from
the list

Once you've clipped the copied mesh against all contours,
change the connectivity of the mesh so that all coincident
vertices are welded together, e.g., rebuild the indexed
mesh out of triangle soup. And you're done!

Now, you could do something fancier...instead of making
a triangle soup and then rebuilding an indexed mesh in the
end, use a winged-edge data structure (WEDS) to cut holes
directly in the indexed mesh. But coding that will be
quite a bit more difficult.

If you have multiple ground geometries that overlap, you'll
have to deal with that somehow, and you could do it by
adding logic to handle locomotion transitions from one nav
mesh to another, or by clipping one against the other and
welding them together into one....anyway, something to

Hope this helps!

Share this post

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

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. 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!