Sweep and prune

Deep dive

How it works

In: boxes (min and max per axis) and last step's sorted order · Out: candidate overlapping pairs, or begin/end events in the incremental form · State: the sorted order (or endpoint arrays and a pair set) · Cost: O(n + s + k_x) per step, cold start O(n log n)

Sort and sweep (one axis, rebuilt pair list each frame)

1. Keep a persistent array order of box ids sorted by min[axis].
2. Each frame, re-sort with insertion sort; with small motions each element moves a few slots.
3. Sweep in order. For box b: remove active boxes whose max[axis] < b.min[axis]; test b against the rest on all axes; add b to the active list.
4. Choose next frame's axis by the largest variance of box centers.

Incremental sweep and prune (3 axes, persistent pairs)

1. Keep, per axis, a sorted array of endpoints (value, box_id, is_min).
2. Insertion-sort each axis. Whenever a min endpoint of A passes a max endpoint of B (or vice versa), the two intervals start or stop overlapping on that axis.
3. On "start overlap", test the other two axes; if they overlap too, add the pair. On "stop overlap", remove the pair if present.
4. The pair set is persistent: the narrowphase gets begin/end events instead of rebuilding.

axis x:  A[-----]      C[--]
            B[------]        D[---]
sweep:   A  → active {A}
         B  → test A, active {A,B}
         A ends, C → test B, active {B,C}
         B ends, C ends, D → active {D}

Code

#[derive(Clone, Copy)]
pub struct Aabb { pub min: [f32; 3], pub max: [f32; 3] }

fn overlap(a: &Aabb, b: &Aabb) -> bool {
    (0..3).all(|k| a.min[k] <= b.max[k] && b.min[k] <= a.max[k])
}

/// Single-axis sweep and prune with a persistent order.
/// `order` survives between frames, so insertion sort does O(n + swaps) work.
pub struct Sap { pub axis: usize, order: Vec<u32>, active: Vec<u32> }

impl Sap {
    pub fn new(n: usize) -> Self { Sap { axis: 0, order: (0..n as u32).collect(), active: Vec::new() } }

    /// Insertion sort by min on the sweep axis: near-linear when the
    /// order barely changed since last frame (temporal coherence).
    fn sort(&mut self, boxes: &[Aabb]) {
        let ax = self.axis;
        for i in 1..self.order.len() {
            let id = self.order[i];
            let key = boxes[id as usize].min[ax];
            let mut j = i;
            while j > 0 && boxes[self.order[j - 1] as usize].min[ax] > key {
                self.order[j] = self.order[j - 1];
                j -= 1;
            }
            self.order[j] = id;
        }
    }

    pub fn pairs(&mut self, boxes: &[Aabb], out: &mut Vec<(u32, u32)>) {
        self.sort(boxes);
        let ax = self.axis;
        self.active.clear();
        let mut mean = [0.0f32; 3];
        let mut sq = [0.0f32; 3];
        for &id in &self.order {
            let b = &boxes[id as usize];
            // drop intervals that ended before this one starts (swap_remove: order irrelevant)
            let mut k = 0;
            while k < self.active.len() {
                if boxes[self.active[k] as usize].max[ax] < b.min[ax] { self.active.swap_remove(k); }
                else {
                    let other = self.active[k];
                    if overlap(b, &boxes[other as usize]) { out.push((other.min(id), other.max(id))); }
                    k += 1;
                }
            }
            self.active.push(id);
            for a in 0..3 { // centroid variance per axis, for next frame's axis choice
                let c = 0.5 * (b.min[a] + b.max[a]);
                mean[a] += c; sq[a] += c * c;
            }
        }
        let n = boxes.len().max(1) as f32;
        let var = |a: usize| sq[a] / n - (mean[a] / n) * (mean[a] / n);
        // Sweep along the axis with the largest spread: fewest false overlaps.
        // Switching axis makes next frame's insertion sort expensive once.
        self.axis = (0..3).max_by(|&a, &b| var(a).total_cmp(&var(b))).unwrap();
    }
}

Complexity and constants

