Separating Axis Theorem
The Separating Axis Theorem (SAT) provides a way to find the intersection between any n-sided convex polygon or circle. In this tutorial, I will explain how this theorem works, and how you can use it to both detect and resolve collisions in your simulation.
Explanation of Separating Axis Theorem
SAT makes use of vector projection to figure out whether or not two concave polygons are intersecting. I believe the best way to describe it is to show you the instance where two polygons do not intersect.
Images two shapes A and B as shown below (they are triangles here, but they can be anything really).
We know inutitively that if we were able to draw a line between the two objects, that means that they're not intersecting. In this case, that line is a vertical-ish line:
That line could be any of the infinite number of lines between the objects, so we can't really select that exact line. So the problem becomes: how do we infer that the vertical line shown in the previous diagram is a line that splits the objects? That is where the Separating Axis Theorem comes in.
To do separating axis theorem, we iterate all of the edges of both shapes. For each edge, we get the normal at that edge (In two-dimensions, this amounts to getting the perpendicular of the line segment defined by the two points of the edge).
We then, in our heads, extend this normal to create an axis across our scene (keep in mind that you won't have to do any "extending" of this axis in code; the normal will do just fine).
At this point, you will see that I named the three vertices on each of the triangles. Triangle A is made of vertices a1, a2, a3 and triangle B is made of vertices b1, b2, b3. At this point, we project the shape onto the axis. To do this, we project the vertices of each shape onto the axis to figure out which one maximizes the dot product and which one minimizes the dot product. The projection of the shape is then the range defined by this min and max value.
Finally, we check if the two ranges overlap. If they don't overlap, then the shapes do not intersect. If they do overlap, we repeat the process for all of the other edges. If all of these ranges overlap, then the shape overlaps, and there is no separating line between them.
Algorithm for Finding the Intersection
Given two polygons A and B:
- For each edge on A, get the normal n of that edge.
- Project each vertex v of A onto n. Return the minimum and maximum projection of all vertices as the projection of the shape.
- Repeat Step 2 for polygon B.
- If the min and max projections found in Steps 2 and 3 do NOT overlap, the polygons are not intersecting. Return false.
- If the projections overlap for each edge of both shapes, the shapes are intersecting. Return true.
Vector2 getProjection(Vector2* vertices, int numVertices, Vector2 axis) {
// Find the min and max vertex projections
float32 min = axis.dot(vertices[0]);
float32 max = min;
for (int v = 1; v < numVertices; v++) {
float32 d = axis.dot(vertices[v]);
if (d < min) {
min = d;
} else if (d > max) {
max = d;
}
}
return Vector2 { min, max };
}
bool projectionsOverlap(Vector2 first, Vector2 second) {
return first.x <= second.y && second.x <= first.y;
}
bool doIntersect(ConvexPolygon* first, ConvexPolygon* second) {
IntersectionResult ir;
// Check agaisnt the edges of the first polygon
for (int i = 0; i < first->numVertices; i++) {
Vector2 normal = first->edges[i].normal;
Vector2 firstProj = getProjection(first->transformedVertices, first->numVertices, normal);
Vector2 secondProj = getProjection(second->transformedVertices, second->numVertices, normal);
if (!projectionsOverlap(firstProj, secondProj)) {
return false;
}
}
// Check against the edges of the second polygon
for (int i = 0; i < second->numVertices; i++) {
Vector2 normal = second->edges[i].normal;
Vector2 firstProj = getProjection(first->transformedVertices, first->numVertices, normal);
Vector2 secondProj = getProjection(second->transformedVertices, second->numVertices, normal);
if (!projectionsOverlap(firstProj, secondProj)) {
return false;
}
}
return true;
}
SAT Collision Resolution
Now that we know our objects have intersected, we want to be able to send them tumbling away from each other to simulate a collision. To do this, we will need to find the following things:
- Collision Normal: in what direction, point towards object A, did the polygons intersect
- Point of Application: at what point on each object did the objects first intersect
- Relative Velocity: easily found by taking the difference between the two velocities.
Collision Normal