View source for 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|spatial indexing]] and temporal coherence.

Common broad-phase structures include uniform grids, [[Quadtree|quadtrees]], [[Spatial hashing|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.''

See also: [[Collision detection]], [[Narrow-phase algorithm]], [[Spatial indexing]], [[Quadtree]]

[[Category:Computer Science]] [[Category:Systems]] [[Category:Graphics]]