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 too 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 very 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’. It needs to be a unit vector, so when you calculate it, be sure to normalize it.
Something a bit like:
// points / verts in the geometry. Make sure they are in
let vertices = [ {x:1, y:1}, {x:1, y:-1}, {x:-1, y:-1}, {x:-1, y:1} ];
// get the perpendicular axis - you would need to loop over these...
let axis = {
x: -(vertices[1].y - vertices[0].y),
y: vertices[1].x - vertices[0].x
}
// be sure to normalize the axis by making it length to 1. You can do that with something like
let magnitude = Math.sqrt(Math.pow(axis.x,2), Math.pow(axis.y, 2));
if (magnitude != 0)
{
axis.x *= 1 / magnitude;
axis.y *= 1 / magnitude;
}
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)
// helper method for calculating the dot product of a vector
vectorDotProduct(pt1, pt2)
{
return (pt1.x * pt2.x) + (pt1.y * pt2.y);
}
// verts and axis from earlier...
// vertices = [ {x:1, y:1}, {x:1, y:-1}, {x:-1, y:-1}, {x:-1, y:1} ];
// axis = {x:1, y: 0}
// get an initial min/max value. you will need the min max for both shapes
let p1min = vectorDotProduct(axis, vertices[0]);
let p1max = min;
// loop over all the other verts to complete the range
for (let i =1; i < verts.length; i++)
{
let dot = vertices[i];
p1min = Math.min(p1min , dot);
p1max = Math.max(p1max , dot);
}
Step 3. Do the same for the second polygon.
Now you will have both sets of vertices projected onto the axis, which is good, but they will probably be overlapping at this point because we haven't taken into consideration the distance between the two objects. (I forgot about this step until I rewrote the code, hence the picture doesn't show it...) You can correct for this spacing issue by projecting the distance between the shapes onto the same axis, then adding it to one of the shapes projection. Something kinda like this:
// vector offset between the two shapes
let vOffset = { polygon1.x - polygon2.x, polygon1.y - polygon2.y };
// project that onto the same axis as just used
let sOffset = vectorDotProduct(axis, vOffset);
// that will give you a scaler value that you can add to the min/max of one of the polygons from earlier
p1min += sOffset;
p1max += sOffset;
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.
// quick overlap test of the min and max from both polygons
if ( (p1min - p2max > 0) || p2min - p1max > 0) )
{
// there is a gap - bail
return null;
}
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.
// presume with have some info
vertices = [ {x:1, y:1}, {x:1, y:-1}, {x:-1, y:-1}, {x:-1, y:1} ];
polygonPos = { x:0, y: 0}
circlePos = { x: 5, y:1}
circleRadiuis = 4;
// find the closest by doing a distance check
let minDist = Number.MAX_VALUE;
let closestDelta = null;
let axis = null;
for (let vert in vertices)
{
// make sure you are using the vert in the same space... this will depend on how you have the data set up
let worldVert = { x: polygonPos.x + vert.x, y: polygonPos.y + vert.y }
// delta between the circle and this vert in world space.
let delta= { x: worldVert.x - circlePos.x, y: worldVert.y - circlePos.y }
// use pythagoras theorem to get the distance - you can skip the sqrt because we don't need the true distance in this check
let dist = Math.pow(delta.x, 2) + Math.pow(delta.y, 2));
if (dist < minDist)
{
minDist = dist;
closestDelta = delta;
}
}
// you can now convert the closest delta into a unit vector axis
let magnitude = Math.sqrt(Math.pow(closestDelta.x,2), Math.pow(closestDelta.y, 2));
if (magnitude != 0)
{
axis.x = closestDelta.x * (1 / magnitude);
axis.y = closestDelta.x * (1 / magnitude);
}
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.
// props from earlier
// axis = {x:1, y: 0}
// circleCenter = {x:5, y:1 }
// project the center
let temp = vectorDotProduct(axis, circleCenter );
// calc the range using the radius
let circleMin = temp - circleRadius;
let circleMax = temp + circleRadius;
// Now use this range to do the overlap test described earlier...
Pros and Cons
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 the code for my interactive demo, you can grab them from my SAT_JS GitHub Repo. It is in no way optimised but should serve as a good example of the above explanation.
(The original AS3 version is also available is you are so inclined)
Basically, you create two shapes from the (SATPolygon or SATCircle classes) and then test them with the static 'SAT.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.
The SATDemo class contains all the logic for creating the demo shown earlier in this post.
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.
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 🙂
emm.. 10x 🙂
Explained in a very simple way. Liked it and will be referencing your article when I publish my own story.
Thanks 🙂
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. ;(
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.
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 🙂 )
The problem seems to be that the axis given for separation is the wrong one, any help?
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
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 !
Ah yes – you are absolutely correct. I’ve fixed that now – thanks for that 🙂
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.
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
This is a great explanation, thanks!
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.
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.
Thanks a lot, this has been really helpful!
Thanks for the article it was really helpful in better learning of SAT.
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.
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?
I agree with meming – Great tutorial, but a simple useage example is always nice!
I can get circle and box working, but not polygon. How do I create a basicPolygon?
Ah I got it!
var shape = new Polygon();
shape = Polygon.basicPolygon();
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.
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.
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,
Hi,
I have proven the circle is a binary polygon,therefore:
Your work can be completed with my theory.
Thank you,
Giuseppe Stagno
I read several articles on this topic before coming here. This article is the first one where it all really started to click for me. Thank you!
Hi this is a good article, thank you. One thing with SAT that I didn’t see mentioned here. You may find objects passing through each other if they are going too fast. This is fixed by solving for t in
||(P0 + tV0) – (P1 + tV1)|| = R0 + R1 where the distance between the centers of the interval extents of your smashed points is equal to the sum of their radii.
Hi a very good article but my main problem is, that I don’t know how to calculate the sides of an rotated rectangle… I don’t know how to get the corners of it to calculate the sides and I don’t know where to find a solution to that.
Hey Proxtx, I haven’t looked at this code in a long time and my 2d math is pretty rusty, and I am falling asleep, but I’ll try and point you in the right direction.
The way I usually do stuff like this is to start by thinking of the shape’s points in a local space when there is no rotation / scaling, etc. So, a 1unit square with the registration point at the center would be something like (-0.5, -0.5), (0.5, -0.5), (0.5, 0.5) and (-0.5, 0.5).
Now that you have them in that space, you can apply a rotation to them. Depending on what language / libraries you are using, you could do this using trigonometry math or perhaps a 2d matrix transformation. I would use the matrix because you can apply scale, etc. in one action.
Once that is done, you can update all of the points to their world position by adding the registration point’s position to them.
Now that everything is in world space, you should be able to calculate the edges/angles by subtracting one corner from another.
I hope that make sense a bit of sense. Google stuff like ‘2d math rotate point around origin’ or ‘2D matrix rotation’ and you should get some better descriptions than what I can give you.
Best of luck!
Great article, although I had to point out:
“From a programming point of view it would be *to(o) 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.”
Sorry to be that guy, but you deserve to look as professional as possible. I got linked here from MDN Web Docs, which is… quite an endorsement by the programming community.
I also like it. And also the library. But for that I’ve a question (because it isn’t working as expected).
I have two rectangles (i.e. [100/100, 135/100, 135/169, 100/169], [200/100, 235/100, 235, 269, 200,269]
As you can see, they don’t touch 🙂 but when I create it with a SATPolygon with x/y=100/100 and 200/200 and the list of points I added at the top, it ever says I have a collision. So how do I need to create the vertices and the main point?
Hey TSS, I’m not entirely sure what is going on there. I fired up the demo and hardcoded in the co-ords you gave and it didn’t give me a collision. Without seeing any code, my guess would be that the vertices are possibly in the wrong space.
The x and y props on the SATPolygon is where the registration point / rotation point of the shape is located in world space.
The vertices you add to to the SATPolygon are meant to be local to the that registation point.
So, a shape at (100,100) with vertices [(-10, 20), (10, 20), (10, -20), (-10, -20) ] would translate to a rectangle in worldspace [(90, 120), (110, 120), (110, 80), (90, 80)] – of course, and rotation / scale changes would alter these world space values.
Like I said though, I am just guessing this is the problem. Hopefully it can put you on the right track for figuring out what is going on.
@Andrew – Thanks for the help. Your description did help me. I fixed the vectors (a small description what is expected here would be nice) and also found out that the “rotation” was set wrong – what was the 2nd problem. After that it is working. Good Job!
Hi, I’ve implemented this in C, but I’d like to know what vectors to push back each polygon so that they un-intersect themselves. I’ve been working on this problem for hours and I can’t figure out what to do.
Thanks in advance
@Jia – I just took a quick glance at teh code to refresh my memory. I believe that the vector and distance you are looking for would be whatever is being stored in the ‘result.distance = distMin’ and ‘result.vector = axis’.
If you was using polygon shaped like me, you want to apply this to the polygon’s position and not the individual verts, as they are local to the polygon’s position.
I’m not sure, but you may need to reverse either the vector or the distance value – they be measuing the overlap, and hence removing the overlap would require you to go the other way.
I hope all that makes sense 🙂 Best of luck!