Sweep and prune is a broad-phase collision detection algorithm commonly employed in computer graphics, physics simulation, and real-time interactive applications such as video games. The method quickly identifies pairs of objects that may potentially intersect by exploiting the spatial coherence of moving objects, thereby reducing the number of narrow-phase collision checks required.
Algorithmic Overview
-
Axis Selection
A set of one or more orthogonal axes (typically the Cartesian x, y, and optionally z axes) is chosen for projection. -
Bounding Interval Projection
Each object in the simulation is enclosed within an axis-aligned bounding box (AABB). The minimum and maximum extents of each AABB are projected onto each selected axis, producing a list of intervals. -
Sorting (Sweep)
For each axis, the interval endpoints are sorted, usually in ascending order. Efficient incremental sorting techniques—such as insertion sort—are often used because the ordering of objects changes only slightly between successive frames. -
Overlap Detection (Prune)
As the sorted list is traversed, active intervals are maintained in a temporary data structure (e.g., a set). When the start point of an interval is encountered, the corresponding object is added to the active set; when an end point is encountered, the object is removed. Any object already present in the active set overlaps with the newly started interval on that axis, generating a candidate pair. -
Pair Reduction
Candidate pairs that overlap on all selected axes are retained for the narrow-phase collision detection stage, where precise geometric tests are performed.
Performance Characteristics
- Temporal Coherence – Because object positions typically change incrementally from frame to frame, the sorting step can be performed with near‑linear time complexity using incremental algorithms.
- Scalability – The algorithm scales well with moderate numbers of objects (hundreds to low thousands) but may become less efficient for very large scenes, where spatial partitioning methods (e.g., uniform grids, BVH, octrees) are preferred.
- Dimensional Flexibility – While originally formulated for 2‑dimensional environments, sweep and prune is readily extended to three dimensions by applying the same process to three orthogonal axes.
Historical Context and Usage
The sweep and prune technique emerged in the early 1990s as part of the development of real-time physics engines for interactive simulations. It has been incorporated into several widely used middleware libraries, including Havok Physics, NVIDIA PhysX, and the open‑source Bullet physics library. Its simplicity and effectiveness have made it a standard component of many game development pipelines.
Variations and Enhancements
- Multi‑axis Strategies – Some implementations use a primary axis for sorting, with secondary axes applied only to refine candidate sets, reducing computational overhead.
- Quantized or Integer‑Based Representations – To improve cache performance and reduce floating‑point errors, bounding intervals may be stored using fixed‑point or integer coordinate systems.
- Hybrid Approaches – Sweep and prune is often combined with spatial partitioning structures, employing the latter for densely populated regions while using sweep and prune for sparser areas.
Limitations
- The algorithm assumes that objects can be reasonably approximated by AABBs; highly elongated or rotating objects may generate excessive candidate pairs.
- In scenarios with extremely rapid or chaotic motion, the assumption of temporal coherence diminishes, potentially degrading performance.
References
- Gottschalk, S., Lin, M. C., & Manocha, D. (1996). “OBB-Tree: A Hierarchical Structure for Rapid Interference Detection.” Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’96).
- McGuire, M. (2018). “Fast and Stable Sweep And Prune for Large Scale Physics.” Journal of Computer Graphics Techniques.
See Also
- Broad-phase collision detection
- Axis-aligned bounding box (AABB)
- Spatial partitioning
- Physics engine (computing)