Sweep-and-Prune
Divide and Conquer for Collision Detection
(Monday, July 1, 2002)

Introduction

In collision detection, we want to do as little work as possible while maintaining a physically-consistent environment. ... The sweep-and-prune method relies on a special case of the Separating Axis Theorem. ...

A Hypothetical Broad-Phase

Ideally, we would use some imaginary perfect broad-phase algorithm which gives us the exact set of colliding pairs of objects in O(n) time (where n is the number of colliding pairs). Then the narrow-phase would extract the necessary fine-grain collision information. Thus, no non-colliding pairs (false-positives) would fall through the broad-phase.

In practice, a broad-phase algorithm will return false-positives that serve to waste cycles in the narrow-phase. Our objective is to cull as many pairs from the set of n(n-1)/2 possible colliding pairs of rigid bodies as possible.

The important aspects of sweep-and-prune are:

Spatial coherence: (ignore far-away objects...)
Temporal coherence: (faster sorting...)

Implementation

There are two approaches to ... One is complex but has good worst-case behavior, and the other is simple but has bad worst-case behavior.

Spatial Hashing Approach

Mirtich [1] discusses the use of a hierarchical spatial hash table. ... Scheduling algorithm ... ...

The disadvantage of spatial hashing is the complexity of implementation, as compared to the simplicity of implementing the coordinate sorting approach.

Coordinate Sorting Approach

... Construct start & end lists, formed from swept volumes of sphere motions ... Sort each with O(n) radix sort, (show state diagram), ... ... Maintain list of active spheres, ... ...

The coordinate sorting approach has the disadvantage of worst-case O(n²) behavior if all the objects are highly clustered along one of the sorting axes (see Figure 6 in Mirtich's paper [1]). To see why this is bad, imagine the size of the active list when sorting along an axis with highly-clustered bounds. For this reason, the spatial hashing approach is more desirable for its worst-case behavior. However, as pointed out my Mirtich [1], no spatial hashing scheme can cull as many pairs as coordinate sorting.

There are many issues to consider when choosing which approach to use:

Will you need to reset the hash/sorting structures often (to accomodate rapidly-varying simulation extents)?
What is the ratio between the largest & smallest objects in your system?
Can you guarantee that the coordinate sorting worst-case scenario won't occur?

References

Mirtich, Brian. Efficient Algorithms for Two-Phase Collision Detection.
Describes a broad-phase comprising AABBs and hiearchical spatial hashing and a narrow-phase using Lin-Canny. Also presents alternatives to these methods. ...Hierarchical spatial hashing is an alternative to sweep-and-prune...
Terdiman, Pierre. Radix Sort Revisited.
Describes floating-point radix sort and applications to sweep-and-prune.
Herf, Michael. Radix Tricks.
Even better than Pierre's method.