• Sort: O(n + s), s = number of inversions since last frame. Cold start or axis switch: insertion sort is O(n²) in the worst case, so use sort_unstable_by (O(n log n)) or a radix sort on float keys when s would be large.
• Sweep: O(n + k_x), k_x = pairs overlapping on the sweep axis. k_x / k (axis overlaps per true pair) is the efficiency number to watch; for objects spread in 3D it is small, for objects on a plane swept along the plane's normal it approaches n²/k.
• Memory: 4 bytes per id plus the boxes; the incremental 3-axis version stores 6 endpoints per box plus a pair hash set.
• Branch-predictable linear scans; sorting moves 4-byte ids, so keep the box array hot or copy (min, max, id) into a contiguous sweep array.

Efficiency

• Cost: a step is one near-sorted insertion pass (each element moves a few slots) and one sweep: sequential reads of 4-byte ids or a contiguous (min, max, id) array, branch-predictable. The bound is memory bandwidth plus the axis overlaps k_x that the other axes must reject.
• Levers:
  • insertion sort on last step's order — near-linear under small motion (this page) — coherent scenes
  • sweep array of (min, max, id) — sequential memory in the inner loop — always
  • 16- or 32-bit integer endpoints — exact, cheap compares (Bullet btAxisSweep3) — bounded worlds
  • radix sort on float keys — linear cold start or after teleports — loads, mass moves
  • sweep axis from the covariance of box centres — maximises spread, fewer k_x (MuJoCo, docs) — non-isotropic scenes
• Naive → standard → state of the art:
  • test all pairs · O(n²)
  • sort and sweep one axis with insertion sort · O(n + s + k_x)
  • incremental 3-axis SAP (events only) or multi-SAP regions (PhysX MBP) · cost follows the change, bounded worst case

Implementation notes

• Sweep array layout: copy (min_x, max_x, id) into one array in sorted order before the sweep; the inner loop then reads sequential memory instead of jumping through ids.
• Quantised endpoints: integer endpoints (16- or 32-bit) relative to world bounds make comparisons exact and cheap; Bullet's btAxisSweep3 (16-bit) and bt32BitAxisSweep3 do this.
• Radix sort on floats: flip the sign bit for positives, all bits for negatives, then sort as u32; linear time for cold starts.
• Region splitting (multi-SAP, PhysX's MBP): partition the world into regions, run SAP per region, dedupe pairs that straddle borders. Bounds the cost of a single long axis.
• Static objects: keep them in a separate list; test only dynamic-vs-dynamic and dynamic-vs-static, never static-vs-static.
• Parallelism: the one-axis sweep is sequential, but it can be split into slabs along the axis with overlap handling, or replaced by a parallel radix sort plus per-thread sweeps over subranges.

Pitfalls

• Insertion sort after a teleport or level load: O(n²) stall. Detect large moves or count swaps and fall back to a full sort.
• Using < in one comparison and <= in another: touching boxes flicker in and out of the pair list. Pick one convention everywhere.
• Sweep axis aligned with gravity in a game with a flat ground plane: almost every object overlaps every other on that axis.
• Removing from the active list with Vec::remove (O(n) shift) instead of swap_remove.
• NaN coordinates break the sort's strict weak ordering; partial_cmp().unwrap() panics, plain > silently corrupts the order.

Variants and alternatives

In production

Games, VR and effects: Bullet (btAxisSweep3, bt32BitAxisSweep3), PhysX (PxBroadPhaseType::eSAP, plus the region-based MBP and automatic ABP variants), I-COLLIDE. Robotics: MuJoCo's broad phase is a modified sweep and prune that sorts along the principal axis of the geom centres (docs).

Implementations

Sources

• David Baraff, Dynamic Simulation of Non-Penetrating Rigid Bodies, PhD thesis, Cornell University, 1992.
• Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, Madhav K. Ponamgi, I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments, I3D 1995. paper
• Christer Ericson, Real-Time Collision Detection, Morgan Kaufmann, 2005 (ch. 7, spatial partitioning).
• Pierre Terdiman, Sweep-and-prune, technical note (codercorner.com), 2007.
• MuJoCo documentation, Computation: collision detection. docs