We propose a physics-based combustion simulation method for computer graphics that extends the mathematical models of previous efforts to automatically capture more realistic flames as well as temperature and soot distributions. Our method includes mathematical models for the thermodynamic properties of real-world fuels which enables, for example, the prediction of adiabatic flame temperatures. We couple this with a model of heat transfer that includes convection, conduction as well as both radiative cooling and heating. This facilitates among other things ignition at a distance without heating up the intermediate air. We model the combustion as infinitely fast chemistry and couple this with the thin flame model, spatially varying laminar burning velocities based on local species and empirical measurements, physically validated soot formation and oxidation as well as water vapor production and condensation. We implement this on adaptive octree-like grids with collocated state variables, a new SBDF2-derived semi-Lagrangian time integrator for velocity, and a multigrid scheme used for multiple solver components. In combination, these models enable us to simulate deflagration phenomena ranging from small scale premixed and diffusion flames to fireballs and subsonic explosions which we demonstrate by several examples. In addition, we validate several of the results based on reference footage and measurements and discuss the relation of prevalent heuristic techniques arising in visual effects production to some of the physics-based models we propose.

Optimizing distortion energies over a mesh, in two or three dimensions, is a common and critical problem in physical simulation and geometry processing. We present three new improvements to the state of the art: a barrier-aware line-search filter that cures blocked descent steps due to element barrier terms and so enables rapid progress; an energy proxy model that adaptively blends the Sobolev (inverse-Laplacian-processed) gradient and L-BFGS descent to gain the advantages of both, while avoiding L-BFGS's current limitations in distortion optimization tasks; and a characteristic gradient norm providing a robust and largely mesh- and energy-independent convergence criterion that avoids wrongful termination when algorithms temporarily slow their progress. Together these improvements form the basis for Blended Cured Quasi-Newton (BCQN), a new distortion optimization algorithm. Over a wide range of problems over all scales we show that BCQN is generally the fastest and most robust method available, making some previously intractable problems practical while offering up to an order of magnitude improvement in others.

We propose a novel unsteady Stokes solver for coupled viscous and pressure forces in grid-based liquid animation which yields greater accuracy and visual realism than previously achieved. Modern fluid simulators treat viscosity and pressure in separate solver stages, which reduces accuracy and yields incorrect free surface behavior. Our proposed implicit variational formulation of the Stokes problem leads to a symmetric positive definite linear system that gives properly coupled forces, provides unconditional stability, and treats difficult boundary conditions naturally through simple volume weights. Surface tension and moving solid boundaries are also easily incorporated. Qualitatively, we show that our method recovers the characteristic rope coiling instability of viscous liquids and preserves fine surface details, while previous grid-based schemes do not. Quantitatively, we demonstrate that our method is convergent through grid refinement studies on analytical problems in two dimensions. We conclude by offering practical guidelines for choosing an appropriate viscous solver, based on the scenario to be animated and the computational costs of different methods.

We present a mesh-based, interpolatory method for interactively creating artist-directed inbetweens from arbitrary sets of 2D drawing shapes without rigging. To enable artistic freedom of expression we remove prior restrictions on the range of possible changes between shapes; we support interpolation with extreme deformation and unrestricted topology change. To do this, we extend discrete variational interpolation by introducing a consistent multimesh structure over drawings, a Comesh Optimization algorithm that optimizes our multimesh for both intra- and inter-mesh quality, and a new shape-space energy that efficiently supports arbitrary changes and can prevent artwork overlap when desired. Our multimesh encodes specified correspondences that guide interpolation paths between shapes. With these correspondences, an efficient local-global minimization of our energy interpolates n-way between drawing shapes to create inbetweens. Our Comesh Optimization enables artifact-free minimization by building consistent meshes across drawings that improve both the quality of per-mesh energy discretization and inter-mesh mapping distortions, while guaranteeing a single, compatible triangulation. We implement our method in a test-bed interpolation system that allows interactive creation and editing of animations from sparse key drawings with arbitrary topology and shape change.

