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:

Interactive Demo should be here

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.

{lang: 'en-GB'}
Posted in ActionScript | Tagged , , , | 27 Comments

27 Responses to Separating Axis Theorem (SAT) Explanation

  1. Jengerer says:

    This helped a lot. You should include that you have to cycle through all of the sides of that one polygon you choose in Step 1. From one “shadow” it could look like it’s colliding, but from a perpendicular, it might look otherwise.

  2. Andrew Sevenson says:

    Glad it helped – and thanks for the tip. It is a very valid point. I will add that is as soon as I get the chance :)

  3. emm.. 10x :)

  4. Priyank says:

    Explained in a very simple way. Liked it and will be referencing your article when I publish my own story.

    Thanks :)

  5. ant says:

    This explains the SAT very well, although your version works, when I try and make my own version using a custom polygon class it doesnt seem to work, I think im missing something but im not sure what. ;(

  6. Hey Ant, sorry to hear that you are having trouble. When you say that you are you are using your own version, do you mean your own sat classes as well? Or are you using my code and it is not working?
    If you are writing you’re own, it could be a number of things – the thing that always tripped me up was that I always forgot to convert the vector normal to a unit vector before projecting the sides of the polygons.

  7. Will says:

    I’m writing an implementation of this, and I can’t figure out how to find the vector that separates the shapes (called collisionInfo.separation in your implementation). Having just read through your version, trying to write your way of finding it, and watching my two shapes fly right through each other, I was wondering if you could provide some light on this topic.

    BTW the original implementation that I based mine upon could be found here (if you could put how it works in the wiki, that’d be awesome :) )

  8. Will says:

    The problem seems to be that the axis given for separation is the wrong one, any help?

  9. Hi Will,

    I had a quick look at the implementation you posted. It appears to be checking for a collision only, and not actually figuring out how to separate them. If you were to use the ‘axis’ property directly after that method you would always get the last axis that was tested, which is not necessarily the the shortest path of separation.

    To get the right axis, you would have to keep track of which axis had the shortest amount of overlap. This should be as simple as having another vector variable declared and checking it each time an axis is tested. If you get to the end and there is a collision, simply use the vector you have stored for the separation.

    At least, that is how my code works.

    Hope that helps

  10. Vanderful says:

    Great tuto !

    Just some details:
    In your first sentence you talk about concave polygons instead of convex ones.
    The axis to be kept is the one which has the minimal overlap (not the greatest).

    Anyway, really nice work !

  11. Ah yes – you are absolutely correct. I’ve fixed that now – thanks for that :)

  12. wwwebber says:

    Great post…question, I used your code as a basis for my own SAT test..question though–what is the purpose of sOffset and vOffset? Intersection tests in my version, work perfectly, without using either of these.

  13. Hmm – good question. Its been a while since I wrote it so I had to have a look at the code again.
    At a quick glance it looks like the vOffset is the vector between two shapes, and the sOffset seems to be a scalar used to calc the projected points of the second shape. I can’t remember exactly why it is there – my instinct is that it would be to keep the objects in the same coordinate space – but if yours works without it, maybe it isn’t needed :p

  14. Adam Baker says:

    This is a great explanation, thanks!

  15. Adam Baker says:

    In fact, now I have some feedback: it would be worth emphasizing more that it’s necessary to use normals from *both* polygons as axes.

  16. meming says:

    I totally understand whats going on, its just I dont know how to put this in code, I give this tut a 90% ( which is great ) but if you put a little code under each step, (especially when we create the “axis”) this would get an instant 110%. You wont have to reply to this, ill just spend an hour on google, but future viewers will want the same.

  17. dmc says:

    Thanks a lot, this has been really helpful!

  18. vladab says:

    Thanks for the article it was really helpful in better learning of SAT.

  19. dysseus88 says:

    Thanks for this powerfull code. It will be very helpful to me and I see I am not the first. I was looking for solid explanations about SAT and thanks to you, I know this is exactly what I should use. Please, could you publish source code of the above demo ? I tkink it would be easier for everyone to use your library in the future by analyzing this example.

  20. Dave says:

    Nice work!

    Just thinking though – is all that shadow detection really necessary? What about:

    1) I know the centroid (middle) of the two polygons
    2) I know the angle and length of the line between the two centroids (hypot of a triangle)
    3) I can work out the point that’s closest to the other shape on one object.
    4) I can use that point and the hypot to create a plane (using a line equation) that sits against my first shape but perpendicular to the hypot.
    5) And then I can test if any points in the other shape are beyond that line – maybe by checking against the lines normal value (dot or cross product – I always get them confused)?

    I don’t know if that’s any faster – just musing. Seems like more math but less work and no loops?

  21. Andy says:

    I agree with meming – Great tutorial, but a simple useage example is always nice!

  22. Andy says:

    I can get circle and box working, but not polygon. How do I create a basicPolygon?

  23. Andy says:

    Ah I got it!
    var shape = new Polygon();
    shape = Polygon.basicPolygon();

  24. Matt says:

    In your article you mention that this technique does not provide the features of the two colliding objects. This is not true. This technique can be easily extended to provide the features of each object for further processing i.e. finding actual contact points.

  25. Pingback: How to resolve collisions of compound shapes using SAT? | Q&A System

  26. the guy says:

    i completly agree with meming.

    when he said u should write down a little code after the line. i understand everything except the axis part. I understand it. I just dont know how to put it into code.

  27. Krystian says:

    I’m not completely sure, but IMHO it is not very fast. For now I can’t see any way to implement this faster than O(nm) (n – number of vertices in 1st polygon, m – the same for 2nd). If you want algorithm only for convex polygons (like this) you can sort vertices in one polygon by angle (around the Center of Mass), and do binary search for each vertex of 2nd polygon (and then swap polygons and repeat), using cross product to check, if a point lies in a certain triangle (CM + one edge). This gives O((n+m) log(nm)). However, this theorem is good for some divide and conquer algorithm for simulations with loads of relatively small figures,

Leave a Reply

Your email address will not be published. Required fields are marked *


8 − = one

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>