## Physics in Graphics |
There will come a time when you believe everything is finished.
That will be the beginning. |

**
Particle-Based Simulation of Granular Materials
**
(SCA 2005)
(project page)

Nathan Bell,
Yizhou Yu,
Peter J. Mucha

Granular materials, such as sand and grains, are
ubiquitous. Simulating the 3D dynamic motion of such materials
represents a challenging problem in graphics because of their unique
physical properties. In this paper we present a simple and effective
method for granular material simulation. By incorporating techniques
from physical models, our approach describes granular phenomena more
faithfully than previous methods. Granular material is represented by
a large collection of non-spherical particles which may be in
persistent contact. The particles represent discrete elements of the
simulated material. One major advantage of using discrete elements is
that the topology of particle interaction can evolve freely. As a
result, highly dynamic phenomena, such as splashing and avalanches,
can be conveniently generated by this meshless approach without
sacrificing physical accuracy. We generalize this discrete model to
rigid bodies by distributing particles over their surfaces. In this
way, two-way coupling between granular materials and rigid bodies is
achieved.

**
Simulation of Smoke based on Vortex Filament Primitives
**
(SCA 2005)
(project page)

Alexis Angelidis,
Fabrice Neyret

We describe a method that permits the high performance simulation of
fluid phenomena such as smoke, with high-level control for the
artist. Our key primitives are vortex filament and vortex ring:
vorticity defines a flow as well as velocity does, and for numerous
interesting flows such as smoke or explosions this information is very
compact and tightly linked to the visual features of the fluid. We
treat these vortices as 1D Lagrangian primitives (i.e. connected
particles), which permit unbounded fluids and very accurate
positioning of the features. The simulation of passive density
particles for rendering is totally independent of the fluid animation
itself. Thus, the animation can be efficiently simulated, edited and
even stored, while the fluid resolution used for rendering can be
arbitrarily high. We aim at plausible fluids rather than physical
accuracy. For efficiency and stability, we introduce a new
formalization of the Biot-Savart law and a modified Biot-Savart
kernel. Our model also introduces a hierarchical filament structure
for animation LOD, turbulent noise, and an original scheme for density
particles.

**
Modeling and Animating Gases with Simulation Features
**
(SCA 2005)
(project page)

Joshua Schpok,
William Dwyer,
David S. Ebert

Modeling and animating complex volumetric natural phenomena, such as
clouds, is a difficult task. Most systems are difficult to use,
require adjustment of numerous, complex parameters, and are
non-interactive. Therefore, we have developed an intuitive,
interactive system to artistically model, animate, and render visually
convincing volumetric clouds using modern consumer graphics
hardware. Our natural, high-level interface models volumetric clouds
through the use of qualitative cloud attributes. The animation of the
implicit skeletal structures and independent transformation of octaves
of noise emulate various environmental conditions. The resulting
interactive design, rendering, and animation system produces
perceptually convincing volumetric cloud models that can be used in
interactive systems or exported for higher quality offline rendering.

**
Directable Animation of Elastic Objects
**
(SCA 2005)
(project page)

Ryo Kondo,
Takashi Kanai,
Ken-ichi Anjyo

There is a crucial demand in the computer animation industry to make
animations that blend animator-specified expressive motion with
physics-based realism. We propose a novel framework to create
directable animation of elastically deformable objects. The
directable animation is created with animator-specified keyframes and
the motion trajectory of the deformable object, while maintaining a
plausible realism. Our framework mainly consists of two complementary
approaches. The first is a method to control the time-varying
geometry of an elastic object, using a loose key-framing
technique. In our keyframing, we introduce an FEM-based elastic
deformation algorithm that allows us to rearrange the elastic object
motion, guided by the shape or pose specified at each keyframe. The
second is a motion compensation technique, which allows us to
rearrange the physical behavior of elastically deformable objects
under a user-specified trajectory. The animation examples demonstrate
that our framework provides plausibly realistic deformation
animations with greater controllability and usability than existing
approaches.

**
Simulating Complex Hair with Robust Collision Handling
**
(SCA 2005)

Byoungwon Choe,
Min Gyu Choi,
Hyeong-Seok Ko

We present a new framework for simulating dynamic movements of complex
hairstyles. Assuming that hair consists of a number of wisps, we
propose methods for simulating dynamic wisp movements and handling
wisp.body collisions and wisp.wisp interactions. For simulation of
wisps, we introduce a new hair dynamics model, a hybrid of the rigid
multi-body serial chain and mass-spring models, to formulate the
simulation system using an implicit integration method. Consequently,
the simulator can impose collision/contact constraints systematically,
so that it can handle wisp-body collisions efficiently without the
need for backtracking or taking sub-timesteps. In addition, the
simulator handles wisp-wisp collisions based on the impulse while
taking account of viscous damping and cohesive forces. Experimental
results show that the proposed technique can stably simulate hair with
intricate geometries while robustly handling wisp.body collisions and
wisp-wisp interactions.

**
Robust Quasistatic Finite Elements and Flesh Simulation
**
(SCA 2005)

Joseph Teran,
Eftychios Sifakis,
Geoffrey Irving,
Ronald Fedkiw

Quasistatic and implicit time integration schemes are typically
employed to alleviate the stringent time step restrictions imposed
by their explicit counterparts. However, both quasistatic and implicit
methods are subject to hidden time step restrictions associated with
both the prevention of element inversion and the effects of discontinuous
contact forces. Furthermore, although fast iterative solvers
typically require a symmetric positive definite global stiffness
matrix, a number of factors can lead to indefiniteness such as large
jumps in boundary conditions, heavy compression, etc. We present a
novel quasistatic algorithm that alleviates geometric and material
indefiniteness allowing one to use fast conjugate gradient solvers
during Newton-Raphson iteration. Additionally, we robustly compute
smooth elastic forces in the presence of highly deformed, inverted
elements alleviating artificial time step restrictions typically
required to prevent such states. Finally, we propose a novel strategy
for treating both collision and self-collision in this context.

**
Particle-based Viscoelastic Fluid Simulation
**
(SCA 2005)
(project page)

Simon Clavet,
Philippe Beaudoin,
Pierre Poulin

We present a new particle-based method for viscoelastic fluid
simulation. We achieve realistic small-scale behavior of substances
such as paint or mud as they splash on moving
objects. Incompressibility and particle anti-clustering are enforced
with a double density relaxation procedure which updates particle
positions according to two opposing pressure terms. From this process
surface tension effects emerge, enabling drop and filament
formation. Elastic and non-linear plastic effects are obtained by
adding springs with varying rest length between particles. We also
extend the technique to handle interaction between fluid and dynamic
objects. Various simulation scenarios are presented including rain
drops, fountains, clay manipulation, and floating objects. The method
is robust and stable, and can animate splashing behavior at
interactive framerates.

**
Taming Liquids for Rapidly Changing Targets
**
(SCA 2005)
(project page)

Lin Shi,
Yizhou Yu

Following rapidly changing target objects is a challenging problem in
fluid control, especially when the natural fluid motion should be
preserved. The fluid should be responsive to the changing
configuration of the target and, at the same time, its motion should
not be overconstrained. In this paper, we introduce an efficient and
effective solution by applying two different external force
fields. The first one is a feedback force field which compensates for
discrepancies in both shape and velocity. Its shape component is
designed to be divergence free so that it can survive the velocity
projection step. The second one is the gradient field of a potential
function defined by the shape and skeletion of the target object. Our
experiments indicate a mixture of these two force fields can achieve
desirable and pleasing effects.

**
Particle-Based Fluid-Fluid Interaction
**
(SCA 2005)

Matthias Müller,
Barbara Solenthaler,
Richard Keiser,
Markus Gross

The interesting and complex behavior of fluids emerges mainly from
interaction processes. While interactions of fluids with static or
dynamic solids has caught some attention in computer graphics lately,
the mutual interaction of different types of fluids such as air and
water or water and wax has received much less attention although
these types of interaction are the basis for a variety of important
phenomena. In this paper we propose a new technique to model
fluid-fluid interaction based on the Smoothed Particle Hydrodynamics
(SPH) method. For the simulation of air-water interaction, air
particles are generated on the fly only where needed. We also model
dynamic phase changes and interface forces. Our technique makes
possible the simulation of phenomena such as boiling water, trapped
air and the dynamics of a lava lamp.

**
Fluids in Deforming Meshes
**
(SCA 2005)
(project page)

Bryan Feldman,
James F. O'Brien,
Bryan M. Klingner,
Tolga Goktekin

This paper describes a simple modification to an Eulerian fluid
simulation that permits the underlying mesh to deform independent of
the simulated fluid's motion. The modification consists of a
straightforward adaptation of the commonly used semi-Lagrangian
advection method to account for the mesh's motion. Because the method
does not require more interpolation steps than standard
semi-Lagrangian integration, it does not suffer from additional
smoothing and requires only the added cost of updating the mesh. By
specifying appropriate boundary conditions, mesh boundaries can
behave like moving obstacles that act on the fluid resulting in a
number of interesting effects. The paper includes several examples
that have been computed on moving tetrahedral meshes.

**
Physically Based Rigging for Deformable Characters
**
(SCA 2005)
(project page)

Steve Capell,
Matthew Burkhart,
Brian Curless,
Tom Duchamp,
Zoran Popovic

In this paper we introduce a framework for instrumenting ("rigging")
characters that are modeled as dynamic elastic bodies, so that their
shapes can be controlled by an animator. Because the shape of such a
character is determined by physical dynamics, the rigging system
cannot simply dictate the shape as in traditional animation. For this
reason, we introduce forces as the building blocks of rigging. Rigging
forces guide the shape of the character, but are combined with other
forces during simulation. Forces have other desirable features: they
can be combined easily and simulated at any resolution, and since they
are not tightly coupled with the surface geometry, they can be more
easily transferred from one model to another. Our framework includes a
new pose-dependent linearization scheme for elastic dynamics, which
ensures a correspondence between forces and deformations, and at the
same time produces plausible results at interactive speeds. We also
introduce a novel method of handling collisions around creases.

**Meshless Deformations Based on Shape Matching**
(Siggraph 2005)
(project page)

Matthias Müller,
Bruno Heidelberger
(Eidgenössische Technische Hochschule Zürich ),
Matthias Teschner
(Universität Freiburg),
Markus Gross
(Eidgenössische Technische Hochschule Zürich )

We present a new approach for simulating deformable objects. The
underlying model is geometrically motivated. It handles point-based
objects and does not need connectivity information. The approach does
not require any pre-processing, is simple to compute, and provides
unconditionally stable dynamic simulations. The main idea of our
deformable model is to replace energies by geometric constraints and
forces by distances of current positions to goal positions. These goal
positions are determined via a generalized shape matching of an
undeformed rest state with the current deformed state of the point
cloud. Since points are always drawn towards well-defined locations,
the overshooting problem of explicit integration schemes is
eliminated. The versatility of the approach in terms of object
representations that can be handled, the efficiency in terms of memory
and computational complexity, and the unconditional stability of the
dynamic simulation make the approach particularly interesting for
games.

**MoXi: Real-Time Ink Simulation**
(Siggraph 2005)
(project page)

Nelson S.-H. Chu,
Chiew-Lan Tai
(Hong Kong University of Science and Technology)

We present a physically-based method for simulating ink dispersion in
absorbent paper for art creation purposes. We devise a novel fluid
flow model based on the lattice Boltzmann equation suitable for
simulating percolation in disordered media, like paper, in real
time. Our model combines the simulations of spontaneous shape
evolution and porous media flow under a unified framework. We also
couple our physics simulation with simple implicit modeling and
image-based methods to render high quality output. We demonstrate the
effectiveness of our techniques in a digital paint system and achieve
various realistic effects of ink dispersion, including complex flow
patterns observed in real artwork, and other special effects.

**Dynamic Response for Motion Capture Animation**
(Siggraph 2005)
(project page)

Victor Zordan,
Bill Chiu,
Anna Majkowska,
Matthew Fast
( University of California, Riverside)

Human motion capture embeds rich detail and style which is diffcult to
generate with competing animation synthesis technologies. However,
such recorded data requires principled means for creating responses in
unpredicted situations, for example those immediately following
impact. This paper introduces a novel technique for incorporating
unexpected impacts into a motion capture-driven animation system
through the combination of a physical simulation which responds to
contact forces and a specialized search routine which determines the
best plausible reentry into motion library playback following the
impact. Our system generates a physics-based response as it
transitions between motion capture segments using an actuated dynamic
model and smoothly moves the character toward the re-entry clip over
time. Our method allows characters to have un-canned responses to
unexpected changes in the environment based on the specific dynamic
effects of a given contact while also taking advantage of the
realistic movement made available through motion capture. We show the
results of our system under various conditions and with varying
responses using martial arts motion capture as a testbed.

**Animating Gases with Hybrid Meshes**
(Siggraph 2005)
(project page)

Bryan Feldman,
James F. O'Brien,
Bryan M. Klingner
(University of California, Berkeley)

This paper presents a method for animating gases on unstructured
tetrahedral meshes to efficiently model the interaction of the fluids
with irregularly shaped obstacles. Because our discretization scheme
parallels that of the standard staggered grid mesh we are able to
combine tetrahedral cells with regular hexahedral cells in a single
mesh. This hybrid mesh offers both accuracy near obstacles and
efficiency in open regions.

**A Vortex Particle Method for Smoke, Fire, and Explosions**
(Siggraph 2005)

Andrew Selle
(Stanford University and
Intel Corporation),
Nick Rasmussen (Industrial Light & Magic),
Ron Fedkiw
(Stanford University and Industrial Light & Magic)

Vorticity confinement reintroduces the small scale detail lost when
using efficient semi-Lagrangian schemes for simulating smoke and
fire. However, it only amplifies the existing vorticity, and thus can
be insufficient for highly turbulent effects such as explosions or
rough water. We introduce a new hybrid technique that makes
synergistic use of Lagrangian vortex particle methods and Eulerian
grid based methods to overcome the weaknesses of both. Our approach
uses vorticity confinement itself to couple these two methods
together. We demonstrate that this approach can generate highly
turbulent effects unachievable by standard grid based methods, and
show applications to smoke, water and explosion simulations.

**Discontinuous Fluids**
(Siggraph 2005)
(project page)

Jeong-Mo Hong,
Chang-Hun Kim
(Korea University)

