Fact-checked by Grok 2 weeks ago

Sweep and prune

Sweep and prune (SAP), also known as sort and sweep, is a broad-phase collision detection algorithm employed in computer graphics, physics simulations, and virtual reality applications to efficiently identify potential intersecting pairs among a set of objects by projecting their axis-aligned bounding boxes (AABBs) onto spatial axes and eliminating non-overlapping candidates.^[1]^[2] The method reduces the naive O(N²) complexity of pairwise intersection tests—where N is the number of objects—by leveraging spatial and temporal coherence to prune irrelevant pairs, typically achieving near-linear performance in practice for dynamic scenes.^[2] The algorithm operates in two main phases: a preliminary step that computes AABBs for all collision models in the scene, followed by a sweeping process that sorts the projected intervals along each principal axis (x, y, z).^[1] Overlaps are detected by scanning the sorted lists to find adjacent intervals that intersect; pairs overlapping in all three dimensions are flagged as potential colliders for subsequent narrow-phase verification using more precise geometric tests.^[2] This axis-by-axis decomposition simplifies 3D detection into manageable 1D problems, with sorting often optimized via insertion methods that exploit frame-to-frame object motion for O(N) updates rather than full O(N log N) resorts.^[2] SAP has been enhanced for large-scale and dynamic environments, incorporating structures like segmented interval lists to support efficient AABB insertion, removal, and batch operations without resorting the entire dataset, making it suitable for simulations with thousands of objects including many static ones.^[3] These improvements address challenges in virtual reality and real-time applications, outperforming alternatives like octrees in temporally coherent scenarios while maintaining low memory overhead.^[3]

Overview

Definition and purpose

Sweep and prune (SaP), also known as sort and sweep, is a broad-phase collision detection algorithm designed to efficiently identify potential overlapping pairs among a set of moving or static objects in three-dimensional space. It achieves this by projecting the axis-aligned bounding boxes (AABBs) of objects onto the principal coordinate axes (x, y, z), sorting the resulting one-dimensional intervals, and then pruning pairs that do not overlap on at least one axis. This method leverages both geometric and temporal coherence—assuming objects move continuously and do not change drastically between frames—to maintain sorted lists incrementally, avoiding full resorting in each timestep.^[4] The primary purpose of sweep and prune is to reduce the computational complexity of collision detection from the naive O(n²) pairwise checks, where n is the number of objects, to approximately O(n + k) time, with k representing the number of potential colliding pairs (typically much smaller than n² in sparse scenes). By filtering out distant object pairs early, it enables subsequent narrow-phase exact collision tests (e.g., using separating axis theorems or feature-based methods) to focus only on promising candidates, making it suitable for real-time applications such as computer graphics, video games, robotics simulations, and virtual reality environments. This pruning step is particularly effective in dynamic scenes with hundreds to thousands of objects, where full pairwise evaluation becomes prohibitive.^[5]^[6] Introduced in the context of interactive multi-body simulations, sweep and prune addresses the bottleneck in large-scale environments by exploiting the low dimensionality of projections while preserving accuracy for AABB-based approximations. Early implementations demonstrated interactive rates, processing over 1,000 complex polytopes in under 1/20 of a second on mid-1990s hardware, highlighting its scalability for architectural walkthroughs and deformable object interactions. Modern variants continue to build on this foundation, adapting it for parallel processing and higher dimensions, but the core algorithm remains a staple for its simplicity and robustness in broad-phase culling.^[4]^[5]

Algorithm fundamentals

Sorting phase

