Separating Axis Theorem

Moving beyond the simple collision shapes we saw in Basic Collisions, we eventually may need to test for collisions against complex shapes. One of the most useful tools we can apply here is the Separating Axis Theorem, which states:

If an axis can be found upon which the projection of the two shapes does not overlap (a separating axis), then there can be no collision between the two shapes

Much like some of our earlier tests, instead of trying to show the shapes overlap, we instead try to prove that they do not. If we can't do that, then we know that there is no collision.

But just what axes do we need to test? There is, after all, an infinite number of axes to chose from... but a good answer can be found by looking at how we represent our collision shapes.

Representing Collision Shapes

One common approach is to represent the shapes as convex polygons, keeping track of the edges as vectors.

If the shape is best represented as a concave polygon, we would need to break it into two or more concave polygons, and test for collisions against each.

If our objects rotate, we would also need to rotate the collision polygons by rotating these vectors using a rotation method like the one in our vector library.

The key point to using convex polygons is that the minimal set of potentially separating axes we need to check to ensure we know if there is or isn't a collision is the set of all normals to the polygon's edges.

Finding the Edge Normals

The edges of our collision shape are the vectors between successive vertices. Since we're storing our vertices as vectors, this would be the vector difference between two adjacent vertex vectors. I.e., if a and b are two adjacent vertices, then a-b is the vector between them. Then we need to find the normal for this edge - a vector perpendicular to the two. This can be done by flipping the x and y values and inverting one of them - also a method in our vector library. Finally, to be a true normal, we must normalize the perpendicular vector, making it length 1. The resulting code would look like:

const Vector = require('./vector'); function findAxes(shape) { var axes = []; shape.forEach(function(p1, i){ // find the adjacent vertex var p2 = (shape.length == i+1) ? shape[0] : shape[i+1]; var edge = Vector.subtract(p2, p1); var perp = Vector.perpendicular(edge); var normal = Vector.normalize(perp); axes.push(normal); }); return axes; }

Note that we're assuming the parameter shape is an array of vectors representing the vertices of our collision shape.

Projecting a Shape onto an Axis

The Separating Axis Theorem guides us to look for an axis where the projections of the two shapes onto the potentially separating axis. This means we need to calculate the projection for each shape - which we can represent as the maximum and minimum point the projection reaches along the axis.

These can be found by projecting the individual vertices of the shape onto the axis. Normally, this would be a . (b / |b|), where a is our vector to project, and b is the axis to project on, normalized. Since our axis normal is already normalized, we simply take a . b:

function project(shape, axis){ var min = Vector.dotProduct(shape[0], axis); var max = min; for(int i = 1; i < shape.length; i++){ var p = Vector.dotProduct(shape[i], axis); if(p < min) min = p; else if(p > max) max = p; } return {min: min, max: max}; }

Testing for Collisions

Armed with the ability to create projections for our shapes onto an axis, the next step is to test for collision between shapes. We need to find the union of the sets of side normals for both shapes - this is our minimal set of axes to check.

To check, we calculate the projection for both shapes onto this axes, and then we determine if they overlap. If they don't, we have found a separating axis, and can exit early - there's no collision. Otherwise, once we have checked all of the axes, we can say the collision did occur. So our test looks like:

function testForShapeCollision(shape1, shape2) { var axes = findAxes(shape1) + findAxes(shape2); for(var i = 0; i < axes.length; i++) { var proj1 = project(shape1, axes[i]); var proj2 = project(shape2, axes[i]); if(proj1.max < proj2.min || proj1.min > proj2.max) { return false; } } return true; }

Special Cases

It is also interesting to consider our previous efforts at collision detection in light of the Separating Axis Theorem.

Consider circle-on-circle collisions. When we compare the distances between circles' centers to the sum of their radii, we are testing for a separating axis perpendicular to the line between their centers. In effect, we are projecting the two circles onto the vector between them, and seeing if they overlap. Since the line between the centers is the shortest distance between the two circles, this is the minimal set of axes we need to check.

Similarly, our rectangle-on-rectangle collisions consider the projection of the rectangles onto the x and y axes. As long as these rectangles are axis-aligned (i.e. parallel to the x and y axis), this is the minimal set of axes we need to check.