Most fluid scenarios in graphics have a high Reynolds number, where viscosity is dominated by inertial effects, thus most solvers drop viscosity altogether: numerical damping from coarse grids is generally stronger than physical viscosity while resembling it in character. However, viscosity remains crucial near solid boundaries, in the boundary layer , to a large extent determining the look of the flow as a function of Reynolds number. Typical graphics simulations do not resolve boundary layer dynamics, so their look is determined mostly by numerical errors with the given grid size and time step, rather than physical parameters. We introduce two complementary techniques to capture boundary layer dynamics, bringing more physical control and predictability. We extend the FLIP particle-grid method with viscous particle strength exchange[Rivoalen and Huberson 2001] to better transfer momentum at solid boundaries, dubbed VFLIP. We also introduce Weakly Higher Resolution Regional Projection (WHIRP), a cheap and simple way to increase grid resolution where important by overlaying high resolution grids on the global coarse grid.

Most visual effects fluid solvers use a time-splitting approach where velocity is first advected in the flow, then projected to be incompressible with pressure. Even if a highly accurate advection scheme is used, the self-advection step typically transfers some kinetic energy from divergence-free modes into divergent modes, which are then projected out by pressure, losing energy noticeably for large time steps. Instead of taking smaller time steps or using significantly more complex time integration, we propose a new scheme called IVOCK (Integrated Vorticity of Convective Kinematics) which cheaply captures much of what is lost in self-advection by identifying it as a violation of the vorticity equation. We measure vorticity on the grid before and after advection, taking into account vortex stretching, and use a cheap multigrid V-cycle approximation to a vector potential whose curl will correct the vorticity error. IVOCK works independently of the advection scheme (we present examples with various semi-Lagrangian methods and FLIP), works independently of how boundary conditions are applied (it just corrects error in advection, leaving pressure etc. to take care of boundaries and other forces), and other solver parameters (we provide smoke, fire, and water examples). For 10 ~ 25% extra computation time per step much larger steps can be used, while producing detailed vorticial structures and convincing turbulence that are lost without correction.

We present a new brittle fracture simulation method based on a boundary integral formulation of elasticity and recent explicit surface mesh evolution algorithms. Unlike prior physically-based simulations in graphics, this avoids the need for volumetric sampling and calculations, which aren't reflected in the rendered output. We represent each quasi-rigid body by a closed triangle mesh of its boundary, on which we solve quasi-static linear elasticity via boundary integrals in response to boundary conditions and loads such as impact forces and gravity. A fracture condition based on maximum tensile stress is subsequently evaluated at mesh vertices, while crack initiation and propagation are formulated as an interface tracking procedure in material space. Existing explicit mesh tracking methods are modified to support evolving cracks directly in the triangle mesh representation, giving highly detailed fractures with sharp features, independent of any volumetric sampling (unlike tetrahedral mesh or level set approaches); the triangle mesh representation also allows simple integration into rigid body engines. We also give details on our well-conditioned integral equation treatment solved with a kernel-independent Fast Multipole Method for linear time summation. Various brittle fracture scenarios demonstrate the efficacy and robustness of our new method.

We present a new adaptive fluid simulation method that captures a high resolution surface with precise dynamics, without an inefficient fine discretization of the entire fluid volume. Prior adaptive methods using octrees or unstructured meshes carry large overheads and implementation complexity. We instead stick with coarse regular Cartesian grids, using detailed cut cells at boundaries, and discretize the dynamics with a p-adaptive Discontinuous Galerkin (DG) method. This retains much of the data structure simplicity of regular grids, more efficiently captures smooth parts of the flow, and offers the flexibility to easily increase resolving power where needed without geometric refinement.

Solving the N -body problem, i.e. the Poisson problem with point sources, is a common task in graphics and simulation. The naive direct summation of the kernel function over all particles scales quadratically, rendering it too slow for large problems, while the optimal Fast Multipole Method has drastic implementation complexity and can sometimes carry too high an overhead to be practical. We present a new Particle-Particle Particle-Mesh (PPPM) algorithm which is fast, accurate, and easy to implement even in parallel on a GPU. We capture long-range interactions with a fast multigrid solver on a background grid with a novel boundary condition, while short-range interactions are calculated directly with a new error compensation to avoid error from the background grid. We demonstrate the power of PPPM with a new vortex particle smoke solver, which features a vortex segment-approach to the stretching term, potential flow to enforce no-stick solid boundaries on arbitrary moving solid boundaries, and a new mechanism for vortex shedding from boundary layers. Comparison against a simpler Vortex-in-Cell approach shows PPPM can produce significantly more detailed results with less computation. In addition, we use our PPPM solver for a Poisson surface reconstruction problem to show its potential as a general-purpose Poisson solver.

