Continuous Collision Detection (CCD)

CCD models the motion of an object as a continuous trajectory in space-time, computing the swept volume—the union of all space occupied during the interval. A collision is reported if this volume intersects any obstacle. This contrasts with Discrete Collision Detection (DCD) , which only samples static configurations at frame boundaries. The swept volume is often approximated using convex hulls of the object's pose at the start and end of the timestep, enabling efficient overlap tests with bounding volume hierarchies.

A core CCD algorithm computes the Time of Impact (TOI) —the exact fractional moment between t=0 and t=1 when two moving objects first make contact. Conservative Advancement (CA) methods iteratively advance objects along their trajectories by the minimum separation distance until the distance falls below a tolerance. The TOI is critical for physics engines and robotic path planners, enabling them to roll back simulations to the precise instant of contact for accurate constraint resolution.

Conservative Advancement (CA) is the foundational iterative algorithm for CCD. At each step, it computes the minimum distance between two convex shapes, then advances time by a fraction proportional to that distance divided by an upper bound on relative velocity. This guarantees no collision is missed because the advancement is conservative—it never jumps past a potential contact. The Gilbert-Johnson-Keerthi (GJK) algorithm is typically used for the distance queries, making CA robust for polygonal and implicit surfaces.

The tunneling artifact occurs in discrete detection when a fast-moving projectile or thin feature traverses an obstacle entirely within a single timestep, leaving no overlapping samples. CCD eliminates this by considering the continuous motion. This is critical in:

• Robotic surgery: preventing needle-thin tools from piercing virtual safety boundaries
• High-speed assembly: ensuring fast pick-and-place end-effectors don't clip through fixtures
• Game physics: stopping bullets from passing through walls at high frame rates

In robotic path planning, CCD is integrated into collision checking routines to validate entire trajectory segments, not just waypoints. Sampling-based planners like RRT and PRM use CCD to ensure the straight-line connection between two sampled configurations is collision-free. Without CCD, a planner might certify a path as valid even though the robot's swept volume intersects an obstacle during the motion. MoveIt and OMPL both support CCD backends like FCL (Flexible Collision Library) for this purpose.

CCD is computationally more expensive than DCD because it requires solving for the earliest contact time rather than a simple overlap test. Key performance considerations include:

• Narrow-phase cost: TOI queries using GJK/CA are O(n) in iteration count
• Broad-phase acceleration: Sweep-and-prune or bounding volume hierarchies cull non-intersecting pairs before CCD
• Adaptive strategies: Many systems use DCD by default and fall back to CCD only for objects exceeding a velocity-thickness ratio threshold, balancing safety with throughput