Creating a navmesh from a voxel terrain

Question

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"?

Answer 1

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.

Answer 2

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.