Collision Detection

Collision detection is the computational problem of determining when two or more geometric objects intersect or come into contact. It is a foundational problem in computer graphics, robotics, game development, and physical simulation — anywhere that virtual objects must interact with each other or with their environment. The naive approach, testing every pair of objects for intersection, has O(n²) complexity and becomes intractable as scene complexity grows. Efficient collision detection relies on spatial indexes — particularly quadtrees, R-trees, and k-d trees — to prune the search space by identifying pairs of objects that cannot possibly intersect.

The problem splits into two phases: the broad phase, which uses spatial partitioning to eliminate distant object pairs from consideration, and the narrow phase, which performs exact geometric intersection tests on the remaining candidate pairs. The broad phase is where the choice of spatial index matters: a quadtree divides space uniformly and works well for evenly distributed objects; an R-tree adapts to clustered objects but with more complex update logic.

Collision detection is often treated as a solved problem in game engines, but the reality is more nuanced. The broad-phase algorithms that make real-time collision detection possible are not geometric truths; they are engineering compromises between accuracy, speed, and memory. The collision detection pipeline is a microcosm of systems design: the exact same geometry can be handled efficiently or disastrously depending on the spatial index chosen, and most engine developers do not understand why their broad phase is slow until they trace the index structure.