Abstract In this paper, we consider retargeting a tracked facial performance to other people or virtual characters. We utilize the same rig framework for both tracking and animation to remove the difficulties associated with retargeting the semantics of one framework to another. Our carefully designed set of Simon‐Says expressions and regularizers is used to calibrate each rig to the motion signatures of the relevant performer or target. Although a uniform set of Simon‐Says expressions can likely be used for all person‐to‐person retargeting, we argue that person‐to‐virtual‐character retargeting benefits from an expression set that captures the distinct motion signature of the virtual character rig. The Simon‐Says calibrated rigs tend to produce the desired expressions when exercising animation controls. Unfortunately, these well‐calibrated rigs still lead to undesirable controls when tracking a performance, even though they generally produce acceptable geometry reconstructions. Thus, we propose a fine‐tuning approach that modifies the rig used by the tracker to promote the output of more semantically meaningful animation controls, facilitating high efficacy retargeting. To better address real‐world scenarios, the fine‐tuning relies on implicit differentiation so that the tracker can be treated as a potentially non‐differentiable black box. Experiments demonstrate the benefits of our calibration methods on high‐fidelity expressive performance retargeting for different capture conditions, trackers, and rig frameworks.

Abstract We present a novel learning framework for cloth deformation by embedding virtual cloth into a tetrahedral mesh that parametrizes the volumetric region of air surrounding the underlying body. In order to maintain this volumetric parameterization during character animation, the tetrahedral mesh is constrained to follow the body surface as it deforms. We embed the cloth mesh vertices into this parameterization of three‐dimensional space in order to automatically capture much of the nonlinear deformation due to both joint rotations and collisions. We then train a convolutional neural network to recover ground truth deformation by learning cloth embedding offsets for each skeletal pose. Our experiments show significant improvement over learning cloth offsets from body surface parameterizations, both quantitatively and visually, with prior state of the art having a mean error five standard deviations higher than ours. Without retraining, our neural network generalizes to other body shapes and T‐shirt sizes, giving the user some indication of how well clothing might fit. Our results demonstrate the efficacy of a general learning paradigm where high‐frequency details can be embedded into low‐frequency parameterizations.

We present a novel deep learning-based approach to the 3D reconstruction of clothed humans using weak supervision via 2D normal maps. Given a single RGB image or multiview images, our network is optimized to infer a person-specific signed distance function (SDF) discretized on a tetrahedral mesh surrounding the body in a rest pose. Subsequently, estimated human pose and camera parameters are used to generate a normal map from the SDF. A key aspect of our approach is the direct use of the Marching Tetrahedra algorithm in end-to-end optimization, and in order to do so we derive analytical gradients to facilitate straightforward differentiation (and thus backpropagation). Additionally, predicted normal maps allow us to leverage pretrained image-to-normal networks in order to minimize a surface error instead of a photometric error. We demonstrate the efficacy of our approach on both labeled and in-the-wild data in the context of existing clothed human reconstruction methods.

The Extended Position Based Dynamics (XPBD) approach of Macklin et al. (2016) addresses issues with iteration-dependent behavior in the original Position Based Dynamics (Müller et al., 2007) (PBD). PBD itself is a powerful method for the real-time simulation of elastic objects, however, it is limited in its application to hyperelastic solids. It can only treat models with a strain energy density that is quadratic in some notion of constraint. Furthermore, we show that even when applicable the formulation does not always lead to convergent behaviors with hyperelasticity. We isolate the root cause to be the approximate linearization of the nonlinear backward Euler systems utilized by XPBD. We provide two fixes to these terms that allow for convergent behavior. The first (B-PXPBD) is a small modification to an existing XPBD code, but can only be used with models addressable by the original XPBD. The second (FP-PXPBD) is a more general formulation that extends XPBD (and our residual correction) to arbitrary hyperelasticity. We show that our modifications allow for convergent behavior that rivals accurate techniques like Newton’s method when the computational budget is large without sacrificing the stable and robust behavior exhibited by the original PBD and XPBD when the computational budget is limited.

