Physics in Graphics

There will come a time when you believe everything is finished.
That will be the beginning.

paper summary - paper details - visual index - other ressources - about

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.