64x64 icon dark hosting
Choose a hosting plan here and get a free year's subscription to Tuts+ (worth $180).
Advertisement

Collision Detection Using the Separating Axis Theorem

by
Gift

Start a hosting plan from $3.92/mo and get a free year on Tuts+ (normally $180)

The Separating Axis Theorem is often used to check for collisions between two simple polygons, or between a polygon and a circle. As with all algorithms, it has its strengths and its weaknesses. In this tutorial, we'll go over the math behind the theorem, and show how it can be used in game development with some sample code and demos.


Note: Although the demos and sourcecode of this tutorial use Flash and AS3, you should be able to use the same techniques and concepts in almost any game development environment.


What the Theorem States

The Separating Axis Theorem (SAT for short) essentially states if you are able to draw a line to separate two polygons, then they do not collide. It's that simple.

SAT collision detection

In the diagram above, you can easily see collisions occurring in the second row. However you try to squeeze a line in between the shapes, you will fail. The first row is exactly the opposite. You can easily draw a line to separate the shapes -- and not just one line, but a lot of them:

Lines separating shapes

Okay, let's not overdo this; I think you get the point. The key argument here is that if you can draw such a line, then there must be a gap separating the shapes. So how do we check for this?


Projection Along an Arbitrary Axis

basic idea of algorithm

Let's assume for now that the polygons we refer to are squares: box1 on the left and box2 on the right. It's easy to see that these squares are horizontally separated. A straightforward approach to determine this in code is to calculate the horizontal distance between the two squares, then subtract the half-widths of box1 and box2:

What if the boxes are not oriented nicely?

oriented boxes

Although the evaluation of the gap remains the same, we'll have to think of another approach to calculate the length between centers and the half-widths -- this time along the P axis. This is where vector math comes in handy. We'll project vectors A and B along P to get the half-widths.

Let's do some math revision.


Vector Math Revision

We'll start by recapping the definition of the dot product between two vectors A and B:

Dot product operation

We can define the dot product using just the components of the two vectors:

\[
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix}=
(A_x)(B_x)+(A_y)(B_y)
\]

Alternatively, we can understand the dot product using the magnitudes of the vectors and the angle between them:

\[
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix}=
A_{magnitude}*B_{magnitude}*cos(theta)
\]

Now, let's try to to figure out the projection of vector A onto P.

description of image

Referring to the diagram above, we know that the projection value is \(A_{magnitude}*cos(theta)\) (where theta is the angle between A and P). Although we can go ahead and calculate this angle to obtain the projection, it's tricky. We need a more direct approach:

\[
A. P=A_{magnitude}*P_{magnitude}*cos(theta)\\
A.\frac{P}{P_{magnitude}}=A_{magnitude}*cos(theta)\\
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=
A_{magnitude}*cos(theta)
\]

Note that \(\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}\) is actually the unit vector of P.

Now, instead of using the right side of the equation, as we were, we can opt for the left side and still arrive at the same result.


Application to a Scenario

Before we proceed, i'd like to clarify the naming convention used to denote the four corners of both boxes. This will be reflected in the code later:

naming conventions of points

Our scenario is as below:

projection of various lengths

Let's say both boxes are oriented 45° from the horizontal axis. We must calculate the following lengths in order to determine the gap between the boxes.

  • Projection of A on axis P
  • Projection of B on axis P
  • Projection of C on axis P

Take special note of the arrows' directions. While projection of A and C onto P will give a positive value, projection of B onto P will actually produce a negative value as the vectors are pointing in opposite directions. This is covered in line 98 of the AS3 implementation below:

Here's a demo using the above code. Click and drag the red middle dot of both boxes and see the interactive feedback.

For the full source, check out DemoSAT1.as in the source download.


The Flaws

Well, we can go with the above implementation. But there are a few problems -- let me point them out:

First, vectors A and B are fixed. So when you swap the positions of box1 and box2, the collision detection fails.

wrong vector selected

Second, we only evaluate the gap along one axis, so situations like the one below will not be evaluated correctly:

only one axis evaluated

Although the previous demo is flawed, we did learn from it the concept of projection. Next, let's improve on it.


Solving the First Flaw

So first of all, we'll need to get the minimum and maximum projections of corners (specifically the vectors from the origin to the boxes' corners) onto P.

projection of minimum and maximum of two boxes

The diagram above shows the projection of the minimum and maximum corners onto P when the boxes are oriented nicely along P.

But what if box1 and box2 are not oriented accordingly?

projection if boxes are not oriented accordingly

The diagram above shows boxes which are not neatly oriented along P, and their corresponding min-max projections. In this situation, we'll have to loop through each corner of each box and select the correct ones as appropriate.

Now that we have the min-max projections, we'll evaluate whether the boxes are colliding with each other. How?

Checking for collision

By observing the diagram above, we can clearly see the geometrical representation for projection of box1.max and box2.min onto axis P.

