Collision Detection - Appendix A - Collisions

Not much to report this week. Work was busy, leaving little time for important stuff. Still, I don't want to let the week pass with no updates over here, so I decided to share some of the stuff I didn't go into detail before.

For starters, how I'm actually resolving the collisions. It's still a bit buggy, so writing it down might help me figure out what is wrong.

As I said in the first part, I'm doing elastic collisions between spheres. If I was making a billiards game, this would be all I really need. Upon detecting a collision, as I said, I determine the position when the two objects first touch by moving them back in time until the distance to their centers is the sum of their radii. Basically multiply their speed by a negative number and add it to their positions.

Next I need to calculate their new speeds. In order to do this, it's helpful to move ourselves into a convenient reference frame. It's often the case in physics problems that you can get halfway to a solution just by changing how you look at it. In my case, all speeds and positions are stored relative to a frame of reference where all the spheres are initially at rest, and the origin is where the player first appears.

This means that the first collision will always be between an object at rest and one moving. Further collisions may be between moving objects, with no reasonable expectation of any relationship between their movements. Instead of this, we'll move the collision to the reference frame of the center of mass of the two colliding objects.

This has certain advantages; in an elastic collision, the speed of the center of mass before the collision and after the collision will not change. From the center of mass, the collision looks as if two objects approached each other, hit, and then moved away, regardless of what their speed in the standard reference frame is. Their respective speeds depend on the relationship between their masses, as well.

For example, consider two spheres of equal mass, one at rest and the other rolling to hit it head on. From the center of mass, it looks as if the two spheres approach, each moving at half the speed of the original sphere in the original frame of reference, meet at the center, and then their speeds where reflected off each other. From the original reference frame, it looks as if the first sphere stops and the sphere that was at rest moves away at the speed of the first sphere.

The angle of the green line represents the movement of the center of mass through the three stages of the collision.

From the point of view of the center of mass, if the masses were different the larger mass would appear to move more slowly, and when they bounce it would move away more slowly as well.

This is fairly straightforward for head on collisions, but far more often collisions are slightly off-center. For these, we need to apply a little more thought. Still, the same rules apply. The main difference is that we need to reflect the speeds by the angle of the collision surface, the plane tangent to both spheres at the collision point.

In order to do this we need to know the normal of the collision surface, which is simple enough as it is the normalized vector that joins the center of both spheres. In our example the masses are equal, which means that in order for the center of mass to remain static the speeds must be equal and opposite, and this relationship must be maintained after the collision as well.

Off-center collision showing speed vectors, collision plane and normal.

The equation to reflect the speed vectors is

Vect2 = Vect1 - 2 * CollisionNormal * dot(CollisionNormal,Vect1)

This must be applied to both bodies, of course.

We can see that the situation of both bodies crashing into each other is actually a special case of the off-centre collision, as we would expect. The dot product of the speed vector and the collision normal in that case is the length of the speed vector, since the dot product can be considered the projection of one vector on the other, and both vectors share the same direction.

Multiplying the length of the speed vector by a normalized vector in the same direction yields the original speed vector, and when subtracted twice from the original vector we end with a vector of the same length and opposite direction, which is what happens in head on collisions.

In off-center collisions, the effect is that we reverse the component of the speed along the collision direction, and leave the perpendicular component intact. The more glancing a blow is, the greater the angle between the collision direction and the speed direction, resulting in a smaller speed component along that axis and as a consequence a smaller deflection.

Collision Detection - Part 3 - Space Partitioning

In the previous two parts I walked through my own implementation of collision detection and resolution, a pretty basic one at that. You can find a working demo of everything I described here: Framework-0.0.7.

As I was saying last time, however, this method of comparing everything to everything has a problem. The number of collision tests required grows with the square of the number of items. This severly limits the number of elements that can fit in a scene. It should not be too noticeable in the demo, but once I add better shaders. more complex models and more game logic it all starts adding up.

It's also just plain wasteful to check things we know can't collide. The question lies in how to make the computer aware of this. That's where space partitioning comes in.

Consider a surface with a set of scattered circles. My current method would have me compare every object to every object. For the case of say, fifty circles, that would require 1,225 checks. However, we know that the objects on the far sides of the surface can't possibly touch each other. So we split the surface in two, so that each half contains twenty-five objects, and run the collision detection on each half independently.

