Method of Separating Axes

Okay, now we need to start looking at exactly what the problem is and how to solve it. I'm assuming that at this point you have yourself a large area in space that you would like to fill with spaceships, lasers, missles, asteroids, etc. The objects themselves are represented as complex shapes made up of many small triangles. Now you just want to take all the objects and have them start crashing into each other. At the very highest level you have some kind of list (linked list, map, vector, whatever makes you happy) of these space objects. Now you need a function which will take any 2 objects and check to see if they collide. I'm going to try to explain how to find that in the following sections:

Collision Detection:

Collision detection in the REngine is handled using the "Method of Seperating Axes." There are many papers on this subject (see the 2 I mentioned earlier by David Eberly for some good examples) so I am not taking it on myself to provide a rigorous, mathmatical explanation. I am going to try to provide a simple explanation. Imagine 2 objects floating in space:
The idea is that if we project those objects onto an axis we can see whether or not those objects overlap on that axis. If you're not familiar with the term "project" just imagine shining a flashlight on an object and looking only at it's shadow. Similarly we look only at the projection (or shadow) of an object along a single axis. If the projections of those objects do not intersect along that axis, then the axis is said to be a "seperating axis" and the two objects do not intersect. Below is an image of the same 2 objects projected onto a vertical axis and a horizontal one:
Notice that along the horizontal axis the projections do not touch, however along the vertical axis they do. The horizontal axis is a seperating axis. Now this all seems well and good, however the problem you can imagine is that there are an infinite number of axes to test against, how can this system actually be efficient? Well through the magic of some math I don't understand, it turns out that there are actually only a very small number of axes that we need to test. Specifically we need to check the normal vector of every edge on each polygon, and the cross products of all the normals from the first polygon and all the normals from the second polygon, ie: 

for( iterA=AllNormalsInObjectA )
{
	for( iterB=AllNormalsInObjectB )
	{
		TestAxis = iterA.CrossProduct( iterB );
	}
}
This can still be a rather large set of axes to test against, however it's definitely smaller then an infinite set. There are also a whole bunch of optimizations for common shapes which I will go into when we start looking at code.

Separating Axes and Linear Velocity:

Hopefully all the above is making sense to you but you may still be thinking that Separating Axes is useless as all that only applied to stationary objects and your objects will be moving. Well it's not much of a step to apply some linear velocity to our equations (notice I said LINEAR velocity). It turns out that just as we can project an object on an axis, we can also project an object's velocity on that same axis. Consider the following:

This object is moving down and to the left. Just as you can project the stationary object along the axis, you can project every location that a moving object occupies during a time step onto an axis. And with the help of trusty old v=d/t you can easily see where an object's projection is at any time during the time step. Using this trick we can extend the stationary Separating Axes test to objects that are moving.

Our test is now starting to take shape. Generally in a video game we spend some time updating non-Physics things like the video, the AI, the network, etc. Eventually we get to the Phyics loop and it's time to figure out whether or not anything has collided during the past time step. We can combine this elapsed time and the linear velocity of objects to figure out whether or not any objects have collided during the elapsed time. If they have we can respond to that collision.

Separating Axes and Angular Velocity

Okay, so what about angular velocity? Imagine a spinning propeller. It has no linear velocity, so the previous test is of no interest, however it has a large angular component. How does Separating Axes apply to that? Well the unfortunate answer is it doesn't. If you need a collision detection system to accurately predict when the end of a spinning propeller will collide with something then this is probably not the system for you. The math to figure out the projection of a spinning object on an axis is too computationally intensive to run in a video game (or so I'm told, I can't even figure out what the math would look like).

Now you see a problem that needs to be addressed when using the Method of Separating Axes. What happens with collisions due to spinning objects is that the Method of Separating Axes will completely miss the collision over the time step. So when we begin our next collision check we will have objects that have actually already collided and are now intersecting. This situation is called the "penetrating case", and while it's not physically possible in the real world, it's pretty much unavoidable in our simulation. However we can build our Physics engine in such a way that it can handle this case gracefully and produce results that look correct, even if they're a little bit faked.

Convex Polyhedra:

There is another caveat to the Method of Separating Axis that isn't as big a deal, but it does need to be dealt with. The entire system only works for objects that are convex. What is a convex object? If you draw a line between every pair of points on a polyhedra, and every one of those lines is completely inside the polyhedra, then it's a convex polyhedra. Or more simply put, a convex polyhedra is puffed out, with no dents or smashed in sides. It's pretty plain to see that a complex shape like a space ship is NOT a convex polyhedra. However this does not mean you can not use the Method of Separating Axes for space ships. What it means is that you just need to be a little sneaky about it. If you build your concave space ship out of convex parts, and then test the parts individually, you end up with a system that works just fine. For example the object on the left is concave and you can not use Seperating Axes to test it:
However you CAN break it into 2 smaller convex objects and test both of them. As simple as this sounds it actually took me a while to figure it out. Eventually the light came on and the REngine now walks a tree of collision shapes to test only the smaller, convex objects at leaf nodes.

The Results of Collision Detection

At this point you should understand the basics of the Method of Separating Axes. Feel free to check out the papers I've mentioned for a more rigorous approach (we'll be using parts of them soon enough). Now imagine we want to create a function where we pass in 2 moving objects and it checks to see if they collide. Exactly what info do we need to get from this function in order to simulate a nice collision response? Well first and foremost we need to know whether or not the objects collide. If the answer is no, then that's all we need. However if they do collide we need some more info. It should be pretty obvious that we'll need to know where those objects collided. If you imagine a spaceship getting shot on the left wing, we need to know that it was the left wing that got shot. Having the ship react as if it was shot in the nose would look stupid. We also need to know the normal for the collision. You can think of this normal as showing us in which direction the colliding missle came from, ie if you shoot the left wing from the front the ship will be knocked backwards, however if you shoot it from behind it will be knocked forwards. It is the normal that helps us know how to react. Lastly we need to know the time of the collision. Ideally the time will be at some point in the future. However remember the penetrating case. In this case the time of collision will be zero, meaning the 2 objects have already collided and we missed it. Again this is an annoying reality of the Method of Separating Axes and it needs to be dealt with. In any event, our collision detection system will return:

Collision Detection Summary

Hopefully now have a good idea of how collision detection works. You should feel comfortable with the application of linear velocity to the system. You also need to be wary of concave polyhedra and rotational velocity. Most of all you should be a little bit afraid of the penetrating case, where two objects have collided and we missed it and need to deal with it sanely. At this point I'm going to stop the high level discussion and begin working with specifics. I'm going to start out by describing some of the fundamentals of the REngine...