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.