Swept capsule vs triangle test

2^nd December, 2024

Swept shape tests are used primarily in order to find the exact time when two moving shapes will first collide.

I like to use these kinds of tests in my games, because they’re very robust. I also like to use capsules and triangle meshes for collision shapes. But until recently, I could never figure out how to sweep a capsule against a triangle. I couldn’t find any blog posts talking about this, or any open-source code that does it. But then I read Real-Time Collision Detection by Christer Ericson, which taught me all the tricks that are needed to come up with the procedure myself.

Introduction to sweep tests#

The conceptually simplest way to test and resolve collisions between a moving object with position $\mathrm{P}$ and velocity $\mathbf{v}$ , and a bunch of stationary objects goes something like this:

P += dt*v                    # move forward
for object in objects
    if collision(object)     # check for collisions
        d = collision.depth
        n = collision.normal
        P += d*n             # move A out of collision
        v += dot(v,n)*n      # cancel velocity towards collision
    end
end

Every time-step, you move the object forward a little bit, and then you check for collisions. If the two objects collide, you adjust the position by the smallest distance such they no longer collide, and then you cancel out the velocity in the direction of the collision.

The major problem with this approach is that collisions are checked only at discrete points in time, so collisions which happen only in the middle of a step are ignored. This means objects can “tunnel” through each other if they’re moving very fast.

Sweep tests don’t have this tunneling problem as they effectively check for collisions during the entire motion of the object. You can think of a sweep test as simply “sweeping” or “smearing” the shape along its velocity vector - creating a new shape which is then used for collision testing.

If we update the routine from earlier to use sweep tests we get something that looks like this:

u = dt*v
loop
    t = INFINITY
    for object in objects
        s = sweep(object, u) # find time of first contact
        t = min(t, s)        # only consider first collision
    end
    P += t*u                 # advance until collision
    if t < 1                 # if there was a collision..
        d = collision.depth
        n = collision.normal
        u *= 1 - t           # calculate remaining movement
        u += dot(v,n)*n      # cancel movement towards collision
        P += d*n             # move A out of collision
        v += dot(v,n)*n      # cancel velocity towards collision
    end
while t < 1

Note how collisions are resolved in a loop until none remain. In practice there is no guarantee that this loop would ever terminate. So you always want to cap it to some maximum number of iterations.

Using a sweep test like this, objects can no longer tunnel through each other. Additionally, it decouples the collision detection from the simulation rate.

The downside is that sweep tests are usually around an order of magnitude more expensive than the simple discrete collision detection, because they involve colliding more complicated swept shapes.

Capsules as collision shapes#

A Capsule is defined by 2 points forming a line segment, and a radius defining the maximum distance from this segment.

Capsules are my favorite collision shape for the player character in games. They approximate a humanoid shape better than a bounding sphere. Also, since they’re rounded from the sides, they allow the player to smoothly slide along the corners of obstacles they walk into. A box would not slide so smoothly - the player would instead get stuck on the corners. This is not only frustrating for experienced players, it’s also very discouraging for new players who are still learning how to navigate game worlds.

Also, since capsules have rounded endpoints, they also allow the player to slide smoothly along small bumps in terrain, or to climb stairs. With other collision shapes you usually have to either special-case these scenarios, or to heavily restrict your collision meshes to make sure they don’t occur. For example, instead of a stair shaped collision mesh, you have to use a ramp. It’s usually a good idea to use these techniques in addition to using capsules. However, capsules at least give you a safety net if your hard-coded special-casing fails to detect a bump, or if you forget to preprocess a set of stairs.

Capsules have many upsides. The main downside of using a capsule instead of a box, cylinder, or sphere is that it’s a more complicated and expensive shape. Therefore you probably shouldn’t use capsules unless you can actually make use of their upsides.

Triangle meshes as collision shapes#