Abstract The creation of a volumetric mesh representing the interior of an input polygonal mesh is a common requirement in graphics and computational mechanics applications. Most mesh creation techniques assume that the input surface is not self‐intersecting. However, due to numerical and/or user error, input surfaces are commonly self‐intersecting to some degree. The removal of self‐intersection is a burdensome task that complicates workflow and generally slows down the process of creating simulation‐ready digital assets. We present a method for the creation of a volumetric embedding hexahedron mesh from a self‐intersecting input triangle mesh. Our method is designed for efficiency by minimizing use of computationally expensive exact/adaptive precision arithmetic. Although our approach allows for nearly no limit on the degree of self‐intersection in the input surface, our focus is on efficiency in the most common case: many minimal self‐intersections. The embedding hexahedron mesh is created from a uniform background grid and consists of hexahedron elements that are geometrical copies of grid cells. Multiple copies of a single grid cell are used to resolve regions of self‐intersection/overlap. Lastly, we develop a novel topology‐aware embedding mesh coarsening technique to allow for user‐specified mesh resolution as well as a topology‐aware tetrahedralization of the hexahedron mesh.

When considering sparse motion capture marker data, one typically struggles to balance its overfitting via a high dimensional blendshape system versus underfitting caused by smoothness constraints. With the current trend towards using more and more data, our aim is not to fit the motion capture markers with a parameterized (blendshape) model or to smoothly interpolate a surface through the marker positions, but rather to find an instance in the high resolution dataset that contains local geometry to fit each marker. Just as is true for typical machine learning applications, this approach benefits from a plethora of data, and thus we also consider augmenting the dataset via specially designed physical simulations that target the high resolution dataset such that the simulation output lies on the same so-called manifold as the data targeted.

The Extended Position Based Dynamics (XPBD) approach of Macklin et al. [2016] addresses the issues with iteration-dependent behavior in the original Position Based Dynamics [2007] (PBD) which itself is a powerful method for the real-time simulation of elastic objects. However, it is limited in its application to hyperelastic solids. It can only treat models with a strain energy density that is quadratic in some notion of constraint. Furthermore, we show that even when applicable the formulation does not always lead to convergent behaviors with hyperelasticity. We isolate the root cause in the approximate linearization of the nonlinear backward Euler systems utilized by XPBD. We provide two fixes to these terms that allow for convergent behavior. The first (B-PXPBD) is a small modification to an existing XPBD code, but can only be used with models addressable by the original XPBD. The second (FP-PXPBD) is a more general formulation that extends XPBD (and our residual correction) to arbitrary hyperelasticity. We show that our modifications allow for convergent behavior that rivals accurate techniques like Newton’s method when the computational budget is large without sacrificing the stable and robust behavior exhibited by the original PBD and XPBD when the computational budget is limited.

Abstract We propose a novel approach to learning cloth deformation as a function of body pose, recasting the graph‐like triangle mesh data structure into image‐based data in order to leverage popular and well‐developed convolutional neural networks (CNNs) in a two‐dimensional Euclidean domain. Then, a three‐dimensional animation of clothing is equivalent to a sequence of two‐dimensional RGB images driven/choreographed by time dependent joint angles. In order to reduce nonlinearity demands on the neural network, we utilize procedural skinning of the body surface to capture much of the rotation/deformation so that the RGB images only contain textures of displacement offsets from skin to clothing. Notably, we illustrate that our approach does not require accurate unclothed body shapes or robust skinning techniques. Additionally, we discuss how standard image based techniques such as image partitioning for higher resolution can readily be incorporated into our framework.

Muscle-based systems have the potential to provide both anatomical accuracy and semantic interpretability as compared to blendshape models; however, a lack of expressivity and differentiability has limited their impact. Thus, we propose modifying a recently developed rather expressive muscle-based system in order to make it fully-differentiable; in fact, our proposed modifications allow this physically robust and anatomically accurate muscle model to conveniently be driven by an underlying blendshape basis. Our formulation is intuitive, natural, as well as monolithically and fully coupled such that one can differentiate the model from end to end, which makes it viable for both optimization and learning-based approaches for a variety of applications. We illustrate this with a number of examples including both shape matching of three-dimensional geometry as as well as the automatic determination of a three-dimensional facial pose from a single two-dimensional RGB image without using markers or depth information.

