Separation of Axis Theorem (SAT) for Collision Detection

The separating line and axis form a 90 degree angle.

The Separation of Axis Theorem(SAT) is a technique to test whether two convex polygons are colliding. The SAT theorem: “given two convex shapes, there exists a line onto which their projections will be separate if and only if they are not intersecting.” The line where the shapes have disjoint projections is called the separating axis.

A separating line is the line that can be drawn between the two shapes, without touching either shape. Because flash is 2D, I will only be showing this method for 2D, but it can be done in 3D(in 3D, its called the separating plane theorem). 2D also means less math, so it will run fast.

How SAT Works

When you shine the light from the top, you can clearly see the gap.

The SAT method, like all collision detection, tests to see if there is a gap between the two shapes or if the two shapes are touching(i.e. are the shapes colliding or not).

SAT works like this: imagine you have a flash light. You take your flashlight and shine it at the two shapes. Fisrt, you shine it from the left. You look at the wall, and you see no gaps. The shapes might be colliding, but uou cannot tell yet.

If there was a gap here, you could be positive that the two shapes were not touching. Because you cannot tell for sure, you must continue on and test other sides.

However, when you shine your flashlight from the top, and look on the floor, you can see a spot where the light hits the floor. If the shapes were colliding, you would not see any light on the floor. Therefore, the shapes must not be colliding. You can move on to test other shapes.

What about rotation?

What if the shapes are rotated?

What if one of the shapes was rotated? What if both were rotated?

Well, the SAT method has a simple way to check this. You only need to check as many sides as both objects have combined. In the previous example(with the triangle and square), you would only need to perform 3(triangle has 3 sides)+4(square has 4 sides) = 7 checks. For a hexagon and decagon, it would be 6(hexagon)+10(decagon) = 16 checks. This may sound like a lot, but remember, if you ever see the light between the objects, you can stop right there and be sure they aren’t colliding(this can be further optimized with a broad phase, which we’ll talk about later).

Just one caveat!

Concave shapes will give a false positive.

Concave polygons must be made of convex polygons to work.

This method will only work with convex polygons.

Why? Because if you shine a light from the top of the blue shape, you would never know there is a hole in the middle. The light would hit the top part, and the middle would appear dark(like a shadow), and the computer would assume that the shapes are colliding in that spot.

But you can fix it! All you need to do is compose the desired concave polygon out of multiple convex polygons.

Coding the SAT

Now that we’re done with the theory, lets put this into code!

The SAT method makes use of vectors. If you don’t know about vectors, you might want to go read up on them a bit. I have a nice Vector2D class that we will use(flash 10 does provide a Vector3D class, but most of those features we don’t need).

Download Vector2D.as

Step 1: Take the current side and find its normal. This will be the axis you will test.

Step 2: Project all the points, of both shapes, onto the axis, keeping track of the maximum and minimum values for each shape. The max and min values are used to determine if the objects are overlapping.

A rotated square projected onto a line.

There is some math to projection.

Since you are projecting the point onto a line, the scalar is the point’s the distance along the line.

A square and triangle projected onto a line.

Step 3: Now all you have to do is check the value of the project points to see if they overlap. Now remember we stored the min and max value for each shape? That’s how we test for an overlap. Lets say the square had a max of 8 and a min of 4 and the triangle had a max of 12 and a min of 9. Since the triangle’s min(9) is greater than the square’s max(8), they aren’t colliding. But what if the triangle had a max of 8 and a min of 4 and the square had a max of 12 and a min of 9? The triangle’s min(4) is less than the square’s max(12) so they should be colliding, but they aren’t. You also have to test if the square’s min(9) is less than the triangle’s max(8). Since 9 < 8 is false, they aren’t colliding. If the square’s min was 5 and its max was 10, and the triangle’s mine was 6 and its max was 8, then we would know they are colliding. The square’s max(10) > the triangle’s max(8) and the triangles min(6) > the square’s min(5).

What about circles?

Because circles have no lines, they won’t work with that method. But you can use circles. All you have to do is break it into circle vs. circle checks and circle vs. polygon checks. A circle vs. circle check is just a normal distance check.

For circle vs. polygon checks, its a bit more complex. What axis do you test on? You have to test on the axis from the circles center to the nearest vertex on the polygon.

The code

We’ll start out with the easy stuff, circle vs. circle.