Triangle meshes are rarely the “best” collision shape to use. For example, a box is a way cheaper, simpler, and more robust collision shape than the 12 triangles it’s made of. However, triangle meshes can be very economical as collision shapes.

You very likely already have a triangle mesh for rendering. These meshes used for visuals are typically too high-poly to be used directly for collisions. However, you usually have low LOD versions of high-poly meshes, and these can be used for collisions. Or maybe your game has a low-poly 3D aesthetic to begin with. Then all of your visual meshes can be used directly as collision shapes.

The point is, that using triangle-meshes as collision shapes is a lot less work than using other, more specialized collision shapes.

Coming up with sweep tests#

There is very little information about collision detection and resolution in general online. I don’t know why there are so many blogs about cool graphics techniques, yet very few about collision detection. If you’re not using any physics library or engine, you will need to come up with collision tests by yourself. This probably sounds daunting, that’s exactly how I felt, until I read Real-Time Collision Detection. Reading through it finally gave me the insights necessary to device collision tests between almost any two shapes. I’ll try to summarize these insights here.

Minkowski difference#

The first bit of insight is that volume, area, or length can be transferred from one shape onto another. You know how in math equations you can subtract the same value from both sides? For example $4x = 8$ is the same as $4x - 8 = 0$ , because you can subtract $8$ from both sides. Well, you can do the same sort of thing with shapes.

If you imagine each shape as a set of points which it contains, then you can imagine subtracting all of the points from one shape with all of the points from another to create another expanded shape. This is called the Minkowski difference. You can also do this subtraction or transfer only along a particular axis. Let me illustrate how to use this with some examples:

Testing whether a sphere with radius $3$ centered at $\mathrm{P}_0$ intersects a sphere with radius $4$ centered at $\mathrm{P}_1$ is the same as testing whether a sphere with radius $0$ (a point) centered at $\mathrm{P}_0$ intersects a sphere with radius $4+3=7$ centered at $\mathrm{P}_1$ .

Testing whether a vertical cylinder at position $\mathrm{P}$ with radius $r$ and height $h$ intersects a unit square on the $xz$ -plane is the same as testing whether a sphere at position $\mathrm{P}$ with radius $r$ intersects a box with unit width and length, and height $h$ extending below the $xz$ -plane.

Velocity is length#

This should be pretty self explanatory, you can treat linear velocity as if it adds another dimension of length to a shape. Imagine combining all of the points you get when moving the shape to any position along the velocity vector, all of these points form a new shape. Let me again illustrate how to use this with some examples:

Testing whether a moving point at position $\mathrm{P}$ with velocity $\mathbf{v} = (0,-9)$ hits the line at $x = 0$ is the same as testing whether the stationary point at $\mathrm{P}$ is inside the area of space bounded by $0 \le x \le 9$ .

Testing whether two unit-circles with positions $\mathrm{P}_0$ and $\mathrm{P}_1$ , and velocities $\mathbf{v_0} = (0,4)$ and $\mathbf{v_1} = (3,0)$ collide is the same as testing whether a unit-circle at $\mathrm{P}_0$ with with velocity $\mathbf{v_0} = (-3,4)$ collides with a stationary unit-circle at $\mathrm{P}_1$ .

Divide and conquer#

Using the Minkowski difference, you can always reduce any collision test or sweep test between shapes $\mathrm{A}$ and $\mathrm{B}$ with an equivalent test between a point and shape $\mathrm{A} \ominus \mathrm{B}$ . This combined shape $\mathrm{A} \ominus \mathrm{B}$ will be more complicated than $\mathrm{A}$ or $\mathrm{B}$ individually. However, you don’t have to deal with the entire combined shape at once. $\mathrm{A} \ominus \mathrm{B}$ can be decomposed into a bunch of smaller, simpler shapes like spheres, cylinders, triangles, and prisms. You can then individually test against each of these simple shapes, and combine the results at the end.

Testing whether a point intersects a capsule is equivalent to testing whether that same point intersects the cylindrical part of the capsule, or with either of the spherical endcaps.