In this paper, we present a method for animating multiphase flow of immiscible fluids using unstructured moving meshes. Our underlying discretization is an unstructured tetrahedral mesh, the deformable simplicial complex (DSC), that moves with the flow in a Lagrangian manner. Mesh optimization operations improve element quality and avoid element inversion. In the context of multiphase flow, we guarantee that every element is occupied by a single fluid and, consequently, the interface between fluids is represented by a set of faces in the simplicial complex. This approach ensures that the underlying discretization matches the physics and avoids the additional book-keeping required in grid-based methods where multiple fluids may occupy the same cell. Our Lagrangian approach naturally leads us to adopt a finite element approach to simulation, in contrast to the finite volume approaches adopted by a majority of fluid simulation techniques that use tetrahedral meshes. We characterize fluid simulation as an optimization problem allowing for full coupling of the pressure and velocity fields and the incorporation of a second-order surface energy. We introduce a preconditioner based on the diagonal Schur complement and solve our optimization on the GPU. We provide the results of parameter studies as well as a performance analysis of our method, together with suggestions for performance optimization.

Computer animated ocean waves for feature films are typically carefully choreographed to match the vision of the director and to support the telling of the story. The rough shape of these waves is established in the previsualization (previs) stage, where artists use a variety of modeling tools with fast feedback to obtain the desired look. This poses a challenge to the effects artists who must subsequently match the locked-down look of the previs waves with high-quality simulated or synthesized waves, adding the detail necessary for the final shot. We propose a set of automated techniques for synthesizing Fourier-based ocean waves that match a previs input, allowing artists to quickly enhance the input wave animation with additional higher-frequency detail that moves consistently with the coarse waves, tweak the wave shapes to flatten troughs and sharpen peaks if desired (as is characteristic of deep water waves), and compute a physically reasonable velocity field of the water analytically. These properties are demonstrated with several examples, including a previs scene from a visual effects production environment.

Physically-based liquid animations often ignore the influence of air, giving up interesting behavior. We present a new method which treats both air and liquid as incompressible, more accurately reproducing the reality observed at scales relevant to computer animation. The Fluid Implicit Particle (FLIP) method, already shown to effectively simulate incompressible fluids with low numerical dissipation, is extended to two-phase flow by associating a phase bit with each particle. The liquid surface is reproduced at each time step from the particle positions, which are adjusted to prevent mixing near the surface and to allow for accurate surface tension. The liquid surface is adjusted around small-scale features so they are represented in the grid-based pressure projection, while separate, loosely coupled velocity fields reduce unwanted influence between the phases. The resulting scheme is easy to implement, requires little parameter tuning, and is shown to reproduce lively two-phase fluid phenomena.

Continuous collision detection (CCD) between deforming triangle mesh elements in 3D is a critical tool for many applications. The standard method involving a cubic polynomial solver is vulnerable to rounding error, requiring the use of ad hoc tolerances, and nevertheless is particularly fragile in (near-)planar cases. Even with per-simulation tuning, it may still cause problems by missing collisions or erroneously flagging non-collisions. We present a geometrically exact alternative guaranteed to produce the correct Boolean result (significant collision or not) as if calculated with exact arithmetic, even in degenerate scenarios. Our critical insight is that only the parity of the number of collisions is needed for robust simulation, and this parity can be calculated with simpler non-constructive predicates. In essence we analyze the roots of the nonlinear system of equations defining CCD through careful consideration of the boundary of the parameter domain. The use of new conservative culling and interval filters allows typical simulations to run as fast as with the non-robust version, but without need for tuning or worries about failure cases even in geometrically degenerate scenarios. We demonstrate the effectiveness of geometrically exact detection with a novel adaptive cloth simulation, the first to guarantee to remain intersection-free despite frequent curvature-driven remeshing.

