Separating Axis Theorem (SAT) - Tue, Nov 2, 2010
In the past few weeks I was working on a Rigid-Body 2D Physics Simulator, and I came across many problems in the Collision Detection part. Collision Detection is one of the most important things in any physics engine so it must work perfectly.
After doing some research, I found the perfect algorithm to do the Collision Detection and Resolution for me, which is called SAT (short for Separating Axis Theorem)…
SAT in 2D basically says that “for objects lying in a plane, there exists a line onto which their projections will be separate if and only if they are not intersecting".
This means that if we can find a line that completely separates our objects from each other, we can be sure that they are not overlapping. However, this method only works with convex polygons, so if we are going to have concave shapes in our game, we have to break them into convex sub-shapes. Fortunately, there are many ways to do that (Like using BSP trees, or Triangulating the shape). I’ve decided to go with triangulation, since my game is not going to be that complex, and I wanted to have “a working prototype” before doing any optimization.
Well, I talked about the Collision Detection part; but what about Collision Resolution? This method can also give us the MTD or Minimum Translation Distance, which is a push vector that can separate two overlapping objects. So basically what we do is Check if the objects are colliding, Find the MTD, Apply the MTD to our objects (based on their mass) and we’re done.
So, I’ve shared my SAT and Triangulation code which are part of my polygon class, and you can download it from here:
http://cid-a2c1909da87670e9.office.live.com/embedicon.aspx/RedBulb/Polygon.zip
Using this class is pretty simple. First you have to create your polygons like this:
poly1 = new Polygon();
poly1.AddVertex(0, 0);
poly1.AddVertex(0, 170);
poly1.AddVertex(100, 150);
poly1.AddVertex(100, 0);
poly2.AutoTriangulate = true;
poly1.Triangulate();
(Notice that this polygon is already convex, so it doesn’t really need to be partitioned.)
Then we can use the static Polygon.Collide(…) method on our objects to determine whether they are colliding or not. Polygon.Collide(…) also gives us the MTD, so we can use that to separate overlapping objects.
It’ll be like this:
Vector mtd;
if (Polygon.Collide(poly1, poly2, out mtd))
{
poly.Offset(mtd); //or do some other stuff based on what you want.
}
You can learn more about SAT on Wikipedia or this website. I’ve made two demos so you can feel how this method works; these demos require xna 4.0.
http://cid-a2c1909da87670e9.office.live.com/embedicon.aspx/RedBulb/Polygon%20Demos.zip
One last thing: This code only works well with slow-moving objects. if you want to use objects that move at a fast speed (like bullets and lasers) in your simulation, you have to feed the relative velocity of the objects and time to the SAT. You can also easily modify the code to support segment-polygon Collision Detection.