Intro to the REngine
Okay, enough of the vague overviews, it's time to delve into some real code to see how all of this can be done in a real game environment. The next two sections are going to be looking at each individual function and how it helps solve the problem. This section is going to take a look at the classes that are involved, and giving a higher level description of what they do. You should have yourself a copy of the REngine source, and ideally you should be able to compile it and run the test programs. You should be looking at the header and source files as you read the rest of this paper. In this section I'm going to introduce the major players:
This is the vector class. It consists of the typical x, y, and z components (as well as a w which we don't need to worry about for this). At the simplest level this class overrides the necessary operators (+, -, *, /) to let us use it in math. It can also figure its length, as well as its length squared (which is an optimization as it's much faster then finding the length and can be used just as easily in some cases). It also can find the dot product and cross product of itself with another RVector. I had to learn what the dot and cross products are for during the early days of writing the REngine. For this discussion I won't delve deeply into their meaning, but very briefly...
The dot product of two vectors will return a float which is the length of the projection of the first vector on the second. Obviously this can be very useful when using the Method of Separating Axes, which depends almost entirely on finding projections of vectors onto other vectors. This value also tells you something about the cosine of the angle between the two vectors, but I don't use that (at least I don't know if I do).
The cross product of two vectors returns a third vector which is perpendicular to the original two. For example, the cross product between the positive Y axis and the positive Z axis is the positive X axis. The application of this isn't so handy in Separating Axes, but you will find it useful for rotational physics. A good example is torque, which is the cross product of a force applied to a point, and the vector between the origin and that point. The length of the resultant vector tells you something about the sin of the angle between the two vectors (again, I don't make obvious use of this).
As a simplification of position and rotation the REngine uses an RAxis object. Internally this object is sort of complex in its use of quaternions and matrixes to cache rotation info. You don't need to worry about that. Think of an axis as simply a position in space and three vectors, one pointing directly forward, one pointing to the left, and one pointing up. You can spin this thing around vectors, and you can move it to any position. It can get complicated when you start to think about Object coords (ie an object's idea of which way is forward) versus World coords (ie which way actually is forward). For now try not to worry about that too much. I'll point out which coords to use in which situations.
The integrator is sort of the keeper of all things related to physics. It is the one that knows how to apply all the various formulas to actually make objects move. It knows how to apply the collision detection engine to two objects and if a collision is found it knows how to find the impulse and move the objects accordingly. It also knows how to apply all the forces to change all the velocities, and how to move the objects based on those velocities. If you want to look at it as a black box then think about it this way, you hand it a list of objects and over a little bit of time it will move them for you.
Just as the RIntegrator is the keeper of all things related to physics, the RCollisionSolver is the keeper of all things related to collisions. It understands how to take any two objects and apply the Method of Separating Axes to figure out if they collided. It can then go further to figure out where the collision happened, and at what time. If it had no optimizations it would be a very simple object. Unfortunately collision detection is expensive, so the RCollisionSolver has to apply a whole bunch of optimizations to speed things up. Because of this it starts to get rather tricky. A large part of explaining the collision detection system will be explaining which optimizations it's applying. Again if you want a black box picture for this thing then you just hand it two objects and it will figure out if those objects collide, and if so where and when.
A rigid body is a physical object that does not deform. For example consider a car when it's not crashing. It has only one shape, and that shape doesn't change. The opposite to this would be a deformable body like a piece of cloth or a bag of broccoli. Rigid body physics is much simpler then working with deformable bodies, and thankfully a rigid body is good enough for a space simulator. This rigid body class contains all of the phyiscs behind the motion of a rigid body. It has the position, mass, velocity, applied force, impulse, rotational velocity, etc etc etc. It does not actually describe what the body looks like in space, however it does hold other objects that handle that.
The collision model contains the model of what an object actually looks like. I create these things in a 3D modeling tool and then read them into this. It's sort of difficult to describe how this differs from an RConvexPolyhedron (below). Basically it's the model of what a ship looks like, but it isn't the actual ship. It doesn't move, it doesn't rotate, it doesn't crash into things. One single model for a specific type of ship is shared between all instances of that ship. However if you take one of these and copy all the parts out to space and move them and rotate them then you'd have an RConvexPolyhedron.
It's worth noting the parent/child relationship going on here. This is mostly an optimization, but it also lets us provide guesses to complex things like how to find collisions from rotational velocity. The general idea is that you compose the models such that the parent is nothing but the sum of a small handful of children. Then each child is also the sum of some more children and so on until you drill down to some actual physical things. For example a space ship may be made of 3 children, a fusulage, a left wing assembly, and a right wing assembly. Then the fusulage may be a cockpit and a body, whereas the wing assembly may be a wing and a rocket and a laser turret. Then the laser turret may be a housing and 3 guns. This tree structure is what I was alluding to earlier when I said that you need to compose your complex, concave shape out of simpler, convex shapes. The model that is shows on the screen is a concave polyhedron, however the actual parts that are individually tested are small, simple, convex polyhedrons.
Another important aspect of the parent/child relationship is the optimizations that come from it. Collision detection is expensive, so many steps need to be taken to find fast, "good enough" approximations that can be used to determine whether or not the hard work really needs to be done. For example a parent node keeps a radius that describes a sphere that encapsulates all of the children. Testing whether or not two spheres are close enough to intersect is very easy. So the simplest step to collision detection is to check to see if these bounding spheres intersect. If they don't then there's no need to do any more work.
One final thing to consider is that while the model displayed on the screen is a very rich model with textures and many surfaces, the collision model is vastly simplified to include as few surfaces as possible. It doesn't look very nice at all, but it has generally the same rough shape. For example you may have a nose cone that is a beautifully rounded half sphere made of 500 little triangles. Trying to do collision detection on that would be killer. However you can use a simple, 12 sided half sphere that will tell you whether or not a laser got within an inch of the nose cone. And since nobody is going to notice the difference of an inch, you're better off using the 12 sided object.
The representation of the actual object in space. This object is created by taking a model and then moving every point and every normal and every face into the real world. In other words, it's expensive to build. For this reason I only actually create convex polyhedra when I absolutely need to use one to check on a collision. I also try to reuse them if I can (ie within the same moment in time). Consider the case where you have 20 objects passed to the Integrator. While the collision detection is happening those objects are not moving. This means that the position and rotation of one of the objects does not change when you compare it to other objects within this time slice. Obviously by the next collision detection cycle the objects will move and need to be refigured, however for this time slice you only need to build one of these once. Also just because you need to build a parent to check on a collision does not imply you need to build all the children. It's possible to get halfway down the tree and find a bounding sphere that simply can not collide against the other object. There is no need to continue down the tree. Like the RCollisionSolver the complexity in this object lies mostly in its optimizations.
Note that the RConvexPolyhedron has the same parent/child relationship as the RCollisionModel (see above).
The Oriented Bounding Box. This class exists purely as an optimization. Imagine if you had 2 sphers in space, each with 100 sides. Trying to check to see if those objects collided would take an awful lot of separating axes checks. However you can put both of those spheres into a box (which only has 6 sides) and then check to see if the boxes collide. If the boxes do not collide then there's no way that the spheres can collide. This is that box.
Those are the objects that make up the collision detection and response system used by the REngine. The rest of this paper will go through every function to show you how these objects work. The first step is to take a look at the physics implementation...