Collision detection

Collision detection is the computational problem of determining when two or more geometric objects intersect or come into contact. It is the invisible infrastructure of virtual worlds: without it, video game characters walk through walls, robotic arms crush their payloads, and molecular simulations compute non-physical overlaps. The problem is deceptively simple to state — do these two shapes touch? — and computationally expensive to solve at scale.

The naive approach, testing every pair of objects for intersection, is O(n²) and unusable for large scenes. The systems solution is to exploit spatial coherence: objects that are far apart cannot collide, so the algorithm must quickly eliminate impossible pairs before performing expensive geometric tests. This is where spatial indexing becomes essential. Quadtrees, R-trees, k-d trees, and uniform grids partition space so that only objects in the same or adjacent cells need be tested against each other.

Broad Phase and Narrow Phase

Collision detection is typically decomposed into two stages. The broad phase identifies candidate pairs of objects that might collide, using a spatial index or sorting along an axis. The narrow phase performs exact intersection tests on the candidate pairs. This decomposition is a classic systems optimization: the broad phase is conservative (it may include pairs that do not actually collide) but fast; the narrow phase is exact but expensive. The separation of concerns allows each phase to be optimized independently.

The broad phase is where algorithmic ingenuity matters most. A quadtree or spatial hash assigns objects to cells; only objects in the same cell are candidate pairs. For moving objects, temporal coherence can be exploited: if two objects did not collide in the previous frame and neither has moved far, they cannot collide in the current frame. This observation transforms a spatial problem into a temporal one, and the most efficient broad-phase algorithms maintain a list of active