Separating Axis Theorem (SAT) Explanation

Separating Axis Theorem (SAT) is a technique for calculating collisions between convex polygons.

I’m by no means an expert on it, but after the need arose for me to do some collision detection I did a pile of reading and finally got it working in ActionScript 3.

I thought I would share what I learned in the hope others wouldn’t suffer so much

When I found myself in a need to calculate collisions between polygons in flash, I came across a method known as Separating Axis Theorem (SAT). The only problem I had was that I really struggled to get a grasp on it.

After a lot of reading about collision detection, and looking at code samples, it all finally clicked.

To help out the other non-maths minded people I thought I would write this quick explanation to run through the basic principles of how it works. I’ve also included a demo using SAT collision detection, as well as some ActionScript 3 classes you can download and use.

Note: SAT does require a bit of work with vector math, so it may be a good idea to brush up on your vectors before getting too far into SAT.

Interactive Demo:

Use your mouse to drag the shapes around. Whilst dragging, use the arrow keys to change the scale and rotation of the shapes. When the two shapes collide they will change colour (red) and show a possible reaction (grey).

The quick rundown

Basically, the goal of SAT (and every other collision detection) is to test and see if is a gap between two shapes. The method that SAT uses is what makes it unique.

The best analogy I have heard for SAT technique is like this:

Imagine taking a torch and shining it on the two shapes you are testing from different angles. What sort of shadows would it cast on the wall behind it?

If you work your way around the shapes and never find a gap in the shadows then the objects must be touching. If you find a gap, then they are clearly not touching.

From a programming point of view it would be to intensive to check every possible angle. Luckily, due to the nature of the polygons, there is only a few key angles you need to check.

The angles you need to check are the same as the sides of the polygons. This means that the maximum number of angles to check is the sum of the number of sides the two shapes you are testing have. Eg. Two pentagons would require ten angles to be checked.

So how do you make it work in code?

It’s a simple but repetitive method, so here is a basic step by step:

Step 1. Take one side from one of the polygons you are testing and find the normal (perpendicular) vector from it. This will be the ‘axis’.

Step 2. Loop through every point on the first polygon and project it onto the axis. (Keep track of the highest and lowest values found for this polygon)

Step 3. Do the same for the second polygon.

Step 4. Check the values you found and see if they overlap.

If you find a gap between the two ’shadows’ you have projected onto the axis then the shapes must not intersect. However, if there is no gap, then they might be touching and you have to keep checking until you have gone through every side of both polygons. If you get through them all without finding a gap then they collide.

That’s basically it.

As an added bonus, if you keep track of which axis has the smallest shadow overlap (and how much of an overlap that was) then you can apply that value to the shapes to separate them.

What about circles?

Testing a circle against a polygon in SAT is a little bit strange but it can be done.

The main thing to note is that a circle does not have any sides so there is no obvious axis that you can test against. There is one ‘not so obvious’ axis you do need to test however. This is the axis that runs from the centre of the circle to the closest vertex on the polygon.

After that it is just a matter of going through the usual routine of looping through every axis on the other polygon and checking for overlaps.

Oh, and in case you are wondering how to project a circle onto the axis, you simply project the centre point of the circle and then add and subtract the radius.

Pro’s and Con’s

Like all collision detection techniques, SAT has it’s pro’s and cons. Here is a quick rundown of some of them:

Pros

• It is fast – It uses pretty basic vector math and you can bail out of a test as soon as a gap is detected, eliminating unnecessary calculations.
• It is accurate – at least as far as I can tell.

Cons

• It only works with Convex polygons – complex shapes are out unless you build them out of smaller convex shapes, and then test each individual shape.
• It doesn’t tell you which sides are touching – only how far they are overlapping and the shortest distance to separate them.

There is probably a bunch more but these were the main ones I could think of.

Conclusion

I hope that this has helped to shed some light on the separating axis theorem. I’ve tried to keep it as simple as possible without shedding too much information. (I’m by no means an expert in maths so I apologise if I left anything out)

Here are a few links to other pages that helped me understand SAT collision detection.

• harverycartel.org – more detailed descriptions and some cool interactive examples. I learnt a lot from this page.
• GPWiki.org - good SAT explanation and sample code – I used this as a basis for creating my own code.
• Tony Pa – Vector tutorials – Good resource for learning about Vectors
• GameDev.net forum – a SAT collision system a member created – gave me some ideas on how to calculate reactions, etc.

Download:

If you want to see my AS3 SAT classes you can download them here: SAT AS3 Classes (They are a bit of a mess, but they work)

Basically, you create two shapes and then test them with the ‘Collision.test()’ method. If they touch then a ‘CollisionInfo’ object will be returned. If they don’t touch then it will return ‘null’. The CollisionInfo object has a bunch of information about the collision that can be used to separate the two objects, etc.

I tagged this with: ActionScript, AS3, Flash, Programming