At interfaces between different fluids, properties such as density,
viscosity, and molecular cohesion are discontinuous. To animate
small-scale details of incompressible viscous multi-phase fluids
realistically, we focus on the discontinuities in the state variables
that express these properties. Surface tension of both free and bubble
surfaces is modeled using the jump condition in the pressure field;
and discontinuities in the velocity gradient field, driven by
viscosity differences, were also considered. To obtain derivatives of
the pressure and velocity fields with sub-grid accuracy, they are
extrapolated across interfaces using continuous variables based on
physical properties. The numerical methods that we present are easy to
implement and do not influence the performance of existing
solvers. Small-scale fluid motions, such as capillary instability,
breakup of liquid sheets, and bubbly water were all successfully
animated.

**Water Drops on Surfaces**
(Siggraph 2005)
(project page)

Huamin Wang,
Peter J. Mucha,
Greg Turk
(Georgia Institute of Technology)

We present a physically-based method to enforce contact angles at the
intersection of fluid free surfaces and solid objects, allowing us to
simulate a variety of small-scale fluid phenomena including water
drops on surfaces. The heart of this technique is a virtual surface
method, which modifies the level set distance field representing the
fluid surface in order to maintain an appropriate contact angle. The
surface tension that is calculated on the contact line between the
solid surface and liquid surface can then capture all interfacial
tensions, including liquid-solid, liquid-air and solid-air
tensions. We use a simple dynamic contact angle model to select
contact angles according to the solid material property, water
history, and the fluid front's motion. Our algorithm robustly and
accurately treats various drop shape deformations, and handles both
flat and curved solid surfaces. Our results show that our algorithm is
capable of realistically simulating several small-scale liquid
phenomena such as beading and flattened drops, stretched and
separating drops, suspended drops on curved surfaces, and capillary
action.

**
Adaptive Dynamics of Articulated Bodies
**
(Siggraph 2005)
(project page)

Stephane Redon,
Nico Galoppo,
Ming C. Lin
(University of North Carolina)

Forward dynamics is central to physically-based simulation and control
of articulated bodies. We present an adaptive algorithm for computing
forward dynamics of articulated bodies: using novel motion error
metrics, our algorithm can automatically simplify the dynamics of a
multi-body system, based on the desired number of degrees of freedom
and the location of external forces and active joint forces. We
demonstrate this method in plausible animation of articulated bodies,
including a large-scale simulation of 200 animated humanoids and
multi-body dynamics systems with many degrees of freedom. The graceful
simplification allows us to achieve up to two orders of magnitude
performance improvement in several complex benchmarks.

**Fast Frictional Dynamics for Rigid Bodies**
(Siggraph 2005)
(project page)

Danny M. Kaufman,
Timothy Edmunds,
Dinesh K. Pai
(Rutgers University)

We describe an efficient algorithm for the simulation of large sets of
non-convex rigid bodies. The algorithm finds a simultaneous solution
for a multi-body system that is linear in the total number of contacts
detected in each iteration. We employ a novel contact model that uses
mass, location, and velocity information from all contacts, at the
moment of maximum compression, to constrain rigid body velocities. We
also develop a new friction model in the configuration space of rigid
bodies. These models are used to compute the feasible velocity and the
frictional response of each body. Implementation is simple and leads
to a fast rigid body simulator that computes steps on the order of
seconds for simulations involving over one thousand non-convex objects
in high contact configurations.

**Meshless Animation of Fracturing Solids**
(Siggraph 2005)

Mark Pauly
(Stanford University),
Richard Keiser
(Eidgenössische Technische Hochschule Zürich ),
Bart Adams,
Philip Dutré
(Katholieke Universiteit Leuven),
Markus Gross
(Eidgenössische Technische Hochschule Zürich),
Leonidas Guibas
(Stanford University)

We present a new meshless animation framework for elastic and plastic
materials that fracture. Central to our method is a highly dynamic
surface and volume sampling method that supports arbitrary crack
initiation, propagation, and termination, while avoiding many of the
stability problems of traditional mesh-based techniques. We explicitly
model advancing crack fronts and associated fracture surfaces embedded
in the simulation volume. When cutting through the material, crack
fronts directly affect the coupling between simulation nodes,
requiring a dynamic adaptation of the nodal shape functions. We show
how local visibility tests and dynamic caching lead to an efficient
implementation of these effects based on point collocation. Complex
fracture patterns of interacting and branching cracks are handled
using a small set of topological operations for splitting, merging,
and terminating crack fronts. This allows continuous propagation of
cracks with highly detailed fracture surfaces, independent of the
spatial resolution of the simulation nodes, and provides effective
mechanisms for controlling fracture paths. We demonstrate our method
for a wide range of materials, from stiff elastic to highly plastic
objects that exhibit brittle and/or ductile fracture.

**Animating sand as a fluid**
(Siggraph 2005)

Yongning Zhu,
Robert Bridson,
(University of British Columbia)

We present a physics-based simulation method for animating sand. To
allow for efficiently scaling up to large volumes of sand, we abstract
away the individual grains and think of the sand as a continuum. In
particular we show that an existing water simulator can be turned into
a sand simulator with only a few small additions to account for
inter-grain and boundary friction. We also propose an alternative
method for simulating fluids. Our core representation is a cloud of
particles, which allows for accurate and flexible surface tracking and
advection, but we use an auxiliary grid to efficiently enforce
boundary conditions and incompressibility. We further address the
issue of reconstructing a surface from particle data to render each
frame.

**Coupling Water and Smoke to Thin Deformable and Rigid Shells**
(Siggraph 2005)
(project page)

Eran Guendelman
(Stanford University and Industrial Light & Magic)
Andrew Selle
(Stanford University and
Intel Corporation),
Frank Losasso,
Ronald Fedkiw
(Stanford University and Industrial Light & Magic)

We present a novel method for solid/fluid coupling that can treat
infinitesimally thin solids modeled by a lower dimensional
triangulated surface. Since classical solid/fluid coupling algorithms
rasterize the solid body onto the fluid grid, an entirely new approach
is required to treat thin objects that do not contain an interior
region. Robust ray casting is used to augment a number of
interpolation, finite difference and rendering techniques so that
fluid does not leak through the triangulated surface. Moreover, we
propose a technique for properly enforcing incompressibility so that
fluid does not incorrectly compress (and appear to lose mass) near the
triangulated surface. This allows for the robust interaction of cloth
and shells with thin sheets of water. The proposed method works for
both rigid body shells and for deformable manifolds such as cloth, and
we present a two way coupling technique that allows the fluid's
pressure to affect the solid. Examples illustrate that our method
performs well, especially in the difficult case of water and cloth
where it produces visually rich interactions between the particle
level set method for treating the water/air interface and our newly
proposed method for treating the solid/fluid interface. We have
implemented the method on both uniform and adaptive octree grids.

**Real-Time Subspace Integration for St.Venant-Kirchhoff Deformable Models**
(Siggraph 2005)
(project page)

Jernej Barbic,
Doug L. James
(Carnegie Mellon University)

In this paper, we present an approach for fast subspace integration of
reduced-coordinate nonlinear deformable models that is suitable for
interactive applications in computer graphics and haptics. Our
approach exploits dimensional model reduction to build
reduced-coordinate deformable models for objects with complex
geometry. We exploit the fact that model reduction on large
deformation models with linear materials (as commonly used in
graphics) result in internal force models that are simply cubic
polynomials in reduced coordinates. Coefficients of these polynomials
can be precomputed, for efficient runtime evaluation. This allows
simulation of nonlinear dynamics using fast implicit Newmark subspace
integrators, with subspace integration costs independent of geometric
complexity. We present two useful approaches for generating
low-dimensional subspace bases: modal derivatives and an interactive
sketching technique. Mass-scaled principal component analysis
(mass-PCA) is suggested for dimensionality reduction. Finally, several
examples are given from computer animation to illustrate high
performance, including force-feedback haptic rendering of a
complicated object undergoing large deformations.

**Learning Physics-Based Motion Style With Nonlinear Inverse Optimization**
(Siggraph 2005)
(project page)

C. Karen Liu
(University of Washington),
Aaron Hertzmann
(University of Toronto),
Zoran Popovic
(University of Washington)

This paper presents a novel physics-based representation of realistic
character motion. The dynamical model incorporates several factors of
locomotion derived from the biomechanical literature, including
relative preferences for using some muscles more than others, elastic
mechanisms at joints due to the mechanical properties of tendons,
ligaments, and muscles, and variable stiffness at joints depending on
the task. When used in a spacetime optimization framework, the
parameters of this model define a wide range of styles of natural
human movement.
Due to the complexity of biological motion, these style parameters are
too difficult to design by hand. To address this, we introduce
Nonlinear Inverse Optimization, a novel algorithm for estimating
optimization parameters from motion capture data. Our method can
extract the physical parameters from a single short motion sequence.
Once captured, this representation of style is extremely flexible:
motions can be generated in the same style but performing different
tasks, and styles may be edited to change the physical properties of
the body.

**Free Surface Lattice-Boltzmann fluid simulations with and without level sets**
(VMV 2004)
(project page)

Nils Thuerey
Ulrich Ruede

We present two variants of free surface Lattice-Boltzmann fluid
simulations for the animation of liquids in computer graphics. The
Lattice-Boltzmann method is an attractive alternative to conventional
fluid solvers, due to its simplicity and flexibility, especially for
changing geometries and topologies. While our first method directly
calculates the mass fluxes between the cells of the computational
grid, another variant of the method is explained, that uses level
sets to track the fluid surface. This has advantages for the
smoothness of the fluid surface and improves the representation of
details in the free surface, but makes the conservation of mass more
difficult. Several examples will beshown to highlight the differences
between the two methods.

**Contact Handling for Deformable Point-Based Objects**
(VMV 2004)
(project page)

Richard Keiser,
Matthias Muller,
Bruno Heidelberger,
Matthias Teschner,
Markus Gross

This paper presents an approach to collision detection and response
for dynamically deforming point-based objects. Both the volume of an
object and its surface are represented by point sets. In case of a
collision, response forces are computed for penetrating surface
points and distributed to volume points which are used for simulating
the object dynamics. The decoupling of collision handling and
deformation allows for a very stable collision response while
maintaining interactive update rates of the dynamic simulation for
environments with moderate complexity. Simulation results are
presented for elastically and plastically deforming objects with
changing topology.

**Consistent Penetration Depth Estimation for Deformable Collision Response**
(VMV 2004)
(project page)

Bruno Heidelberger,
Matthias Teschner,
Richard Keiser,
Matthias Muller,
Markus Gross

Penalty approaches can be used to efficiently resolve collisions of
dynamically simulated rigid and deformable objects. These methods
compute penalty forces based on the penetration depth of intersecting
objects. However, in discrete-time simulations, this information can
cause non-plausible collision responses in case of large penetrations
or due to the object discretization. In this project, we investigate
methods to compute consistent n-body collision information in order to
reduce collision response artifacts inherent to existing penetration
depth approaches.

**Hierarchy Accelerated Stochastic Collision Detection**
(VMV 2004)
(project page)

Stefan Kimmerle,
Matthieu Nesme,
François Faure

In this paper we present a new framework for collision and
self-collision detection for highly deformable objects such as
cloth. It permits to efficiently trade off accuracy for speed by
combining two different collision detection approaches. We use a newly
developed stochastic method, where close features of the objects are
found by tracking randomly selected pairs of geometric primitives, and
a hierarchy of discrete oriented polytopes (DOPs). This bounding
volume hierarchy (BVH) is used to narrow the regions where random
pairs are generated, therefore fewer random samples are
necessary. Additionally the cost in each time step for the BVH can be
greatly reduced compared to pure BVH-approaches by using a lazy
hierarchy update. For the example of a cloth simulation framework it
is experimentally shown that it is not necessary to respond to all
collisions to maintain a stable simulation. Hence, the tuning of the
computation time devoted to collision detection is possible and yields
faster simulations.

**Physically Based Animation and Rendering of Lightning**
(PG 2004)
(project page)

Theodore Kim,
Ming C. Lin
(University of North Carolina at Chapel Hill)

We present a physically-based method for animating and rendering
lightning and other electric arcs. For the simulation, we present the
dielectric breakdown model, an elegant formulation of electrical
pattern formation. We then extend the model to animate a sustained,
'dancing' electrical arc, by using a simplified Helmholtz equation for
propagating electromagnatic waves. For rendering, we use a convolution
kernel to produce results competitive with Monte Carlo ray
tracing. Lastly, we present user parameters for manipulation of the
simulation patterns.

**Real-Time 3D Fluid Simulation on GPU with Complex Obstacles**
(PG 2004)
(project page)

Youquan Liu,
Enhua Wu,
Xuehui Liu

In this paper, we solve the 3D fluid dynamics problem in a complex
environment by taking advantage of the parallelism and programmability
of GPU. In difference from other methods, innovation is made in two
aspects. Firstly, more general boundary conditions could be processed
on GPU in our method. By the method, we generate the boundary from a
3D scene with solid clipping, making the computation run on GPU
despite of the complexity of the whole geometry scene. Then by
grouping the voxels into different types according to their positions
relative to the obstacles and locating the voxel that determines the
value of the current voxel, we modify the values on the boundaries
according to the boundary conditions. Secondly, more compact structure
in data packing with flat 3D textures is designed at the fragment
processing level to enhance parallelism and reduce execution
passes. The scalar variables including density and temperature are
packed into four channels of texels to accelerate the computation of
3D Navier-Stokes Equations (NSEs). The test results prove the
efficiency of our method, and as a result, it is feasible to run
middle-scale problems of 3D fluid dynamics in an interactive speed for
more general environment with complex geometry on PC platform.

**A Data-driven Approach for Real-Time Clothes Simulation**
(PG 2004)

Frederic Cordier,
Nadia Magnenat-Thalmann

A data-driven approach for real-time processing of clothes,
particularly suitable for simulating dresses worn by virtual
characters, is proposed. It starts, prior to realtime simulation, by
analyzing cloth behavior in relation to the underlying skeleton
movement from a pre-simulated sequence of the cloth obtained using any
high quality offline simulators. The idea is to use this analysis to
find an optimal combination of physics-based simulation and geometric
approximation of the simulator; potentially colliding regions are
defined on the cloth such that they will hold true for the skeleton
movement that closely matches that of pre-simulated sequence. At
runtime, using these analyses, our simulation process provides both
visually pleasing results and performance, as long as the motion of
the character remains sufficiently close to the original sequence used
for the pre-computation. The key contributions of this paper are (1)
efficient collision handling that prunes out potentially colliding
objects by using the off-line simulation sequence as examples; (2)
data-driven fix-up process for the coarse mesh simulation that deduces
the gross behavior of the cloth; and (3) geometric approximation of
the fine mesh deformation, responsible for details in the shape of the
cloth such as wrinkles.

