Collision Detection and Response for Computer Animation
Matthew Moore and Jane Wilhelms
SIGGRAPH '88

Review by Kenneth E. Hoff III

OVERVIEW

This paper presents (the now classic) physically-based techniques
for collision detection and response. Two general collision 
detection strategies are presented: for flexible surfaces and 
for convex polyhedra. Two collision response methods are also
presented one consisting of a simple spring system and one that
computes an analytical solution. The analytical collision response 
is calculated for single pairs of rigid bodies and then extended 
to articulated figures composed of connected sets of rigid bodies.
The overall goal of this paper is to detect the collision and
compute responses based solely on dynamics without requiring
intervention by the animator.

COLLISION DETECTION DETAILS

Flexible Surfaces

Flexible surfaces are considered as meshes of triangles. An
algorithm is presented for surface-surface collisions and for
inner-object collisions (collision of the flexible surface with
itself). The basic strategy is to simply detect the penetration
of each mesh vertex through a triangular facet. In addition,
two addition considerations are taken into account: moving points
and a static mesh, moving points and meshes. The first involves
simply intersection an edge with the triangular mesh. This edge
is formed between the current and previous positions of the
current vertex being tested. This is solved using standard
ray-plane intersection tests. A 3x3 system of equations is formed
and easily solved by a matrix inversion. The fully dynamic
version forms a much more complicated system of equations that
is transformed into a root-finding problem and is solved by
the bisection method. They report only requiring 8-10 iterations.

These brute-force edge-face intersection tests are made more
efficient through several simple "culling" strategies:

1) for each time step, test the endpoints of an edge being tested
   against each face plane. If the distances are of opposite sign
   then the vertices could possibly have penetrated the
   associated face thus invoking the exact solver. Vertices that
   resulted in the same sign are removed from further computation;
   they could not have penetrated the mesh.
2) for the dynamic meshes, each triangle has a start and ending
   position. The resulting extruded geometry is surrounded by
   a simple bounding volume. Edge intersection tests are compared
   to the bounding volume before performing exact tests.
3) pts are inserted into an octree, bounding volumes surround
   the start and end positions of the triangles and the vertices.
   pts contained in the resulting bounding volume are searched
   for hierarchically.

Convex Polyhedra

Polyhedra are defined by a set of boundary planes, edges, and
vertices that form a distinct inside and outside region. The
collision detection strategy is based on the Cyrus-Beck line
clipping algorithm. The overlap test between two polyhedra A
and B proceeds as follows:

1) Each pt of B is tested against the planes of A. If any pt
   of B is "inside" all planes of A, we have an intersection.
   If all pts are "outside" of any plane, A and B cannot overlap.
2) each edge of B is tested for intersection against the planes
   of A. The edge of B is represented in a parametric form and
   is split by the planes at particular parametric values. Only
   values within [0,1] are considered. Each interval, defined
   by a contiguous pair of values (in sorted order), is tested
   for containment within polyhedron A (using the standard
   vertex inside test use in (1) using the midpoint of the
   interval segment as the test point).
3) The centroid of each face of B is tested against A. This
   handles the degenerate case of two polyhedra that are 
   nearly coincident.
4) If an overlap is still not found, the process is reversed
   to test B against A.

For efficiency, they employ various (now classic) techniques
based on bounding volumes and spatial partitioning:

1) surround polyhedra with a simply bounding box or sphere.
2) use an octree or voxel-based method.
3) for the vertex in-out tests, we can compare the vertex against
   an axis-aligned bounding box surrounding the polyhedron.


COLLISION RESPONSE DETAILS

Two methods based on dynamics are presented that both attempt 
to conserve linear and angular momentum.

Spring System

A temporary stiff spring is introduced between the contact points
of most interpenetration. The spring force is applied equally
to both objects in opposite directions. Elasticity in the
collision is handled by making a distinction between approaching
and receding contact pairs. Spring force is normal when objects
are approaching, but its effects are greatly reduced when the
objects are moving away from each other. The technique is fairly
straightforward, but results in a "stiff ODE" which requires
a very accurate ODE solver when collisions occur rapidly. This
technique works very well when the collisions are very gentle or
objects are in resting contact. The system will become very
unstable when the strength of the spring becomes very large as a
result of a rapid collision.

Analytical Solution

This paper summarizes an analytical solution for collision response
beween two rigid bodies. This idea is extended to articulated
figures composed of tree-like connections with revolving and
sliding joints between rigid bodies.

Physically-based objects with key-framed objects

A small section also discusses using the dynamics-based techniques
presented here with the more traditional key-frame animation
techniques. The interaction of the objects can be simulated.
The key-framed objects are unaffected by the physical simulation;
the dynamic objects "react" to the key-framed objects.

DISCUSSION

This papers presents a wealth of techniques that have now become
classic. Subsequent work seems to address all of the weaknesses
of the techniques presented here. The collision detection methods
are "brute-force" in that they do all pairwise edge-face
intersection tests. They do not mention the use of bounding-volume
hierarchies which has now become the standard way of efficiently
detecting collisions. They do utilize spatial partitioning
hierarchies.