Each line represents one required pairwise check. Doubling from three to six elements increased the required checks five times, from three to fifteen.

 Using the formula from before, (n-1)*n/2, we determine that each half now requires 300 checks, for a total of 600 checks for both sides. With just splitting the space once, we've halved the required number of checks. We can go further, of course. If we split the space in four, leaving thirteen objects in each quarter(rounding up), we will require 78 checks per quarter. A total of 312 checks.

Split the space again, into eights, so that each contains seven elements. The required number of checks is then 21 per partition, or 168 total. How low can we go? Let's say we split the space in 32 areas, each with 2 elements. We only need one check to make sure two objects aren't touching. The total would then be 32 checks. That's a considerable decrease from the original scenario, about a fortieth of the number of required checks.

The goal, then would seem to be to split the space until we have as few elements in each area as possible. However, for this example, I took the liberty of assuming the circles were all uniformly distributed, and would fill all the areas without leaving gaps. In reality, as they move and bounce about, the density of circles in a given area will change unpredictably. If we draw a fixed grid, there's no way to guarantee that they won't all find their way into the same spot.

We could try making the grid very fine, to limit the likelyhood of many elements occupying one at once, but that means that we have a great number of areas, many of which may well be empty. We have to go through each and every cell to check how many objects it has, so we want to avoid empty cells as much as posible, since they add to our overhead. Furthermore, if the cells are very small, the likelyhood of a single circle occupying several cells increases. For a given grid, a circle could fit in between one and four cells, provided the cells are as large as the circle.
 
There is an additional overhead that space partitioning brings, in that you have to keep the grid updated. It's easy enough to determine what grid an object belongs to, but we want to traverse the grid, not the object list. That means that each time an object moves, we need to keep track of wether or not it changed cells. We can at least get rid of empty cells, and avoid checking cells with just one element.

There is a way to avoid some of the problems with grids, however, through the use of structures called quadtrees (in 2D) and their extension in 3D, octrees. These are complex enough to require a post of their own. The important thing is that we can see how, through the use of space partitioning, we can cut down the time consuming issue of collision detection into something more manageable.

Collision Detection - Part 2 - Resolution

Last week, I talked a bit about how to detect collisions. I didn't go into too much detail, focusing on first order approaches to limit the number of tests we have to do. There are multiple ways of getting increasingly tighter results, such as a hierarchy of bounding volumes. The way it works is you split the body into a series of smaller bounding volumes, such that the whole object is contained within them. Properly built, you can discard half the triangles in a body on each level, until you find the intersection.

But that's beyond the scope of my first attempt. I'm going to be pretending that my bodies are all perfectly round, and handle the crashes accordingly. The result is that the first order check with spherical bounding volumes gives me all the information I need.

After comparing the bodies' distance from each other, I have a list of all the collisions that happened in a given frame. This should be a fairly small list. It's unlikely that in a given frame you'll find many collisions. Still, we don't want to assume we'll only ever find one, or we may find strange results in some cases.

Of course, after going to all this trouble to determine when two objects are getting too close, we actually have to decide what to do about it. This decision has to be informed by the kind of game, and the actors involved. For example, if you detect the collision between a bullet and an object, you'll want to remove the bullet and deal damage to the object. If you are simulating billiard balls, you'll want to have them bounce off of each other. If it's a person walking into a wall, you might just want to move them back so they're not inside the wall any more and stop them.

I'm going to be pretending my 'asteroids' act as billiard balls for now. This means elastic collisions. It won't look very good when the asteroids gain better detail, but by then we can improved the tests in different ways.

Starting with the collision list, we can determine how long ago each crash was. We know the distance between the bodies and their speeds. The difference between the sum of their radii and their actual distance divided by their relative speeds tells us the time since they crashed. We can then back up the simulation to the first crash by reversing the speed of the objects and moving them to the positions they would have been in at the time of the crash.

Once this is done, we calculate the new speeds, using simple collision physics. There's plenty of information on how to do this on the internet, so I won't go into the details. It doesn't really add to the subject in any case, the important thing is that the math gives us new speeds for the objects involved. We now advance the simulation to the time we were at before backing up, and run the collision detection again.