The swept capsule triangle test#

Using the principles from above, I was finally able to decompose the capsule triangle sweep into a problem simple enough for me to solve.

First, subtract the capsule shape from the triangle. This turns the moving capsule into a moving point, and the triangle into a triangular prism with rounded corners:

Then we just have to collide the line segment with the rounded prism shape. The surface of this shape is composed of 2 triangles, 3 parallelograms, 9 uncapped cylinders, and 6 spheres. And on the inside, there is a normal triangular prism without rounded edges.

To find the time of first collision of the swept point against the rounded prism, we need to find the time of first collision with each of these constituent shapes, and then find the minimum time amongst those. I will now attempt to explain how to do the collision test against each constituent shape. You can also find the full source code of the procedure here.

Inner prism volume#

The capsule is defined by two points, $\mathrm{C}_0$ and $\mathrm{C}_1$ , and a radius $r$ . The triangle is defined by 3 points $\mathrm{T}_0$ , $\mathrm{T}_1$ , and $\mathrm{T}_2$ . The velocity of the capsule is defined by $\mathbf{v}$ .

Firstly, we have to check if point $\mathrm{C}_0$ intersects with the triangular prism. This can be done by checking if the point lies on the same side of all 5 planes formed by the faces of the prism. This can be evaluated cheaply by checking if the signed distance between the point and the plane $(\mathrm{P}-\mathrm{P}_0) \cdot \mathbf{n}$ has the same sign for all 5 planes.

Care must be taken about the winding-order of the 5 faces. All of their normals must face in the same direction, either inwards or outwards, in order for the test to be valid. This can be done by making sure the top and bottom triangular faces have the opposite winding order, and that the side faces have the same windowing order as the top face.

We can calculate the plane normal $\mathbf{n}$ from from 3 points on the plane using the cross product $\mathbf{n} = (\mathrm{P}_1 - \mathrm{P}_0) \times (\mathrm{P}_2 - \mathrm{P}_0)$ . We don’t even need to normalize this vector, since we only care about the sign of the dot product, not its magnitude. This also allows us to disregard the potentially degenerate sides of the prism.

vec3 faces[5][3]; // 3 points from every face of the prism.
float sgn;
for (int i = 0; i < 5; i++) {
    vec3 p0 = faces[i][0];
    vec3 p1 = faces[i][1];
    vec3 p2 = faces[i][2];
    vec3 p01 = p1 - p0;
    vec3 p02 = p2 - p0;
    vec3 n = cross(p01,p02);
    float d = dot(n,p - p0);
    if (i == 0) sgn = d;
    if (sgn*d <= 0) return false; // Point outside of prism.
}
return true; // Point inside of prism.

If this first test detects a collision, then the capsule starts off initially colliding with the triangle, and we need to push it out. Note that this only tests whether the center-line of the capsule collides with the triangle, so the collision normal will always point out of the nearest triangle face, and never away from an edge. We can check which capsule side is closer to the triangle by comparing the signed distance of both capsule points to the triangle plane:

In code, we just have to calculate the collision noramal and penetration depth, and the collision resolution routine outside of the sweep test will take care of removing the penetration:

vec3 n = normalize(cross(t1 - t0,t2 - t0));
float d0 = dot(n,c0 - t0);
float d1 = dot(n,c1 - t0);
float d = abs(d0) <= abs(d1) ? d0 : d1;
sweep->time = 0;
sweep->depth = abs(d) + r;
sweep->point = c0 + d0*n;
sweep->normal = d >= 0 ? n : -n;
return true; // Capsule and triangle intersect.

Prism faces#

Now that we’ve dealt with the internal volume of the prism, we can move on to the outer shell. A triangular prism has 5 faces in total, 2 of which are triangular, and 3 are parallelograms. Both types of faces are defined by 3 points, and they are handled in almost exactly the same way.

