Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Wouldn't that make the navmesh (and pathfinding) a bit complex? –  Boreal 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. –  Boreal Aug 30 '12 at 13:04
add comment

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.

share|improve this answer
    
This just generates a grid, doesn't it? I want to avoid "the grid", or worse, a waypoint graph, at all costs. –  Boreal 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. –  Boreal Sep 1 '12 at 0:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.