We propose a new ghost fluid approach for free surface and solid boundary conditions in Smoothed Particle Hydrodynamics (SPH) liquid simulations. Prior methods either suffer from a spurious numerical surface tension artifact or drift away from the mass conservation constraint, and do not capture realistic cohesion of liquid to solids. Our Ghost SPH scheme resolves this with a new particle sampling algorithm to create a narrow layer of ghost particles in the surrounding air and solid, with careful extrapolation and treatment of fluid variables to reflect the boundary conditions. We also provide a new, simpler form of artificial viscosity based on XSPH. Examples demonstrate how the new approach captures real liquid behaviour previously unattainable by SPH with very little extra cost.

Art direction of high resolution naturalistic liquid simulations is notoriously hard, due to both the chaotic nature of the physics and the computational resources required. Resimulating a scene at higher resolution often produces very different results, and is too expensive to allow many design cycles. We present a method of constraining or guiding a high resolution liquid simulation to stay close to a finalized low resolution version (either simulated or directly animated), restricting the solve to a thin outer shell of liquid around a guide shape . Our method is generally faster than an unconstrained simulation and can be integrated with a standard fluid simulator. We demonstrate several applications, with both simulated and hand-animated inputs.

We introduce an Eulerian liquid simulation framework based on the Voronoi diagram of a potentially unorganized collection of pressure samples. Constructing the simulation mesh in this way allows us to place samples anywhere in the computational domain; we exploit this by choosing samples that accurately capture the geometry and topology of the liquid surface. When combined with high-resolution explicit surface tracking this allows us to simulate nearly arbitrarily thin features, while eliminating noise and other artifacts that arise when there is a resolution mismatch between the simulation and the surface---and allowing a precise inclusion of surface tension based directly on and at the same resolution as the surface mesh. In addition, we present a simplified Voronoi/Delaunay mesh velocity interpolation scheme, and a direct extension of embedded free surfaces and solid boundaries to Voronoi meshes.

We present a new discretization for the physics-based animation of developable surfaces. Constrained to not deform at all in-plane but free to bend out-of-plane, these are an excellent approximation for many materials, including most cloth, paper, and stiffer materials. Unfortunately the conforming (geometrically continuous) discretizations used in graphics break down in this limit. Our nonconforming approach solves this problem, allowing us to simulate surfaces with zero in-plane deformation as a hard constraint. However, it produces discontinuous meshes, so we further couple this with a "ghost" conforming mesh for collision processing and rendering. We also propose a new second order accurate constrained mechanics time integration method that greatly reduces the numerical damping present in the usual first order methods used in graphics, for virtually no extra cost and sometimes significant speed-up.

Physical simulation has emerged as a compelling animation technique, yet current approaches to coupling simulations of fluids and solids with irregular boundary geometry are inefficient or cannot handle some relevant scenarios robustly. We propose a new variational approach which allows robust and accurate solution on relatively coarse Cartesian grids, allowing possibly orders of magnitude faster simulation. By rephrasing the classical pressure projection step as a kinetic energy minimization, broadly similar to modern approaches to rigid body contact, we permit a robust coupling between fluid and arbitrary solid simulations that always gives a well-posed symmetric positive semi-definite linear system. We provide several examples of efficient fluid-solid interaction and rigid body coupling with sub-grid cell flow. In addition, we extend the framework with a new boundary condition for free-surface flow, allowing fluid to separate naturally from solids.

Procedural methods for animating turbulent fluid are often preferred over simulation, both for speed and for the degree of animator control. We offer an extremely simple approach to efficiently generating turbulent velocity fields based on Perlin noise, with a formula that is exactly incompressible (necessary for the characteristic look of everyday fluids), exactly respects solid boundaries (not allowing fluid to flow through arbitrarily-specified surfaces), and whose amplitude can be modulated in space as desired. In addition, we demonstrate how to combine this with procedural primitives for flow around moving rigid objects, vortices, etc.

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.

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.

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.