The sorting phase of the sweep and prune algorithm begins by projecting the axis-aligned bounding boxes (AABBs) of all objects onto each of the coordinate axes—typically x, y, and z in three-dimensional space—to reduce the problem to one-dimensional interval overlaps. For each object, this projection yields two endpoints per axis: the minimum and maximum coordinates of the AABB along that axis, representing the start and end of an interval. These endpoints are then collected into separate lists, one for each dimension, where each entry is tagged with the corresponding object identifier to track ownership.^[5] The core operation in this phase is sorting these endpoint lists to establish a linear order of the projections. The algorithm sorts the endpoints in ascending order, distinguishing between minimum (left) and maximum (right) endpoints, often by using flags or separate structures to differentiate them. This sorting enables efficient identification of overlapping intervals by "sweeping" a plane through the sorted list, as adjacent overlapping projections indicate potential collisions in that dimension. In the original formulation, an insertion sort is employed, which exploits temporal coherence in dynamic scenes—where object positions change incrementally between frames—to achieve expected O(n average-case performance for n objects, rather than the O(n log n) of full sorts like quicksort.^[5] To handle multiple dimensions, the sorting is performed independently on each axis's list, creating three sorted arrays. Overlaps are only considered for object pairs whose projections overlap in all dimensions simultaneously, which filters out non-intersecting pairs early. This phase must be repeated or updated each simulation step to account for object motion, with optimizations like lazy resorting (only swapping adjacent misordered endpoints) preserving efficiency in coherent animations. Subsequent work has refined this by using priority queues or binary search trees for endpoint management, but the foundational projection-and-sort mechanism remains central to scalability in large-scale environments.^[7]

Pruning phase

The pruning phase of the sweep and prune algorithm identifies potential colliding pairs of objects by detecting overlaps in their axis-aligned bounding boxes (AABBs) after the sorting phase has ordered the projections along each coordinate axis. This phase exploits the sorted lists of interval endpoints (minima and maxima) for each dimension—typically x, y, and z—to efficiently prune non-overlapping pairs, reducing the computational load for subsequent narrow-phase collision tests. Two AABBs are considered potentially colliding only if their projections overlap on all three axes; otherwise, they are discarded. This dimension-reduction approach ensures that the algorithm avoids exhaustive pairwise checks, achieving near-linear time complexity in practice for coherent scenes.^[4] In detail, the process maintains a set of active pairs—those whose bounding boxes overlap in all dimensions—along with boolean flags indicating overlap status per dimension for relevant object pairs. Overlap detection is integrated with the sorting updates: during the insertion sort on each axis's endpoint list, when two adjacent endpoints are swapped (due to object motion), the algorithm re-evaluates the overlap status on that axis for the two objects owning those endpoints and toggles the corresponding flag if necessary. A pair is added to the active set if all three flags become true (overlaps on x, y, and z), and removed if any flag turns false. This local, incremental approach leverages temporal coherence, avoiding full re-computation each frame. The resulting active pairs are forwarded to exact collision detection.^[4]^[1] Implementations often optimize this phase by using insertion sort during updates for O(n) expected performance when object motions are small, and by employing pair managers to avoid redundant checks. For instance, in large-scale environments, box-pruning variants may supplement the sweep with brute-force overlap tests on reduced candidate sets to handle insertions and removals efficiently. This phase's effectiveness stems from its simplicity and adaptability, making it suitable for real-time applications like rigid body dynamics, where it can prune over 90% of potential pairs in clustered scenarios.^[8]^[3]

Implementation

Data structures

The sweep and prune algorithm relies on axis-aligned bounding boxes (AABBs) to represent the spatial extents of objects for collision detection. Each AABB is defined by six scalar values: the minimum and maximum coordinates along the x, y, and z axes, which bound the object's geometry conservatively. These coordinates are typically stored in a simple structure or array per object, allowing quick projection onto individual axes to form one-dimensional intervals [min, max]. This representation exploits the alignment with coordinate axes to simplify overlap tests, with updates to the AABBs performed incrementally as objects move or deform, recomputing extrema from vertices or using fixed-size approximations like bounding cubes for further efficiency.^[5] To enable the sorting and sweeping operations, the algorithm maintains three independent sorted lists—one for each axis—comprising projections of all n objects' AABBs. In the basic formulation, each list is a sorted array of 2n endpoints: the minimum and maximum coordinates along the respective axis for each object, with each endpoint including the scalar value, a reference or index to the owning object, and a flag distinguishing min from max. These endpoints are stored in arrays for cache-friendly access, with initial sorting in O(n log n) time via radix or merge sort, and maintenance via insertion sort that exploits frame-to-frame coherence for O(n) expected update time. Overlaps are detected by sweeping the sorted endpoint list: traversing from low to high while maintaining an active set of objects whose intervals contain the current position (adding an object on its min endpoint and removing on max), and identifying overlapping pairs by testing the new object against the active set upon encountering a min endpoint.^[5]^[9] For dynamic scenes requiring frequent insertions, deletions, or updates, advanced implementations augment the endpoint lists with hierarchical or segmented structures, such as node-based interval trees per axis, to avoid full resorting. Each node in these structures references minima and maxima, enabling localized adjustments while preserving overall sort order. An auxiliary active pair set, often implemented as a hash table or list, stores object pairs that overlap on all three axes, passing them to narrow-phase detection. These designs balance memory usage (typically O(n space) with query efficiency, scaling to thousands of objects in real-time simulations.^[3]

Updating and maintenance

In dynamic simulations where objects move, deform, or are added and removed, the sweep and prune algorithm requires efficient mechanisms to update its sorted lists of axis-aligned bounding box (AABB) endpoints without resorting the entire dataset each frame, which would be computationally expensive at O(n log n) per update for n objects. Instead, persistent variants exploit temporal coherence by performing local adjustments: when an object's AABB changes position, its min and max endpoints are updated along each axis, and the affected entries are reinserted into the sorted list using insertion sort or by swapping with adjacent elements until the correct order is restored. This incremental approach typically costs O(k) time per object, where k is the number of swaps needed, often small due to limited motion between frames.^[10] For insertion of a new object, the algorithm computes its AABB projections on all axes and inserts the six endpoints (min and max per axis) into the respective sorted lists using binary search to find the position followed by a shift or swap operation, achieving O(log n + m) time where m is the list length affected by the shift. Removal is analogous: locate the endpoints via object references and delete them, shifting remaining elements, also in O(log n + m) time. To handle large-scale scenes with frequent updates, segmented interval lists divide the sorted arrays into fixed-size blocks or a hierarchy, allowing localized updates within segments and reducing global shifts; this structure supports batch processing of multiple insertions or removals, minimizing overhead in environments with many dynamic objects.^[3] Maintenance also involves periodic full resorts to correct accumulated errors from lazy updates, especially if motion is erratic, and pruning stale overlap pairs from the candidate set after each sweep to prevent growth. In adaptive implementations, the update strategy switches dynamically based on object count and motion patterns—for instance, favoring segmented lists for mostly static scenes and batch resorts for high-dynamics—ensuring scalability across CPU or GPU architectures with reported speedups of 5-6x on multi-core systems. These techniques maintain the algorithm's O(n log n + p) overall complexity per frame, where p is the number of potential pairs, while supporting real-time performance in simulations with thousands of objects.^[11]

Variants and extensions

Dimensional adaptations

The sweep and prune algorithm, originally formulated for detecting interval overlaps in one dimension, adapts to higher dimensions by independently projecting axis-aligned bounding volumes onto each coordinate axis and performing overlap tests across all projections. In two dimensions, objects are represented by axis-aligned bounding rectangles, with endpoints sorted along the x- and y-axes separately; potential collisions are identified only for pairs whose projections overlap on both axes, reducing the number of exact intersection tests from O(n²) to O(n log n + k), where n is the number of objects and k is the number of overlapping pairs. This approach leverages the separating axis theorem, ensuring that non-overlapping projections on any single axis prune impossible collisions efficiently.^[12] In three dimensions, the method extends naturally to axis-aligned bounding boxes (AABBs) by projecting onto the x-, y-, and z-axes, maintaining sorted lists for each and updating them incrementally to exploit temporal coherence between simulation steps. Overlaps are reported only if intervals intersect on all three axes, further culling candidates before narrow-phase checks; this is the standard adaptation in real-time graphics and physics simulations, achieving near-linear performance O(n + c) per frame under high coherence, where c is the number of endpoint swaps. The I-COLLIDE system exemplifies this in large-scale 3D environments with thousands of moving polytopes, processing over 1,000 objects in under 1/20 of a second on 1990s hardware by using insertion sort on projections.^[5]^[12] While the algorithm generalizes to d dimensions by sorting projections along each of d axes and requiring overlaps on all to flag candidates, its use beyond three dimensions is uncommon due to increasing overhead from additional sorts and the rarity of high-dimensional collision detection in practical applications like virtual reality or robotics. In such cases, the time complexity approaches O(d n log n + k), with pruning effectiveness improving as d grows—since more axes provide opportunities for separation—but at the cost of higher memory and computation per object. Seminal formulations emphasize its scalability in 2D and 3D, where it balances simplicity and efficiency without assuming object motion constraints.^[12]

Parallel and optimized versions

Parallel versions of the sweep and prune algorithm address scalability challenges in large-scale simulations by leveraging multi-core CPUs and GPUs, enabling efficient broad-phase collision detection for millions of objects.^[13] These implementations typically parallelize the sorting and pruning phases while incorporating optimizations to handle object clustering and temporal coherence.^[14] A key multi-core CPU approach divides the algorithm into three parallel stages: sorting endpoints with radix sort exploiting temporal coherence for load balancing, generating candidate pairs via dual-axis sweeping using a cache-friendly SuccTree data structure, and performing object pairing through adaptive partitioning that distributes long intervals across threads.^[13] To optimize for three-dimensional dynamic box intersections, this method dynamically selects the primary sweeping axis based on a dispersion measure, reducing bottlenecks in clustered scenarios.^[13] On 16-core systems, it achieves up to 16x speedup and processes 1 million objects in 122–167 ms, depending on density, outperforming prior CPU methods and rivaling early GPU implementations.^[13] For GPU acceleration, a CUDA-based variant integrates parallel sweep and prune into continuous collision detection pipelines, using radix sort to identify potential colliding sets from sorted endpoint lists across axes, combined with spatial decomposition for workload distribution across GPU clusters via MPI.^[15] Optimizations include stream-based processing of bounding volumes and dynamic load balancing by transferring cells between nodes, enabling real-time culling for 100,000 entities in 300 ms on four GPU nodes, with a 2.6x speedup over single-node GPU setups.^[15] Earlier parallel adaptations, such as a 2010 implementation on the Cell Broadband Engine, parallelize endpoint sorting across three synergistic processing elements using vectorized SIMD insertion sorts that exploit temporal coherence, alongside a hash-based pair manager for efficient overlap tracking.^[16] This yields superior initial sorting performance over x86 equivalents for 512–1024 objects but incurs overheads in dynamic scenes with 10% moving objects, limiting interactive rates.^[16] Additional optimizations across platforms emphasize succinct bi-dimensional representations to reduce memory usage in pruning and context-aware axis processing for runtime efficiency, as seen in hybrid multi-core and multi-GPU frameworks that achieve 5.1x speedup on eight cores and 4.2x on a single GPU for 20,000 cubes through OpenMP threading and sequential axis handling.^[17]^[14]

Applications and performance

Use in collision detection

Sweep and prune serves as a broad-phase collision detection algorithm, primarily used to efficiently cull non-intersecting object pairs in dynamic environments before performing more computationally expensive narrow-phase tests. By projecting axis-aligned bounding boxes (AABBs) of objects onto the principal axes (x, y, z) and sorting these projections, the algorithm identifies potential overlaps by sweeping through the sorted lists and pruning pairs that do not overlap in all dimensions. This approach reduces the complexity from O(n²) pairwise checks to O(n + k), where n is the number of objects and k is the number of potential colliding pairs, making it suitable for real-time applications such as video games and simulations.^[5] In the seminal I-COLLIDE system, sweep and prune is integrated as the initial filtering stage for interactive collision detection among hundreds to thousands of moving polytopes. The algorithm exploits temporal coherence by using insertion sort on the axis projections, which maintains order efficiently when objects move incrementally between frames, achieving near-linear scaling. For instance, in benchmarks on an HP-9000/750 workstation, it processed over 1000 polytopes at interactive rates of up to 23 frames per second, trimming interactions to a manageable subset for exact narrow-phase detection using hierarchical bounding volumes. This framework demonstrates its robustness in handling dense scenes without assumptions on object velocities or accelerations.^[5] Modern physics engines and simulation frameworks widely adopt sweep and prune variants for broad-phase culling. In Bullet Physics, the btAxisSweep3 implementation uses array-based storage for 3D axis projections to detect overlaps among rigid bodies, supporting dynamic worlds with insertion and removal of objects. It is particularly effective for scenarios with moderately sized scenes, such as games, where it prunes pairs before GJK-based narrow-phase checks. Similarly, the SOFA framework employs DirectSAP, a sweep and prune method that sorts primitives along axes using AABBs, allocating memory once for efficiency in multi-body simulations like soft tissue deformation. These implementations highlight its adaptability to both rigid and deformable object collision detection in real-time systems.^[18]^[1] The algorithm's strengths in collision detection lie in its simplicity and low memory footprint, requiring only sorted lists per axis, which enables easy parallelization and integration with other spatial structures. However, its effectiveness depends on object distribution; in highly clustered scenes, the number of reported pairs can approach O(n²), necessitating hybrid approaches with grids or trees for very large-scale environments. Despite this, sweep and prune remains a foundational technique due to its proven performance in interactive applications.^[5]

Advantages and limitations

Sweep and prune (SaP) offers several advantages in broad-phase collision detection, particularly in dynamic environments. Its time complexity is typically O(n + k), where n is the number of objects and k is the number of overlapping pairs, making it output-sensitive and more efficient than brute-force O(n²) methods for sparse scenes.^[19] The algorithm exploits both spatial coherence, by projecting axis-aligned bounding boxes (AABBs) onto principal axes to quickly reject non-overlapping pairs, and temporal coherence, through incremental updates that minimize resorting when objects move slightly between frames.^[3] This results in significant reductions in pairwise tests, enabling interactive rates such as 23 frames per second for 1,000 polytopes in rigid-body simulations.^[20] Despite these strengths, SaP has notable limitations, especially in scalability for large-scale applications. In environments with many objects, frequent endpoint swaps during incremental sorting can lead to super-linear performance degradation, approaching O(n^{2-1/k}) where k is the number of axes, due to dense interval lists dominating runtime.^[3] Insertion and removal of objects are inefficient without optimizations, requiring O(n) time for resorting, which hampers dynamic scenes with high turnover.^[3] Additionally, the reliance on conservative AABBs can generate excessive false positives in dense or high-velocity scenarios, where overlaps occur in all projections but not in 3D space, and performance drops to near-quadratic in worst-case stacked configurations.^[21]^[20] SaP is less suitable for static scenes or non-coherent queries like path planning, where spatial partitioning methods like grids or trees outperform it.^[21]^[19]

References

[1]
Detection Sweep and Prune - SOFA Documentation
In this section, we describe the two collision detection methods based on the "Sweep and Prune" algorithm, noted SAP.
[2]
Sweep and Prune
Given a number N of objects, O(N2) object pairs have to be checked for collision. In general, the objects in most of the pairs aren't even close to each other ...
[3]
(PDF) Efficient Large-Scale Sweep and Prune Methods with AABB ...
Collision detection is often split into two phases: a broad-phase, which formulates a potential collision list for each particle (neighbor list), and a narrow- ...
[4]
[PDF] Interactive and Exact Collision Detection for Multi-Body ... - GAMMA
This paper focuses on collision detection for ... tation details of the Sweep and Prune algorithm, the exact collision detection algorithm, ... First ...
[5]
[PDF] An Interactive and Exact Collision Detection System for Large-Scale ...
We present an exact and interactive collision detection system, I-COLLIDE, for large-scale environments. Such environments are characterized by the number ...
[6]
[PDF] Collision Detection: Algorithms and Applications - GAMMA
The I COLLIDE routines are able to compute all contacts between environments composed of hun- dred of convex polytopes at interactive rates (about. 1=20 of a ...
[7]
[PDF] Rigid Body Simulation II—Nonpenetration Constraints
The problem can be solved initially by a sort and sweep algorithm. A sorted list of all the bi and ei values is created, from lowest to highest. The list is ...
[8]
[PDF] Efficient Large-Scale Sweep and Prune Methods with AABB ...
An improved variant of the broad phase collision-detection algorithm called Sweep and Prune (SaP) for large datasets in three-dimensional environments that ...
[9]
[PDF] Sweep-and-prune I) Single SAP - CODER CORNER
The sweep-and-prune (SAP) [8] is a broad-phase algorithm whose goal is to determine overlapping pairs of objects in a 3D world. An object in the SAP is defined ...
[10]
Chapter 32. Broad-Phase Collision Detection with CUDA
1 Sort and Sweep. One approach to the broad phase, as mentioned, is the sort and sweep algorithm (Witkin and Baraff 1997). In this approach, the bounding ...
[11]
[PDF] Collision Detection Crash Course - GDC Vault
collision detection is something for the not-so-near future. » In game ... Re-order endpoints of moving objects. B. A. Page 77. Sweep and Prune (3/3).
[12]
[PDF] Dynamic Adaptation of Broad Phase Collision Detection Algorithms
Jan 14, 2011 · In I-COLLIDE [5] used ”Sweep and Prune”, a pseudo-dynamic object collision pruning method that reduced 3D collision detection between AABBs ...
[13]
[PDF] Rigid Body Simulation II—Nonpenetration Constraints
Please note: This document is 1997 by David Baraff. This chapter may be ... Analytical methods for dynamic simulation of non-penetrating rigid bodies.<|control11|><|separator|>
[14]
[PDF] Adaptive Collision Culling for Large-Scale Simulations by a Parallel ...
We propose a parallel Sweep and Prune algorithm that solves the dynamic box intersection problem in three di- mensions. It scales up to very large datasets, ...<|control11|><|separator|>
[15]
Adaptive Collision Culling for Massive Simulations by a Parallel and ...
Abstract—We present an improved parallel Sweep and Prune algorithm that solves the dynamic box intersection problem in three dimensions.
[16]
[PDF] Parallel Continuous Collision Detection for High-Performance GPU ...
Hence, we can use a continuous bounding volume (CBV) to bound the trajectory of the SBV during the time interval. 3.3 GPU-based Parallel Sweep and Prune. The ...
[17]
[PDF] Broadphase Collision Detection on the Cell Processor
Sep 13, 2010 · The sweep and prune algorithm is suited to generally static scenes, where only a small number of objects are moving. It does this by maintaining ...
[18]
[PDF] Collision Detection: Broad Phase Adaptation from Multi-Core ... - HAL
We focus on the first step (Broad-phase) and propose three new ways of parallelization of the well-known Sweep and Prune algorithm. We first developed a ...
[19]
Bullet Collision Detection & Physics Library: btAxisSweep3 Class ...
The btAxisSweep3 is an efficient implementation of the 3d axis sweep and prune broadphase. It uses arrays rather then lists for storage of the 3 axis.
[20]
[PDF] Collision detection between geometric models: a survey - GAMMA
It uses dynamically sized AABBs, linear sweep and prune, and geometric coher- ence to quickly reject the object pairs, that are unlikely to collide within the ...Missing: limitations | Show results with:limitations
[21]
[PDF] Collision Detection and Proximity Queries SIGGRAPH 2004 Course
The sweep and prune algorithm used to reduce the number of object pairs that need to undergo further testing will also be discussed. Instead of determining ...
[22]
[PDF] Chapter 3 Collision Detection
not used for collision detection. One adaptation of coordinate sorting that has proved quite popular is the sweep and prune method used in I-COLLIDE [28].