**Measurement-based interactive simulation of viscoelastic solids**
(EG 2004)

Jeff Schoner,
Jochen Lang,
H.-P. Seidel

Animation of viscoelastic solids in entertainment and medical
applications as well as scientific simulation can be improved through
observations of real world objects. This paper presents a method for
simulating viscoelastic solids in real-time for visual and haptic
display along with a method for determining the parameters of the the
underlying model from automated physical measurements of real world
objects. The viscoelastic model is a novel extension of the discrete
Green's function matrix for linear elasticity, which combines static
behavior represented by Green's functions with dynamic behavior
expressed by differential equations inspired by particle systems. We
describe a novel estimation method of dynamic contact behavior for
heterogeneous complex objects based on these measurements. For this
estimation, our method relies only on measurement data previously used
in the acquisition less realistic elastostatic models. In this way our
method allows more physically accurate realism in animation of
viscoelastic solids without large additional computational costs or
any measurements besides those associated with related methods for
elastostatic solids.

**An Oriented Particles and Generalized Spring Model for Fast Prototyping
Deformable Objects**
(EG 2004)

Il-Kwon Jeong, Inho Lee
(Korean Electronics and Telecommunications Research Institute)

We present a new mass-spring system, in particular, by using an
oriented particle and generalized spring model, which can be used for
fast prototyping or animation of deformable objects. Conventional
mass-spring system is widely used especially in cloth
animation. However animating deformable objects such as a jelly cube
requires extra diagonal springs in addition to structural springs in
order to provide shear strain force and guarantee stability on the
original shape formation. One has to use his a priori knowledge or
trial-and-error method to construct a stable spring network for a
given deformable object. This is due to the inherent one-dimensional
nature of the conventional spring model. In order to overcome the
difficulty in designing a spring network and make it possible to
construct a stable network easily and intuitively, we propose an
oriented particle and generalized spring model that reacts against
bending and twisting force as well as stretching. By using our new
mass-spring system, one can easily construct a spring network from a
given geometric model. Moreover, one can animate one-dimensional
flexible object such as a mobile as well as a thin two-dimensional
object with sharp folds or creases. In addition, we present an
offsetting method for tweaking mass-spring system to have valuable
properties that help animating deformable objects with various shapes.

**An Interactive Physically-based Animation System for Dense Meshes**
(EG 2004)

Ryo Kondo, Takashi Kanai (Keio University SFC)

In this paper we describe an interactive physically-based animation
system for dense meshes. Our method extracts a coarse mesh from an
original mesh to make a tetrahedral mesh for the reduction of
computational costs. For computing reaction forces we precompute
penetration depth values and gradients at mesh vertices by creating a
distance field. They are interpolated when collisions are detected and
are used for the calculation of forces with a penalty method. Our
method can handle dense meshes with physically-based animation and
collision response at interactive frame rates.

**Layered Dynamic Control for Interactive Character Swimming**
(SCA 2004)
(project page)
(portal page)

Paul Yang,
Joseph Laszlo,
Karan Singh

This paper proposes a layered strategy for controlling character
motion in a dynamically varying environment. We illustrate this
approach in the context of a physically simulated human swimmer. The
swimmer attempts to follow a dynamic target by augmenting cyclic
stroke control with a set of pre-specified variations, based on the
current state of the character and its environment. Control of a given
swim stroke is decomposed into three layers: a basic stroke sequence,
a set of per-stroke control variations, and a set of continuously
applied control variations. Interactive control of the swimmer is
possible as a result of an efficient physical simulation using a
simplified fluid model. Our results show layered dynamic control to be
an effective adaptive control technique in well conditioned physical
simulations such as swimming, where simulation states resulting from
control errors are recoverable.

**Quasi-Rigid Objects in Contact**
(SCA 2004)
(portal page)
(slides)

Mark Pauly,
Dinesh Pai,
Leo Guibas

We investigate techniques for modeling contact between quasi-rigid
objects - solids that undergo modest deformation in the vicinity of a
contact, while the overall object still preserves its basic shape. The
quasi-rigid model combines the benefits of rigid body models for
dynamic simulation and the benefits of deformable models for resolving
contacts and producing visible deformations. We argue that point cloud
surface representations are advantageous for modeling rapidly varying,
wide area contacts. Using multi-level computations based on point
primitives, we obtain a scalable system that efficiently handles
complex contact configurations, even for high-resolution models
obtained from laser range scans. Our method computes consistent and
realistic contact surfaces and traction distributions, which are
useful in many applications.

**Collision Between Deformable Objects Using a Fast-Marching on Tetrahedral Models**
(SCA 2004)

Damien Marchal,
Fabrice Aubert,
Christophe Chaillou

This paper presents an approach to handling collision between
deformable objects using tetrahedral decomposition. The tetrahedral
volumetric model is often used to simulate deformable objects that
handle cuts and splits. Interaction between such objects in a complex
environment is still an open problem in interactive simulation. This
paper is mainly focused on obtaining a fast computation of a reliable
penalty response. The method consists in using an approximated
distance map to compute a penalty based response. We propose to
compute the distances to the boundary using a modified "Closest Point"
algorithm derived from Fast Marching. The presented algorithm,
inspired by the [FL01], has the advantage of computing rapidly the
Closest Point in the volumetric tetrahedral mesh without any use of
an additional computation grid. From the resulting distance map a
response is computed using a new "segment-in-object" response that
offers more reliable results than the "point-in-object" generally used
in previous works. Using this collision model, simulation at
interactive rate can be considered in an environment composed of
objects that can be deformed and cut.

**Invertible Finite Elements for Robust Simulation of Large Deformation**
(SCA 2004)
(portal page)

Geoffrey Irving,
Joseph Teran,
Ron Fedkiw

We present an algorithm for the finite element simulation of
elastoplastic solids which is capable of robustly and efficiently
handling arbitrarily large deformation. In fact, our model remains
valid even when large parts of the mesh are inverted. The algorithm is
straightforward to implement and can be used with any material
constitutive model, and for both volumetric solids and thin shells
such as cloth. We also provide a mechanism for controlling plastic
deformation, which allows a deformable object to be guided towards a
desired final shape without sacrificing realistic behavior. Finally,
we present an improved method for rigid body collision handling in the
context of mixed explicit/implicit time-stepping.

**Point Based Animation of Elastic, Plastic and Melting Objects**
(SCA 2004)
(project page)
(portal page)
(demo)

Matthias Muller,
Richard Keiser,
Andrew Nealen,
Mark Pauly,
Markus Gross,
Marc Alexa

We present a method for modeling and animating a wide spectrum of
volumetric objects, with material properties anywhere in the range
from stiff elastic to highly plastic. Both the volume and the surface
representation are point based, which allows arbitrarily large
deviations form the original shape. In contrast to previous point
based elasticity in computer graphics, our physical model is derived
from continuum mechanics, which allows the specification of common
material properties such as Young's Modulus and Poisson's Ratio. In
each step, we compute the spatial derivatives of the discrete
displacement field using a Moving Least Squares (MLS) procedure. From
these derivatives we obtain strains, stresses and elastic forces at
each simulated point. We demonstrate how to solve the equations of
motion based on these forces, with both explicit and implicit
integration schemes. In addition, we propose techniques for modeling
and animating a point-sampled surface that dynamically adapts to
deformations of the underlying volumetric model.

**Decomposing Cloth**
(SCA 2004)
(portal page)

Eddy Boxerman,
Uri Ascher

Implicit schemes have become the standard for integrating the
equations of motion in cloth simulation. These schemes, however,
require the solution of a system representing the entire, fully
connected cloth mesh at each time step. In this paper we present
techniques that dynamically improve the sparsity of the underlying
system, ultimately allowing the mesh to be decomposed into multiple
components which can then be solved more efficiently and in parallel.
Our techniques include a novel adaptive implicit-explicit (IMEX)
scheme which takes advantage of simulation parameters, locally in both
space and time, to minimize the coupling of the system. This scheme
further directly improves the efficiency of the computation at each
time step. Other sparsity improvements are obtained by exploiting the
physical model of Choi and Ko (2002), as well as static constraints in
the system.
In addition, we present a *modified* preconditioner for the
modified preconditioned conjugate gradient (MPCG) technique of Baraff
and Witkin (1998), improving its performance by taking constraints
into account.

**Momentum-based Parameterization of Dynamic Character Motion**
(SCA 2004)
(project page)
(portal page)

Yeuhi Abe,
C. Karen Liu,
Zoran Popovic

This paper presents a system for rapid editing of highly dynamic
motion capture data. The heart of this system is an optimization
algorithm that can transform the captured motion so that it satisfies
high-level user constraints while enforcing that the linear and
angular momentum of the motion remain physically plausible. Unlike
most previous approaches to motion editing, our algorithm does not
require pose specification or model reduction, and the user only need
specify high-level changes to the input motion. To preserve the
similar dynamic behavior of the input motion, we introduce a
spline-based parameterization that matches the linear and angular
momentum pattern of the motion capture data. Because our algorithm
enables rapid convergence by presenting a good initial state of the
optimization, the user can efficiently generate a large family of
realistic motions from a single input motion. The algorithm can then
populate the dynamic space of motions by simple interpolation,
effectively parameterizing the space of realistic motions. We show how
this framework can be used to produce an effective interface for rapid
creation of dynamic animations, as well as to drive the dynamic motion
of a character in real-time.

**Directable Photorealistic Liquids**
(SCA 2004)
(portal page)

Nick Rasmussen,
Doug Enright,
Duc Nguyen,
Sebastian Marino,
Nigel Sumner,
Willi Geiger,
Samir Hoon,
Ron Fedkiw

We present a method for the directable animation of photorealistic
liquids using the particle level set method to obtain smooth, visually
pleasing complex liquid surfaces. We also provide for a degree of
control common to particle-only based simulation techniques. A variety
of directable liquid primitive variables, including the isosurface
value, velocity, and viscosity, can be set throughout the
liquid. Interaction of thin liquid sheets with immersed rigid bodies
is improved with newly proposed object-liquid boundary
conditions. Efficient calculation of large-scale animations is
supported via a multiple grid pipelined flow method and a novel moving
grid windowing technique. In addition, we propose a few significant
algorithmic enhancements to the basic liquid simulation algorithm to
provide for the smooth merging of liquid drops, allow for the
efficient calculation of high viscosity liquids, and ensure the proper
treatment of isolated free liquid pockets surrounded by controlled
liquid regions.

**Animation of Reactive Gaseous Fluids through Chemical Kinetics**
(SCA 2004)
(project page)
(portal page)

Insung Ihm,
Byungkwon Kang,
Deukhyun Cha

Although chemically reactive fluids may be used effectively to
increase the reality of visual effects, little work has been done with
the general modeling of chemical reactions in computer animation. In
this paper, we attempt to extend an established, physically based
fluid simulation technique to handle reactive gaseous fluids. The
proposed technique exploits the theory of chemical kinetics to account
for a variety of chemical reactions that are frequently found in
everyday life. In extending the existing fluid simulation method, we
introduce a new set of physically motivated control parameters that
allow an animator to control intuitively the behavior of reactive
fluids. Our method is straightforward to implement, and is flexible
enough to create various interesting visual effects including
explosions and catalysis. We demonstrate the effectiveness of our new
simulation technique by generating several animation examples with
user control.

**Extended Galilean Invariance for Adaptive Fluid Simulation**
(SCA 2004)
(portal page)

Maurya Shah,
Jonathan M. Cohen,
Sanjit Patel,
Penne Lee,
Fred Pighin

In an unbounded physical domain, simulating a turbulent fluid on an
Eulerian grid is rather tricky. Since it is difficult to predict the
motion of the fluid, it is also difficult to guess which
computational domain would allow the simulation of the fluid without
crossing the computational boundaries. To address this dilemma, we
have developed a novel adaptive framework where the simulation grid
follows the motion of the flow. Our technique is based on the
principle of Galilean Invariance and the culling of simulation cells
using a metric derived from continuative boundary conditions. We
describe our framework and showcase its advantages over traditional
techniques. Timing results and visual comparisons are presented.

**Modeling and Editing Flows Using Advected Radial Basis Functions**
(SCA 2004)
(portal page)

Fred Pighin,
Jonathan M. Cohen,
Maurya Shah

Fluid simulations are notoriously difficult to predict and control. As
a result, authoring fluid flows often involves a tedious trial and
error process. There is to date no convenient way of editing a fluid
after it has been simulated. In particular, the Eulerian approach to
fluid simulation is not suitable for flow editing since it does not
provide a convenient spatio-temporal parameterization of the simulated
flows. In this research, we develop a new technique to learn such
parameterization. This technique is based on a new representation, the
Advected Radial Basis Function. It is a time-varying kernel that
models the local properties of the fluid. We describe this
representation and demonstrate its use for interactive
three-dimensional flow editing.

**Flow Tiles**
(SCA 2004)
(project page)
(portal page)

Stephen Chenney

We present *flow tiles*, a novel technique for representing and
designing velocity fields. Unlike existing procedural flow generators,
tiling offers a natural user interface for field design. Tilings can
be constructed to meet a wide variety of external and internal
boundary conditions, making them suitable for inclusion in larger
environments. Tiles offer memory savings through the re-use of
prototypical elements. Each flow tile contains a small field and many
tiles can be combined to produce large flows. The corners and edges of
tiles are constructed to ensure continuity across boundaries between
tiles. In addition, all our tiles and the resulting titing are
divergence-free and hence suitable for representing a range of
effects. We discuss issues that arise in designing flow tiles,
algorithms for creating tilings, and three applications: a crowd on
city streets, a river flowing between banks, and swirling fog. The
first two applications use stationary fields, while the latter
demonstrates a dynamic field.

**Better with Bubbles: Enhancing the Visual Realism of Simulated Fluid**
(SCA 2004)
(project page)
(portal page)

Shannon Greenwood,
Donald House

