Friday, August 2, 2013

Voxel Collision Heightmap

One of the unexpectedly challenging aspects of getting our voxel systems integrated fully into the engine is achieving stable and efficient collision detection and response, and decent vehicle behaviour when driving over portions of the world implemented using voxels.

Currently, the voxel system collision detection system I have in place works correctly. However, if you dig deep enough into a large voxel volume so that much of it has been eaten away, the optimization steps I can take to keep the number of intersections against individual voxels lessens. To put it another way, when you’ve dug into the voxel system sufficiently, the voxel data has been expanded a lot and so many calculations need to be performed. In my stress testing I had a vehicle driving through a large voxel tunnel where most of it had been dug away, with all of the vehicle collisions volumes / lines enabled (there are a lot). I encountered two problems.

The first problem was that the performance dropped significantly, to the point where I started to become very concerned about where to go next. However, I gave it some thought and have some solutions planned (and partially implemented). I am optimistic about these, and will elaborate further in a moment.

The second problem I had was that if we had pursued the more simplistic method I had in mind initially, the wheels would be moving over a relatively blocky surface when you’re digging up or down an incline (which we do need to do). This would give erratic behaviour, and we’d need to find a solution to this. Smoothing it out by using a greater number of smaller voxels helps the dynamics behaviour but would compound performance difficulties. This got me to thinking that converting the 'ground layer' of the voxel system into a collision heightmap that you drive on top of would be a better alternative.

What I mean by this is that when performing wheel collisions tests I sample a collision heightmap instead. This heightmap is constructed using the voxel data (it essentially reduces a 3D problem to a 2D problem so as to improve vehicle driving behaviour).

I have been hacking away and have a significant portion of the collision heightmap code implemented, though it is still a work-in-progress and so more work will need to be done before it is useable (I'm estimating a day or two). A benefit of this is that I can eliminate sharp jumps in height (i.e. the surface beneath the wheels will appear to the dynamics to be smooth rather than blocky).

I will achieve this via interpolation. So, for example, if you sample the collision heightmap beneath the wheel, I will also sample surrounding height values and filter the results. I have recently implemented exactly the same functionality in the D3D11-based engine / demo I have been working on at home (see previous blog entries), and so I can just bring in and re-use that code, which has been honed and works well. Basically it makes use of hand-coded bilinear interpolation.

Note that this technique makes certain assumptions about the intended usage of the sim -- it assumes a single 'layer' of empty space. You couldn't, for example, construct a bridge out of voxels with this feature enabled and expect it to behave as expected. But for our current purposes the limiting assumption holds true, and so this is not a concern.

To summarize, using a collision heightmap will give smooth, stable behaviour when driving over a surface or tunnel represented by voxels, and will also yield performance benefits.

Here is a screenshot of some debug lines used to visualize a small portion of the underlying heightmap data. It is difficult to see from this picture (perhaps I should use tiny boxes instead to show heights), but these lines extend from the base of the heightmap to the first section of empty space directly above them.