In a 3D simulation, one of the most difficult problems is finding and responding to collisions. The sophistication required ranges from minimal, such as a cellphone app game where we can simply test bounding boxes in 2D; to highly sophisticated, such as a crash test simulation where a body panel will be folded up and smashed into a very small space without passing through any other simulated objects.

Method |
Description |
Speed |
Pitfalls |

Naive |
Collision-test every part of every object
against every part of every other object, every frame. |
N^{2} tests,for N parts |
Does not scale to real meshes, which have
millions of parts. |

Bounding volumes | Speed up collision testing by first checking
object bounding spheres: if (sphere1.m(sphere2).length()<sphere1.radius+sphere2.radius) then collision is possible; |
N^{2} cheap tests,for N objects |
Only improves performance by a constant
factor, not asymptotically. |

Bounding volume hierarchy |
Use a nested tree of bounding volumes to
recursively find intersections. |
N log N for N objects |
Building the tree is hard, especially for
externally generated meshes. |

Voxel grid |
Rasterize each object into a space-filling 2D
or 3D grid, usually implemented as a hash table. Then
check the lists of objects in each grid cell for
collisions. (Also runs
well in parallel!) |
N+V for V voxels |
A fixed voxel grid is usually too coarse near
the action, and too fine far away. |

In a time-dependent simulation with fast moving objects, typically we can handle the coarse phase by adjusting the object bounding volumes. For example, if an object starts the timestep at P and ends the timestep at P_new, we can create a 3D bound for the 4D object by adding a bounding sphere centered at (P+P_new)/2, and inflate the sphere's radius by P.minus(P_new).length()/2.

Method |
Math |
Description |
Pitfalls |

Point-Plane test |
if (dot(N,P-V1)<0) then collision; |
Measure if the colliding vertex lies behind
the normal of your surface, with a dot product. |
It's easy to get false positives on a spiky
object, resulting in false collisions that tangle up the
objects rather than letting go. |

Point-Triangle test |
Four point-plane tests: normal and three
edges |
As above, but check if the point is inside
the projection of the triangle. |
It's possible to get false negatives on
inside surfaces, resulting in interpenetrating objects that
don't realize they're interpenetrating. |

Point-Surface test |
if any ray leaving the point hits surface an
odd
number of times, it's inside the volume |
Shoot a ray, and count intersections.
This works well if you already have a raytracer. |
It's slow, and the surface must be closed and
manifold. If the ray passes very close to a vertex or
edge, numerical roundoff can determine the answer. |

Point-Volume test |
Check each surface normal, or determinants of 4x4 matrices, to determine if the point is inside the tetrahedron | If the point is inside one of your tets, the
point is inside your object. |
You need a volume representation of a solid
object already; just the boundary is not enough. |

Distance field test |
if (object.distance(P)<0) then collision; |
Look up the point's location in a distance
field. You need a distance field, though! (Distance
fields are a popular way to raytrace.) |
Simple voxel-rasterized distance fields are
slow, memory intensive, and inaccurate. Sophisticated
hierarchical distance fields take work to build. |

Again, with fast-moving objects these 3D tests may not be sufficiently accurate for the full 4D collision. A slow solution is to take smaller sub-timesteps to the desired accuracy. Another approach is to use the bisection or secant method to iteratively converge on the actual collision time. A more complex solution is to include the object motion vectors into a full 4D collision calculation.

Method |
Description |
Pitfalls |

Penalty method F+=d*N; |
Add a spring force pushing penetrating vertex
out along object's normal vector. |
If you push hard enough, objects can overcome
the spring force and pass through one another: this means
the bottom of a tower of wooden blocks will eventually sink
into the ground. Typically penalty methods are local
solutions to a global problem, and so may produce unphysical
behavior when a mesh is trapped between a rock and hard
place. The penalty method is fast, though, taking
constant work per collision. |

Distance field penalty F+= ∇D; |
Add spring force pushing out along gradient
of the distance field. |
A distance field can produce better global
behavior, by combining information from all adjacent
objects. Your scene must be set up to provide a
distance field, however. |

Priority method if (ok(P_new)) P=P_new; |
Move one vertex at a time, and don't allow a
moving vertex to move inside another object. |
A naive implementation has quadratic time
complexity, and this approach is not physically symmetric:
if two identical meshes smash into each other, the vertex
that moves first will prevent the other vertex from moving,
breaking the mirror symmetry. |

Constraint method P=constrain(P_new); |
Apply global constraints to prevent moving vertex from entering any other object. | Even if the constraints are planar triangles,
simultaneously solving all the constraints is equivalent to
linear
programming (linearly constrained convex
optimization). The simplex
method has an exponential worst-case time in the
number of constraints, even though the average case
performance is quite good. One advantage is you can
include other features like mesh joints as their own
non-collision constraints. |

There's an excellent summary of the collision response problem at myphysicslab. Some games have very little to them aside from the collision mechanics, such as the open source driving-crash game Rig of Rods (crash video).

For today's example mesh collision detection program, I used a voxel-based broad phase, a trivial point-plane narrow phase, and a simple penalty method response.