CoreSource checked

Sweep and Prune

Reduces collision candidates by sorting bounding-box intervals along one or more axes.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Simulation
Difficulty: Intermediate
Family: Broad Phase Collision Detection
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

Sweep and prune maintains sorted interval endpoints for object bounds. Only objects whose intervals overlap on every tested axis are passed to narrow-phase collision checks.

Core Concepts

axis projectioninterval overlapsorted endpointscandidate pair

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n + k)

Worst

O(n^2)

Space

O(n)

When to Use

Use when many objects move gradually and broad-phase collision pruning is needed.
Use when axis-aligned bounding boxes are available and coherence between frames is high.

When Not to Use

Avoid when objects teleport frequently and sorting loses temporal coherence.
Avoid when bounding boxes overlap so much that pruning produces too many candidates.

What It Does

Finds collision candidates by sorting object bounds along one or more axes
Uses axis projection and interval overlap to guide the work.
Produces updated state.

Use Cases

Physics simulation
Animation
Interactive systems

Inputs

Current state
Forces or constraints
Time step

Outputs

Updated state
Constraint corrections
Collision results

Key Formulas (1)

Interval overlap

a_min ≤ b_max and b_min ≤ a_max

a_min <= b_max and b_min <= a_max

Tests whether two projected bounds overlap on one axis.

Pseudocode

1.Compute bounding intervals for each object
2.Sort interval endpoints along the sweep axis
3.Maintain the active set while scanning endpoints
4.Emit pairs whose intervals overlap
5.Repeat or filter across other axes
6.Send remaining pairs to narrow phase

Canonical Example

Input: A interval [0,2], B [1,3], C [4,5] on x-axis
Output: A-B is a candidate pair; C is not
Explanation: Only A and B overlap along the swept axis.

Implementation Notes

Use insertion sort or incremental updates when endpoints change slowly.
Track active intervals while sweeping each axis.
Intersect candidate sets across axes before narrow-phase testing.

Common Pitfalls

Overlaps on one axis are not enough for a collision candidate in multiple dimensions.
Endpoint ordering must handle equal coordinates deterministically.
The broad phase only produces candidates; narrow-phase tests are still required.