||Collision-test every part of every object
against every part of every other object, every frame.
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:
then collision is possible;
|N2 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.
||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!)
for V voxels
|A fixed voxel grid is usually too coarse near
the action, and too fine far away.
|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.
||Four point-plane tests: normal and three
||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.
||if any ray leaving the point hits surface an
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.
||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
|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.
|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
|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.
|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.
|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
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