Broad-phase algorithm

A broad-phase algorithm is the first stage of collision detection, responsible for rapidly identifying candidate pairs of objects that might intersect, without performing expensive exact geometric tests. It is a conservative filter: it may include pairs that do not actually collide, but it must never exclude pairs that do. The broad phase transforms an O(n²) pairwise problem into a near-linear problem by exploiting spatial indexing and temporal coherence.

Common broad-phase structures include uniform grids, quadtrees, spatial hashes, and sweep-and-prune algorithms that sort objects along a coordinate axis. The choice of structure encodes an assumption about the data: uniform grids assume evenly distributed objects; quadtrees assume hierarchical spatial clustering; sweep-and-prune assumes that objects are mostly stationary between frames. No broad-phase structure is universally optimal, and the failure to match structure to data distribution is a recurring source of performance collapse in physics engines and game simulations.