Swept Capsule Continuous Collision Detection

Continuous collision detection (CCD) for capsule-capsule pairs prevents fast-moving game entities, such as player avatars and projectiles, from tunneling through one another between discrete simulation frames. Because computing the exact non-convex swept volume generated by moving capsules is mathematically complex and computationally expensive, physics engines rely on geometric reductions and approximations. This article explains how game physics engines approximate swept volumes using relative motion, core-segment reduction, bilinear patch representations, and iterative root-finding algorithms like Conservative Advancement to reliably calculate the exact Time of Impact (TOI).

Mathematical Definition of a Capsule

A capsule is geometrically defined as the Minkowski sum of a core line segment and a sphere. Formally, a capsule \(C\) with endpoints \(A\) and \(B\) and radius \(r\) represents the set of all points within distance \(r\) from the line segment \(S = [A, B]\):

\[C = \{ P \in \mathbb{R}^3 \mid \min_{s \in [0,1]} \| P - (A + s(B - A)) \| \le r \}\]

Because the radius is uniform in all directions, continuous collision detection between two moving capsules can be simplified by decoupling the linear core segments from their spherical radii.

Reduction to Relative Motion

Simulating two objects moving simultaneously over a time interval \(t \in [0, 1]\) introduces complex quadratic or higher-degree trajectories. To simplify the continuous test, physics engines transform the coordinate space so that Capsule 2 remains stationary while Capsule 1 absorbs the relative linear velocity:

\[\vec{v}_{\text{rel}} = \vec{v}_1 - \vec{v}_2\]

Under this transformation, Capsule 2's core segment remains fixed at \(S_2 = [C_0, D_0]\), while Capsule 1's segment \(S_1 = [A_0, B_0]\) sweeps along the translation vector \(\vec{v}_{\text{rel}}\) over \(t \in [0, 1]\).

Furthermore, by applying the Minkowski addition of radii, the problem reduces to testing a moving line segment against a static, dilated line segment. The collision occurs if the minimum distance between the swept segment of Capsule 1 and the static segment of Capsule 2 is less than or equal to the combined radius \(R = r_1 + r_2\):

\[R = r_1 + r_2\]

The Swept Segment as a Bilinear Patch

When the core segment \(S_1(u) = A_0 + u(B_0 - A_0)\) (where \(u \in [0, 1]\)) translates linearly by \(t \vec{v}_{\text{rel}}\) (where \(t \in [0, 1]\)), it sweeps out a planar parallelogram or a ruled bilinear quadrilateral surface \(Q(u, t)\):

\[Q(u, t) = A_0 + u(B_0 - A_0) + t \vec{v}_{\text{rel}}\]

To approximate the swept volume:

  1. Triangulation: The quadrilateral \(Q(u, t)\) is split into two static triangles along its diagonal.
  2. Segment-Triangle Queries: The static segment \(S_2\) is tested against each triangle of the swept quadrilateral using standard 3D segment-triangle closest-point algorithms.
  3. Radius Inclusion: If the shortest distance between segment \(S_2\) and the triangles is less than \(R\), a collision occurs within the time step.

While fast, this planar approach assumes purely linear translation. If angular velocity (rotation) is present, the swept surface forms a non-planar helicoid or hyperbolic paraboloid, which standard engines usually approximate by piecewise linear subdivision of the time step.

Conservative Advancement (Time of Impact Calculation)

Rather than generating an explicit geometric mesh of the swept volume, modern physics engines (such as PhysX and Havok) frequently employ Conservative Advancement to find the Time of Impact (TOI). This technique uses a distance-based root finder:

  1. Distance Query: Compute the minimum separation distance \(d\) between the two capsules at the current lower time bound \(t\) (initially \(t = 0\)) using static capsule-capsule closest-point routines.
  2. Safety March: If \(d \le R + \epsilon\), a collision is registered at time \(t\).
  3. Bound Approach Velocity: Compute an upper bound on the maximum relative approach velocity \(v_{\text{max}}\) along the vector separating the two closest points.
  4. Time Step Advance: Advance time by a safe, conservative increment: \[\Delta t = \frac{d - R}{v_{\text{max}}}\]
  5. Iteration: Set \(t = t + \Delta t\). If \(t > 1\), the capsules do not collide during the frame. Otherwise, repeat from Step 1 until convergence.

Because \(\Delta t\) guarantees that the surfaces cannot cross each other during that interval, Conservative Advancement avoids misses entirely without having to explicitly construct the high-dimensional Minkowski swept boundary.

Bounding Volume Hierarchies and Early Out Tests

Before executing exact bilinear sweeps or Conservative Advancement, coarse swept bounding volumes are evaluated:

  • Swept Oriented Bounding Boxes (OBBs): An OBB is constructed to tightly enclose both the initial capsule position at \(t=0\) and the final position at \(t=1\).
  • Separating Axis Theorem (SAT): The engine tests the static OBB of Capsule 2 against the swept OBB of Capsule 1. If an axis of separation exists, continuous intersection is ruled out immediately, bypassing finer algebraic or iterative tests.