Using 3 points on each face, we calculate the face plane normal $\mathbf{n} = (\mathrm{P}_1-\mathrm{P}_0)\times(\mathrm{P}_2-\mathrm{P}_0)$ . We can then check whether a sphere centered at $\mathrm{P} = \mathrm{C}_0$ with radius $r$ and velocity $\mathbf{v}$ collides with this plane by solving the linear equation $(\mathrm{P} + t\mathbf{v} - \mathrm{P}_0)\cdot\hat{\mathbf{n}} = r$ for $t$ .

If the sphere does collide with the plane, we have to test if the point of collision lies inside of the face. A point is inside the face if it is on the same side of all of the planes containing parallel to the face’s edges.

The sphere and the face collide if the sphere collides with the plane containing the face, and the sphere center is inside the face at the collision time. We only have to check the sphere center for containment, because collisions with the outside of the sphere are handled by the edge and vertex collision tests.

vec3 n = cross(p1 - p0,p2 - p0);
float len = length(n);
if (len < EPSILON) return false; // Degenerate face.
pn /= len;
float d = dot(n,c0 - p0);
if (d < 0) n = -n; // Orient normal towards sphere.
float t;
float pen = max(r - abs(d),0);
if (pen > 0) t = 0; // Initially colliding.
else {
    float div = dot(n,v);
    if (div >= 0) return false; // Moving away from plane.
    t = (r - abs(d))/div;
}
if (t >= sweep->time) return false; // Miss triangle plane.
vec3 collision = c0 + t*v - r*n;
// Either pointInsideTriangle or pointInsideParallelogram.
if (!pointInsideXXX(collision,p0,p1,p2)) return false;
sweep->time = t;
sweep->depth = pen;
sweep->point = collision;
sweep->normal = n;
return true; // Sphere and triangle collide.

Note that when a triangle edge is completely parallel to the capsule’s direction, the parallelogram face formed from extruding the edge will degenerate into a line. In this case computing the plane normal of the parallelogram is impossible, and the degenerate face must be skipped.

Testing whether a point is on the inside of a triangle can be done by calculating its barycentric coordinates and then validating them. Testing if a point is inside a parallelogram can just be done by testing the two triangles of the parallelogram individually.

bool pointInsideTriangle(vec3 p,vec3 t0,vec3 t1,vec3 t2) {
    vec3 a = t1 - t0;
    vec3 b = t2 - t0;
    vec3 c = p - t0;
    float aa = dot(a,a);
    float ab = dot(a,b);
    float bb = dot(b,b);
    float ca = dot(c,a);
    float cb = dot(c,b);
    float d = aa*bb - ab*ab;
    float vd = bb*ca - ab*cb;
    float wd = aa*cb - ab*ca;
    return vd >= 0 && wd >= 0 && vd + wd <= d;
}
bool pointInsideParallelogram(vec3 p,vec3 p0,vec3 p1,vec3 p2) {
    vec3 p3 = p2 + (p1 - p0);
    return
        pointInsideTriangle(p,p0,p1,p2) ||
        pointInsideTriangle(p,p1,p3,p2);
}

Cylindrical edges#

The 9 edges of the rounded triangular prism can be handled as finite cylinders. Each cylinder is defined by two points $\mathrm{C}_0$ and $\mathrm{C}_1$ forming a line, and all cylinders have the radius $r$ . The equation of an infinite cylinder is $\big(\mathbf{n}\times(\mathrm{X}-\mathrm{C}_0)\big)^2 =r^2\mathbf{n}^2$ where $\mathbf{n} = \mathrm{C}_1 - \mathrm{C}_0$ . In order to find the time of intersection of the capsule point $\mathrm{P} = \mathrm{C}_0$ with velocity $\mathbf{v}$ , we can substitute the line equation $\mathrm{P}+t\mathbf{v}$ in the cylinder equation to get this combined equation:
$\big(\mathbf{n}\times(\mathrm{P} + t\mathbf{v} - \mathrm{C}_0))^2 = r^2\mathbf{n^2}$
Using $\mathbf{d} = \mathrm{P} - \mathrm{C}_0$ , this equation can be expanded and rearranged into:
$(\mathbf{n}\times\mathbf{v})^2t^2 + \big((\mathbf{n}\times\mathbf{v})\cdot(\mathbf{n}\times\mathbf{d})\big)t + (\mathbf{n}\times\mathbf{d})^2-r^2\mathbf{n}^2 = 0$