We present a method for including the visual effect of bubbles in a
computer graphics fluid simulation, thus enhancing the illusion of
realism for a splashing fluid. Previous fluid simulation methods have
not included bubbles. Bubble creation is integrated into the particle
level-set fluid simulation algorithm. Individual bubbles are
approximated by spheres, which form more complex shapes where they
intersect. The rendering of bubbles and fluid are integrated to create
the appearance of one continuous surface. At the fluid-air boundary,
we integrate bubbles whenever level-set marker particles pass from
from the outside to the inside of the fluid. Thus, these particles
represent air that has become trapped within the fluid surface. In
addition, we detect empty pockets within the fluid, that are often
formed due to turbulence, and create bubbles within this space. This
is an inexpensive way of giving the impression that the air trapped in
air pockets has become bubbles. Photo-realistic images of simulation
results are rendered with a raytracer that has been enhanced to
include caustics, and to handle bubble-bubble interfaces. Comparison
of these images with images rendered without bubbles supports our
position that the simple addition of bubbles to a fluid simulation
greatly enhances visual realism.

**A Hybrid Algorithm for Modeling Ice Formation**
(SCA 2004)
(project page)
(portal page)

Theodore Kim,
Michael Henson,
Ming C. Lin

We present a novel algorithm that simulates ice formation. Motivated
by the physical process of ice growth, we develop a novel hybrid
algorithm by synthesizing three techniques: diffusion limited
aggregation, phase field methods, and stable fluid solvers. Each
technique maps to one of the three stages of solidification. The
visual realism of the resulting algorithm appears to surpass that of
each technique alone, particularly in animations of freezing. In
addition, we present a faster, simplified phase field method, as well
as a unified parameterization that enables artistic manipulation of
the simulation. We illustrate the results on arbitrary 3D surfaces.

**Animation and Control of Breaking Waves**
(SCA 2004)
(portal page)

Viorel Mihalef,
Dimitris Metaxas,
Mark Sussman

Controlling fluids is still an open and challenging problem in fluid
animation. In this paper we develop a novel fluid animation control
approach and we present its application to controlling breaking
waves. In our *Slice Method* framework an animator defines the
shape of a breaking wave at a desired moment in its evolution based on
a library of breaking waves. Our system computes then the subsequent
dynamics with the aid of a 3D Navier-Stokes solver. The wave dynamics
previous to the moment the animator exerts control can also be
generated based on the wave library. The animator is thus enabled to
obtain a full animation of a breaking wave while controlling the shape
and the timing of the breaking. An additional advantage of the method
is that it provides a significantly faster method for obtaining the
full 3D breaking wave evolution compared to starting the simulation at
an early stage and using solely the 3D Navier-Stokes equations. We
present a series of 2D and 3D breaking wave animations to demonstrate
the power of the method.

**A Viscous Paint Model for Interactive Applications**
(CASA 2004)
(project page)

William Baxter,
Yuanxin Liu,
Ming C. Lin

We present a novel viscous fluid model for use in real-time
simulation applications, such as interactive painting systems, based
on the well-known Stokes' equations for viscous flow. Our method is
perhaps the first unconditionally stable numerical method that treats
viscous fluid with a free surface boundary. We have integrated our
fluid model with a prototype painting system, which demonstrates the
model's effectiveness in animating viscous fluid flow and capturing a
thick, impasto-like style of painting.

**Modeling and Rendering Viscous Liquids**
(CASA 2004)
(project page)

Kevin Steele,
David Cline,
Parris K. Egbert,
Jonathan Dinerstein

We present a particle-based algorithm for modeling highly viscous
liquids. Using a numerical time-integration of particle acceleration
and velocity, we apply external forces to particles and use a
convenient organization, the adhesion matrix, to represent forces
between different types of liquids and objects. Viscosity is handled
by performing a momentum exchange between particle pairs such that
momentum is conserved. Volume is maintained by iteratively adjusting
particle positions after each time step. We use a two-tiered approach
to time stepping that allows particle positions to be updated many
times per frame while expensive operations, such as calculating
viscosity and adhesion, are done only a few times per frame. The
liquid is rendered using an implicit surface polygonization algorithm,
and we present an implicit function that convolves the liquid surface
with a Gaussian function, yielding a smooth liquid skin.

**Interaction of Fluids with Deformable Solids**
(CASA 2004)

Matthias Muller,
Simon Schirm,
Matthias Teschner,
Bruno Heidelberger,
Markus Gross

In this project, we have investigated a method for simulating the
interaction of fluids with deformable solids. The method is designed
for the use in interactive systems such as virtual surgery simulators
where the real-time interplay of liquids and surrounding tissue is
important. The method models the exchange of momentum between
Lagrangian particle-based fluid models and solids represented by
polygonal meshes. To model the solid-fluid interaction we use virtual
boundary particles. They are placed on the surface of the solid
objects according to Gaussian quadrature rules allowing the
computation of smooth interaction potentials that yield stable
simulations.

**Rigid Fluid: Animating the Interplay Between Rigid Bodies and Fluid**
(Siggraph 2004)
(project page)
(portal page)

Mark Carlson,
Peter J. Mucha,
Greg Turk
(Georgia Institute of Technology)

We present the Rigid Fluid method, a technique for animating the
interplay between rigid bodies and viscous incompressible fluid with
free surfaces. We use distributed Lagrange multipliers to ensure
two-way coupling that generates realistic motion for both the solid
objects and the fluid as they interact with one another. We call our
method the rigid fluid method because the simulator treats the rigid
objects as if they were made of fluid. The rigidity of such an object
is maintained by identifying the region of the velocity field that is
inside the object and constraining those velocities to be rigid body
motion. The rigid fluid method is straightforward to implement,
incurs very little computational overhead, and can be added as a
bridge between current fluid simulators and rigid body solvers. Many
solid objects of different densities (e.g. wood or lead) can be
combined in the same animation.

**A Virtual Node Algorithm for Changing Mesh Topology During Simulation**
(Siggraph 2004)

(portal page)
Neil Molino,
Zhaosheng Bao,
(Stanford University)
Ronald P. Fedkiw
(Stanford University and
Industrial Light + Magic)

We propose a virtual node algorithm that allows material to separate
along arbitrary (possibly branched) piecewise linear paths through a
mesh. The material within an element is fragmented by creating several
replicas of the element and assigning a portion of real material to
each replica. This results in elements that contain both real material
and empty regions. The missing material is contained in another copy
(or copies) of this element. Our new virtual node algorithm
automatically determines the number of replicas and the assignment of
material to each. Moreover, it provides the degrees of freedom
required to simulate the partially or fully fragmented material in a
fashion consistent with the embedded geometry. This approach enables
efficient simulation of complex geometry with a simple mesh, i.e. the
geometry need not align itself with element boundaries. It also
alleviates many shortcomings of traditional Lagrangian simulation
techniques for meshes with changing topology. For example, slivers do
not require small CFL time step restrictions since they are embedded
in well shaped larger elements. To enable robust simulation of
embedded geometry, we propose new algorithms for handling rigid body
and self collisions. In addition, we present several mechanisms for
influencing and controlling fracture with grain boundaries,
prescoring, etc. We illustrate our method for both volumetric and
thin-shell simulations.

**BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models**
(Siggraph 2004)
(project page)
(portal page)

Doug L. James
(Carnegie Mellon University),
Dinesh K. Pai
(Rutgers University)

We introduce the Bounded Deformation Tree, or BD-Tree, which can
perform collision detection with reduced deformable models at costs
comparable to collision detection with rigid objects. Reduced
deformable models represent complex deformations as linear
superpositions of arbitary displacement fields, and are used in a
variety of applications of interactive computer graphics. The BD-Tree
is a bounding sphere hierarchy for output-sensitive collision
detection with such models. Its bounding spheres can be updated after
deformation in any order, and at a cost independent of the geometric
complexity of the model; in fact the cost can be as low as one
multiplication and addition per tested sphere, and at most linear in
the number reduced deformation coordinates. We show that the BD-Tree
is also extremely simple to implement, and performs well in practice
for a variety of real-time and complex off-line deformable simulation
examples.

**Simulating Water and Smoke with an Octree Data Structure**
(Siggraph 2004)
(portal page)

Frank Losasso,
Frederic Gibou
(Stanford University),
Ronald Fedkiw
(Stanford University
and Industrial Light + Magic)

We present a method for simulating water and smoke on an unrestricted
octree data structure exploiting mesh refinement techniques to
capture the small scale visual detail. We propose a new technique for
discretizing the Poisson equation on this octree grid. The resulting
linear system is symmetric positive definite enabling the use of fast
solution methods such as preconditioned conjugate gradients, whereas
the standard approximation to the Poisson equation on an octree grid
results in a non-symmetric linear system which is more
computationally challenging to invert. The semi-Lagrangian
characteristic tracing technique is used to advect the velocity,
smoke density, and even the level set making implementation on an
octree straightforward. In the case of smoke, we have multiple
refinement criteria including object boundaries, optical depth, and
vorticity concentration. In the case of water, we refine near the
interface as determined by the zero isocontour of the level set
function.

**A Method for Animating Viscoelastic Fluids**
(Siggraph 2004)
(project page)
(portal page)

Tolga Goktekin,
Adam W. Bargteil,
James F. O'Brien
(University of California, Berkeley)

This paper describes a technique for animating the behavior of
viscoelastic fluids, such as mucus, liquid soap, pudding, toothpaste,
or clay, that exhibit a combination of both fluid and solid
characteristics. The technique builds upon prior Eulerian methods for
animating incompressible fluids with free surfaces by including
additional elastic terms in the basic Navier-Stokes equations. The
elastic terms are computed by integrating and advecting strain-rate
throughout the fluid. Transition from elastic resistance to viscous
flow is controlled by von Mises's yield condition, and subsequent
behavior is then governed by a quasi-linear plasticity model.

**Target-Driven Smoke Animation**
(Siggraph 2004)
(project pape)
(portal page)

Raanan Fattal,
Dani Lischinski
(The Hebrew University of Jerusalem)

In this paper we present a new method for efficiently controlling
animated smoke. Given a sequence of target smoke states, our method
generates a smoke simulation in which the smoke is driven towards each
of these targets in turn, while exhibiting natural-looking interesting
smoke-like behavior. This control is made possible by two new terms
that we add to the standard flow equations: (i) a driving force term
that causes the fluid to carry the smoke towards a particular target,
and (ii) a smoke gathering term that prevents the smoke from diffusing
too much. These terms are explicitly defined by the instantaneous
state of the system at each simulation timestep. Thus, no expensive
optimization is required, allowing complex smoke animations to be
generated with very little additional cost compared to ordinary flow
simulations.

**Fluid Control Using the Adjoint Method**
(Siggraph 2004)
(project page)
(portal page)

Antoine McNamara,
Adrien Treuille,
Zoran Popović
(University of Washington),
Jos Stam
(Alias Systems)

In recent years, the graphics community has made great strides
modeling complex dynamic phenomena through physical simulation. These
simulation techniques can generate very realistic results, but the
animations they produce are often difficult to control. This project
is concerned with developing intuitive, efficient techniques for
controlling the high-level behavior of complex physical
simulations. Our initial work has focused on fluid simulations, which
are highly nonlinear and hence especially difficult to control.

**Interactive Virtual Materials**
(GI 2004)
(portal page)
(demo)

Matthias Muller,
Markus Gross

In this paper we present a fast and robust approach for simulating
elasto-plastic materials and fracture in real time. Our method extends
the warped stiffness finite element approach for linear elasticity and
combines it with a strain-state-based plasticity model. The internal
principal stress components provided by the finite element computation
are used to determine fracture locations and orientations. We also
present a method to consistently animate and fracture a detailed
surface mesh along with the underlying volumetric tetrahedral
mesh. This multi-resolution strategy produces realistic animations of
a wide spectrum of materials at interactive rates that have typically
been simulated off-line thus far.

**Practical Physics for Articulated Characters**
(GDC 2004)

Vangelis Kokkevis(Sony Computer Entertainment America)

This presentation describes a set of techniques for implementing a
fast and stable dynamics simulator for articulated characters using an
analytical constraint approach combined with Featherstone's
linear-time forward dynamics algorithm. It presents an efficient method
for enforcing multiple simultaneous constraints on an articulated
character in order to control the character's motion and model
its interactions with the environment. The technique described employs
an optimized process derivedfrom Featherstone's recursive
algorithm to form a linear system representing the constraint
conditions at each time instant of the simulation. The system is
subsequently solved to compute the exact magnitude of the forces
necessary to satisfy theseconstraints. This work demonstrates how a
combination of unilateral and bilateral constraints can be used to
model the effects of impacts and contacts, to enforce joint limits,
and to accurately control limb motion through trajectory
following. The algorithms are presented from a practical standpoint
and pseudocode is provided to facilitate their implementation. The
goal of this presentation is twofold: first, to convince developers
that building a practical, stable, real-time physics simulator for
articulated characters is a tractable problem, and second, to give
them enough confidence and information to start building one for their
game.

**Using Verlet Integration and Constraints in a Six Degree of Freedom Rigid Body Physics Simulation**
(GDC 2004)

Rick Baltman
(Rainbow Studios)

At the 1999 Game Developers Conference, Thomas Jakobsen presented a
semi-implicit rigid body physics simulation. The simulation could
integrate stiff systems at the time steps used in games without the
need to compute expensive Jacobian matrices and had very simple
constraint implementations. However, the simulation was limited
because it did not include a velocity state and it did not integrate
the rotational equations of motion, necessitating large numbers of
particles and distance constraints to simulate a single rigid body. It
was also difficult to set up pin constraints, common in rag-doll
simulations. By extending the simulation to six degrees of freedom
through the Verlet-like integration of a state quaternion, joint
constraints became simple and straightforward, though a slightly more
complicated constraint equation was required. Two methods for
implementing the additional degrees of freedom are presented; one that
uses the current quaternion and last quaternion as the system states
and one that uses the quaternion and the angular rate. The advantages
and disadvantages of both methods are discussed. The equations used in
pin and angle constraints and the method for resolving collisions are
presented. This simulation was developed for the game MX Unleashed,
published by THQ.

**Physical Touch-Up of Human Motions**
(PG 2003)
(portal page)

Hyun Joon Shin,
Lucas Kovar,
Michael Gleicher

Many popular motion editing methods do not take physical principles
into account potentially implausible motions. This paper introduces an
efficient method for touching up edited motions to improve physical
plausibility. We start by estimating a mass distribution consistent
with reference motions known to be physically correct. The edited
motion is then divided into ground and flight stages and adjusted to
enforce appropriate physical laws for, respectively, zero moment point
(ZMP) constraints and correct ballistic trajectory. Unlike previous
methods, we do not solve a nonlinear optimization to calculate the
adjustment. Instead, closed-form methods are used to construct a
hierarchical displacement map which sequentially refines
user-specified degrees of freedom at different scales. THis is
combined with standard methods for kinematic constraint enforcement,
yielding an efficient and scalable editing method that allows users to
model real human behaviors. The potential of our approach is
demonstrated in a number of examples.

