Prior Work

Many researchers, from many domains, have addressed the problem of collision detection. Following Lin and Gottschalk in [#!linSurvey!#], we separate out two main areas of work: $n$-body collision detection, the ``broad phase'' which determines which pairs among $n$ objects may intersect; and pairwise collision detection, the ``narrow phase'' which decides whether a single pair of objects collide. Any $n$-body algorithm depends on a pairwise algorithm to perform the final tests.

Finally, although the two problems are distinct, the common and literature usage of the term ``collision detection'' can refer to work in either $n$-body or pairwise detection. The voxel method, whose presentation forms the bulk of this work, addresses the $n$-body problem.