A computational subsystem that continuously tests whether geometric objects in a simulation or physical environment intersect or are about to intersect, enabling physics engines, robotics planners, and interactive applications to respond to contact events. It combines spatial partitioning structures with narrow-phase geometry tests to balance accuracy against performance.
Content
- Early collision detection was performed via simple bounding-sphere or axis-aligned bounding-box tests in arcade games of the late 1970s and early 1980s. As polygonal meshes grew in complexity, the O(n²) naïve pair-wise test became computationally prohibitive, driving the development of spatial subdivision schemes: octrees, BSP trees, and k-d trees subdivide space to reduce candidate pairs before geometric intersection tests.
- Modern collision detection architectures separate broad-phase from narrow-phase computation. Broad-phase algorithms — sweep-and-prune, bounding volume hierarchies (BVH), or GPU-accelerated spatial hashing — produce a list of candidate pairs with potential overlap. Narrow-phase algorithms then apply precise geometry tests: Gilbert–Johnson–Keerthi (GJK) for convex hulls, Minkowski Portal Refinement (MPR), or signed distance field (SDF) queries. Continuous collision detection (CCD) handles fast-moving objects that might tunnel through thin geometry within a single time-step.
- The collision detection ecosystem spans game middleware (PhysX, Havok, Bullet), robotics frameworks (FCL, coal), CAD/CAM tools, and simulation platforms. GPU-accelerated BVH construction and traversal have become standard in high-performance use cases, with NVIDIA’s OptiX and RTX hardware providing ray-triangle intersection at hardware speed. Robotics motion planners integrate collision detection tightly with configuration-space representations via libraries such as MoveIt and OMPL.
- In 2024–2025, neural collision detection approaches — learning approximate signed distance functions or contact manifolds from data — are complementing classical geometric methods in deformable-body simulation and soft-robotics planning. XR applications at higher resolutions and frame rates (120 Hz+) are pushing latency budgets below 2 ms for collision queries, driving further GPU offloading and algorithmic innovation.