**
Adaptive Grouping and Subdivision for Simulating Hair Dynamics
**
(PG-2003)
(project page)
(portal page)

Kelly Ward
Ming C. Lin

We present a novel approach for adaptively grouping and subdividing
hair using discrete level-of-detail (LOD) representations. The set of
discrete LODs include hair strands, clusters and strips. Their
dynamic behavior is controlled by a base skeleton. The base skeletons
are subdivided and grouped to form clustering hierarchies using a
quad-tree data structure during the precomputation. At run time, our
algorithm traverses the hierarchy to create continuous LODs on the
fly and chooses both the appropriate discrete and continuous hair LOD
representations based on the motion, the visibility, and the viewing
distance of the hair from the viewer. Our collision detection for
hair represented by the proposed LODs relies on a family of "swept
sphere volumes" for fast and accurate intersection computations. We
also use an implicit integration method to achieve simulation
stability while allowing us to take large time steps. Together, these
approaches for hair simulation and collision detection offer the
flexibility to balance between the overall performance and visual
quality of the animated hair. Furthermore, our approach is capable of
modeling various styles, lengths, and motion of hair.

**Particle-Based Simulation of Fluids**
(EG 2003)
(project page)

Simon Premoze,
Tolga Tasdizen,
James Bigler,
Aaron Lefohn,
Ross Whitaker
(University of Utah)

Due to our familiarity with how fluids move and interact, as well as
their complexity, plausible animation of fluids remains a challenging
problem. We present a particle interaction method for simulating
fluids. The underlyingequations of fluid motion are discretized using
moving particles and their interactions. The method allows
simulationand modeling of mixing fluids with different physical
properties, fluid interactions with stationary objects, andfluids that
exhibit significant interface breakup and fragmentation. The gridless
computational method is suitedfor medium scale problems since
computational elements exist only where needed. The method fits well
into thecurrent user interaction paradigm and allows easy user control
over the desired fluid motion.

**Particle-Based Fluid Simulation for Interactive Applications**
(SCA 2003)
(portal page)

Matthias Muller,
David Charypar,
Markus Gross
(ETH Zurich)

Realistically animated fluids can add substantial realism to
interactive applications such as virtual surgery simulators or
computer games. In this paper we propose an interactive method based
on Smoothed Particle Hydrodynamics (SPH) to simulate fluids with free
surfaces. The method is an extension of the SPH-based technique by
Desbrun to animate highly deformable bodies. We gear the method
towards fluid simulation by deriving the force density fields
directly from the Navier-Stokes equation and by adding a term to
model surface tension effects. In contrast to Eulerian grid-based
approaches, the particle-based approach makes mass conservation
equations and convection terms dispensable which reduces the
complexity of the simulation. In addition, the particles can directly
be used to render the surface of the fluid. We propose methods to
track and visualize the free surface using point splatting and
marching cubes-based surface reconstruction. Our animation method is
fast enough to be used in interactive systems and to allow for user
interaction with models consisting of up to 5000 particles.

**A Practical Dynamics System**
(SCA 2003)
(portal page)

Zoran Kacic-Alesic,
Marcus Nordenstam,
David Bullock
(Industrial Light + Magic)

We present an effective production-proven dynamics system. It uses an
explicit time differencing method that is efficient, reasonably
accurate, conditionally stable, and above all simple to implement. We
describe issues related to integration of physically based simulation
techniques into an interactive animation system, present a high level
description of the architecture of the system, report on techniques
that work, and provide observations that may seem obvious, but only
in retrospect. Applications include rigid and deformable body
dynamics, particle dynamics, and at a basic level, hair and cloth
simulation.

**Discrete Shells**
(SCA 2003)
(project page)
(portal page)

Eitan Grinspun,
(California Institute of Technology),
Anil Hirani
(Caltech),
Mathieu Desbrun
(University of Southern California),
Peter Schroder
(California Institute of Technology)

In this paper we introduce a discrete shell model describing the
behavior of thin flexible structures, such as hats, leaves, and
aluminum cans, which are characterized by a curved undeformed
configuration. Previously such models required complex continuum
mechanics formulations and correspondingly complex algorithms. We show
that a simple shell model can be derived geometrically for triangle
meshes and implemented quickly by modifying a standard cloth
simulator. Our technique convincingly simulates a variety of curved
objects with materials ranging from paper to metal, as we demonstrate
with several examples including a comparison of a real and simulated
falling hat.

**Simulation of Clothing with Folds and Wrinkles**
(SCA 2003)
(project page)
(portal page)

Robert Bridson,
Sebastian Marino
(Industrial Light + Magic),
Ronald P. Fedkiw
(Stanford University and
Industrial Light + Magic)

Clothing is a fundamental part of a character's persona, a key
storytelling tool used to convey an intended impression to the
audience. Draping, folding, wrinkling, stretching, etc. all convey
meaning, and thus each is carefully controlled when filming live
actors. When making films with computer simulated cloth, these subtle
but important elements must be captured. In this paper we present
several methods essential to matching the behavior and look of
clothing worn by digital stand-ins to their real world
counterparts. Novel contributions include a mixed explicit/implicit
time integration scheme, a physically correct bending model with
(potentially) nonzero rest angles for pre-shaping wrinkles, an
interface forecasting technique that promotes the development of
detail in contact regions, a post-processing method for treating
cloth-character collisions that preserves folds and wrinkles, and a
dynamic constraint mechanism that helps to control large scale
folding. The common goal of all these techniques is to produce a cloth
simulation with many folds and wrinkles improving the realism.

**Efficient Synthesis of Physically Valid Human Motion**
(Siggraph 2003)
(portal page)
(project page)

Anthony C. Fang,
Nancy S. Pollard
(Brown University)

Optimization is a promising way to generate new animations from a
minimal amount of input data. Physically based optimization
techniques, however, are difficult to scale to complex animated
characters, in part because evaluating and differentiating physical
quantities becomes prohibitively slow. Traditional approaches often
require optimizing or constraining parameters involving joint torques;
obtaining first derivatives for these parameters is generally an O(D2)
process, where D is the number of degrees of freedom of the
character. In this paper, we describe a set of objective functions and
constraints that lead to linear time analytical first derivatives. The
surprising finding is that this set includes constraints on physical
validity, such as ground contact constraints. Considering only
constraints and objective functions that lead to linear time first
derivatives results in fast per-iteration computation times and an
optimization problem that appears to scale well to more complex
characters. We show that qualities such as squash-and-stretch that are
expected from physically based optimization result from our
approach. Our animation system is particularly useful for synthesizing
highly dynamic motions, and we show examples of swinging and leaping
motions for characters having from 7 to 22 degrees of freedom.

**Smoke Simulation For Large Scale Phenomena**
(Siggraph 2003)
(portal page)

Nick Rasmussen
(Industrial Light + Magic),
Duc Nguyen
(Stanford University and
Industrial Light + Magic), Willi Geiger
(Industrial Light + Magic),
Ronald P. Fedkiw
(Stanford University and
Industrial Light + Magic)

In this paper, we present an efficient method for simulating highly
detailed large scale participating media such as the nuclear
explosions shown in figure 1. We capture this phenomena by simulating
the motion of particles in a fluid dynamics generated velocity
field. A novel aspect of this paper is the creation of highly detailed
three-dimensional turbulent velocity fields at interactive rates using
a low to moderate amount of memory. The key idea is the combination of
two-dimensional high resolution physically based flow fields with a
moderate sized three-dimensional Kolmogorov velocity field tiled
periodically in space.

**Animating Suspended Particle Explosions**
(Siggraph 2003)
(project page)
(portal page)

Bryan E. Feldman,
James F. O'Brien,
Okan Arikan
(University of California, Berkeley)

This paper describes a method for animating suspended particle
explosions. Rather than modeling the numerically troublesome, and
largely invisible blast wave, the method uses a relatively stable
incompressible fluid model to account for the motion of air and hot
gases. The fluid's divergence field is adjusted directly to account
for detonations and the generation and expansion of gaseous combustion
products. Particles immersed in the fluid track the motion of
particulate fuel and soot as they are advected by the
fluid. Combustion is modeled using a simple but effective process
governed by the particle and fluid systems. The method has enough
flexibility to also approximate sprays of burning liquids. This paper
includes several demonstrative examples showing air bursts, explosions
near obstacles, confined explosions, and burning sprays. Because the
method is based on components that allow large time integration steps,
it only requires a few seconds of computation per frame for the
examples shown.

**Keyframe Control of Smoke Simulations**
(Siggraph 2003)
(project page)
(portal page)

Adrien Treuille,
Antoine McNamara,
Zoran Popović
(University of Washington),
Jos Stam
(Alias|Wavefront)

We describe a method for controlling smoke simulations through
user-specified keyframes. To achieve the desired behavior, a
continuous quasi-Newton optimization solves for appropriate "wind"
forces to be applied to the underlying velocity field throughout the
simulation. The cornerstone of our approach is a method to efficiently
compute exact derivatives through the steps of a fluid simulation. We
formulate an objective function corresponding to how well a simulation
matches the user's keyframes, and use the derivatives to solve for
force parameters that minimize this function. For animations with
several keyframes, we present a novel multiple-shooting approach. By
splitting large problems into smaller overlapping subproblems, we
greatly speed up the optimization process while avoiding certain local
minima.

**Untangling Cloth**
(Siggraph 2003)
(portal page)

David Baraff,
Andrew Witkin, Michael Kass
(Pixar Animation Studios)

Deficient cloth-to-cloth collision response is the most serious
shortcoming of most cloth simulation systems. Past approaches to
cloth-cloth collision have used history to decide whether nearby cloth
regions have interpenetrated. The biggest pitfall of history-based
methods is that an error anywhere along the way can give rise to
persistent tangles. This is a particularly serious issue for
production character animation, because characters' bodies routinely
self-intersect, for instance in the bend of an elbow or knee, or where
the arm or hand rests against the body. Cloth that becomes pinched in
these regions is often forced into jagged self-intersections that
defeat history-based methods, leaving a tangled mess when the body
parts separate. This paper describes a history-free cloth collision
response algorithm based on global intersection analysis of cloth
meshes at each simulation step. The algorithm resolves tangles that
arise during pinching as soon as the surrounding geometry permits, and
also resolves tangled initial conditions. The ability to untangle
cloth after pinching is not sufficient, because standard cloth-solid
collision algorithms handle pinches so poorly that they often give
rise to visible flutters and other simulation artifacts during the
pinch. As a companion to the global intersection analysis method, we
present a cloth-solid collision algorithm called collision
flypapering, that eliminates these artifacts. The two algorithms
presented have been used together extensively and successfully in a
production animation environment.

**Nonconvex Rigid Bodies with Stacking**
(Siggraph 2003)
(project page)
(portal page)

Eran Guendelman,
Robert Bridson,
Ronald P. Fedkiw
(Stanford University)

We consider the simulation of nonconvex rigid bodies focusing on
interactions such as collision, contact, friction (kinetic, static,
rolling and spinning) and stacking. We advocate representing the
geometry with both a triangulated surface and a signed distance
function defined on a grid, and this dual representation is shown to
have many advantages. We propose a novel approach to time integration
merging it with the collision and contact processing algorithms in a
fashion that obviates the need for ad hoc threshold velocities. We
show that this approach matches the theoretical solution for blocks
sliding and stopping on inclined planes with friction. We also present
a new shock propagation algorithm that allows for efficient use of the
propagation (as opposed to the simultaneous) method for treating
contact. These new techniques are demonstrated on a variety of
problems ranging from simple test cases to stacking problems with as
many as 1000 nonconvex rigid bodies with friction as shown in Figure 1.

**Precomputing Interactive Dynamic Deformable Scenes**
(Siggraph 2003)
(project page)
(portal page)

Doug L. James,
Kayvon Fatahalian
(Carnegie Mellon University)

We present an approach for precomputing data-driven models of
interactive physically based deformable scenes. The method permits
real-time hardware synthesis of nonlinear deformation dynamics,
including self-contact and global illumination effects, and supports
real-time user interaction. We use data-driven tabulation of the
system's deterministic state space dynamics, and model reduction to
build efficient low-rank parameterizations of the deformed shapes. To
support runtime interaction, we also tabulate impulse response
functions for a palette of external excitations. Although our approach
simulates particular systems under very particular interaction
conditions, it has several advantages. First, parameterizing all
possible scene deformations enables us to precompute novel reduced
coparameterizations of global scene illumination for low-frequency
lighting conditions. Second, because the deformation dynamics are
precomputed and parameterized as a whole, collisions are resolved
within the scene during precomputation so that runtime self-collision
handling is implicit. Optionally, the data-driven models can be
synthesized on programmable graphics hardware, leaving only the
low-dimensional state space dynamics and appearance data models to be
computed by the main CPU.

**Improvements on a simple muscle-based 3D face for realistic facial expressions**
(CASA 2003)

The Duy Bui,
Dirk Heylen,
Anton Nijholt

Facial expressions play an important role in face-to-face
communication. With the development of personal computers capable of
rendering high quality graphics, computer facial animation has
produced more and more realistic facial expressions to enrich
human-computer communication. In this paper, we present a simple
muscle-based 3D face model that can produce realistic facial
expressions in real-time. We extend Waters. muscle model to generate
bulges and wrinkles and to improve the combination of multiple muscle
actions. In addition, we present techniques to reduce the computation
burden on the muscle model.

**Modeling Hair Using Level-of-Detail Representations**
(CASA 2003)
(project page)
(portal page)

Kelly Ward,
Ming C. Lin,
Joohi Lee,
Susan Fisher, Dean Macri

We present a novel approach for modeling hair using level-of-detail
representations. The set of representations include individual
strands, hair clusters, and hair strips. They are represented using
subdivision curves or surfaces, and have the same underlying base
skeleton to maintain consistent high-level physical behavior when a
transition between different levels of detail occurs. This framework
supports automatic simplification of dynamic simulation, collision
detection, and graphical rendering of animated hair. It also offers
flexibility to balance between the overall performance and visual
quality, and can be used to model and render different hairstyles. We
have used these level-of-detail representations to animate various
hairstyles and obtained noticeable performance improvement, with
little loss in visual quality. This framework enables fast dynamic
simulation for animating hair of modest lengths at interactive rates.

**Clothing Manipulation**
(UIST 2002)
(project page)
(portal page)

Takeo Igarashi
(University of Tokyo),
John F. Hughes
(Brown University)