We propose a novel framework for hair animation as well as hair-water interaction that supports millions of hairs. First, we develop a hair animation framework that embeds hair into a tetrahedralized volume mesh that we kinematically skin to deform and follow the exterior of an animated character. Allowing the hairs to follow their precomputed embedded locations in the kinematically deforming skinned mesh already provides visually plausible behavior. Creating a copy of the tetrahedral mesh, endowing it with springs, and attaching it to the kinematically skinned mesh creates more dynamic behavior. Notably, the springs can be quite weak and thus efficient to simulate because they are structurally supported by the kinematic mesh. If independent simulation of individual hairs or guide hairs is desired, they too benefit from being anchored to the kinematic mesh dramatically increasing efficiency as weak springs can be used while still supporting interesting and dramatic hairstyles. Furthermore, we explain how to embed these dynamic simulations into the kinematically deforming skinned mesh so that they can be used as part of a blendshape system where an artist can make many subsequent iterations without requiring any additional simulation. Although there are many applications for our newly proposed approach to hair animation, we mostly focus on the particularly challenging problem of hair-water interaction. While doing this, we discuss how porosities are stored in the kinematic mesh, how the kinematically deforming mesh can be used to apply drag and adhesion forces to the water, etc.

We present a novel method for posing and animating botanical tree models interactively in real time. Unlike other state of the art methods which tend to produce trees that are overly flexible, bending and deforming as if they were underwater plants, our approach allows for arbitrarily high stiffness while still maintaining real-time frame rates without spurious artifacts, even on quite large trees with over ten thousand branches. This is accomplished by using an articulated rigid body model with as-stiff-as-desired rotational springs in conjunction with our newly proposed simulation technique, which is motivated both by position based dynamics and the typical algorithms for articulated rigid bodies. The efficiency of our algorithm allows us to pose and animate trees with millions of branches or alternatively simulate a small forest comprised of many highly detailed trees. Even using only a single CPU core, we can simulate ten thousand branches in real time while still maintaining quite crisp user interactivity. This has allowed us to incorporate our framework into a commodity game engine to run interactively even on a low-budget tablet. We show that our method is amenable to the incorporation of a large variety of desirable effects such as wind, leaves, fictitious forces, collisions, fracture, etc.

We present a novel method to simulate codimensional non-Newtonian fluids on simplicial complexes. Our method extends previous work for codimensional incompressible flow to various types of non-Newtonian fluids including both shear thinning and thickening, Bingham plastics, and elastoplastics. We propose a novel time integration scheme for semi-implicitly treating elasticity, which when combined with a semi-implicit method for variable viscosity alleviates the need for small time steps. Furthermore, we propose an improved treatment of viscosity on the rims of thin fluid sheets that allows us to capture their elusive, visually appealing twisting motion. In order to simulate complex phenomena such as the mixing of colored paint, we adopt a multiple level set framework and propose a discretization on simplicial complexes that facilitates the tracking of material interfaces across codimensions. We demonstrate the efficacy of our approach by simulating a wide variety of non-Newtonian fluid phenomena exhibiting various codimensional features.

Many visually interesting natural phenomena are characterized by thin liquid sheets, long filaments, and droplets. We present a new Lagrangian-based numerical method to simulate these codimensional surface tension driven phenomena using non-manifold simplicial complexes. Tetrahedra, triangles, segments, and points are used to model the fluid volume, thin films, filaments, and droplets, respectively. We present a new method for enforcing fluid incompressibility on simplicial complexes along with a physically-guided meshing algorithm to provide temporally consistent information for interparticle forces. Our method naturally allows for transitions between codimensions, either from tetrahedra to triangles to segments to points or vice versa, regardless of the simulation resolution. We demonstrate the efficacy of this method by simulating various natural phenomena that are characterized by thin fluid sheets, filaments, and surface tension effects.

