Friday, July 31, 2009

Navmesh Height Accuracy

I have spent some time recently to research different methods to improve the height accuracy of the navigation meshes. I had four ideas how I wanted to approach problem:
  1. Subdivide the navmesh polygons to better conform the underlying terrain
  2. Use subdivision based displacement mapping per navmesh poly
  3. Use method similar to texture mapping per polygon
  4. User callback function
Option number one would not require any changes to the run-time part, but it would cost both memory as well as performance, since the A* node count would increase.

Option two was my number one choice for a long time. The idea would be to have some sort of subdivision scheme which is easy to reproduce at runtime and store deltas per subdivision. In the end I rejected this since I could not find proper subdivision scheme that would work on polygons and slivers too.

The texture mapping approach would store a small heightmap texture per polygon or per couple of polygons much like lightmappers do. The additional awesomeness about this feature is that it would allow to embed other kinds of gameplay related information into the navmesh, such as how stealth the current location is, or stance value for the character, etc.

Some path finding solutions use the user callback mechanism and I might add that to Detour at some point too. The rationale behind that solution is that the height data can take a lot of memory and is often already stored somewhere.

After some failed prototypes with the tesselation approach I tried out the texture mapping and it seemed to work better, but not without its own set of problems. The image above shows first the raw navigation mesh and below is the texture mapped version.

The heigthfield texel size in the picture is roughly the width of the thin polygons on the bridge. The image shows less than a quater of the level, and the textures for that level take 128.3 kB. It should be possible to trim that number using some simple compression and omitting textures which are not really used.

If you have good pointers to simple texture compression schemes which allow fast random lookup, let me know! Bonus points for anything that allows fast bilerp too.

I have tried to make the textures so that the height is slight over estimation. That should make it easier to trace a perfect ground alignment. It is possible to later on add different downsampling schemes if necessary.

Currently there is a small texture stored per polygon. First I wanted to store a texture per region, but that turned out to be more complicated than I expected. When the texel size increases there starts to be more and more problems. Since the regions are non-convex, something like U-shaped staircase can create a lot of problems if you try to own sample it.

There are still some similar problems with the per polygon textures, but they reasonable to fix.

The next update of Recast and Detour will include the height texture feature. Hopefully out soonish. The code will be laid out so that the textures are optional.


  1. dxt is a standart and here is its opensource implementation
    At the bottom of this page are another different libs including s3tc.

  2. also I thought that the best way is 4 + 3.
    Have a user defined callback (4) + implement it as texture mapping sheme(3) by default.

  3. I'll take a look at that. The data format in DXT is quite a bit different than what I need, but I might be able to use the idea.

    Yeah, I'm going to use 4+3. Textures will be implemented first and I will then take a look at how to best implement the callbacks.

  4. Have you considered UV unwrapping and a texture atlas for the textures, like lightmaps? This would smooth out transitions between polygons.

  5. Hmm why don't you use your first approach but with a modified data model?
    The polygons which are the outcome of the subdivide process are still parts of the original polygon. Hence you can have a structure like that:

    indices contains the border vertices of the original polygon

    vertices contains all (including the new ones generated from the subdivide process) vertices

    subdividePolygons contains the indices of the subdivide-polygons (also stored in vertices)

    With that extension the pathfinding isn't slowed down because the node count in searchspace keeps the same and you still can access the height information.

    Maybe I missed something

  6. @Steve, that's pretty much what I'm doing, but there are several cases where it just does not work.

    @fish, that's pretty much the tesselation idea I had. Keep the original simple navigation data, but allow have finer tesselation for just the height. Storing extra polygons requires quite a lot more extra data and refining the height can become quite intensive task because you need to look through all the subdiv polygons too.

    I will post an update on the same topic soon, which should answer your question more inde detail.