Broad phase
Related terms: narrow phase, spatial partitioning, quadtree, octree, grid
Testing every object against every other is too slow: 1,000 objects means about 500,000 pairs. The broad phase throws out pairs that cannot possibly touch, using bounding boxes and a spatial structure. The narrow phase then runs exact tests on the few pairs left.
The structure is a grid, a quadtree in 2D, an octree in 3D, or a BVH. The same structures answer "what is near me?" for AI and speed up raycasts.
- Further reading
- Box2D: Dynamic tree and broad phase