We present an efficient grid structure that extends a uniform grid to create a significantly larger far-field grid by dynamically extending the cells surrounding a fine uniform grid while still maintaining fine resolution about the regions of interest. The far-field grid preserves almost every computational advantage of uniform grids including cache coherency, regular subdivisions for parallelization, simple data layout, the existence of efficient numerical discretizations and algorithms for solving partial differential equations, etc. This allows fluid simulations to cover large domains that are often infeasible to enclose with sufficient resolution using a uniform grid, while still effectively capturing fine scale details in regions of interest using dynamic adaptivity.

We propose a new algorithm for rigid body simulation that guarantees each body is in an interpenetration free state, both increasing the accuracy and robustness of the simulation as well as alleviating the need for ad hoc methods to separate bodies for subsequent simulation and rendering. We cleanly separate collision and contact resolution such that objects move and collide in the first step, with resting contact handled in the second step. The first step of our algorithm guarantees that each time step produces geometry that does not intersect or overlap by using an approximation to the continuous collision detection (and response) problem and, thus, is amenable to thin shells and degenerately flat objects moving at high speeds. In addition, we introduce a novel fail-safe that allows us to resolve all interpenetration without iterating to convergence. Since the first step guarantees a noninterfering state for the geometry, in the second step we propose a contact model for handling thin shells in proximity considering only the instantaneous locations at the ends of the time step.

We propose a novel technique that allows one to conserve energy using the time integration scheme of one's choice. Traditionally, the time integration methods that deal with energy conservation, such as symplectic, geometric, and variational integrators, have aimed to include damping in a manner independent of the size of the time step, stating that this gives more control over the look and feel of the simulation. Generally speaking, damping adds to the overall aesthetics and appeal of a numerical simulation, especially since it damps out the high frequency oscillations that occur on the level of the discretization mesh. We propose an alternative technique that allows one to use damping as a material parameter to obtain the desired look and feel of a numerical simulation, while still exactly conserving the total energy-in stark contrast to previous methods in which adding damping effects necessarily removes energy from the mesh. This allows, for example, a deformable bouncing ball with aesthetically pleasing damping (and even undergoing collision) to collide with the ground and return to its original height exactly conserving energy, as shown in Fig. 2. Furthermore, since our method works with any time integration scheme, the user can choose their favorite time integration method with regards to aesthetics and simply apply our method as a postprocess to conserve all or as much of the energy as desired.

Abstract We propose a series of techniques for hybridizing implicit and semi‐implicit time integration methods in a manner that retains much of the speed of the implicit method without sacrificing all of the higher quality vibrations one obtains with methods that handle elastic forces explicitly. We propose our scheme in the context of asynchronous methods, where different parts of the mesh are evolved at different time steps. Whereas traditional asynchronous methods evolve each element independently, we partition all of our elements into two groups: one group evolved at the frame rate using a fully implicit scheme, and another group which takes a number of substeps per frame using a scheme that is implicit on damping forces and explicit on the elastic forces. This allows for a straightforward coupling between the implicit and semi‐implicit methods at frame boundaries for added stability. As has been stressed by various authors, asynchronous schemes take some of the pressure off of mesh generation, allowing time evolution to remain efficient even in the face of sliver elements. Finally, we propose a force distributing projection method which allows one to redistribute the forces felt on boundaries between implicit and semi‐implicit regions of the mesh in a manner that yields improved visual quality.

In this paper, we propose a method designed to allow creatures to actively respond to a fluid environment. We explore various objective functions in order to determine ways to direct the behavior of our creatures. Our proposed method works in conjunction with generalized body forces as well as both one-way and two-way coupled fluid forces. As one might imagine, interesting behaviors can be derived from minimizing and maximizing both drag and lift as well as minimizing the effort that a creature's internal actuators exert. A major application for our work is the automatic specification of secondary motions, for example, certain joints can be animated, while others are automatically solved for in order to satisfy the objective function.

Large scale fluid simulation can be difficult using existing techniques due to the high computational cost of using large grids. We present a novel technique for simulating detailed fluids quickly. Our technique coarsens the Eulerian fluid grid during the pressure solve, allowing for a fast implicit update but still maintaining the resolution obtained with a large grid. This allows our simulations to run at a fraction of the cost of existing techniques while still providing the fine scale structure and details obtained with a full projection. Our algorithm scales well to very large grids and large numbers of processors, allowing for high fidelity simulations that would otherwise be intractable.