var totalRadius:Number = circle1.radius+circle2.radius; //add both radii together to get the colliding distance
var distanceSquared:Number = (circle1.x-circle2.x)*(circle1.x-circle2.x)+(circle1.y-circle2.y)*(circle1.y-circle2.y); //find the distance between the two circles using Pythagorean theorem. No square roots for optimization

if(distanceSquared < totalRadius*totalRadius){ //if your distance is less than the totalRadius square(because distance is squared)
var difference:Number = totalRadius-Math.sqrt(distanceSquared); //find the difference. Square roots are needed here.
return new Vector2D((circle2.x - circle1.x)*difference, (circle2.y - circle1.y)*difference); //find the movement needed to separate the circles
}
return null; //no collision, return null

Circles are pretty easy. Next, and slightly more difficult, is polygon vs. polygon checking. This is were we will actually use the SAT method!

var test1:Number;// numbers to use to test for overlap
var test2:Number;
var testNum:Number; // number to test if its the new max/min
var min1:Number; //current smallest(shape 1)
var max1:Number;//current largest(shape 1)
var min2:Number;//current smallest(shape 2)
var max2:Number;//current largest(shape 2)
var axis:Vector2D;//the normal axis for projection
var offset:Number;
var vectorOffset:Vector2D;
var vectors1:Vector.<Vector2D>;//the points
var vectors2:Vector.<Vector2D>;//the points
vectors1 = polygon1.vertices.concat();//these functions are in my polygon class, all they do is return a Vector.<Vector2D> of the vertices of the polygon
vectors2 = polygon2.vertices.concat();
// add a little padding to make the test work correctly
if (vectors1.length == 2) {
var temp:Vector2D = new Vector2D(-(vectors1[1].y - vectors1[0].y), vectors1[1].x - vectors1[0].x);
temp.truncate(0.0000000001);
vectors1.push(vectors1[1].add(temp));
}
if (vectors2.length == 2) {
temp = new Vector2D(-(vectors2[1].y - vectors2[0].y), vectors2[1].x - vectors2[0].x);
temp.truncate(0.0000000001);
vectors2.push(vectors2[1].add(temp));
}
// find vertical offset

vectorOffset= new Vector2D(polygon1.x - polygon2.x, polygon1.y - polygon2.y);

// loop to begin projection
for (var i:int = 0; i < vectors1.length; i++) {
// get the normal axis, and begin projection
axis = findNormalAxis(vectors1, i);

// project polygon1
min1 = axis.dotProduct(vectors1[0]);
max1 = min1;//set max and min equal

for (var j:int = 1; j < vectors1.length; j++) {
testNum = axis.dotProduct(vectors1[j]);//project each point
if (testNum < min1) min1 = testNum;//test for new smallest
if (testNum > max1) max1 = testNum;//test for new largest
}

// project polygon2
min2 = axis.dotProduct(vectors2[0]);
max2 = min2;//set 2's max and min

for (j = 1; j < vectors2.length; j++) {
testNum = axis.dotProduct(vectors2[j]);//project the point
if (testNum < min2) min2 = testNum;//test for new min
if (testNum > max2) max2 = testNum;//test for new max
}

// apply the offset to each max/min(no need for each point, max and min are all that matter)
offset = axis.dotProduct(vectorOffset);//calculate offset
min1 += offset;//apply offset
max1 += offset;//apply offset

// and test if they are touching
test1 = min1 - max2;//test min1 and max2
test2 = min2 - max1;//test min2 and max1
if(test1 > 0 || test2 > 0){//if they are greater than 0, there is a gap
return null;//just quit
}

}

//if you're here, there is a collision

return new Vector2D(axis.x*((max2-min1)*-1), axis.y*((max2-min1)*-1)); //return the separation, apply it to a polygon to separate the two shapes.

You may have notices the finNormalAxis function call. It’s just a simple little function:

private function findNormalAxis(vertices:Vector.<Vector2D>, index:int):Vector2D {
var vector1:Vector2D = vertices[index];
var vector2:Vector2D = (index >= vertices.length - 1) ? vertices[0] : vertices[index + 1]; //make sure you get a real vertex, not one that is outside the length of the vector.

var normalAxis:Vector2D = new Vector2D( -(vector2.y - vector1.y), vector2.x - vector1.x);//take the two vertices, make a line out of them, and find the normal of the line
normalAxis.normalize();//normalize the line(set its length to 1)
return normalAxis;
}

Now its time for the most complex one of all, polygon vs. circle.