This paper presents interaction techniques (and the underlying
implementations) for putting clothes on a 3D character and
manipulating them. The user paints freeform marks on the clothes and
corresponding marks on the 3D character; the system then puts the
clothes around the body so that corresponding marks match. Internally,
the system grows the clothes on the body surface around the marks
while maintaining basic cloth constraints via simple relaxation
steps. The entire computation takes a few seconds. After that, the
user can adjust the placement of the clothes by an enhanced dragging
operation. Unlike standard dragging where the user moves a set of
vertices in a single direction in 3D space, our dragging operation
moves the cloth along the body surface to make possible more flexible
operations. The user can apply pushpins to fix certain cloth points
during dragging. The techniques are ideal for specifying an initial
cloth configuration before applying a more sophisticated cloth
simulation.

**
Fast Penetration Depth Computation For Physically-based Animation
**
(SCA 2002)
(project page)
(portal page)

Young Kim,
Miguel Otaduy,
Ming Lin,
Dinesh Manocha

We present a novel and fast algorithm to compute penetration depth
(PD) between two polyhedral models for physically-based
animation. Given two overlapping polyhedra, it computes the minimal
translation distance to separate them using a combination of
object-space and image-space techniques. The algorithm computes
pairwise Minkowski sums of decomposed convex pieces and performs a
closest point query using rasterization hardware. It uses bounding
volume hierarchies, object-space and image-space culling algorithms to
further accelerate the computation and refines the estimated PD in a
hierarchical manner. We demonstrate its application to contact
response computation and a time-stepping method for dynamic
simulation.

**A Multiresolution Framework for Dynamic Deformations**
(SCA 2002)
(project page)
(portal page)

Steve Capell
Seth Green
Brian Curless
Tom Duchamp
Zoran Popović

We present a novel framework for the dynamic simulation of elastic
deformable solids. Our approach combines classical finite element
methodology with a multiresolution subdivision framework in order to
produce fast, easy to use, and realistic animations. We represent
deformations using a hierarchical basis constructed using volumetric
subdivision. The subdivision framework provides topological
flexibility and the hierarchical basis allows the simulation to add
detail where it is needed. Since volumetric parameterization is
difficult for complex models, we support the embedding of objects in
domains that are easier to parameterize.

**
Stable Real-Time Deformations
**
(SCA 2002)
(portal page)
(applet)

Matthias Muller,
Leonard McMillan,
Julie Dorsey,
Robert Jagnow,
Barbara Cutler

The linear strain measures that are commonly used in real-time
animations of deformable objects yield fast and stable
simulations. However, they are not suitable for large
deformations. Recently, more realistic results have been achieved in
computer graphics by using Green's non-linear strain tensor, but the
non-linearity makes the simulation more costly and introduces
numerical problems.In this paper, we present a new simulation
technique that is stable and fast like linear models, but without the
disturbing artifacts that occur with large deformations. As a
precomputation step, a linear stiffness matrix is computed for the
system. At every time step of the simulation, we compute a tensor
field that describes the local rotations of all the vertices in the
mesh. This field allows us to compute the elastic forces in a
non-rotated reference frame while using the precomputed stiffness
matrix. The method can be applied to both finite element models and
mass-spring systems. Our approach provides robustness, speed, and a
realistic appearance in the simulation of large deformations.

**Melting and Flowing**
(SCA 2002)
(project page)
(portal page)

Mark Carlson,
Peter J. Mucha,
R. Brooks Van Horn III,
Greg Turk
(Georgia Institute of Technology)

We present a fast and stable system for animating materials that melt,
flow, and solidify. Examples of real-world materials that exhibit
these phenomena include melting candles, lava flow, the hardening of
cement, icicle formation, and limestone deposition. We animate such
phenomena by physical simulation of fluids --- in particular the
incompressible viscous Navier-Stokes equations with free surfaces,
treating solid and nearly-solid materials as very high viscosity
fluids. The computational method is a modification of the
Marker-and-Cell (MAC) algorithm in order to rapidly simulate fluids
with variable and arbitrarily high viscosity. This allows the
viscosity of the material to change in space and time according to
variation in temperature, water content, or any other spatial
variable, allowing different locations in the same continuous material
to exhibit states ranging from the absolute rigidity or slight bending
of hardened wax to the splashing and sloshing of water. We create
detailed polygonal models of the fluid by splatting particles into a
volumetric grid and we render these models using ray tracing with
sub-surface scattering. We demonstrate the method with examples of
several viscous materials including melting wax and sand drip castles.

**CHARMS: A Simple Framework for Adaptive Simulation**
(Siggraph 2002)
(portal page)
(slides)

Eitan Grinspun
(California Institute of Technology),
Petr Krysl
(University of California, San Diego),
Peter Schröder
(California Institute of Technology)

Finite element solvers are a basic component of simulation
applications; they are common in computer graphics, engineering, and
medical simulations. Although adaptive solvers can be of great value
in reducing the often high computational cost of simulations they are
not employed broadly. Indeed, building adaptive solvers can be a
daunting task especially for 3D finite elements. In this paper we are
introducing a new approach to produce conforming, hierarchical,
adaptive refinement methods (CHARMS). The basic principle of our
approach is to refine basis functions, not elements. This removes a
number of implementation headaches associated with other approaches
and is a general technique independent of domain dimension (here 2D
and 3D), element type (eg, triangle, quad, tetrahedron, hexahedron),
and basis function order (piecewise linear, higher order B-splines,
Loop subdivision, etc.). The (un-)refinement algorithms are simple and
require little in terms of data structure support. We demonstrate the
versatility of our new approach through 2D and 3D examples, including
medical applications and thin-shell animations.

**Graphical Modeling and Animation of Ductile Fracture**
(Siggraph 2002)
(project page)
(portal page)

James F. O'Brien,
Adam W. Bargteil
(University of California, Berkeley),
Jessica K. Hodgins
(Carnegie Mellon University)

