se based simulator that can cur
rently achieve interactive simulation times and real time
simulation seems within reach In addition the simulator
has produced physically accurate results in several qualitative
and quantitative experiments After giving an overview of
impulse based dynamic simulation we discuss collision de
tection and collision response in this context and present
results from several experiments
Introduction
The foremost requirement of a dynamic simulator is phys
ical accuracy The simulation is to take the place of a phys
ical model and hence its utility is directly related to how
well it mimics this model A second important requirement
is computational e ciency Many applications e g elec
tronic prototyping
bene t most from interactive simula
tion others e g virtual reality demand real time speeds
This paper discusses a new approach to dynamic simu
lation called impulse based simulation founded on the twin
goals of physical accuracy and computational e ciency The
initial results from our impulse based simulator look very
promising both from speed and accuracy standpoints In
this paper we give an overview of the impulse based ap
proach then discuss collision detection and resolution and
results from several experiments
mirtich cs berkeley edu Department of Computer Science
Soda Hall University of California Berkeley CA
Supported
in part by NSF grant FD
y
jfc cs berkeley edu Department of Computer Science
Soda
Hall University of California Berkeley CA
Supported in part
by NSF grant FD
Related work
Moore and Wilhelms give one of the earliest treatments of
two fundamental problems in dynamic simulation collision
detection and collision response
Hahn also pioneered
dynamic simulation modeling sliding and rolling contacts
using impact equations
His work is the precursor of our
method although we extend the applicability of impulse dy
namics to resting contacts and model multiple objects in
contact with impulse trains as well These early approaches
all su ered from ine cient collision detection and unrealis
tic assumptions concerning impact dynamics e g in nite
friction at the contact point
Cremer and Stewart describe
Newton
probably
the most advanced general purpose dynamic simulator in use
today Newton s forte is the formulation and simulation of
constraint based dynamics for linked rigid bodies although
the contact modeling is fairly simplistic Bara has studied
multiple rigid bodies in contact
and shown that com
puting contact forces in the presence of friction is NP hard
A summary of his work in this area appears in
There are few full treatments of frictional collisions
Routh
is still considered the authority on this subject
and more recently Keller gives an excellent treatment of
frictional collisions
Our analysis is extremely similar to
that of Bhatt and Koechling who independently derived the
same key equation for integration of relative contact veloc
ities during impact They give a classi cation of frictional
collisions based on the ow patterns of tangential contact
velocity
Wang and Mason have studied two dimensional impact
dynamics for robotic applications based on Routh s ap
proach
Finally a number of researchers have inves
tigated several problems and paradigms for dynamic simu
lation and physical based modeling
The impulse based method
One of the most di cult aspects of dynamic simulation
is dealing with the interactions between bodies in contact
Most of the work which has been done in this area falls into
the category of constraint based methods
An
example will illustrate the approach Consider a ball rolling
along a table top The normal force which the table ex
erts on the ball is a constraint force that does no work on
the ball but only enforces a non penetration constraint In
the Lagrangian constraint based approach this force is not
modeled explicitly but is accounted for by a constraint on
the con guration of the ball here its
z
coordinate is held
constant Alternatively one may model the forces explic
itly solving for their magnitudes using Lagrange multipli ers However this still requires complete exact knowledge of
the instantaneous state of contact between the objects since
that determines where and when such forces can exist
A problem with this method is that as a dynamic sys
tem evolves the constraints may change many times e g
the ball may roll o the table may hit an object on the
table etc Determining the correct equations of motion for
the ball means keeping track of these changing constraints
which can become complicated Moreover it is not even al
ways clear what type of constraint should be applied there
exist at least two models for rolling contact which in some
cases predict di erent behaviors
Finally impacts are
not easily incorporated into the constraint model as they
generally give rise to impulses not constraint forces present
over some interval These collision impulses must be handled
separately as in
In contrast to constraint based methods impulse based
dynamics involves no explicit constraints on the con gura
tions of the moving objects when the objects are not collid
ing they are in ballistic trajectories Furthermore all modes
of continuous contact are handled via trains of impulses ap
plied to the objects whether they be resting sliding or
rolling on one another Under impulse based simulation a
block resting on a table is actually experiencing many rapid
tiny collisions with the table each of which is resolved using
only local information at the collision point
Now consider the case of a ball bouncing along the terrain
shown in gure
Under constraint based simulation the
Figure
A nightmare for constraint based simulation
constraints change as the ball begins traveling up the ramp
leaves the ramp and settles into a roll along the ground All
these occurrences must be detected and processed Impulse
based simulation avoids having to worry about such transi
tions In this sense it is a more physically sound treatment
since it does not establish an arti cial boundary between
for example bouncing and rolling but instead handles the
entire continuum of contact between these phases
We do not wish to discredit constraint based methods of
dynamic simulation indeed there are many situations for
which they are the perfect tool We believe the impulse
based method is better suited to simulating many common
physical systems especially those which are collision inten
sive or that have many changes in contact mode We ex
amine the possibility of using both methods of simulation
together combining the strengths of each in section
Two obvious questions concerning impulse based simula
tion are
Does it work i e does it result in physically
accurate simulations and
Is it fast enough to be practi
cal We defer more thorough answers to these questions to
section but for now state the following impulse based dy
namic simulation
does
produce physically accurate results
and the approach is extremely fast Simulations can cer
tainly be run interactively with our current implementation
and we believe real time simulation is a reachable goal
Collision detection
Impulse based dynamic simulation is inherently collision
intensive since collisions are used to a ect all types of inter
action between objects Hahn found collision detection to be
the bottleneck in dynamic simulation
and e cient data
structures and algorithms are needed to make impulse based
simulation feasible
Currently in our simulator all objects are geometrically
modeled as convex polyhedra or combinations of them The
polyhedral restriction is not at all severe because our colli
sion detection system is very insensitive to the complexity of
the geometric models permitting ne tessellations Indeed
some of the simulations described in section use polyhedral
models with over
facets with negligible slowdown
Prioritizing collisions
Obviously checking for possible collisions between all
pairs of objects after every integration step is too ine cient
Instead collisions are prioritized in a heap see gure
For
dynamic state
collision heap
A-B
A
B
Lin-
Canny
TOI
estimator
Figure
Prioritizing collisions in a heap
each pair of objects in the simulation there is an element
in the heap which also contains a lower bound on the time
of impact TOI for the given pair of objects The heap is
sorted on the TOI eld thus the TOI eld of the top heap
element always gives a safe value for the next collision free
integration step
After an integration step the distance between the ob
jects on the top of the heap call them
A
and
B
must be
recomputed In our implementation we use the Lin Canny
closest features algorithm
This is an extremely e
cient algorithm which maintains the closest features ver
tices edges or faces between a pair of convex polyhedra
It is fastest in applications like dynamic simulation when
the objects move continuously through space and geometric
coherence can be exploited
Collisions are declared when the distance between objects
falls below some threshold
c
First suppose the distance
between
A
and
B
lies above
c
In this case the dynamic
states of
A
and
B
along with the output of the Lin Canny
algorithm are used to compute a new conservative bound
on the time of impact of
A
and
B
The
A
B
heap pair
is updated with this new value possibly a ecting its heap
position and the integrator is ready for another step
If the distance between
A
and
B
is less than
c
a collision
is declared The collision resolution system computes and
applies collision impulses to the two objects changing their
dynamic state At this point the TOI is recomputed for these
objects as before however another step is necessary the
TOI between all object pairs of the form
A
x
and
B
x
must
also be recomputed The reason is that the TOI estimator
uses a ballistic trajectory assumption to bound the time of
impact for a pair of objects Applying collision impulses to
objects violates this assumption and so every previous TOI
involving such an object be