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!