Cheap Collision Detection in Processing

In the process of writing the BUGS! sketch I stumbled onto a quick and simple collision detection algorithm, so I figured I would share it. For the purpose of this article I will be assuming 2D, however it should work in 3D just as well.

The detection system is implemented in Processing, which is basically Java specialized for multimedia. The core algorithm is independent of any Processing specific features and it should be easy to port to any other language.

Motivation

I made a 2D flocking/gravitation visualization, and I wanted the particles to “follow” each other, but only when an object is close to another object. The code developed here is a cleaned up and simplified version of this original sketch. You may want to take a quick look at the final product before starting to get an idea of what I am trying to accomplish.

Particles are updated on every frame, and then drawn. During the update step, each particle can move freely, but then must look for nearby particles that it could possibly follow. The brute force method would be to compare all combinations of objects and check for a collision, requiring 2^(n-1) comparisons (where n is the number of particles), resulting in O(2^n) time complexity just for the collision detection phase. But time is precious and I wanted to allow for a large number of particles, so O(2^n) was unacceptable. I figured, if two particles are more than 2x the particle size away from each other, they don’t need to be tested at all. This is the core of the Algorithm that follows.

The Uniform Grid Algorithm

The technique I stumbled upon is acutally well known and documented; it is known as a uniform grid [1]. Since particles only collide when in the same general area, the simulation area can be decomposed into small sectors:

This way, only particles occupying the same sector need to be compared, drastically reducing the total number of comparisons.

Notice that in the example, the number of comparisons for the red dot is reduced from 7 to 2; the total number of comparisons is reduced from 128 to 6! This example glosses over the issue of particle size, which will increase the number of required comparisons, but it does illustrate the general performance improvement.

Data Structure

The speedup obtained by the uniform grid is almost entirely based on a simple data structure. Below is a high level definition of the algorithms components, as well as descriptions of how they will work:

• Particle: An object. In this simulation a particle is simply a circle.
• Grid: The collection of all sectors, which together composes the simulation space.
• Sector: A square area that may or may not contain particles. The size of each sector should be the maximum size of the largest particle at any rotation. This ensures that any particle will occupy at most 4 sectors.
• The sector a particle occupies is represented by an x,y coordinate pair, just like a regular point. The sector is uniquely determined by the x,y world coordinate of the particle, divided by the sector size. For example, if the particle world location is (110,210), and the sector size is 10, then the sector location is (11, 21).
• All particles are bounded by axis aligned bounding boxes (AABBs). An AABB is a rectangle bounding the entire particle. The location of the current particle is determined by the four corners of the AABB:
  
  So a single object can exist in up to 4 different sectors on the grid at once.
• When a particle moves, its status in the grid must also be updated. For this reason, finding sectors in the grid must be *extremely* fast. (An alternative approach is to *not* update the particles as they move, but rather to rebuild the grid from scratch at every frame. It’s easy to argue that this may actually be faster than updating the Grid, due to the overhead of finding the particle to remove it during the update phase.)

Collision Queries

Queries are the primary action performed on the grid. A query uses the grid data structure to retrieve candidates for collision tests.

• Given a point P=(x,y) in world coordinates, a query begins by translating the world coords into sector coords.
• The sector contents are particles, and each particle is compared to P
• The comparison to P is done by component wise clamping P to the AABB of the current object, to produce the point Q:
  
  The distance (d) between P and Q is the distance from the given point to the AABB. If P = Q, then the point P is inside the AABB.
• Once the AABB test passes, we know that the point and the particle are very close, but not necessarily colliding. Since my simulation uses circles, my final detail test is: dist(P, center(Particle)) < radius. In words: test if the distance from point P to the center of the circle is less than the radius of the Particle being tested.

Notice that the lookup of particles is amost effortless. The major work here is simply testing the point P against the particle in two phases. The first phase is a broad phase using AABBs, and the second phase is a detail phase using the actual geometry of the object.

You may be thinking that a two stage testing process is overkill for testing circles, and you are right. It would actually be faster to test the circle directly, but I’m assuming here that you may want to use geometry other than circles, in which case you would do an expensive polygon test in the detail phase.

Implementing the Grid

The sectors compose an infinite grid that covers the world. A flyweight hash table is used to index the grid, since an infinite list would take a **really** long time to search.

The grid is a 2-dimensional array, the index into the array is a sector coordinate moded by the sector size. This gives the illusion of an infinitely large array, but actually only contains (sector size)^2 elements. This is like a circular array in two dimensions, resulting in a toroidal array.

The down side is that many sectors map to the same array entry. To accomidate for this, each entry in the array is an ArrayList of sectors. To find a specific sector, the list is searched until the requested sector is found. This search adds an additional O(n) lookup overhead, however, in the average case, n (the number of sectors contained in the array entry) is very small, so the slowdown is minimal. The public Grid members are as follows:


class Grid {
int sectorWidth
int sectorHeight

void addParticle(Particle obj)
void removeParticle(Particle obj)

Sector getSector(float x, float y)
ArrayList getSectors(Particle obj)
}


Now that objects can be stored, and retrieved, it’s time to add the ability to query it.

Putting the Grid to Use

I’ve created a small simulation of bouncing particles exibiting the collision detection system and the uniform grid. In the simulation each particle is given a random velocity (vx, vy) which describes their x and y movement in terms of pixels per second. During each frame, the following actions are performed, given the time elapsed since the last frame, dt:


1. Find the new x,y coords of the particle using:
x = dt * vx + x
y = dt * vy + y
2. Calculate a small step size dx,dy by dividing
the movement by 5
3. Step from the current position to the new position
using dx,dy
4. At each step, check for collisions
5. If a collision is detected, step back one step and
invert the velocity of both particles


The reason for stepping slowly between the current position to the new position is to avoid tunneling, in which the step size of a particle is larger than the particle itself and allows it to step through another particle.

View the uniform grid in action!

Problems

When optimizing collision detection, there is a great deal of give and take, every optimization you make results in new errors in the detection mechanism. The same is true for this method. The problem of tunneling can still occur, even with the additional precautions I’ve taken here. This can be seen in my simulation when two particles get “stuck” together. They become stuck due to the fact that they one particle has actually stepped *inside* another particle. However, because tunneling is really more of an animation issue, I’m not going to attempt to solve it here.

The second problem is if you have objects of highly varying sizes. A uniform grid works best for objects of similar size, when the size varies greatly, the grid becomes inefficient. To solve this problem, use a hierarchical grid instead [2].

The final problem is that the collisions are not very realistic. This is not a problem with the detection system at all, but a problem with how velocities are calculated during a collision. A much nicer way to do this would be to use a concept from physics known as an elastic collision. The formula for an elastic collision is simple, however, I didn’t want to muddy the waters here with any addition details unrelated to collision detection.

Conclusion

The uniform grid concept greatly improves performance of collision detection by using spatial locality of the particles being tested. I hope this tutorial has provided a good starting point for a fast collision detection system, despite some minor issues. Perhaps in the future, I will continue to build upon this framework and refine some of the problems presented here.

References:

[1] C. Ericson. Real Time Collision Detection, Morgan Kaufmann Publishers, pages 285-290, 2005.
[2] C. Ericson. Real Time Collision Detection, Morgan Kaufmann Publishers, pages 300-306, 2005.

Tagged Tags: Algorithms, Java, Math, Processing on January 14, 2009 at 12:53 pm