Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

There are a lot of tutorials and sample code available showing how to implement the SAT collision detection algorithm.

But can someone explain, without math or code, what are the general principls behind this technique.

share|improve this question
add comment

1 Answer

up vote 13 down vote accepted

The basic idea behind the Separating Axis Theorem (SAT) is that if we can find a gap or separation between two objects then they must not be touching.

The corollary is that if we cannot find a gap between them, the objects are touching.

But how can we be sure that there is no gap, how can we be sure we've looked sufficiently hard for a gap? Let's think about what happens in the real world, when two objects are very close to each other and we want to check if they are touching or not;

We look along the edges of the objects!

image1

Imagine the scene in the image above. You have to help your friend in the red car to parallel park into a tight spot. 'Bump parking' is considered rude where I come from, so you want to position yourself where you can see clearly if is getting too close to the white car.

image2

You are probably going to position yourself close to 'A' and look along the yellow line. If you look that way and see daylight between the two cars, you know they are not touching. If the cars get VERY close, then looking along the yellow line is the only way to spot the very moment of collision.

What we are doing here is looking along the rear edge of the white car.

image3

How did we know to look along that particular edge? In the real world we use our intuition. We know that looking along the purple line [long edge of the red car] or the green line [long edge of the white car] will not help in this situation.

But a computer doesn't have intuition, so we will ask it to "look" along all edges of both objects. If it finds a gap along even one of those edges then there's no collision. If it finds no gap on any of those edges, then that means the objects have collided.

How do we get the computer to 'look along an edge'? We use projections. We find a line (any line) at right angles to the edge we are considering and project both objects onto that edge. This line is called an 'axis' (not necessarily a coordinate axis, like x-axis or y-axis,)

A projection is a one dimensional version of the object (much like a shadow is a two dimensional version of a 3D object).

image 4

So we project all the points (usually just the corners) of the objects on to the axis. The projection converts the 2D points into distances along the axis. Now we can check if there is a gap between the projections. There is a gap if the smallest projection of one is greater than the largest projection of the other.

We repeat this process for all the edges, if a gap(separation) is found, that proves that the objects are not colliding. If we check all the edges of both objects and can't find a gap, them we can conclude the objects are touching.

For the underlying math, and examples of how to decide which lines you should be projecting on to, read How do I get the axes for SAT collision detection

share|improve this answer
    
+1 for the photo –  andrew Nov 17 '12 at 8:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.