In this paper we simulate high resolution cloth consisting of up to 2 million triangles which allows us to achieve highly detailed folds and wrinkles. Since the level of detail is also influenced by object collision and self collision, we propose a more accurate model for cloth-object friction. We also propose a robust history-based repulsion/collision framework where repulsions are treated accurately and efficiently on a per time step basis. Distributed memory parallelism is used for both time evolution and collisions and we specifically address Gauss-Seidel ordering of repulsion/collision response. This algorithm is demonstrated by several high resolution and high-fidelity simulations.

We propose a novel solid/fluid coupling method that treats the coupled system in a fully implicit manner making it stable for arbitrary time steps, large density ratios, etc. In contrast to previous work in computer graphics, we derive our method using a simple back-of-the-envelope approach which lumps the solid and fluid momenta together, and which we show exactly conserves the momentum of the coupled system. Notably, our method uses the standard Cartesian fluid discretization and does not require (moving) conforming tetrahedral meshes or ALE frameworks. Furthermore, we use a standard Lagrangian framework for the solid, thus supporting arbitrary solid constitutive models, both implicit and explicit time integration, etc. The method is quite general, working for smoke, water, and multiphase fluids as well as both rigid and deformable solids, and both volumes and thin shells. Rigid shells and cloth are handled automatically without special treatment, and we support fully one-sided discretizations without leaking. Our equations are fully symmetric, allowing for the use of fast solvers, which is a natural result of properly conserving momentum. Finally, for simple explicit time integration of rigid bodies, we show that our equations reduce to form similar to previous work via a single block Gaussian elimination operation, but that this approach scales poorly, i.e. as though four spatial dimensions rather than three.

Our goal is to simulate the full hair geometry, consisting of approximately one hundred thousand hairs on a typical human head. This will require scalable methods that can simulate every hair as opposed to only a few guide hairs. Novel to this approach is that the individual hair/hair interactions can be modeled with physical parameters (friction, static attraction, etc.) at the scale of a single hair as opposed to clumped or continuum interactions. In this vein, we first propose a new altitude spring model for preventing collapse in the simulation of volumetric tetrahedra, and we show that it is also applicable both to bending in cloth and torsion in hair. We demonstrate that this new torsion model for hair behaves in a fashion similar to more sophisticated models with significantly reduced computational cost. For added efficiency, we introduce a semi-implicit discretization of standard springs that makes them truly linear in multiple spatial dimensions and thus unconditionally stable without requiring Newton-Raphson iteration. We also simulate complex hair/hair interactions including sticking and clumping behavior, collisions with objects (e.g. head and shoulders) and self-collisions. Notably, in line with our goal to simulate the full head of hair, we do not generate any new hairs at render time.

Grid-based methods have difficulty resolving features on or below the scale of the underlying grid. Although adaptive methods (e.g. RLE, octrees) can alleviate this to some degree, separate techniques are still required for simulating small-scale phenomena such as spray and foam, especially since these more diffuse materials typically behave quite differently than their denser counterparts. In this paper, we propose a two-way coupled simulation framework that uses the particle level set method to efficiently model dense liquid volumes and a smoothed particle hydrodynamics (SPH) method to simulate diffuse regions such as sprays. Our novel SPH method allows us to simulate both dense and diffuse water volumes, fully incorporates the particles that are automatically generated by the particle level set method in under-resolved regions, and allows for two way mixing between dense SPH volumes and grid-based liquid representations.

We propose a novel approach to proportional derivative (PD) control exploiting the fact that these equations can be solved analytically for a single degree of freedom. The analytic solution indicates what the PD controller would accomplish in isolation without interference from neighboring joints, gravity and external forces, outboard limbs, etc. Our approach to time integration includes an inverse dynamics formulation that automatically incorporates global feedback so that the per joint predictions are achieved. This effectively decouples stiffness from control so that we obtain the desired target regardless of the stiffness of the joint, which merely determines when we get there. We start with simple examples to illustrate our method, and then move on to more complex examples including PD control of line segment muscle actuators.