var test1:Number;//numbers for testing max/mins
var test2:Number;
var test:Number;

var min1:Number;//same as above
var max1:Number;
var min2:Number;
var max2:Number;
var normalAxis:Vector2D;
var offset:Number;
var vectorOffset:Vector2D;
var vectors:Vector.<Vector2D>;
var p2:Vector.<Vector2D>;
var distance:Number;
var testDistance:Number = int.MAX_VALUE;
var closestVector:Vector2D = new Vector2D();//the vector to use to find the normal

// find offset
vectorOffset = new Vector2D(polygon.x - circle.x, polygon.y - circle.y);
vectors = polygon.vertices.concat();//again, this is just a function in my polygon class that returns the vertices of the polgon

//adds some padding to make it more accurate
if (vectors.length == 2) {
var temp:Vector2D = new Vector2D(-(vectors[1].y - vectors[0].y), vectors[1].x - vectors[0].x);
temp.truncate(0.0000000001);
vectors.push(Vector2D(vectors[1]).cloneVector().add(temp));
}

// find the closest vertex to use to find normal
for (var i:int = 0; i < vectors.length; i++) {
distance = (circle.x - (polygon.x + vectors[i].x)) * (circle.x - (polygon.x + vectors[i].x)) + (circle.y - (polygon.y + vectors[i].y)) * (circle.y - (polygon.y + vectors[i].y));
if (distance < testDistance) {//closest has the lowest distance
testDistance = distance;
closestVector.x = polygon.x + vectors[i].x;
closestVector.y = polygon.y + vectors[i].y;
}

}

//get the normal vector
normalAxis = new Vector2D(closestVector.x-circle.x, closestVector.y-circle.y);
normalAxis.normalize();//normalize is(set its length to 1)

// project the polygon's points
min1 = normalAxis.dotProduct(vectors[0]);
max1 = min1;//set max and min

for (j = 1; j < vectors.length; j++) {//project all its points, starting with the first(the 0th was done up there^)
test = normalAxis.dotProduct(vectors[j]);//dotProduct to project
if (test < min1) min1 = test;//smallest min is wanted
if (test > max1) max1 = test;//largest max is wanted
}

// project the circle
max2 = circle.radius;//max is radius
min2 -= circle.radius;//min is negative radius

// offset the polygon's max/min
offset = normalAxis.dotProduct(vectorOffset);
min1 += offset;
max1 += offset;

// do the big test
test1 = min1 - max2;
test2 = min2 - max1;

if (test1 > 0 || test2 > 0) {//if either test is greater than 0, there is a gap, we can give up now.
return null;
}

// find the normal axis for each point and project
for (i = 0; i < vectors.length; i++) {
normalAxis = findNormalAxis(vectors, i);

// project the polygon(again? yes, circles vs. polygon require more testing...)
min1 = normalAxis.dotProduct(vectors[0]);//project
max1 = min1;//set max and min

//project all the other points(see, cirlces v. polygons use lots of this...)
for (j = 1; j < vectors.length; j++) {
test = normalAxis.dotProduct(vectors[j]);//more projection
if (test < min1) min1 = test;//smallest min
if (test > max1) max1 = test;//largest max
}

// project the circle(again)
max2 = circleA.radius;//max is radius
min2 -= circleA.radius;//min is negative radius

//offset points
offset = normalAxis.dotProduct(vectorOffset);
min1 += offset;
max1 += offset;

// do the test, again
test1 = min1 - max2;
test2 = min2 - max1;

if (test1 > 0 || test2 > 0) {

//failed.. quit now
return null

}

}

//if you made it here, there is a collision!!!!!

return new Vector2D(normalAxis.x*(max2-min1)*-1,normalAxis.y*(max2-min1)*-1);//return the separation distance

And that’s it. I have some classes to manage the shapes and run all these tests. Collision response can be done based on some more data(that can be gathered), but that will be saved for another post. I have some classes that are shapes and hold all the data about the shape. It is very useful for this method, but they aren’t necessary. All that is needed for the SAT is that math above. How you pass in and store the data is up to you.

A class to manage the shapes and run all the possible collision tests is also a useful class to have. You could even create custom versions of that to optimize the amount of tests needed. That is, instead of testing all the shapes, you could only test the ones that could collide or only the ones that matter if they collide. For example, if you were making a platform game, you don’t need to check whether the platforms are colliding; that would be a useless test, You could manage it and only test the player/enemies against the platforms.