# Creating a navmesh from a voxel terrain

My world is represented by a 3D density field, where a positive density means solid ground and a negative (or zero) density means air. How can I generate a navmesh from that voxel data, with surfaces with a slope of 45 degrees or less being "walkable"?

-

If you're already building a triangle mesh for rendering these voxels, it shouldn't be too hard to do.

For each triangle, take (or calculate if you haven't) the normal vector, make sure this vector is normalized. Then take the dot product of your "up" direction (for example [0,0,1] if Z is up) and this normal vector. The result is the cosine of the angle between the X/Y plane and the plane the triangle lies in.

If the result is <= cos(degToRad(45)) it meets your criteria and can be added to the nav mesh.

Perhaps perform some pruning of islands of single triangles, or collections of triangles with a small area.

-
Wouldn't that make the navmesh (and pathfinding) a bit complex? – jmegaffin Aug 29 '12 at 13:00
I suppose that depends entirely on the complexity of your density field, and the resolution of your triangle mesh, but it's possible. You could generate the nav mesh from a lower quality mesh, but that might make it inaccurate, or you could optimize the nav mesh afterwards - preserve features but strip geometry. – melak47 Aug 30 '12 at 5:35
That sounds like a good idea - I'll strip unneeded triangles from the land mesh and then simplify it. – jmegaffin Aug 30 '12 at 13:04

rifles through source code

I implemented something like this when I was still using python - it's the primary reason I moved to C++, the array work was getting too large. The solution is a little lost to time, but it went something along the lines of:

Find a value in the 3Grid that is > 0, and has (n) values above it that are < 0 and has not already been defined. This is the definition of "walkable" in a second 3Grid, add this point.

Find all adjacent spaces that meet the same criteria - and adjacent spaces up, and down one unit.

For each point, add a value to the original point to link, and add new point to second 3Grid with link back to original point (so the path goes both ways).

When no more consecutive points can be added, continue to scan through grid, and repeat.

This gives you a grid that you should be able to navigate without issue - my plan was to measure height at run-time.

The 45 degrees is implicit rather than explicit - an incline or decline of 1:1 is ~45 but if you're using a full marching cubes implementation you may encounter a bit of variation on this.

There are variations on this - you could generate the mesh based on the current location and ignore disconnected meshes. Or, select a range where the grid expires.

Edit: You could extend this to a nav-mesh using marching squares, if neighbouring node (including up or down) is valid, add it to the square's bitmask, otherwise leave it blank.

-
This just generates a grid, doesn't it? I want to avoid "the grid", or worse, a waypoint graph, at all costs. – jmegaffin Aug 29 '12 at 13:17
This implementation does - but you could build a nav-mesh in a similar fashion - off the top of my head, the marching squares algorithm will do the work for you - see my edit. – salmonmoose Aug 31 '12 at 2:53
That's an interesting idea. I'll keep that in consideration. – jmegaffin Sep 1 '12 at 0:11