Separating Axis Theorem Collision Detection For Fun And Profit

Published by Jon on

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:

  1. Calculate the normals for each edge of both shapes
  2. Project each shape’s points onto all normal axes, store the minimum and maximum values for each and check for overlaps
  3. 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[0].x) + (axis.y * shape_points[0].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.

Acknowledgements

This explanation (and my project’s implementation) of SAT would not have been possible without this fantastic post on the dyn4j website.

Categories: programming