$n$-body collision detection

Given an algorithm to determine if a given pair of objects collide, the obvious way to determine which of $n$ objects collide is simply to try all $\binom{n}{2}$ possible pairs. Because $\binom{n}{2}=O(n^2)$, this approach requires $O(n^2)$ pair tests.

In fact, any correct $n$-body collision detection algorithm has a worst-case time in $O(n^2)$. This is because it is possible to arrange $n$ objects (see Figure ) so that every object collides with every other object, for $O(n^2)$ separate collisions.

Figure: $n$ line segments arranged to have $\binom{n}{2}$ collisions

However, because physical objects cannot pass though one another, nearly any plausible physical situation actually has at most $O(n)$ collisions, as in Figure (a). Many situations found in practice have as few as $O(1)$ collisions, as shown in Figure (b).

Figure: $n$ circles; (a) with $O(n)$ collisions; (b) with $O(1)$ collisions

Since these rare-collision cases are common, it is quite often possible to do collision detection in faster than $O(n^2)$ time. There are several ways to do this, each with their own advantages. For rigid objects with bounded velocities and accelerations, the collision scheduling method of [#!Lin93!#] can be effective.

Most other $n$-body approaches use some sort of bounding volume. Bounding volumes, although shown quite effective in practice, are subject to rather unlikely worst cases, such as the nested `L' shapes shown in Figure . Suri, Hubbard, and Hughes [#!SHH99!#] show that if the object aspect ratio and ``scale factor''^1.3 are bounded, then bounding boxes introduce no more than a linear amount of overhead. Zhou and Suri [#!ZS99!#] extend this result to include bounded average aspect ratio and scale factor. These theoretical results confirm the practical effectiveness of bounding boxes.

Figure: $n$ nested `L' figures do not collide, but every bounding box intersects every other bounding box.

The two major approaches to $n$-body collision detection [#!JTT98!#] are object subdivision, where we divide up objects into parts that cannot intersect; and spatial subdivision, where we divide up space to separate objects that cannot intersect.