September, 2025

SAT Collision Detection

Collision detection using separating axes.

Collision detection involves determining how objects overlap in 3D space. There are different techniques, I describe here a technique which uses the separating axis theorem (SAT) and is suitable for convex polyhedra with a small number of edges.

The SAT is given by Wikipedia as:

Two closed convex objects are disjoint if there exists a line ("separating axis") onto which the two objects' projections are disjoint.

In other words, if two convex object's don't overlap we can create a plane between the two objects. This works in any dimension.

A line, perpendicular to the separating axis, can be drawn which separates the two convex shapes, they cannot be overlapping.

The SAT immediately suggests an algorithm for collisions detection.

Loop through all separating axes
Project each shape onto the axis, forming two segments
If the segments do not overlap then neither do the objects

Additionally, in the case the shapes do overlap, we want to know the penetration axis (the normal at the initial contact manifold) and the penetration distance (how far along penetration axis we need to move the shapes apart). These quantities can be found by a small modification on the algorithm to keep track of the minimum overlap.

If the segments overlap then calculate the overlap size
If , replace and the penetrating axis

After handling all axis, is the penetration distance and we know the penetration axis. This assumes objects were moving along approximately straight paths between collision checks, which is generally reasonable.

Projection step

We can projecting a shape onto the separating axis, since it is convex it will form a line segment.

For polytopes, we loop through each vertex position in world space and project onto the separating axis , . The line segment is then . For non-polytopes, we may be able to find the segment directly. For example, a sphere with center and radius will form the segment .

One we have the two segments and we can determine if, and how they overlap. There are four cases (noting the order of the shapes is important here).

We can organise these overlaps into two sets of conditions:

: The objects overlap
: Move the red object to the left of the blue

If we need to move the red object to the left then it's penetration axis is and the blue's is . If we need to move to the red object to the right, then the axes are flipped. In either case the penetration distance .

Choosing Separating Axes

We choose a separating axis perpendicular to each edge, in this case the right-most edge of the red shape.

A major problem with the algorithm as presented is that there are an infinite number of possible penetrating axis, which is intractable. Fortunately, for polygons (and other simple shapes) we only need to check a few of these axes. In 2D, we only need to check each direction which is perpendicular to an edge of either one of the shapes.

Two cases, left: a separation axis perpendicular to a face; right: a separation axis perpendicular to an edge pair.

In 3D, we check axes normal to each face of the polyhedra. Additionally, to detect edge on edge collision, we need to check the axis perpendicular to each pair of edges between the two polyhedra. For an edge pair with directions , , the separting axis . Unfortunately, this means the number of possible axes is for the polyhedra edges, which is large for complex polyhedra.