We model flames and fire using the Navier-Stokes equations combined with the level set method and jump conditions to model the reaction front. Previous works modeled the flame using a combination of propagation in the normal direction and a curvature term which leads to a level set equation that is parabolic in nature and thus overly dissipative and smooth. Asymptotic theory shows that one can obtain more interesting velocities and fully hyperbolic (as opposed to parabolic) equations for the level set evolution. In particular, researchers in the field of detonation shock dynamics (DSD) have derived a set of equations which exhibit characteristic cellular patterns. We show how to make use of the DSD framework in the context of computer graphics simulations of flames and fire to obtain interesting features such as flame wrinkling and cellular patterns.

We propose a numerical method for modeling highly deformable nonlinear incompressible solids that conserves the volume locally near each node in a finite element mesh. Our method works with arbitrary constitutive models, is applicable to both passive and active materials (e.g. muscles), and works with simple tetrahedra without the need for multiple quadrature points or stabilization techniques. Although simple linear tetrahedra typically suffer from locking when modeling incompressible materials, our method enforces incompressibility per node (in a one-ring), and we demonstrate that it is free from locking. We correct errors in volume without introducing oscillations by treating position and velocity in separate implicit solves. Finally, we propose a novel method for treating both object contact and self-contact as linear constraints during the incompressible solve, alleviating issues in enforcing multiple possibly conflicting constraints.

We propose a novel approach to fracturing (and denting) brittle materials. To avoid the computational burden imposed by the stringent time step restrictions of explicit methods or with solving nonlinear systems of equations for implicit methods, we treat the material as a fully rigid body in the limit of infinite stiffness. In addition to a triangulated surface mesh and level set volume for collisions, each rigid body is outfitted with a tetrahedral mesh upon which finite element analysis can be carried out to provide a stress map for fracture criteria. We demonstrate that the commonly used stress criteria can lead to arbitrary fracture (especially for stiff materials) and instead propose the notion of a time averaged stress directly into the FEM analysis. When objects fracture, the virtual node algorithm provides new triangle and tetrahedral meshes in a straightforward and robust fashion. Although each new rigid body can be rasterized to obtain a new level set, small shards can be difficult to accurately resolve. Therefore, we propose a novel collision handling technique for treating both rigid bodies and rigid body thin shells represented by only a triangle mesh.

We present a new method for the efficient simulation of large bodies of water, especially effective when three-dimensional surface effects are important. Similar to a traditional two-dimensional height field approach, most of the water volume is represented by tall cells which are assumed to have linear pressure profiles. In order to avoid the limitations typically associated with a height field approach, we simulate the entire top surface of the water volume with a state of the art, fully three-dimensional Navier-Stokes free surface solver. Our philosophy is to use the best available method near the interface (in the three-dimensional region) and to coarsen the mesh away from the interface for efficiency. We coarsen with tall, thin cells (as opposed to octrees or AMR), because they maintain good resolution horizontally allowing for accurate representation of bottom topography.

The particle level set method has proven successful for the simulation oftwoseparate regions (such as water and air, or fuel and products). In this paper, we propose a novel approach to extend this method to the simulation of as many regions as desired. The various regions can be liquids (or gases) of any type with differing viscosities, densities, viscoelastic properties, etc. We also propose techniques for simulating interactions between materials, whether it be simple surface tension forces or more complex chemical reactions with one material converting to another or two materials combining to form a third. We use a separate particle level set method for each region, and propose a novel projection algorithm that decodes the resulting vector of level set values providing a "dictionary" that translates between them and the standard single-valued level set representation. An additional difficulty occurs since discretization stencils (for interpolation, tracing semi-Lagrangian rays, etc.) cross region boundaries naively combining non-smooth or even discontinuous data. This has recently been addressed via ghost values, e.g. for fire or bubbles. We instead propose a new paradigm that allows one to incorporate physical jump conditions in data "on the fly," which is significantly more efficient for multiple regions especially at triple points or near boundaries with solids.

