"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,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.

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;

}

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.

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 */Note you could make a sparse grid with std::map< std::pair<int x,int y>, std::vector<int particleNumber> >.

std::vector< std::vector< std::vector<int> > > grid;

Then you "sift" particles into the grid:

/* Add particles to my grid */Finally, you collision-detect triangles against the particles in all their grid cells:

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);

}

}

void hit(particle *pts,triangle &t){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.

/* 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]);

}

}

}

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

- "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.