I don't actually use the old list because when we changed the velocities of the objects, we changed things in such a way that we can't be sure that that collision happened. Or it may be that the new velocities caused another collision. The only way to be sure is to run the collision detection again. Since the frames should really be very quick, we shouldn't find too many collisions on a single frame. Objects would have to be very tightly packed for this to be a concern, such as in the opening shot of a billiard game.

Still, this can get expensive. Worse still, the way I'm doing things, adding elements to the scene increases the cost very quickly. We can even determine exactly how much more expensive each additional item is. One object requires no checks. Two objects require one check. Three objects require three checks. Four will require six checks. Five will require ten checks. And in general, n objects will require (n-1)*n/2 checks. This is a quadratic function, and something we don't really want to work with. Having just fifty objects in the scene would require 1,225 checks every frame. Double or triple if we have a few impacts.

There is of course a way about this problem as well, which I'll talk about next week.

Collision Detection - Part 1 - Detecting it

I apologize for the tardiness. Should have had this up last Monday. Never decided on an official update schedule, but I think Monday is a good day for it.

So, what have I been so busy that I couldn't post? Well, I've been trying to wrangle with Collision. If you've tested the last demo I put out, you might have noticed that things go through each other, including the player. That's because I haven't included any logic in the loop that looks for objects interacting. I essentially create the spheres and player ship, and draw them, but they're each doing their own thing.

Collision detection (and resolution) is about finding when these objects interact, and how. The clearest example is not letting objects go through each other. But it's also necessary for detecting bullets hitting targets and damaging them, and objects bouncing believably when they hit something.

This is a complex problem, but thankfully computers today are very powerful machines. Collisions on a scale unthinkable years ago can run on current hardware in real time. There's a great deal of studying that has gone into sorting this problem as well, both for research in scientific applications and in the video game industry looking for more realistic behaviors.

The first issue we find is how to determine that there was, indeed, a collision. There are many ways that this can be done, from checking every triangle in a model to every other triangle in the scene (where intersecting triangles identify a collision) to comparing bounding volumes, and ways of speeding up the process itself by culling impossible scenarios.

The way I chose to start with is essentially the simplest (and given my field of spheres, one that should work just fine). I create a bounding volume around each object. A bounding volume is a three dimensional shape built around an object that guarantees that no point in the object lies outside of the volume. Take a square, for example. A circle centered on the square and with a diameter at least as wide as either diagonal bounds the square, since all four points would lie inside it.

In my case, I'm using spheres as the bounding volume. I can center these on the entity, and size them so that they have the same size of the model (in the case of the spheres, for the ship the sphere is a bit bigger than it really needs to be). The idea behind the bounding volumes isn't to find if two objects intersect, but to be able to discard those that don't.

Comparing bounding volumes is faster and easier than comparing the models themselves, triangle to triangle. Since the volumes completely enclose the model, we know that if the two volumes don't meet there is no way for the models to meet, and we can discard the entire models at once instead of making sure triangle by triangle. Checking if two spheres intersect is a trivial check if you know their centers and their respective radii: If the distance between the centers is less than the sum of their radii, the spheres intersect. Else, they don't.

While we can guarantee that if the spheres don't intersect the models don't either (and we can then avoid checking further), it's not necessarily true that if they intersect the models are touching. Thus, it's possible (even expected) that the bounding volume method may yield "false positives", resulting in collisions when two objects aren't touching. The solution is to do a more expensive check, triangle against triangle for example, on these. The advantage is that by excluding the ones we know can't intersect with a cheap check, we save a considerable amount of computing power.

Other bounding volumes commonly used are AABBs and OBBs, which stand for Axis Aligned Bounding Box and Oriented Bounding Box. Both consist of building boxes around the models, with the difference that the OBB builds the smallest box that the model fits in and rotates it together with the model, while the AABB builds the smallest box that can align to the world coordinate system. If the object within an AABB changes orientation, the AABB must be recalculated.

The advantage the boxes have is that they produce fewer false positives than a sphere. Spheres leave too much empty volume, especially the less 'round' the object within it is. Consider a stick, for example. In such a case, where one dimension of the object is much larger than the other two, the sphere will be mostly empty and any objects passing through this empty space will need to be checked against the stick, resulting in wasted computation.