In this paper, we describe a method for realistically animating
ductile fracture in common solid materials such as plastics and
metals. The effects that characterize ductile fracture occur due to
interaction between plastic yielding and the fracture process. By
modeling this interaction, our ductile fracture method can generate
realistic motion for a much wider range of materials than could be
realized with a purely brittle model. This method directly extends our
prior work on brittle fracture [O'Brien and Hodgins, SIGGRAPH 99]. We
show that adapting that method to ductile as well as brittle materials
requires only a simple to implement modification that is
computationally inexpensive. This paper describes this modification
and presents results demonstrating some of the effects that may be
realized with it.

**Robust treatment of collisions, contact and friction for cloth animation**
(Siggraph 2002)
(project page)
(portal page)
(slides)

Robert Bridson,
Ronald P. Fedkiw
(Stanford University and
Industrial Light + Magic),
John Anderson

We present an algorithm to efficiently and robustly process
collisions, contact and friction in cloth simulation. It works with
any technique for simulating the internal dynamics of the cloth, and
allows true modeling of cloth thickness. We also show how our
simulation data can be post-processed with a collision-aware
subdivision scheme to produce smooth and interference free data for
rendering.

**Stable but Responsive Cloth**
(Siggraph 2002)
(portal page)
(project page)
(slides)

Kwang-Jin Choi,
Hyeong-Seok Ko
(Seoul National University)

We present a semi-implicit cloth simulation technique that is very
stable yet also responsive. The stability of the technique allows the
use of a large fixed time step when simulating all types of fabrics
and character motions. The animations generated using this technique
are strikingly realistic. Wrinkles form and disappear in a quite
natural way, which is the feature that most distinguishes textile
fabrics from other sheet materials. Significant improvements in both
the stability and realism were made possible by overcoming the
post-buckling instability as well as the numerical instability. The
instability caused by buckling arises from a structural instability
and therefore cannot be avoided by simply employing a semi-implicit
method. Addition of a damping force may help to avoid instabilities;
however, it can significantly degrade the realism of the cloth
motion. The method presented here uses a particle-based physical model
to handle the instability in the post-buckling response without
introducing any fictitious damping.

**Animation and Rendering of Complex Water Surfaces**
(Siggraph 2002)
(project page)
(portal page)

Douglas P. Enright,
Steve Marschner,
Ronald Fedkiw
(Stanford University)

We present a new method for the animation and rendering of
photo-realistic water effects. Our method is designed to produce
visually plausible three dimensional effects, for example the pouring
of water into a glass (see figure 1) and the breaking of an ocean
wave, in a manner which can be used in a computer animation
environment. In order to better obtain photorealism in the behavior
of the simulated water surface, we introduce a new "thickened" front
tracking technique to accurately represent the water surface and a
new velocity extrapolation method to move the surface in a smooth,
water-like manner. The velocity extrapolation method allows us to
provide a degree of control to the surface motion, e.g. to generate a
windblown look or to force the water to settle quickly. To ensure
that the photorealism of the simulation carries over to the final
images, we have integrated our method with an advanced physically
based rendering system.

**Physically Based Modeling and Animation of Fire**
(Siggraph 2002)
(project page)
(portal page)

Duc Nguyen,
Ronald Fedkiw,
Henrik Wann Jensen
(Stanford University)

We present a physically based method for modeling and animating
fire. Our method is suitable for both smooth (laminar) and turbulent
flames, and it can be used to animate the burning of either solid or
gas fuels. We use the incompressible Navier-Stokes equations to
independently model both vaporized fuel and hot gaseous products. We
develop a physically based model for the expansion that takes place
when a vaporized fuel reacts to form hot gaseous products, and a
related model for the similar expansion that takes place when a solid
fuel is vaporized into a gaseous state. The hot gaseous products,
smoke and soot rise under the influence of buoyancy and are rendered
using a blackbody radiation model. We also model and render the blue
core that results from radicals in the chemical reaction zone where
fuel is converted into products. Our method allows the fire and smoke
to interact with objects, and flammable objects can catch on fire.

**Interactive Skeleton-Driven Dynamic Deformations**
(Siggraph 2002)
(project page)
(portal page)

Steve Capell
Seth Green
Brian Curless
Tom Duchamp
Zoran Popović

This paper presents a framework for the skeleton-driven animation of
elastically deformable characters. A character is embedded in a coarse
volumetric control lattice, which provides the structure needed to
apply the finite element method. To incorporate skeletal controls, we
introduce line constraints along the bones of simple skeletons. The
bones are made to coincide with edges of the control lattice, which
enables us to apply the constraints efficiently using algebraic
methods. To accelerate computation, we associate regions of the
volumetric mesh with particular bones and perform locally linearized
simulations, which are blended at each time step. We define a
hierarchical basis on the control lattice, so for detailed
interactions the simulation can adapt the level of detail. We
demonstrate the ability to animate complex models using simple
skeletons and coarse volumetric meshes in a manner that simulates
secondary motions at interactive rates.

**
Real-Time Simulation of Deformation and Fracture of Stiff Materials
**
(CAS 2001)
(portal page)

Matthias Muller,
Leonard McMillan,
Julie Dorsey,
Robert Jagnow

Existing techniques for real-time simulation of object deformation are
well suited for animating soft materials like human tissue or
two-dimensional systems such as cloth. However, simulation of
deformation in malleable materials and fracture in brittle materials
has only been done offline because the underlying equations of motion
are numericaly stiff, requiring many small steps in explicit
integration schemes. In contrast, the better-behaved implicit
integration techniques are more expensive per time step, particularly
for volumetric meshes. We present a stable hybrid method for
simulating deformation and fracture of materials in real-time. In our
system, the effects of impact forces are computed only at discrete
collision events. At these impacts, we treat objects as if they are
anchored and compute their static equilibrium response using the
Finite Element technique. Static analysis is not time-step bound and
its stability is independent of the stiffness of the equations. The
resulting deformations, or possible fractures, are computed based on
internal stress tensors. Between collisions, disconnected objects are
treated as rigid bodies. The simulator is demonstrated as part of a
system that provides the user with physically-based tools to
interactively manipulate 3D models.

**
Deformed Distance Fields for Simulation of Non-Penetrating Flexible Bodies
**
(CAS 2001)
(project page)
(portal page)

Susan Fisher,
Ming C. Lin

We present a novel penetration depth estimation algorithm based on the
use of deformed distance fields for simulation of non-penetrating
flexible bodies. We assume that the continuum of non-rigid models are
discretized using standard techniques, such as finite element
methods. As the objects deform, the distance fields are deformed
accordingly to estimate penetration depth, allowing enforcement of
non-penetration constraints between two colliding elastic bodies. Our
approach can automatically handle self-penetration and
inter-penetration in a uniform manner. We demonstrate its
effectiveness on moderately complex animated scenes.

**
A Simple Physics Model to Animate Human Hair Modeled in 2D Strips in Real Time
**
(CAS 2001)
(portal page)

Chuan Koon Koh,
Zhiyong Huang

This paper presents a simple Physics model to animate human hair
modeled in 2D strips in real time. A major difficulty in, animating
human hair results from the large number of individual hair strands in
a hairstyle. To address this problem, we have presented a framework of
human hair modeling based on grouping hair strands into strips. Each
hair strip is modeled by one patch of parametric surface. Polygon
tessellation and the alpha-mapping using hair textures are then
applied. To continue that work, we present a simple Physics model. In
particular, a simple dynamic model is adapted and applied to the
control point meshes. A set of dynamics equations are defined and
solved. The parametric representation of hair strips can handle
deformation of any complexity and still appear smooth. Moreover,
because the number of control points is much smaller than that of the
tessellated triangle vertices, the computation is fast and achieves
real time animation. The animation of hair is controlled using
event-triggered procedural animation primitives that implement wind,
gravity as well as head movement, Inter hair strip collision avoidance
is achieved by introducing springs between any two neighboring hair
strips. Collision detection and avoidance of hair with other objects
is implemented using ellipsoids and reaction constraints.

**
A Layered Wisp Model for Simulating Interactions inside Long Hair
**
(CAS 2001)
(project page)
(portal page)

Eric Plante,
Marie-Paule Cani,
Pierre Poulin

This paper presents a method for animating long hair while modelling
both interactions between the hair and the character's body and
between different hair wisps. Our method relies on a layered model
paradigm. Hair is structured into a number of volumetric wisps whose
motion and deformation are computed using a layered model: A first
layer, the skeleton curve, computes the large scale motion of a
wisp. This skeleton is coated by a second layer, the deformable wisp
envelope linked to the skeleton through highly viscous springs. A
third layer is used for rendering the individual hair strands within
each wisp. During motion, anisotropic interactions are computed
between hair wisps, in addition to interactions with character body:
two quasi-parallel wisps are allowed to interpenetrate while a
viscous collision is computed between colliding wisps of different
orientation. This results in a visually-realistic animation, that
captures both continuities and discontinuities that can be observed
in thick, long hair.

**Practical Animations of Liquids**
(Siggraph 2001)
(portal page)

Nick Foster
(PDI/DreamWorks),
Ronald Fedkiw
(Stanford University)

We present a general method for modeling and animating liquids. The
system is specifically designed for computer animation and handles
viscous liquids as they move in a 3D environment and interact with
graphics primitives such as parametric curves and moving polygons. We
combine an appropriately modified semi-Lagrangian method with a new
approach to calculating fluid flow around objects. This allows us to
efficiently solve the equations of motion for a liquid while retaining
enough detail to obtain realistic looking behavior. The object
interaction mechanism is extended to provide control over the liquid s
3D motion. A high quality surface is obtained from the resulting
velocity field using a novel adaptive technique for evolving an
implicit surface.

**Visual Simulation of Smoke**
(Siggraph 2001)
(project page)
(portal page)

Ronald Fedkiw,
Henrik Wann Jensen
(Stanford University),
Jos Stam
(Alias|Wavefront)

In this paper, we propose a new approach to numerical smoke simulation
for computer graphics applications. The method proposed here exploits
physics unique to smoke in order to design a numerical method that is
both fast and efficient on the relatively coarse grids traditionally
used in computer graphics applications (as compared to the much finer
grids used in the computational fluid dynamics literature). We use the
inviscid Euler equations in our model, since they are usually more
appropriate for gas modeling and less computationally intensive than
the viscous Navier-Stokes equations used by others. In addition, we
introduce a physically consistent vorticity confinement term to model
the small scale rolling features characteristic of smoke that are
absent on most coarse grid simulations. Our model also correctly
handles the interaction of smoke with moving objects.

**Dynamic Real-Time Deformations using Space and Time Adaptive Sampling**
(Siggraph 2001)
(project page)
(portal page)

Gilles Debunne,
Marie-Paule Cani
(IMAGIS-GRAVIR),
Mathieu Desbrun
(University of Southern California),
Alan H. Barr
(California Institute of Technology)

This paper presents the first robust method for animating dynamic
visco-elastic deformable objects that provides a guaranteed frame
rate. The approach uses an automatic space and time adaptive level of
detail technique, in combination with a large-displacement (Green)
strain tensor formulation. The body is hierarchically partitioned into
a number of tetrahedral regions and mass samples. The local resolution
is determined by a quality condition that indicates where and when the
resolution is too coarse. As the object moves and deforms, the
sampling is refined to concentrate the computational load into the
regions that deform the most. Our model consist of a continuous
equation solved using a local explicit finite element method. We
demonstrate that our adaptive Green strain tensor formulation
virtually suppresses unwanted artifacts in the dynamic behavior,
compared to adaptive mass-spring and other adaptive approaches. In
particular, damped elastic vibration modes are shown to be nearly
unchanged for several levels of refinement. Results are presented in
the context of a virtual reality system. The user interacts in
real-time with the dynamic object (such as a liver) through the
control of a rigid tool, attached to a haptic device driven with
forces derived from the method.

**Optimization-Based Animation**
(Siggraph 2001)
(project page)
(portal page)

Victor J. Milenkovic
Harald Schmidl
(University of Miami)

Current techniques for rigid body simulation run slowly on scenes with
many bodies in close proximity. Each time two bodies collide or make
or break a static contact, the simulator must interrupt the numerical
integration of velocities and accelerations. Even for simple scenes,
the number of discontinuities per frame time can rise to the
millions. An efficient optimization-based animation (OBA) algorithm is
presented which can simulate scenes with many convex three-dimensional
bodies settling into stacks and other .crowded. arrangements. This
algorithm simulates Newtonian (second order) physics and Coulomb
friction, and it uses quadratic programming (QP) to calculate new
positions, momenta and accelerations strictly at frame times. Contact
points are synchronized at the end of each frame. The extremely small
integration steps inherent to traditional simulation techniques are
avoided. Non-convex bodies are simulated as unions of convex
bodies. Links and joints are simulated successfully with
bi-directional constraints. A hybrid of OBA and retroactive detection
(RD) has been implemented as well. A review of existing work finds no
other packages that can simulate similarly complex scenes in a
practical amount of time.

**Composable Controllers for Physics-Based Character Animation**
(Siggraph 2001)
(portal page)

Petros Faloutsos,
Michiel van de Panne,
Demetri Terzopoulos
(New York University and
University of Toronto)

An ambitious goal in the area of physics-based computer animation is
the creation of virtual actors that autonomously synthesize realistic
human motions and possess a broad repertoire of lifelike motor
skills. To this end, the control of dynamic, anthropomorphic figures
subject to gravity and contact forces remains a difficult open
problem. We propose a framework for composing controllers in order to
enhance the motor abilities of such figures. A key contribution of our
composition framework is an explicit model of the
pre-conditions under which motor controllers are expected
to function properly. We demonstrate controller composition with
pre-conditions determined not only manually, but also automatically
based on Support Vector Machine (SVM) learning theory. We evaluate our
composition framework using a family of controllers capable of
synthesizing basic actions such as balance, protective stepping when
balance is disturbed, protective arm reactions when falling, and
multiple ways of standing up after a fall. We furthermore demonstrate
these basic controllers working in conjunction with more dynamic motor
skills within a prototype virtual stunt-person. Our composition
framework promises to enable the community of physics-based animation
practitioners to easily exchange motor controllers and integrate them
into dynamic characters.

**A Simple, Efficient Method for Realistic Animation of Clouds**
(Siggraph 2000)
(project page)
(portal page)

Yoshinori Dobashi,
Kazufumi Kaneda,
Hideo Yamashita,
Tsuyoshi Okita
(Hiroshima City University),
Tomoyuki Nishita
(University of Tokyo)

This paper proposes a simple and computationally inexpensive method
for animation of clouds. The cloud evolution is simulated using
cellular automaton that simplifies the dynamics of cloud
formation. The dynamics are expressed by several simple transition
rules and their complex motion can be simulated with a small amount of
computation. Realistic images are then created using one of the
standard graphics APIs, OpenGL. This makes it possible to utilize
graphics hardware, resulting in fast image generation. The proposed
method can realize the realistic motion of clouds, shadows cast on the
ground, and shafts of light through clouds.

**Animating Explosions**
(Siggraph 2000)
(project page)
(portal page)

Gary D. Yngve,
James F. O'Brien,
Jessica K. Hodgins
(Georgia Institute of Technology)

In this paper, we introduce techniques for animating explosions and
their effects. The primary effect of an explosion is a disturbance
that causes a shock wave to propagate through the surrounding
medium. The disturbance determines the behavior of nearly all other
secondary effects seen in explosion. We simulate the propagation of an
explosion through the surrounding air using a computational fluid
dynamics model based on the equations for compressible, viscous
flow. To model the numerically stable formation of shocks along blast
wave fronts, we employ an integration method that can handle steep
pressure gradients without introducing inappropriate damping. The
system includes two-way coupling between solid objects and surrounding
fluid. Using this technique, we can generate a variety of effects
including shaped explosive charges, a projectile propelled from a
chamber by an explosion, and objects damaged by a blast. With
appropriate rendering techniques, our explosion model can be used to
create such visual effects as fireballs, dust clouds, and the
refraction of light caused by a blast wave.

**Timewarp Rigid Body Simulation**
(Siggraph 2000)
(project page)
(portal page)

Brian Mirtich
(Mitsubishi Electric Research Laboratory)

The traditional high-level algorithms for rigid body simulation work
well for moderate numbers of bodies but scale poorly to systems of
hundreds or more moving, interacting bodies. The problem is
unnecessary synchronization implicit in these methods. Jefferson's
timewarp algorithm [22] is a technique for alleviating this problem in
parallel discrete event simulation. Rigid body dynamics, though a
continuous process, exhibits many aspects of a discrete one. With
modification, the timewarp algorithm can be used in a uniprocessor
rigid body simulator to give substantial performance improvements for
simulations with large numbers of bodies. This paper describes the
limitations of the traditional high-level simulation algorithms,
introduces Jefferson's algorithm, and extends and optimizes it for the
rigid body case. It addresses issues particular to rigid body
simulation, such as collision detection and contact group management,
and describes how to incorporate these into the timewarp
framework. Quantitative experimental results indicate that the
timewarp algorithm offers significant performance improvements over
traditional high-level rigid body simulation algorithms, when applied
to systems with hundreds of bodies. It also helps pave the way to
parallel implementations, as the paper discusses.

**Interactive Control for Physically Based Animation**
(Siggraph 2000)
(project page)
(portal page)

Joseph Lazlo,
Michiel van de Panne,
Eugene Fiume
(University of Toronto)

We propose the use of interactive, user-in-the-loop techniques for
controlling physically-based animated characters. With a suitably
designed interface, the continuous and discrete input actions
afforded by a standard mouse and keyboard allow for the creation of a
broad range of motions. We apply our techniques to interactively
control planar dynamic simulations of a bounding cat, a gymnastic
desk lamp, and a human character capable of walking, running,
climbing, and various gymnastic behaviors. The interactive control
techniques allows a performer's intuition and knowledge about motion
planning to be readily exploited. Video games are the current target
application of this work.

**Interactive Manipulation of Rigid Body Simulations**
(Siggraph 2000)
(project page)
(portal page)

Jovan Popovic,
Steve Seitz,
Michael Erdmann
(Carnegie Mellon University),
Zoran Popovic
(University of Washington),
Andrew Witkin
(Pixar Animation Studios)

Physical simulation of dynamic objects has become commonplace in
computer graphics because it produces highly realistic animations. In
this paradigm the animator provides few physical parameters such as
the objects' initial positions and velocities, and the simulator
automatically generates realistic motions. The resulting motion,
however, is difficult to control because even a small adjustment of
the input parameters can drastically affect the subsequent
motion. Furthermore, the animator often wishes to change the
end-result of the motion instead of the initial physical
parameters. We describe a novel interactive technique for intuitive
manipulation of rigid multi-body simulations. Using our system, the
animator can select bodies at any time and simply drag them to
desired locations. In response, the system computes the required
physical parameters and simulates the resulting motion. Surface
characteristics such as normals and elasticity coefficients can also
be automatically adjusted to provide a greater range of feasible
motions, if the animator so desires. Because the entire simulation
editing process runs at interactive speeds, the animator can rapidly
design complex physical animations that would be difficult to achieve
with existing rigid body simulators.

**Physically Based Motion Transformation**
(Siggraph 99)
(project page)
(portal page)

Zoran Popovic
(Carnegie Mellon University),
Andrew Witkin
(Pixar Animation Studios)

We introduce a novel algorithm for transforming character animation
sequences that preserves essential physical properties of the
motion. By using the spacetime constraints dynamics formulation our
algorithm maintains realism of the original motion sequence without
sacrificing full user control of the editing process.

**Stable Fluids**
(Siggraph 99)
(portal page)
(slides)
(applet)

Jos Stam

Building animation tools for fluid-like motions is an important and
challenging problem with many applications in computer graphics. The
use of physics-based models for fluid flow can greatly assist in
creating such tools. Physical models, unlike key frame or procedural
based techniques, permit an animator to almost effortlessly create
interesting, swirling fluid-like behaviors. Also, the interaction of
flows with objects and virtual forces is handled elegantly. Until
recently, it was believed that physical fluid models were too
expensive to allow real-time interaction. This was largely due to the
fact that previous models used unstable schemes to solve the physical
equations governing a fluid. In this paper, for the first time, we
propose an unconditionally stable model which still produces complex
fluid-like flows. As well, our method is very easy to implement. The
stability of our model allows us to take larger time steps and
therefore achieve faster simulations. We have used our model in
conjuction with advecting solid textures to create many fluid-like
animations interactively in two- and three-dimensions.

**Graphical Modeling and Animation of Brittle Fracture**
(Siggraph 99)
(project page)
(portal page)

James F. O'Brien,
Jessica K. Hodgins

In this paper, we augment existing techniques for simulating flexible
objects to include models for crack initiation and propagation in
three-dimensional volumes. By analyzing the stress tensors computed
over a finite element model, the simulation determines where cracks
should initiate and in what directions they should propagate. We
demonstrate our results with animations of breaking bowls, cracking
walls, and objects that fracture when they collide. By varying the
shape of the objects, the material properties, and the initial
conditions of the simulations, we can create strikingly different
effects ranging from a wall that shatters when it is hit by a
wrecking ball to a bowl that breaks in two when it is dropped on
edge.

**
Large Steps in Cloth Simulation**(Siggraph 98)
(portal page)

David Baraff,
Andrew Witkin

The bottle-neck in most cloth simulation systems is that time steps
must be small to avoid numerical instability. This paper describes a
cloth simulation system that can stably take large time steps. The
simulation system couples a new technique for enforcing constraints on
individual cloth particles with an implicit integration method. The
simulator models cloth as a triangular mesh, with internal cloth
forces derived using a simple continuum formulation that supports
modeling operations such as local anisotropic stretch or compression;
a unified treatment of damping forces is included as well. The
implicit integration method generates a large, unbanded sparse linear
system at each time step which is solved using a modified conjugate
gradient method that simultaneously enforces particles' constraints.
The constraints are always maintained exactly, independent of the
number of conjugate gradient iterations, which is typically small.
The resulting simulation system is significantly faster than previous
accounts of cloth simulation systems in the literature.

**
Retargeting Motion to New Characters**
(Siggraph 98)
(portal page)

Michael Gleicher

In this paper, we present a technique for retargetting motion: the
problem of adapting an animated motion from one character to
another. Our focus is on adapting the motion of one articulated figure
to another figure with identical structure but different segment
lengths, although we use this as a step when considering less similar
characters. Our method creates adaptations that preserve desirable
qualities of the original motion. We identify specific features of the
motion as constraints that must be maintained. A spacetime constraints
solver computes an adapted motion that re-establishes these
constraints while preserving the frequency characteristics of the
original signal. We demonstrate our approach on motion capture data.

**
Modeling the Motion of Hot, Turbulent Gas**
(Siggraph 97)
(project page)
(portal page)

Nick Foster,
Dimitri Metaxas

This paper describes a new animation technique for modeling the
turbulent rotational motion that occurs when a hot gas interacts with
solid objects and the surrounding medium. The method is especially
useful for scenes involving swirling steam, rolling or billowing
smoke, and gusting wind. It can also model gas motion due to fans and
heat convection. The method combines specialized forms of the
equations of motion of a hot gas with an efficient method for solving
volumetric differential equations at low resolutions. Particular
emphasis is given to issues of computational efficiency and
ease-of-use of the method by an animator. We present the details of
our model, together with examples illustrating its use.

**
Linear-time dynamics using Lagrange multipliers**
(Siggraph 96)
(portal page)

David Baraff

Current linear-time simulation methods for articulated figures are
based exclusively on reduced-coordinate formulations. This paper
describes a general, non-iterative linear-time simulation method based
instead on Lagrange multipliers. Lagrange multiplier methods are
important for computer graphics applications because they bypass the
difficult (and often intractable) problem of parameterizing a system's
degrees of freedom. Given a loop-free set of n equality constraints
acting between pairs of bodies, the method takes O(n) time to compute
the system's dynamics. The method does not rely on matrix bandwidth,
so no assumptions about the constraints' topology are needed. Bodies
need not be rigid, constraints can be of various dimensions, and
unlike reduced-coordinate approaches, nonholonomic
(e.g. velocity-dependent) constraints are allowed. An additional set
of k one-dimensional constraints which induce loops and/or handle
inequalities can be accommodated with cost O(kn). This makes it
practical to simulate complicated, closed-loop articulated figures
with joint-limits and contact at interactive rates. A complete
description of a sample implementation is provided in pseudocode.

**
Limit Cycle Control and its Application to the Animation of Balancing and Walking**
(Siggraph 96)
(project page)
(portal page)

Joseph Laszlo,
Michiel van de Panne,
Eugene Fiume

Seemingly simple behaviors such as human walking are difficult to
model because of their inherent instability. Kinematic animation
techniques can freely ignore such intrinsically dynamic problems, but
they therefore also miss modeling important motion characteristics.
On the other hand, the effect of balancing can emerge in a
physically-based animation, but it requires computing delicate control
strategies. We propose an alternative method that adds closedloop
feedback to open-loop periodic motions. We then apply our technique to
create robust walking gaits for a fully-dynamic 19 degree -of-freedom
human model. Important global characteristics such as direction, speed
and stride rate can be controlled by changing the open-loop behavior
alone or through simple control parameters, while continuing to employ
the same local stabilization technique. Among other features, our
dynamic "human" walking character is thus able to follow desired paths
specified by the animator.

**
OBBTree: a hierarchical structure for rapid interference detection**
(Siggraph 96)
(project page)

Stefan Gottschalk,
Ming C. Lin,
Dinesh Manocha

We present a data structure and an algorithm for efficient and exact
interference detection amongst complex models undergoing rigid
motion. The algorithm is applicable to all general polygonal and
curved models. It pre-computes a hierarchical representation of models
using tight-fitting oriented bounding box trees. At runtime, the
algorithm traverses the tree and tests for overlaps between oriented
bounding boxes based on a new separating axis theorem, which takes
less than 200 operations in practice. It has been implemented and we
compare its performance with other hierarchical data structures. In
particular, it can accurately detect all the contacts between large
complex geometries composed of hundreds of thousands of polygons at
interactive rates, almost one order of magnitude faster than earlier
methods.

**
Automated Learning of Muscle-Actuated Locomotion Through Control Abstraction**
(Siggraph 95)
(portal page)

Radek Grzeszczuk,
Demetri Terzopoulos

We present a learning technique that automatically synthesizes
realistic locomotion for the animation of physics-based models of
animals. The method is especially suitable for animals with highly
flexible, many-degree-of-freedom bodies and a considerable number of
internal muscle actuators, such as snakes and fish. The multilevel
learning process first performs repeated locomotion trials in search
of actuator control functions that produce efficient locomotion,
presuming virtually nothing about the form of these
functions. Applying a short-time Fourier analysis, the learning
process then abstracts control functions that produce effective
locomotion into a compact representation which makes explicit the
natural quasi-periodicities and coordination of the muscle actions.
The artificial animals can finally put into practice the compact,
efficient controllersthat they havelearned. Their locomotion learning
abilities enable them to accomplish higher-level tasks specified by
the animator while guided by sensory perception of their virtual
world; e.g., locomotion to a visible target. We demonstrate
physics-basedanimation of learned locomotion in dynamic models of land
snakes, fishes, and even marine mammals that have trained themselves
to perform "SeaWorld" stunts.

**
Depiction of Fire and Other Gaseous Phenomena Using Diffusion Processes**
(Siggraph 95)
(project page)
(portal page)

Jos Stam,
Eugene Fiume

Developing a visually convincing model of fire, smoke, and other
gaseous phenomena is among the most difficult and attractive problems
in computer graphics. We have created new methods of animating a wide
range of gaseous phenomena, including the particularly subtle problem
of modelling "wispy" smoke and steam, using far fewer primitives than
before. One significant innovation is the reformulation and solution
of the advection-diffusion equation for densities composed of "warped
blobs". These blobs more accurately model the distortions that gases
undergo when advected by wind fields. We also introduce a simple model
for the flame of a fire and its spread. Lastly, we present an
efficient formulation and implementation of global illumination in the
presence of gases and fire. Our models are specifically designed to
permit a significant degree of user control over the evolution of
gaseous phenomena.

**
Versatile and Efficient Techniques for Simulating Cloth and other Deformable Objects**
(Siggraph 95)
(portal page)

Pascal Volino,
Martin Courchesne,
Nadia Magnenat-Thalmann

We are presenting techniques for simulating the motion and the
deformation of cloth, fabrics or, more generally, deformable
surfaces. Our main goal is to be able to simulate any kind of surface
without imposing restrictions on shape or geometrical environment. In
particular, we are considering difficult situations with respect to
deformations and collisions, like wrinkled fabric falling on the
ground. Thus, we have enhanced existing algorithms in order to cope
with any possible situation. A mechanical model has been implemented
to deal with any irregular triangular meshes, handle high deformations
despite rough discretisation, and cope with complex interacting
collisions. Thus, it should deal efficiently with situations where
nonlinearities and discontinuities are really non marginal. Collision
detection has also been improved to efficiently detect
self-collisions, and also to correctly consider collision orientations
despite the lack of surface orientation information from preset
geometrical contexts, using consistency checking and correction. We
illustrate these features through simulation examples.

**
Interactive Physically-Based Manipulation of Discrete/Continuous Models**
(Siggraph 95)
(portal page)

Mikako Harada,
Andrew Witkin,
David Baraff

Physically-based modeling has been used in the past to support a
variety of interactive modeling tasks including free-form surface
design, mechanism design, constrained drawing, and interactive camera
control. In these systems, the user interacts with the model by
exerting virtual forces, to which the system responds subject to the
active constraints. In the past, this kind of interaction has been
applicable only to models that are governed by continuous
parameters. In this paper we present an extension to mixed continuous
/discrete models, emphasizing constrained layout problems that arise
in architecture and other domains. When the object being dragged is
blocked from further motion by geometric constraints, a local discrete
search is triggered, during which transformations such as swapping of
adjacent objects may be performed. The result of the search is a
"nearby" state in which the target object has been moved in the
indicated direction and in which all constraints are satisfied. The
transition to this state is portrayed using simple but effective
animated visual effects. Following the transition, continuous dragging
is resumed. The resulting seamless transitions between discrete and
continuous manipulation allow the user to easily explore the mixed
design space just by dragging objects. We demonstrate the method in
application to architectural floor plan design, circuit board layout,
art analysis, and page layout.

**
Animating soft substances with implicit surfaces**
(Siggraph 95)
(project page)
(portal page)

Mathieu Desbrun,
Marie-Paule Gascuel

This paper presents a hybrid model for animation of soft inelastic
substance which undergo topological changes, e.g. separation and
fusion and which fit with the objects they are in contact with. The
model uses a particle system coated with a smooth iso-surface that is
used for performing collision detection, precise contact modeling and
integration of response forces. The animation technique solves three
problems inherent in implicit modeling. Firstly, local volume
controllers are defined to insure constant volume deformation, even
during highly inelastic processes such as splitting or fusion.
Secondly, we avoid unwanted distance blending between disconnected
pieces of the same substance. Finally, we simulate both collisions and
progressive merging under compression between implicit surfaces that
do not blend together. Parameter tuning is facilitated by the layered
model and animation is generated at interactive rates.

**
Hybrid Simulation: Combining Constraints and Impulses**
(SIVE 95)
(project page)

Brian Mirtich,

Impulse-based simulation has been shown to be a useful paradigm for
rigid body simulation [12, 11], especially for systems which are
collision intensive, or undergo many changes in contact
configuration. In this paper we briefly describe the simulator
Impulse, and report some recent results in the domain of part feeding.
Since the impulse- and constraint-based approaches work best for
orthogonal situations, it is advantageous to use both methods
simultaneously. After describing the range of impulse- to
constraint-based contact interaction, we examine how the impulsive
collision resolution may be extended to constrained systems. We also
discuss some important open problems related to developing an
efficient simulator that uses both contact interaction paradigms.

**
Impulse-Based Simulation of Rigid Bodies**
(SI3D 95)
(portal page)
(project page)

Brian Mirtich,
John Canny,

We introduce a promising new approach to rigid body dynamic simulation
called impulse-based simulation. The method is well suited to modeling
physical systems with large numbers of collisions, or with contact
modes that change frequently. All types of contact (colliding,
rolling, sliding, and resting) are modeled through a series of
collision impulses between the objects in contact, hence the method is
simpler and faster than constraint-based simulation. We have
implemented an impulse-based simulator that can currently 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 detection and collision response in this context, and
present results from several experiments.

**
I-COLLIDE: an interactive and exact collision detection system for large-scale environments**
(SI3D 95)
(project page)
(portal page)

Jonathan D. Cohen,
Ming C. Lin,
Dinesh Manocha,
Madhav Ponamgi

We present an exact and interactive collision detection system,
I-COLLIDE, for large-scale environments. Such environments are
characterized by the number of objects undergoing rigid motion and the
complexity of the models. The algorithm does not assume the objects'
motions can be expressed as a closed form function of time. The
collision detection system is general and can be easily interfaced
with a variety of applications. The algorithm uses a two-level
approach based on pruning multiple-object pairs using bounding boxes
and performing exact collision detection between selected pairs of
polyhedral models. We demonstrate the performance of the system in
walkthrough and simulation environments consisting of a large number
of moving objects. In particular, the system takes less than 1/20 of a
second to determine all the collisions and contacts in an environment
consisting of more than 1000 moving polytopes, each consisting of more
than 50 faces on an HP-9000/750.

**
Fast contact force computation for nonpenetrating rigid bodies**
(Siggraph 94)
(portal page)

David Baraff

A new algorithm for computing contact forces between solid
objects with friction is presented. The algorithm allows a mix
of contact points with static and dynamic friction. In contrast to
previous approaches, the problem of computing contact forces is not
transformed into an optimization problem. Because of this, the need
for sophisticated optimization software packages is eliminated. For
both systems with and without friction, the algorithm has proven
to be considerably faster, simpler, and more reliable than previous
approaches to the problem. In particular, implementation of the
algorithm by nonspecialists in numerical programming is quite
feasible.

**
Artificial fishes: Physics, locomotion, perception, behavior**
(Siggraph 94)
(portal page)

Xiaoyuan Tu,
Demetri Terzopoulos

This paper proposes a framework for animation that can achieve the
intricacy of motion evident in certain natural ecosystems with minimal
input from the animator. The realistic appearance, movement, and
behavior of individual animals, as well as the patterns of behavior
evident in groups of animals fall within the scope of the
framework. Our approach to emulating this level of natural complexity
is to model each animal holistically as an autonomous agent situated
in its physical world. To demonstrate the approach, we develop a
physics-based, virtual marine world. The world is inhabited by
artificial fishes that can swim hydrodynamically in simulated water
through the motor control of internal muscles that motivate
fins. Their repertoire of behaviors relies on their perception of the
dynamic environment. As in nature, the detailed motions of artificial
fishes in their virtual habitat are not entirely predictable because
they are not scripted.

**
Predicting the Drape of Woven Cloth Using Interacting Particles**
(Siggraph 94)
(portal page)

David E. Breen,
Donald H. House,
Michael J. Wozny

We demonstrate a physically-based technique for predicting the drape
of a wide variety of woven fabrics. The approach exploits a
theoretical model that explicitly represents the microstructure of
woven cloth with interacting particles, rather than utilizing a
continuum approximation. By testing a cloth sample in a Kawabata
fabric testing device, we obtain data that is used to tune the model's
energy functions, so that it reproduces the draping behavior of the
original material. Photographs, comparing the drape of actual cloth
with visualizations of simulation results, show that we are able to
reliably model the unique large-scale draping characteristics of
distinctly different fabric types.

**
Turbulent Wind Fields for Gaseous Phenomena**
(Siggraph 93)
(project page)
(portal page)

Jos Stam,
Eugene Fiume

The realistic depiction of smoke, steam, mist and water reacting to a
turbulent field such as wind is an attractive and challenging
problem. Its solution requires interlocking models for turbulent
fields, gaseous flow, and realistic illumination. We present a model
for turbulent wind flow having a deterministic component to specify
large-scale behaviour, and a stochastic component to model turbulent
small-scale behaviour. The small-scale component is generated using
space-time Fourier synthesis. Turbulent wind fields can be superposed
interactively to create subtle behaviour. An advection-diffusion model
is used to animate particle-based gaseous phenomena embedded in a wind
field, and we derive an efficient physically-based illumination model
for rendering the system. Because the number of particles can be quite
large, we present a clustering algorithm for efficient animation and
rendering.

**
Dynamic Simulation of Non-penetrating Flexible Bodies**
(Siggraph 92)
(portal page)

David Baraff,
Andrew Witkin

A model for the dynamic simulation of flexible bodies subject to
non-penetration constraints is presented. Flexible bodies are
described in terms of global deformations of a rest shape. The
dynamical behavior of these bodies that most closely matches the
behavior of ideal continuum bodies is derived, and subsumes the
results of earlier Lagrangian dynamics-based models. The dynamics
derived for the flexible-body model allows the unification of
previous work on flexible body simulation and previous work on
non-penetrating rigid body simulation. The non-penetration
constraints for a system of bodies that contact at multiple points
are maintained by analytically calculated contact forces. An
implementation for first- and second-order polynomially deformable
bodies is described. The simulation of second-order or higher
deformations currently involves a polyhedral boundary approximation
for collision detection purposes.