Continuous Collision Detection (CCD)

The engine you built tests for overlap at the end of each step. A fast body can start a step on one side of a thin wall and end it on the other side, never overlapping at either sample: it has tunnelled. After this lesson your program will ask a different question, "when during this step does the first touch happen?", and use the answer to stop a bullet at the wall and bounce it.

The problem

Discrete detection samples positions at the start and end of the step. A circle of radius 1 moving 30 units per step passes straight through a floor that is 2 units thick: before the step it is above, after the step it is below, and at neither moment does it overlap. Smaller steps, fatter walls and speed limits all help, but only by moving the problem. CCD removes it by treating the motion as a segment and solving for the time of impact (TOI): a fraction t in [0, 1] of the step at which the shapes first touch.

Moving circle against a plane

Treat the whole step as a straight displacement v (the velocity times dt). The centre is at c + v * t. Take a horizontal plane at height p. The circle touches it when the centre is exactly one radius away:

• coming from above (cy > p): cy + vy * t = p + r, so t = (p + r - cy) / vy;
• coming from below (cy < p): cy + vy * t = p - r, so t = (p - r - cy) / vy.

Then validate the answer. Report a hit only if the circle is moving toward the plane (vy has the right sign) and 0 <= t <= 1. A t above 1 means "not during this step", and the next step's check will see it; a negative t means the touch is in the past. A circle that already overlaps the plane at the start (|cy - p| <= r) hits at t = 0.

Worked trace: radius 2, centre (0, 10), displacement (0, -30), plane at 0. t = (0 + 2 - 10) / (-30) = 0.2667. Without CCD the circle would end the step at y = -20 and be nowhere near touching.

Two moving circles

Work in the frame of one circle. Let d = cA - cB be the starting offset and u = vA - vB the relative displacement. They touch when |d + u * t| = rA + rB. Square it and you get a quadratic in t:

(u . u) t^2 + 2 (d . u) t + (d . d - R^2) = 0        R = rA + rB

• If d . d <= R^2 they already overlap: t = 0.
• If u . u = 0 the circles do not move relative to each other: no hit.
• If the discriminant b^2 - 4ac is negative they miss each other.
• Otherwise the smaller root, (-b - sqrt(disc)) / (2a), is the first touch (the larger root is where they would leave the other side). Keep it only if 0 <= t <= 1.

Worked trace: A at (0,0) radius 1 moving (10, 0); B at (6,0) radius 1 moving (-2, 0). d = (-6, 0), u = (12, 0), R = 2. a = 144, b = -144, c = 32, discriminant 2304, root (144 - 48) / 288 = 1/3. The gap of 6 closes at speed 12 until it is 2 wide: (6 - 2) / 12, the same answer.

Using the TOI

Once you know the earliest hit t, advance the body to c + v * t, apply the collision response there (reflect the velocity about the contact normal with restitution, the impulse lesson), and spend the rest of the step, 1 - t of it, moving with the new velocity. With several obstacles take the one with the smallest t.

Cost: who gets CCD?

A TOI solve is more expensive than an overlap test, so engines apply it selectively: Box2D marks fast bodies as "bullets"; other engines use cheaper speculative contacts that inflate the broad-phase boxes by the motion and let the solver prevent the penetration before it happens. Only bodies that move more than a fraction of their own size per step need it. Polygons use the same idea through conservative advancement: step forward by the current separation distance divided by the speed until they touch.

Common mistakes

• Returning a negative t or a t above 1 as a hit.
• Dividing by vy = 0 for a body moving parallel to the plane.
• Using the larger root of the quadratic: you would report where the circles leave each other.
• Forgetting the "already overlapping" case, so a resting body reports no contact.
• Bouncing a body that is overlapping but already moving away from the obstacle.

Your exercise

The starter reads the scene and prints the results. You write toi_plane, toi_circles and advance. The most likely mistake is skipping the validation of t.