Overview

Collision detection is the computational task of determining if and when two or more geometric objects intersect or come into contact. It is a core component of computer graphics, physical simulation, robotics, and safety systems. Inputs to a collision detection system are geometric models (points, lines, polygons, meshes or implicit shapes) together with motion information; the output is detection events, contact points, penetration depths, or times of impact that higher-level systems use to prevent overlaps or compute physical responses.

Key techniques and representations

Practical collision detection separates work into broad-phase and narrow-phase stages. Broad-phase methods quickly discard object pairs that are far apart; narrow-phase algorithms examine candidate pairs in detail. Common representations and algorithms include:

  • Bounding volumes such as axis-aligned bounding boxes (AABB), oriented bounding boxes (OBB), spheres and k-DOPs for fast rejection tests.
  • Hierarchies like bounding volume hierarchies (BVH) that organize complex meshes into tree structures to accelerate queries.
  • Spatial partitioning schemes such as uniform grids, quadtrees/octrees and BSP trees to localize potential collisions.
  • Sweep-and-prune and sort-and-sweep techniques that exploit temporal coherence to find overlapping intervals efficiently.
  • Exact geometric tests including the Gilbert–Johnson–Keerthi (GJK) algorithm, the separating axis theorem (SAT) and triangle-triangle intersection for precise narrow-phase checks.

Implementation and performance considerations

Designing a collision system balances speed, accuracy and robustness. Real-time applications such as games favour approximate, fast tests and aggressive broad-phase culling; safety-critical systems (aviation, robotics) emphasize reliable detection and continuous collision detection to avoid tunneling when objects move fast. Numerical stability, handling of degenerate geometry, and maintaining coherent acceleration structures as objects deform or move are common engineering challenges.

History and development

Collision detection evolved alongside computer graphics and control systems. Early work in computational geometry and robotics established foundational tests for intersections. As interactive 3D graphics and physics simulation became mainstream in the 1990s and 2000s, engine developers and researchers expanded the range of acceleration structures and algorithms to meet real-time constraints and complex scenes.

Applications and examples

Collision detection is used across many fields:

  • Interactive entertainment and simulation: detecting hits, contacts and environment collisions in game engines.
  • Robotics and autonomous systems: ensuring safe motion planning and obstacle avoidance.
  • Engineering and CAD: interference checking for assemblies and virtual prototyping.
  • Aerospace and transportation safety: monitoring potential conflicts between moving objects.
  • Scientific simulation: molecular docking and particle collision analyses.

For practical implementations and libraries consult technical overviews and tool collections such as more detailed articles and repositories of open-source libraries.

Collision detection is distinct from collision response: detection answers whether a collision occurs, while response computes forces, impulses, or corrective motions. Another important distinction is between discrete collision detection (checking at fixed time steps) and continuous collision detection (finding the first time of contact during motion). Robust systems often combine multiple tests and fallback strategies to handle complex or degenerate cases reliably.