Convex Sweep Testing in Ammo.js Explained

This article explains the concept of convex sweep testing, a continuous collision detection technique used to prevent fast-moving objects from passing through obstacles. We will define what a convex sweep test is and explore its mathematical implementation within ammo.js—the Emscripten port of the Bullet physics engine—focusing on the Gilbert-Johnson-Keerthi (GJK) algorithm and the Conservative Advancement (CA) method.

What is Convex Sweep Testing?

In real-time physics engines, standard collision detection is “discrete.” The engine moves objects to their new positions at the end of a time step and checks if they overlap. If an object is moving too fast or the frame rate drops, the object can teleport entirely through a thin wall without a collision being registered—a phenomenon known as “tunneling.”

Convex sweep testing solves this problem using continuous collision detection (CCD). Instead of checking for overlap only at discrete intervals, the physics engine takes a convex shape (like a sphere, box, or cylinder) and “sweeps” it along a linear trajectory from a start position to an end position. The algorithm calculates if, where, and when (at what fraction of the path) this swept volume intersects with any other static or dynamic collision shapes in the world.

The Mathematical Foundation

Because ammo.js is a direct port of Bullet Physics, its mathematical implementation of the convex sweep test relies on two primary algorithms: the Gilbert-Johnson-Keerthi (GJK) distance algorithm and Conservative Advancement (CA).

1. Minkowski Difference and GJK

The GJK algorithm determines the shortest distance between two convex shapes, \(A\) and \(B\). It operates on the mathematical concept of the Minkowski Difference, defined as:

\[A \ominus B = \{ x - y \mid x \in A, y \in B \}\]

If the two shapes overlap, their Minkowski Difference contains the origin \((0,0,0)\).

To find the minimum distance without calculating the entire Minkowski shape (which is computationally expensive), GJK uses a Support Function. The support function \(s_A(\vec{d})\) returns the point in shape \(A\) that has the maximum projection along a direction vector \(\vec{d}\):

\[s_{A \ominus B}(\vec{d}) = s_A(\vec{d}) - s_B(-\vec{d})\]

By iteratively selecting direction vectors and building a simplex (a point, line, triangle, or tetrahedron) inside the Minkowski Difference, GJK quickly calculates the minimum distance \(d\) between the two shapes and the closest points on each shape.

2. Conservative Advancement (CA)

To perform a temporal sweep rather than a static distance check, ammo.js uses Conservative Advancement. This is an iterative algorithm that safe-steps the moving object along its trajectory.

Let shape \(A\) start at position \(x_0\) at time \(t = 0\) and travel along a velocity vector \(\vec{v}\) to a target position at \(t = 1\). Shape \(B\) is a static obstacle.

  1. Calculate Distance: At the current time step \(t\), run the GJK algorithm to find the minimum distance \(d\) between \(A(t)\) and \(B\).

  2. Check for Collision: If \(d\) is less than a tiny tolerance threshold (\(\epsilon\)), a collision is detected at the current time \(t\).

  3. Determine Maximum Safe Step: Calculate the maximum bound of the relative velocity of shape \(A\) projected onto the collision normal vector \(\vec{n}\) (the direction of closest points found by GJK).

    The maximum advancement step \(\Delta t\) is calculated as: \[\Delta t = \frac{d}{\vec{v} \cdot \vec{n} + \omega \cdot r}\] Where:

    • \(d\) is the current minimum distance.
    • \(\vec{v}\) is the linear velocity vector.
    • \(\vec{n}\) is the collision normal.
    • \(\omega\) is the angular velocity.
    • \(r\) is the maximum radius of the swept shape (to account for rotation).

  4. Advance: Advance the shape’s position to \(t = t + \Delta t\). Because \(\Delta t\) is calculated using the absolute minimum distance, the shape is guaranteed not to penetrate the obstacle during this step.

  5. Iterate: Repeat steps 1–4. If \(t\) exceeds \(1.0\) without \(d\) falling below \(\epsilon\), no collision occurs during the sweep.

Implementation in ammo.js

In ammo.js, the sweep test is accessed through the btCollisionWorld class using the convexSweepTest method.

Data Requirements

To perform the test, you must supply: * A Convex Shape: Must inherit from btConvexShape (e.g., btSphereShape, btBoxShape). * Start and End Transforms: Defined as btTransform objects representing the path of the sweep. * A Result Callback: Typically an instance of ClosestConvexResultCallback.

The Callback Output

During the sweep, the mathematical engine updates the callback object with critical collision data: * m_closestHitFraction: A float between \(0.0\) (start) and \(1.0\) (end) indicating exactly when the collision occurred along the path. * m_hitPointWorld: The 3D coordinates in world space where the contact occurred. * m_hitNormalWorld: The normal vector of the surface at the point of contact, pointing away from the hit object.