As you can see, when the's a gap between the two boxes, box2.min-box1.max will be more than zero -- or in other words, box2.min > box1.max. When the position of the boxes are swapped, then box1.min > box2.max implies there's a gap between them.

Translating this conclusion into code, we get:


Initial Code

Let's look at some more detailed code for figuring this out. Note that the AS3 code here is not optimised. Although it's long and descriptive, the advantage is that you can see how the math behind it works.

First of all, we need to prepare the vectors:

Next, we obtain the min-max projection on box1. You can see a similar approach used on box2:

Finally, we evaluate whether there's a collision on that specific axis, P:

Here's a demo of the implementation above:

You may drag either box around via its middle point, and rotate it with the R and T keys. The red dot indicates the maximum corner for a box, while yellow indicates the minimum. If a box is aligned with P, you may find that these dots flicker as you drag, as those two corners share the same characteristics.

Check out the full source in DemoSAT2.as in the source download.


Optimisation

If you'd like to speed up the process, there's no need to calculate for the unit vector of P. You can therefore skip quite a number of expensive Pythagoras's theorem calculations which involve Math.sqrt():

\[ \begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=
A_{magnitude}*cos(theta)
\]

optimisation

The reasoning is as follows (refer to diagram above for some visual guidance on variables):

Now, mathematically, the sign of inequality remains the same if both sides of the inequality are multiplied by the same number, A:

So whether it's a unit vector or not doesn't actually matter -- the result is the same.

Do bear in mind that this approach is useful if you are checking for overlap only. To find the exact penetration length of box1 and box2 (which for most games you'll probably need to), you still need to calculate the unit vector of P.


Solving the Second Flaw

So we solved the issue for one axis, but that's not the end of it. We still need to tackle other axes -- but which?

overlappings on axes

The analysis for boxes is quite straightforward: we compare two axes P and Q. In order to confirm a collision, overlapping on all axes has to be true -- if there's any axis without an overlap, we can conclude that there's no collision.

What if the boxes are oriented differently?

Click the green button to turn to another page. So of the P, Q, R, and S axes, there's only one axis that shows no overlapping between boxes, and our conclusion is that there's no collision between the boxes.

But the question is, how do we decide which axes to check for overlapping? Well, we take the normals of the polygons.

normals of boxes

In a generalised form, with two boxes, we'll have to check along eight axes: n0, n1, n2 and n3 for each of box1 and box2. However, we can see that the following lie on the same axes:

  • n0 and n2 of box1
  • n1 and n3 of box1
  • n0 and n2 of box2
  • n1 and n3 of box2

So we don't need to go through all eight; just four will do. And if box1 and box2 share the same orientation, we can further reduce to only evaluate two axes.

What about for other polygons?

normals of triangles and pentagons

Unfortunately, for the triangle and pentagon above there's no such shortcut, so we'll have to run checks along all normals.


Calculating Normals

Each surface has two normals:

calculating normals

The diagram above shows the left and right normal of P. Note the switched components of the vector and the sign for each.

left normals used

For my implementation, I'm using a clockwise convention, so I use the left normals. Below is an extract of SimpleSquare.as demonstrating this.


New Implementation

I'm sure you can find a way to optimise the following code. But just so that we all get a clear idea of what's happening, I've written everything out in full:

You'll see that some of the variables aren't necessarily calculated to reach the result. If any one of separate_P, separate_Q, separate_R and separate_S is true, then they are separated and there's no need to even proceed.

This means we can save a fair amount of evaluation, just by checking each of those Booleans after they've been calculated. It would require rewriting the code, but I think you can work your way through it (or check out the commented block in DemoSAT3.as).

Here's a demo of the above implementation. Click and drag the boxes via their middle dots, and use the R and T keys to rotate the boxes:


Afterthoughts

When this algorithm is run, it checks through the normal axes for overlappings. I have two observations here to point out:

  • SAT is optimistic that there'll be no collision between polygons. The algorithm can exit and happily conclude "no collision" once any axis shows no overlapping. If there were any collision, SAT will have to run through all the axes to reach that conclusion -- thus, the more collisions there actually are, the worse the algorithm performs.
  • SAT uses the normal of each of the polygons' edges. So the more complex the polygons are, the more expensive SAT will become.

Hexagon-Triangle Collision Detection

Here's another sample code snippet to check for a collision between a hexagon and a triangle:

For the full code, check out DemoSAT4.as in the source download.

The demo is below. Interaction is the same as in previous demos: drag via the middle points, and use R and T to rotate.


Box-Circle Collision Detection

collision with circle

Collision with a circle may be one of the simpler ones. Because its projection is the same in all directions (it's simply the circle's radius), we can just do the following:

Check out the full source in DemoSAT5.as. Drag either the circle or box to see them collide.


Conclusion

Well, that's it for now. Thanks for reading and do leave your feedback with a comment or question. See you next tutorial!

Advertisement