The second easiest volume to check is the AABB. To see if two volumes intersect, one must simply check the sides. It's simplified because they are aligned to the axis, so that the x,y or z values along each side are fixed. On the other hand, building the volume each time the model changes orientation can get expensive. In the case of the stick, for example, we find ourselves in pretty much the same situation as the sphere is it is oriented away from all three axis, and get the best results if lies along any one of them.

The OBB method, finally, guarantees the fewest false positives. Finding the smallest OBB can be a bit expensive, but it needs only be done once when you create the model. On the other hand, comparing OBBs to find intersections is more expensive than either of the previous methods.

There really isn't a 'best method', as they all have their own costs which need to be considered. AABBs are good for scenery, for example, which doesn't change orientation. On the other hand, if you have a roundish object, a sphere will produce less wasted space than either box method. The good thing is we don't need to 'choose' a single method, as for very little overhead we can implement box-sphere checks that let us mix things up.

Further, the bounding volume is only the first test. And as large and complex as models have become, it's not uncommon for there being a hierarchy of checks that are run, cutting the amount of triangle test required down to sane levels. With two ten thousand polygon models, for example, just checking one against the other would be too much wasted time.

Whew. That took more than I thought. Don't really have the time to fish for pictures though.

No new demo today, but soon. Next Monday: what happens when you find an intersection!

In the driver's seat

So I have a basic implementation of newtonian movement worked out. But we're still controlling an object that eventually flies off into the distance. And once it's out of view, it's pretty unlikely that it will come back. Wouldn't it be nice, though, if we could keep track of it?

Yes, yes it would. So having worked out movement, I focused on the camera. I decided to start with two views. One from the cockpit, which tracks the rotation of the object, and the other the familiar chase camera, looking at the object from behind, and tracking the direction of movement.

The reason I made these decisions is that movement in three dimensions is pretty unintuitive, specially when you remove friction. Most space flight games get around this unintuitiveness by treating space as a giant pool. You can remain buoyant at any spot, but there's a constant friction that slows you down as soon as you stop your engines. This allows people to point themselves in the direction they want to go and fire the engines. Any transversal motion will eventually be slowed enough that they end up reaching their destination with a minimum of effort.

With newtonian physics, however, there's no meaning to the idea of slowing down. Slowing down with respect to what? Speed is wholly relative. Firing your engines in the direction you want to go leads you to shoot around your target. It is madness. I needed a way to recover some of the intuitiveness, without sacrificing the fun of being in space.

Surprisingly, still images do a poor job of demonstrating motion.

The chase cam was my solution. Other games implement a chase view, but they waste it by keeping it aligned with the ship, so you're always watching your ship from behind. This is useful for shooting things, since weapons tend to be aligned with the front of the ship, but not so much for navigation. It's essentially the same as the cockpit view, only from outside the ship.

With my implementation, the player will see the direction they're actually moving in. If they want to head towards something, they have to align their objective with the center of this view. In the meantime, the ship is free to rotate any which way, and accelerating in different directions will shift the view. Ironically, racing games make a better use of the chase view than space flight games. For the most part you sit squarely behind the car, but you can notice when turning hard around corners or drifting that your car will turn while you keep looking in the direction that your car is still going in.

Still, shooting things is important. I can see how it would be quite distressing not to be able to see what you're shooting at, which is what the cockpit view is for. Eventually, helpful GUI elements will minimize the difficulty of getting from A to B when you don't have friction helping you along, but for a start the chase view should help.

Of course, before applying these views I had to populate the space somehow. A view from the cockpit in empty space would look completely static regardless of your movement. I decided to do two things. First, I draw a cube around the ship, which remains in a fixed orientation at all times. This let's you see how your orientation changes, but since you don't move around the cube but sit always in the middle, you can't see your translation. This is how skyboxes work, but since I don't have textures working yet green lines will have to do.

So that's what those lines are for.

The second is, I actually start using all the infrastructure I'd been talking about before. During initialization I'm make a few different models (a sphere for 'asteroids', a piramid for the player), and store them in the cache. Then I create an entity for the player, and assign it the piramid model.

For the asteroids I do a little trick to get more variation. Based on the sphere model, I create new models which point to the same vertex buffers (where the sphere shape is stored in the video card), but add a scaling matrix to alter the size.

