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.