The Voxel Method

The $n$-body, spatial subdivision approach we examine in the remainder of this work is the voxel method. A regular, axis-aligned^2.1 grid of voxels is imposed over the problem domain. Each object is added to all the voxels it touches, and the voxels are then collided independently. Any collision detection subscheme may be used to detect collisions within a voxel, from the simple all-pairs test to a recursive application of the voxel method on a smaller domain.

The voxel method was first described by Turk [#!Turk89!#] for molecules, but his approach hashed the grid locations into buckets, ignoring hash collisions, and used the naive all-pairs algorithm on each bucket. Zyda et al. [#!Zyda93!#] describe the NPSNET system, which tests for vehicle/vehicle and vehicle/terrain collision using a parallel 2D grid structure quite similar to the voxel method. Zyda also uses the naive all-pairs approach within each grid cell.

When the objects to be collided are of nearly uniform size, the voxel method is ideal and gives excellent results. For objects much smaller than a voxel, the division into voxels does not help much, and the voxel method degenerates to the subscheme used within a voxel.

Objects much larger than a voxel will be duplicated across many voxels, as shown in Figure . In this case, a careful implementation can avoid duplicating collision tests across voxels by using a convention to decide which voxel is responsible for testing these shared objects. For example, only the voxel that contains the midpoint between the object centers need test the objects for collision. Even with this optimization, however, large objects still waste space and time.

Figure: Large objects may span several voxels

Voxels should be implemented as a sparse grid, via a hash table in most cases. Sparseness is especially important if the problem domain is not naturally bounded, objects are distributed in a nonuniform fashion, or if memory usage is important. A sparse grid can also improve efficiency, because empty cells are automatically ignored.

Although normally implemented in 3D, gridding works well with any number of dimensions. High-dimension problems may consume large quantities of memory, however. The common timestep ``sweeping'' approach illustrated in Figure  can be seen as a kind of gridding along the time axis of spacetime.

Figure: Sweeping objects between timesteps corresponds to a coarse timestep grid in 4D

The voxel approach is easiest to implement via the sloppy strategy of adding each object to all the voxels touched by the object bounding box^2.2. For elongated objects, whose bounding box does not fit well, this can be wasteful; the 3D digital differential analyzer approach of [#!Bandi95!#] could improve performance.

However, since most objects should fit inside a single voxel, gridding only the bounding box normally works well. The fast gridding method described in Appendix  is ideal for this case.