We propose a novel technique for melting and burning solid materials, including the simulation of the resulting liquid and gas. The solid is simulated with traditional mesh-based techniques (triangles or tetrahedra) which enable robust handling of both deformable and rigid objects, collision and self-collision, rolling, friction, stacking, etc. The subsequently created liquid or gas is simulated with modern grid-based techniques, including vorticity confinement and the particle level set method. The main advantage of our method is that state-of-the-art techniques are used for both the solid and the fluid without compromising simulation quality when coupling them together or converting one into the other. For example, we avoid modeling solids as Eulerian grid-based fluids with high viscosity or viscoelasticity, which would preclude the handling of thin shells, self-collision, rolling, etc. Thus, our method allows one to achieve new effects while still using their favorite algorithms (and implementations) for simulating both solids and fluids, whereas other coupling algorithms require major algorithm and implementation overhauls and still fail to produce rich coupling effects (e.g., melting and burning solids).

We propose a novel approach for dynamically simulating articulated rigid bodies undergoing frequent and unpredictable contact and collision. In order to leverage existing algorithms for nonconvex bodies, multiple collisions, large contact groups, stacking, etc., we use maximal rather than generalized coordinates and take an impulse-based approach that allows us to treat articulation, contact, and collision in a unified manner. Traditional constraint handling methods are subject to drift, and we propose a novel prestabilization method that does not require tunable potentially stiff parameters as does Baumgarte stabilization. This differs from poststabilization in that we compute allowable trajectories before moving the rigid bodies to their new positions, instead of correcting them after the fact when it can be difficult to incorporate the effects of contact and collision. A poststabilization technique is used for momentum and angular momentum. Our approach works with any black box method for specifying valid joint constraints and no special considerations are required for arbitrary closed loops or branching. Moreover, our implementation is linear both in the number of bodies and in the number of auxiliary contact and collision constraints, unlike many other methods that are linear in the number of bodies, but not in the number of auxiliary constraints.

Biomechanically accurate finite element models of facial musculature offer a superior accuracy in reproducing facial expressions. We employ such a finite element simulation model to determine the muscle activations and kinematic configuration of the rigid bones associated with an expression from a sparse sampling of the deformation of the face surface over time, acquired using a motion capture system. Our simulation model, consisting of 840K tetrahedral elements, was created through non-rigid registration of a muscle geometry template derived from the visible human dataset to MRI volumetric data acquired from the motion capture subject.

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.

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.

We built an anatomically accurate model of facial musculature, passive tissue and underlying skeletal structure using volumetric data acquired from a living male subject. The tissues are endowed with a highly nonlinear constitutive model including controllable anisotropic muscle activations based on fiber directions. Detailed models of this sort can be difficult to animate requiring complex coordinated stimulation of the underlying musculature. We propose a solution to this problem automatically determining muscle activations that track a sparse set of surface landmarks, e.g. acquired from motion capture marker data. Since the resulting animation is obtained via a three dimensional nonlinear finite element method, we obtain visually plausible and anatomically correct deformations with spatial and temporal coherence that provides robustness against outliers in the motion capture data. Moreover, the obtained muscle activations can be used in a robust simulation framework including contact and collision of the face with external objects.

Simulation of the musculoskeletal system has important applications in biomechanics, biomedical engineering, surgery simulation, and computer graphics. The accuracy of the muscle, bone, and tendon geometry as well as the accuracy of muscle and tendon dynamic deformation are of paramount importance in all these applications. We present a framework for extracting and simulating high resolution musculoskeletal geometry from the segmented visible human data set. We simulate 30 contact/collision coupled muscles in the upper limb and describe a computationally tractable implementation using an embedded mesh framework. Muscle geometry is embedded in a nonmanifold, connectivity preserving simulation mesh molded out of a lower resolution BCC lattice containing identical, well-shaped elements, leading to a relaxed time step restriction for stability and, thus, reduced computational cost. The muscles are endowed with a transversely isotropic, quasi-incompressible constitutive model that incorporates muscle fiber fields as well as passive and active components. The simulation takes advantage of a new robust finite element technique that handles both degenerate and inverted tetrahedra.

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.

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.

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.

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.

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.

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.

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.

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 inter-action of smoke with moving objects.

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.