Separating Axis Theorem Collision Detection For Fun And Profit
This month I ran into a fairly large brick wall with my 2D collision detection code. Up until recently I had been using exclusively axis aligned bounding boxes (AABBs).
For a project I’m currently working on I finally ran face first into the limitations of this method. The main issues were that AABBs don’t support rotation well and are difficult to perform collision checks with other shapes. Luckily I found an alternative solution through the separating axis theorem.
The Separating Axis Theorem
The theorem states that if you can draw line between two convex shapes, they cannot be colliding. The point I’d like to highlight here is convex shapes. This does not work with concave shapes unless you split them into convex ones and test those. It also works with any convex shape at any orientation.
How does it work?
The theorem can be split into three stages for implementation:
- Calculate the normals for each edge of both shapes
- Project each shape’s points onto all normal axes, store the minimum and maximum values for each and check for overlaps
- If all projections overlap then the shapes are colliding
Let’s break down each step.
1. Calculate the normals for each edge of both shapes
Using the points representing the vertices of the shape calculate the edges. Then get the perpendicular vector/normal vector of each edge and store it. These are the axes that will be used for projection.
The pseudocode for doing it for one shape something like this:
normals =  //place to store the normals FOREACH vertex IN shape_vertices DO next_vertex_index = current_vertex_index + 1 //get the next vertex index IF next_vertex_index > shape_vertices.size DO next_vertex_index = 0 //if we've hit the last index reset the next vertex index to 0 ENDIF next_vertex = shape_vertices[next_vertex_index] //sets the next vertex value edge_vector = next_vertex_index - vertex //get the edges by subtracting normal = (edge_vector.x, -edge_vector.y) //gets perpendicular normals.append(edge_vector) ENDFOR
2. Project each shape’s points onto all normal axes, storing the minimum and maximum for each and check for overlaps
After calculating the all of the axes, cycle through each shape’s axes and project both shapes’ points onto them. Since we are working in 2D this is basically projecting them onto a 1D axis where the minimum and maximum values are the start and end of a line.
The pseudocode for this would roughly be:
FOREACH axis IN shape1_normals DO //projects the shapes along the given axis projection1 = projectShape(shape_points1, axis) projection2 = projectShape(shape_points2, axis) IF NOT (overlaps(projection1, projection2)) DO RETURN FALSE //returns false if there is no overlap END IF ENDFOR FOREACH axis IN shape2_normals DO //projects the shapes along the given axis projection1 = projectShape(shape_points1, axis) projection2 = projectShape(shape_points2, axis) IF NOT (overlaps(projection1, projection2)) DO RETURN FALSE //returns false if there is no overlap END IF RETURN TRUE ENDFOR
The projection and overlap pseudocode is below:
FUNCTION projectShape(shape_points, axis) minimum = (axis.x * shape_points.x) + (axis.y * shape_points.y) //sets minimum to a default maximum = minumum //sets the maximum to a default FOREACH point IN shape_points DO projection = (axis.x * point.x) + (axis.y * point.y) //projects the point IF projection < minimum DO minimum = projection //sets the minimum to the projection as needed ENDIF IF projection > maximum DO maximum = projection //sets the maximum to the projection as needed ENDIF ENDFOR RETURN float2(minimum, maximum) //returns the minimum and maximum ENDFUNCTION FUNCTION overlaps(projection1, projection2) IF (projection1.maximum < projection2.minimum) OR (projection2.maximum < projection1.minimum) DO RETURN FALSE //returns false if no overlap ENDIF RETURN TRUE ENDFUNCTION
3. If all projections overlap then the shapes are colliding
For the shapes to be colliding then all the projections must be overlapping. This means that the collision detection function can immediately exit when it finds two projections that don’t overlap, as shown in the pseudocode above.
Optimization and Additional Notes
One particularly good optimization for SAT collision is that parallel edges do not need to be tested. For example, 2 rectangles by default would require 8 checks (4 edge normals * 2 shapes), but when removing parallel edges this becomes 4 checks. This is definitely something to take into account.
Curved shapes like circles don’t really play nice with SAT collision detection. There are methods of dealing with this, but they are outwith the scope of this blog post. I’d recommend checking out the acknowledgements for more in depth information.
Bear in mind that this method of collision detection is one of many. Implementing SAT is more complicated than implementing axis aligned bounding boxes or bounding spheres/circles. Don’t over complicate things if you don’t have to.
This explanation (and my project’s implementation) of SAT would not have been possible without this fantastic post on the dyn4j website.