Analysis of Efficient Collision Detection using Pre-Processing Data Structures
Stephen Goodwin
Department of Computer Science
University of Texas at Austin

Efficient collision detection is key to many graphics applications and games in order to determine the proper interactions between objects.  It gives a physical and realistic feel to particle systems.  Dealing sometimes with millions of particles, pre-processing can easily cut down the number of  collision tests to fractions of the original.

Determining the actual collision detection is not that simple and varies depending on the particle's size and shape:
For 2 spheres is simple, just find the absolute distance between them and if they is less than or equal to the sum of both radiuses, then they've collided.
For 2 cubes, 1 corner of the cube will be contained in the other cube.  Just cycle through different corners until one is found.
For a cube and a sphere, possible collision points include the corner, edge and side.  This requires multiple tests.  The best way is to determine the closest point to the center of the circle, and if this is less than or equal to the radius of the circle, then they're collided.
For a pyramid, you can use a bounding box to first determine if it collides with any other particles.  Then further test specifically for the top point, side edges, bottom corners, and bottom.

Possible algorithm choices:

I .Naive: The naïve collision algorithm involves testing every particle in the system against every other particle. For n particles, this yields n*(n-1) particle pairs that must be tested, giving a O(n^2) runtime. The main problem with this is that the system is testing for collisions of particles that could be no where near each other.

//Naive Algorithm

for each particle a
    for each other particle b
        if (a intersects b)
            doResponse(a,b);

II. Boxing: A better algorithm for testing collisions is doing a little pre-processing of the particles prior to testing for collisions. This reduces the pairs that have to be tested later on. Boxing involves dividing the scene into n x n x n boxes, or dividing the environment into a set of boxes with the dimensions of {dim_x / n, dim_y / n, dim_z / n} (dim_x, dim_y, dim_z are the dimensions of the environment and n is some function of the number of particles and their sizes). This limits comparisons to relatively close particles but still may test areas where particles are not close to one another, since all divisions are uniform.

for each object a
    put a in box x

for each box x
    for each object a in x
        for each other object b in x
            if a intersects b
                doResponse(a,b)‏;

III. Octree: An octree is similar to the boxing method, except it divides the area into 8 uniform boxes, and if some condition is not met (like particle count), it will divide one of the 8 boxes further until it is. The advantages of this is you spend most of your preprocessing time breaking down only the areas of the environment with a large particle density.

Picture of an octree:

From: Wikipedia (http://en.wikipedia.org/wiki/Octree)

develop_octree(x)‏

for each leaf y in x that contains 2 or more objects
    for each object a in y
        for each other object b in y
            if a intersects b
                doResponse(a,b)‏;

The octree is defined like this:

root = new OctNode(particles, min_corner, max_corner);
if root's particle count > max_count

build_octnode(root);

build_octnode:
for each of the 8 child nodes
    child = new OctNode(corner);
for each particle from root
    if child contains particle
        add particle to child

for each of the 8 child nodes
    if child's particle count > max_count)
        build_octree(child);

And for traversing the octree:
find_collisions:
if node's particle count <= max_count
    find_collisions_leaf(node);
    return;
for each of the 8 child nodes
find_collisions(child);

find_collisions_leaf (same as naive but on much smaller number of particles):
for each particle a
    for each other particle b
        if (a intersects b)
        doResponse(a,b);

Once a collision has occurred when can use the conservation of energy and momentum to determine the new velocities for each particle:
Conservation of energy and momentum:
v1f = ((v1i * (m1 - m2) + 2 * m2 * v2i)) / ( m1 + m2 )
v2f = ((v2i * (m2 - m1) + 2 * m1 * v1i)) / ( m1 + m2)

Performance Comparison:

Artifacts: movie1, movie2, movie3

Code: code

References: