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.
Answer
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!
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.
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.
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).
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
No comments:
Post a Comment