Scalable Collision Detection in 3D and 4D

CS 482 Lecture, Dr. Lawlor

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.

Broad Phase Collision Detection

The first step is identifying the objects that might possibly collide. This is hard because collisions can happen between unrelated objects in the scene.

Method	Description	Speed	Pitfalls
Naive	Collision-test every part of every object against every part of every other object, every frame.	N² 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² 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.

Narrow Phase Collision Detection

Once you've identified two things in the simulation that might collide, you need to run a computational geometry test to check if they actually do collide. One continual annoyance at this step is avoiding self-collisions: every triangle will have three potential collisions with its own vertices, which you need to efficiently filter out of the computation.

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.

Collision Response

Once you've detected a collision, you need to respond somehow, by adjusting the model forces, velocities, or positions.

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.