Compressed Heighfields

One of the items on my TODO list for 2011 is support for temporary obstacles. I posted earlier about the possibility to compress the heighfield and use part of the Recast process to regenerate tiles much faster.

I have been prototyping heighfield data compression recently. The above picture shows the test scene I have been using. It has both simple plane like surfaces as well as building with many levels.

The compression process starts by stripping down and packing the heighfield data. I store elevation, free space and area type for each walkable span. In addition to that the ground grid stores number of layers per column. See my previous post on the topic for a bit more details.

That is the minimum amount of data to reproduce a compact heighfield for a particular tile. The minimal heighfield data for the test scene takes 713kB. This is more than the 512kB I reported earlier. The reason is that each tile also contains border, which is required in order to make the tiles match ar borders.

The compressed data for the whole scene takes 82kB. This is the amount of data that needs to kept in memory to regenerate any tile in the scene. It is quite a bit more than the 32kB I reported earlier. The difference between the tests is that the old data was compressed as one huge chunk using zip and my recent prototype compresses each tile individually and uses libLZF which does not compress so well, but it is a lot faster.

For a comparison, the actual navmesh for the test scene takes 98kB. I will provide some timings as I get further with the implementation.

Changes in the Build Process

Currently the build process for a tiled navmesh goes like this:

for each tile

- rasterize triangles

- find walkable cells

- mark areas

- build regions

- build contours

- build poly mesh

- build detail mesh

- store navmesh

With compressed heighfield the process changes to follows:

Preprocess

for each tile

- rasterize static triangles

- find walkable cells

- mark areas

- store compressed heighfield

At Run Time

for a changed tile

- uncompressed heighfield

- mark obstacles

- build regions

- build contours

- build poly mesh

- build detail mesh

- store navmesh

Triangle voxelization is usually dominating facter when generating a tile. For example it takes 71.5% of the time to generate the highlighted tile in the test scene.

The perfectionist in me still would like to find a way to use just the Detour data to adjust the navmesh for temporary obstacles, but I think this test has been worth the effort so far.