Physically Based Animation - Computer Animation: Algorithms and Techniques - page 222

constant is too weak or if the mass is too large, then the collision will not be corrected immediately. If
the spring constant is too strong or the mass is too small, then the colliding surfaces will be thrown apart
in an unrealistic manner. If the point is moving fast relative to the surface it penetrated, then it may take
a few time steps for the spring to take effect and restore a state of nonpenetration. If the desired velocity
after the next time step is known, then this can be used help determine the spring constants.
Using the previous example and implementing the penalty method produces the motion traced in
Figure 7.18 . In this implementation, a temporary spring is introduced into the systemwhenever both the
y component of the position and the y component of the velocity vector are negative; a spring constant
of 250 and a point mass of 10 are used. While the spring force is easy to incorporate with other system
forces such as gravity, the penalty method requires the user to specify control parameters that typically
require a trial-and-error process to determine appropriate values because of other forces that may be
present in the system.
When used with polyhedra objects, the penalty force can give rise to torque when not acting in line
with the center of mass of an object. When two polyhedra collide, the spring is attached to both objects
and imparts an equal but opposite force on the two to restore nonpenetration. Detecting collisions
among polyhedra is discussed next, followed by a more accurate method of computing the impulse
forces due to such collisions.

Testing polyhedra
In environments in which objects are modeled as polyhedra, at each time step each polyhedron is tested
for possible penetration against every other polyhedron. A collision is implied whenever the environ-
ment transitions from a nonpenetration state to a state in which a penetration is detected. A test for
penetration at each time step can miss some collisions because of the discrete temporal sampling,
but it is sufficient for many applications.
Various tests can be used to determine whether an overlap condition exists between polyhedra, and
the tests should be chosen according to computational efficiency and generality. Bounding box tests,
also known as min-max tests, can be used to quickly determine if there is any chance for an intersection.
A bounding box can easily be constructed by searching for the minimum and maximum values in x , y ,
and z . Bounding boxes can be tested for overlap. If there is no overlap of the bounding boxes, then there
can be no overlap of the objects. If the object's shape does not match a rectangle well, then a bounding

200
175
150
125
100
75
50
25

400 800 1,200 1,600

Distance

FIGURE 7.18
Penalty method with a spring constant of 250 and a point mass of 10, for example, from Section 7.4.2 .