Collision Detection & Response

CS 480 Lecture, Dr. Lawlor

"Collision detection" is figuring out when your simulated objects are going to pass through one another.

The simplest form of collision detection is "pairwise" collision detection, involving just two objects. The simplest pairwise collision detection question is "Is this particle inside this triangle?".

The easy way to determine this is to notice that if a point is inside a triangle, it's also inside each edge of the triangle. We can determine which side of an edge AB a point C is sitting on with a "counterclockwise test": is the point C counterclockwise from point B, as viewed from point A? I usually figure this out by thinking of cross products (does the angle ABC have a positive or negative sin?), but you can also motivate the exact same equation by looking at the equation of the line AB.

/* Counterclockwise test: return a positive value if, 
   from a's point of view, c is counterclockwise of b.
   Iff this returns zero, then the points are colinear.
*/
double ccw(const vec2 &a,const vec2 &b,const vec2 &c) 
{
        vec2 B=b-a, C=c-a;
        return B.x*C.y-B.y*C.x;
}

Bottom line: to determine if a point is inside a triangle, do a counterclockwise test on that point versus each edge of the triangle. If the point is inside all the edges of the triangle, the point is inside the triangle.

There are of course many other shapes (triangles, spheres, boxes, etc) that you might want to collision detect. There are many libraries to detect such intersections, including the tiny but very C++'ey GPL Wykobi, every possible intersection function by Magic Software, and (mostly for triangulations) the heavy-duty Computation Geometry Algorithms Library.

"Broad Phase" Collision Detection

For very small problems, all you need is the narrow-phase collision detection above. But the problem is checking every particle against every triangle is O(P*T), which grows pretty fast. For example, with 10^3 particles and triangles, you have a managable 10^6 point-in-triangle tests. For 10^6 particles and triangles, you have 10^12 point-in-triangle tests (a trillion tests), which is going to take way longer than anything else in your program.

A very simple solution to speed up collision detection is to not test every particle against every triangle. For example, we can build a grid, sift particles into their grid cell, and then only compare each triangle with the grid cells the triangle touches. This works great in 1D, 2D, 3D, or even higher dimensions, and is pretty easy to implement with a dense array if your domain is bounded. If objects can move arbitrarily far away, you don't want a regular dense grid, but a sparse grid, like a hashtable from grid cell to list of particles.

The bottom line is that you make a data structure that keeps a list of particles at each x,y grid cell:

        /* For each x,y, a list of nodes in that grid cell */
        std::vector< std::vector< std::vector<int> > > grid;

Note you could make a sparse grid with std::map< std::pair<int x,int y>, std::vector<int particleNumber> >.

Then you "sift" particles into the grid:

        /* Add particles to my grid */
        void sift(const particle *pts,int npts) {
                for (int p=0;p<npts;p++) {
                        int y=grid_y(pts[p].P);
                        int x=grid_x(pts[p].P);
                        grid[y][x].push_back(p);
                }
        }

Finally, you collision-detect triangles against the particles in all their grid cells:

        void hit(particle *pts,triangle &t){
                /* Find the grid cells I touch, by looking at my corners */
                int maxX=0,maxY=0;
                int minX=gridsize-1,minY=gridsize-1;
                for (int corn=0;corn<3;corn++) {
                        int y=grid_y(pts[t.corner[corn]].P);
                        int x=grid_x(pts[t.corner[corn]].P);
                        maxX=max(maxX,x); maxY=max(maxY,y); 
                        minX=min(minX,x); minY=min(minY,y);
                }
                /* Check the points stored in each of my grid cells */          
                for (int y=minY;y<=maxY;y++) 
                for (int x=minX;x<=maxX;x++) 
                {
                        const std::vector<int> &list=grid[y][x];
                        for (unsigned int p=0;p<list.size();p++) {
                                collide(pts,t,list[p]);
                        }
                } 
        }

In practice, you want to make darn sure that you're not reallocating the grid every timestep, or you'll be purely allocator-limited. Also, if points can get outside the bounds of your grid, you need to check that before doing any grid lookup, or you'll access the vector out of bounds. See my "480_gridcollide_fem" example program on the main course page.

I also did my Master's Thesis on a parallel implementation of 3D voxel-based collision acceleration.

Collision Response

OK, so you've found that two objects intersect. What can you do?

"Damage" or kill the objects. This is a common catch-all in games, for when the other methods fail.
Figure out how to move them so they don't intersect, then move them apart. This works with any kind of object, but this "constraint" approach gets really tricky to implement, e.g., with a stack of books--you've got to move the top book up enough to make room for all the lower books.
Allow them to intersect, but push on them--apply force to separate them. This "penalty method" works best with squishy objects.

In real life, intersections are resolved using forces. Back in physics class, you computed the intersection force as a combination of the normal force (pushing into the surface) and the static or sliding friction force. You can still do the same thing!