This is a quadratic equation $at^2 + bt + c$ with the terms:
$\begin{align*} a &= (\mathbf{n}\times\mathbf{v})^2\\ b &= (\mathbf{n}\times\mathbf{v})\cdot(\mathbf{n}\times\mathbf{d})\\ c &= (\mathbf{n}\times\mathbf{d})^2 - r^2\mathbf{n}^2\\ \end{align*}$
Notice that $a$ is zero when the line and cylinder are parallel, and that $c$ is negative when the point starts inside of the cylinder. When the line and cylinder are parallel, we only need to determine whether the point starts inside the cylinder, which happens when $0 \le \mathbf{d}\cdot\mathbf{n} \le \mathbf{n}^2$ . We don’t need to check for collisions with the endcaps because these are handled separately later.

We can use Lagrange’s identity to rewrite the cross products in terms of dot products:
$\begin{align*} a &= \mathbf{n}^2\mathbf{v}^2 - (\mathbf{v}\cdot\mathbf{n})^2\\ b &= \mathbf{n}^2(\mathbf{d}\cdot\mathbf{v}) - (\mathbf{v}\cdot\mathbf{n})(\mathbf{d}\cdot\mathbf{n})\\ c &= \mathbf{n}^2(\mathbf{d}^2 - r^2) - (\mathbf{d}\cdot\mathbf{n})^2\\ \end{align*}$
If the discriminant $abla = b^2 - ac < 0$ , then the point completely misses the cylinder, and we can conclude the test. Otherwise we can find the time of first contact:
$t = \frac{-b - \sqrt{ abla}}{a}$

If $0 \le t \le 1$ then we accept the collision.

vec3 n = c1 - c0;
vec3 d = p - c0;
float dn = dot(d,n);
float vn = dot(v,n);
float nn = dot(n,n);
if (dn < 0 && dn + vn < 0) return false; // Fully outside c0 endcap.
if (dn > nn && dn + vn > nn) return false; // Fully outside c1 endcap.
float t;
float vv = dot(v,v);
float dv = dot(d,v);
float dd = dot(d,d);
float a = nn*vv - vn*vn;
float c = nn*(dd - r*r) - dn*dn;
if (a < EPSILON) { // Sweep direction is parallel to cylinder.
    if (c > 0) return false; // Outside of cylinder.
    if (dn < 0) return false; // Outside of c0 endcap.
    if (dn > nn) return false; // Outside of c1 endcap.
    t = 0;
} else {
    float b = nn*dv - vn*dn;
    float discr = b*b - a*c;
    if (discr < 0) return false; // Miss cylinder.
    t = (-b - sqrt(discr))/a;
}   
if (t < 0 || t >= sweep->time) return false; // Miss cylinder.
vec3 collision = p + t*v;
vec3 center = c0;
if (nn >= EPSILON) center += (dot(collision - c0,n)/nn)*n;
vec3 vec = collision - center;
float len = length(vec);
float depth = r - len;
sweep->time = t;
sweep->depth = t > 0 ? 0 : depth;
sweep->point = collision;
sweep->normal = len >= EPSILON ? vec/len : nearestFaceNormal;
return true; // Point and cylinder collide.

Notice that when the point starts exactly on top of the triangle line, it is impossible to calculate a collision normal. In that case we can just return the normal vector of the nearest face calculated in the previous step.

Spherical corners#

Now only the 6 spherical corners of the prism remain. Each corner is defined by by its center point $\mathrm{S}$ and all corners have the radius $r$ . In order to find the time of intersection of the capsule point $\mathrm{P} = \mathrm{C}_0$ with velocity $\mathbf{v}$ , we can substitute the line equation $\mathrm{P} + t\mathbf{v}$ into the sphere equation $(\mathrm{X} - \mathrm{S})^2 = r^2$ . This results in the combined equation:
$(\mathrm{P} + t\mathbf{v} - \mathrm{S})^2 = r^2$
Using $\mathbf{d} = \mathrm{P} - \mathrm{S}$ , this equation can be expanded and rearranged into:
$\mathbf{v}^2t^2 + 2\big(\mathbf{v}\cdot\mathbf{d}\big)t + \mathbf{d}^2 - r^2 = 0$
This is obviously a quadratic equation $at^2 + bt + c$ with the terms:
$\begin{align*} a &= \mathbf{v}^2\\ b &= 2\big(\mathbf{v}\cdot\mathbf{d}\big)\\ c &= \mathbf{d}^2 - r^2\\ \end{align*}$
If the discriaminant $abla = b^2-ac < 0$ , then the point completely misses the sphere, and we can conclude the test. Otherwise, we can find the time of first contact:
$t = \frac{(-b - \sqrt{ abla})}{a}$

Notice how the sign of $c$ tells us whether the point starts inside of the sphere, and the sign of $b$ tells us whether the point is moving away from the sphere. If $c$ and $b$ are both negative, then the point starts outside the sphere, and moves away from it, so they will never collide. Otherwise, if only $c$ is negative then the point starts inside the sphere, and the time of first contact $t = 0$ .

vec3 d = p - s;
float b = dot(v,d);
float c = dot(d,d) - r*r;
if (c > 0 && b > 0) return false; // Starts outside and moves away.
float a = dot(v,v);
float discr = b*b - a*c;
if (discr < 0) return false; // Miss sphere.
float t = max((-b - sqrt(discr))/a, 0);
if (t >= sweep->time) return false; // Miss sphere.
vec3 collision = p + t*v;
vec3 vec = collision - sc;
float len = length(vec);
sweep->time = t;
sweep->depth = t > 0 ? 0 : r - len;
sweep->point = collision;
sweep->normal = len >= EPSILON ? vec/len : nearestFaceNormal;
return true; // Point and sphere collide.

Note that if the point starts exactly on the center of the sphere, it will be impossible to calculate a collision normal. In this case we can just return the normal vector of the nearest face, which was calculated in one of the previous steps.

Caveats#

For the capsule against triangle sweep test I described here to work properly, the capsule and the triangle must not be degenerate. That means that the capsule must have a length, and the triangle vertices must not lie on a line.

If you need to handle degenerate capsules, you only need to modify the sweep tests against the 3 cylindrical edges formed when extruding the triangle into a prism. These tests need to be skipped if the two cylinder points are sufficiently close to each other. When the points are close, the dot product $(\mathrm{C}_1-\mathrm{C}_0)^2$ will be close to $0$ .

Handling degenerate triangles is a bit more annoying. If the triangle degenerates into a line, the cross product of its edges $(\mathrm{P}_1-\mathrm{P}_0)\times(\mathrm{P}_2-\mathrm{P}_0)$ will be close to a zero vector. You can detect this early on in the routine, and perform a swept capsule test against the line segment formed by the two most extreme vertices. If the triangle generates into a point, the dot product between these two most extreme vertices $(\mathrm{P_{max}} - \mathrm{P_{min}})^2$ will be close to zero. You can detect this too, and then perform a swept capsule test against a point instead.

Conclusion#

It took me a really long time and lots of research to learn how to devise my own collision tests. There isn’t a lot of information about this stuff out there right now. Hopefully this blog post was comprehensive and approachable enough to teach you how to do these things too.

You can find the full source code for the collision detection routine here.