Sweep and Prune

Sweep and prune for AABB overlap tests:

Before two objects are tested for an exact (and usually expensive) geometric collision, simulations first run a cheap broad phase: every object is enclosed in an axis-aligned bounding box (AABB), and only pairs whose boxes overlap are passed on to narrow-phase testing. The simplest broad phase checks all ${n \choose 2} = \frac{n(n-1)}{2}$ pairs of the $n$ objects directly, an $O(n^2)$ cost that quickly becomes the bottleneck in scenes with many objects.

The sweep and prune method (also called sort and sweep) [Coh95,Eri04] avoids most of these tests by exploiting a simple 1D fact: two intervals $[a_{\min},a_{\max}]$ and $[b_{\min},b_{\max}]$ overlap if and only if $$a_{\min} \le b_{\max} \quad\text{and}\quad b_{\min} \le a_{\max}.$$ Two AABBs overlap exactly when their projections overlap on every coordinate axis (in 2D: $x$ and $y$). Sweep and prune therefore reduces the 2D/3D overlap problem to a small number of cheap 1D interval checks along one distinguished axis, and only confirms the remaining axes for the few candidates that survive.

The algorithm

1. Pick one coordinate axis, the sweep axis.
2. Sort all boxes by their lower endpoint ($\min$) along the sweep axis.
3. sweep once through the sorted list, keeping an active list:
4. remove every box from the active list whose upper endpoint ($\max$) already lies before the current box's lower endpoint — since the list is sorted, such a box cannot overlap the current box or any later box on the sweep axis, so it is pruned for good
5. every box still in the active list is now guaranteed to overlap the current box on the sweep axis, so only the remaining axis (axes, in 3D) needs to be checked to confirm a true AABB overlap
6. add the current box to the active list

The simulation on the left visualizes this directly: the arena shows the boxes moving and bouncing off the walls (overlapping boxes are highlighted in red), while the strip next to or below it shows the very same boxes sorted by their lower endpoint along the current sweep axis — i.e. exactly the intermediate data structure the algorithm sweeps through. Watch how only boxes that are neighbors in this sorted list are ever tested against each other.

Choosing the sweep axis

Pruning only helps if the active list stays short. On this axis, an active list only grows long when many box intervals are stacked on top of each other — which happens least often along the axis on which the box centers are spread out the most. The "Auto" mode in this example implements exactly this common heuristic [Eri04]: each frame it measures the extent (spread) of all box centers along $x$ and along $y$, and picks whichever axis has the larger spread as the sweep axis. Compare it with the fixed "X" or "Y" choice, in particular for a scene where the boxes are arranged mostly along one direction, to see why axis selection matters.

Complexity and properties

• Worst case is still $O(n^2)$: if all boxes overlap on the sweep axis (e.g. many long, thin boxes stacked across the whole domain), the active list never shrinks and every pair is tested anyway. Sweep and prune reduces the typical, not the worst-case, cost.
• Exploits temporal coherence: objects usually move only a little between two consecutive simulation steps, so the sort order rarely changes much from one frame to the next. Real implementations re-sort with insertion sort instead of a generic $O(n \log n)$ sort: insertion sort is slow in general but very fast (close to $O(n)$) on an already almost-sorted list, which is exactly the case here.
• Extends to 3D by adding a $z$ interval, or by running one sweep per axis and intersecting the candidate pairs (the classic 3-axis sweep and prune used e.g. in the Bullet physics engine).
• Broad phase only: an AABB overlap does not mean the actual objects touch, it only means they might — the pairs found here would normally be forwarded to an exact narrow-phase test. This mirrors the role of the uniform grid in the neighborhood search example: both quickly discard the vast majority of pairs that cannot possibly interact, using very different underlying data structures (a sorted list here, a spatial hash there).

References

• [Coh95] Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, Madhav Ponamgi. I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments. In Proceedings of the Symposium on Interactive 3D Graphics, 1995.
• [Eri04] Christer Ericson. Real-Time Collision Detection. Morgan Kaufmann, 2004.