CCD: Stopping Bullets from Tunneling Through Walls

Discrete collision detection samples positions at the end of each step and checks for overlap. A fast bullet moving 200 units/frame in front of a 1-unit-thick wall will move from "in front" to "behind" between two samples and never register a hit. This is tunneling.

CCD solves it by computing the time of impact (TOI) — the fraction t in [0, 1] of the step at which two swept volumes first touch. Then you integrate up to t, resolve, and continue with the remaining 1 - t of the step.

Sphere-vs-static-plane TOI (the simplest case)

Plane has constant y = p. Sphere has center (cx, cy), radius r, velocity (vx, vy).

The sphere contacts the plane when cy + vy*t = p + r (touching from above) or cy + vy*t = p - r (touching from below).

Solve:

t = (p + r - cy) / vy        if approaching from above (vy < 0)
t = (p - r - cy) / vy        if approaching from below (vy > 0)

Only valid if 0 <= t <= 1 and the body is moving toward the plane (otherwise the hit is in the past or in the next frame).

Sphere-vs-sphere TOI

Two spheres A (center c_a, vel v_a, radius r_a) and B (c_b, v_b, r_b).

Let d = c_a - c_b, v = v_a - v_b, r = r_a + r_b. Hit when |d + v*t| = r. Square both sides:

(v . v) t^2 + 2 (d . v) t + (d . d - r^2) = 0

Quadratic in t. Real solutions exist iff discriminant (d.v)^2 - (v.v)(d.d - r^2) >= 0. Take the smaller root (earliest TOI).

When to use CCD

Always doing CCD is expensive (every pair needs an extra quadratic). Engines use it selectively:

• Mark fast-moving bodies as "bullets" (Box2D's b2Body::SetBullet(true)).
• Only CCD bullet-vs-static and bullet-vs-bullet pairs.
• After resolving the TOI sub-step, fall back to discrete detection for the remainder of the frame.

Speculative contacts (the modern alternative)

Bullet and Chipmunk use speculative contacts: enlarge each body's AABB by velocity * dt for broad phase. If two bodies might overlap during the step, you create a constraint that lets the solver itself prevent penetration. Cheaper than full TOI but less precise.

Exercise

Compute TOI for a circle vs a horizontal plane.