Collision Detection

Collision detection is typically a two-stage pipeline designed for efficiency. The broadphase stage uses spatial data structures like Bounding Volume Hierarchies (BVH) or spatial hashing to quickly cull pairs of objects that are too far apart to possibly collide. The narrowphase stage then performs precise geometric tests on the remaining candidate pairs to compute exact contact points, surface normals, and penetration depths using algorithms like GJK or SAT (Separating Axis Theorem).

Discrete Collision Detection (DCD) checks for overlaps at discrete points in time (e.g., each simulation frame). It is computationally efficient but can suffer from tunneling, where fast-moving objects pass through thin geometry. Continuous Collision Detection (CCD) tests for collisions along the entire swept volume of an object's path between time steps, preventing tunneling but at a higher computational cost. CCD is essential for simulating bullets, fast-moving robots, or thin walls.

The complexity of collision detection is heavily dependent on object shape. Convex shapes (where any line segment between two points lies entirely within the shape) enable highly efficient algorithms like the Gilbert–Johnson–Keerthi (GJK) algorithm. Non-convex (concave) shapes must be decomposed into convex parts (convex decomposition) or tested using more general but slower methods like mesh-triangle tests. This decomposition is a critical pre-processing step for complex robot parts or environmental assets.

Beyond a simple boolean "collide/don't collide," robust simulation requires detailed contact information. The contact manifold is the set of data describing a collision, typically including:

• Contact Points: The world-space points where shapes intersect.
• Contact Normal: A unit vector pointing from one object to the other, defining the collision direction.
• Penetration Depth: The distance the objects overlap. This manifold is the essential input for the constraint solver, which calculates the impulses to resolve the interpenetration and simulate friction and restitution.

To avoid the O(n²) complexity of checking every object pair, physics engines rely on spatial data structures to accelerate queries. Common structures include:

• Bounding Volume Hierarchy (BVH): A tree of nested bounding volumes (spheres, AABBs, OBBs).
• Spatial Hash Grid / Uniform Grid: Space is divided into fixed-size cells; objects are checked against others in the same or neighboring cells.
• Sort and Sweep: Objects' AABBs are sorted along a principal axis; only overlapping intervals are tested. The choice of structure balances build time, update cost (for dynamic objects), and query performance.

Collision detection is not an isolated process but a core component of the physics pipeline. Its outputs directly feed subsequent stages:

1. Broadphase & Narrowphase: Generate potential and actual contacts.
2. Contact Generation & Persistence: Manifolds are created and tracked across frames for stability.
3. Constraint Formulation: Contacts are converted into non-penetration and friction constraints.
4. Constraint Solver: A solver (like PGS or Sequential Impulses) calculates forces to satisfy all constraints.
5. Time Integration: Forces are applied, and positions/velocities are updated for the next frame.

The first, coarse stage in the collision detection pipeline. Its purpose is to efficiently cull pairs of objects that are obviously not colliding, reducing the number of expensive precise checks needed.

• Uses spatial data structures like Bounding Volume Hierarchies (BVH), grids, or sweep-and-prune.
• Algorithms aim for O(n log n) or better complexity.
• Critical for performance in scenes with thousands of objects.

The second, precise stage where potentially colliding pairs from the broadphase are tested in detail. This stage computes exact geometric information about the contact.

• Calculates contact points, surface normals, and penetration depth.
• Employs algorithms like GJK (Gilbert–Johnson–Keerthi) for convex shapes or SAT (Separating Axis Theorem).
• Output is a set of contact manifolds passed to the constraint solver.

A technique that prevents tunneling, where fast-moving or small objects pass through thin geometry between discrete time steps. Instead of testing static shapes, CCD tests the swept volume along an object's trajectory.

• Essential for simulating bullets, fast-moving robots, or cloth.
• Computationally more expensive than discrete collision detection.
• Often implemented using conservative advancement or speculative contacts.

A tree data structure that accelerates collision and ray queries by organizing scene geometry hierarchically. Each node in the tree has a bounding volume (e.g., Axis-Aligned Bounding Box - AABB) that contains all geometry beneath it.

• Enables efficient culling: if two parent volumes don't intersect, none of their children need to be tested.
• Can be built top-down or bottom-up and updated dynamically.
• Also fundamental to ray tracing and rendering engines.

An iterative algorithm that computes the distance between two convex shapes and detects collisions. It operates in the Minkowski difference space, reducing the problem to finding the distance between the origin and this difference shape.

• Highly efficient for convex polyhedra and implicit shapes.
• Often paired with the Expanding Polytope Algorithm (EPA) to calculate penetration depth and contact normal.
• A cornerstone of modern real-time physics engines like Bullet and PhysX.

The stage following narrowphase where contact data is converted into physical constraints for the solver. The solver's job is to compute forces and impulses to resolve interpenetration and model friction.

• Contacts are formulated as velocity-level or position-level constraints.
• Solvers (like PGS - Projected Gauss-Seidel) iteratively satisfy multiple constraints.
• This step enforces non-penetration and applies material properties like restitution and friction.