I make about fifty asteroids with random sizes and assign them random positions about the starting location for the player. Then during rendering I go through the list of entities, apply the scaling transformation and draw the result. Happily it works with very little additional fussing.

For the demo I only have the cockpit view working, which was pretty easy to implement by giving the camera the same reference frame as the player. It is available for download as usual: Framework-0.0.5r

Since it doesn't work on all machines just yet, I also created a short video of the demo.

 

So what's next? I should have the chase view working, and the possibility to switch between the two views. If I have the time I'll even throw in something special.

Angular Momentum

A couple of posts back, when dealing with rotation, I wondered how I could model the property of angular momentum. Inertial momentum is easy enough to represent with a speed vector which you add to the entity's position every frame. Velocity shares several characteristics with rotation, surprisingly. In physics angular velocity is also represented with a vector, with the direction determining the axis of rotation and the length the angular speed. I figured this was, after all, everything I needed. It would make sense then to try to use it.

The farther away from the axis of rotation, the greater the change in position.

It wasn't too much work to add a vector to the entity object, and modify the code so that pressing the rotation keys would add to this vector. The rather clever bit, I think, is that I store the vector in world coordinates. By keeping track of the frame of reference for my objects I can easily convert between local and world coordinates. This is important because I add rotation along the three local axis, but convert the addition to global coordinates before adding them to my rotation vector.


Then in the update logic I rotate along the vector's axis by an amount determined by its length. One thing to keep in mind though is that to make the rotation look realistic, I have to center models on their center of mass. Easy enough on regular geometric shapes, but I'll have to figure out something for complex models, or models with moving parts.

The demo for this is available for download: Framework-0.0.4r

It's fun to mess around with. There's a weird effect that happens when you spin up significantly, and the refresh rate starts to match up with the turning speed and the sphere appears to slow down or rotate backwards.

You can also hopelessly lose control of the thing if you mix too much spin in different directions. It should be possible to recover from the perspective of someone inside, since you can easily break down the spin one axis at a time. That's something for the next update, though.

Rotation

With translation out of the way, I moved on to something more complicated. Rotation.

The last time I went about it, I tried it with quaternions. It was time consuming and I'm not entirely sure how it even ended up working. Euler angles are even worse. Vectors and matrices, however, seem more suited to solve the problem and play nice with OpenGL. And since the GLTools library I'm using already handles that, I really only need to wrap a few calls in my entities to get it working.

As I mentioned in my previous post, I have a reference frame determined by three vectors and a position. This makes local rotations simple. If I want to roll along the length of the model, I rotate around the forward vector. If I want to change the pitch of the model, I rotate around the right vector. And if I want to turn to either side, I rotate around the up vector.

I do the same basic set up as I did for translation, except my keys now affect rotation. I tie each pair of keys to a fixed rotation around each of my local axis, so that as long as I hold a key the model rotates and on release it stops rotating.

This gets the model turning about, and to spice things up I decide to give it the ability to accelerate. I first create a velocity vector, initially set to 0 so the body is at rest. Then, when I accelerate, I add to the vector a speed increment in the forward direction. When it comes time to update my entity's position, I add the velocity vector to it's position and done. This models newtonian movement well enough; velocity is constant unless I accelerate in a given direction. If I want to stop, I have to accelerate in the opposite direction to my movement.

I can rotate around independently of my direction of movement because I store the velocity vector in global coordinates. I could easily work out the vector in local coordinates as well, and it would provide a vector that moves around as I rotate the ship.

The result is Framework-0.0.2r.

What is missing, however, is that rotation should also be continuous unless I stop it. I'm modeling conservation of momentum, but not of angular momentum. I would need to store another vector, much like the velocity vector, which is affected by what kind of rotation I attempt. Unfortunately I'm not 100% sure on the physics involved here. Ideally I could just add vectors, same as with speed. The angle of rotation would be determined by the magnitude of the vector, while the axis of rotation would be the direction of the vector. That feels about right, and I should have it set up for Framework-0.0.4r.

Next up, I reworked my sphere building algorithms from the very beginnings of this blog. I used to use triangle strips, but together with the fixed pipeline that's obsolete. Vertex lists and indices is where it's at now.