Physics-Based Animation

Fang Da, David Hahn, Christopher Batty, Chris Wojtan, Eitan Grinspun

We propose a novel surface-only technique for simulating incompressible, inviscid and uniform-density liquids with surface tension in three dimensions. The liquid surface is captured by a triangle mesh on which a Lagrangian velocity field is stored. Because advection of the velocity field may violate the incompressibility condition, we devise an orthogonal projection technique to remove the divergence while requiring the evaluation of only two boundary integrals. The forces of surface tension, gravity, and solid contact are all treated by a boundary element solve, allowing us to perform detailed simulations of a wide range of liquid phenomena, including waterbells, droplet and jet collisions, fluid chains, and crown splashes.

Surface-Only Liquids

Gergely Klar, Theodore Gast, Andre Pradhana, Chuyuan Fu, Craig Schroeder, Chenfanfu Jiang, Joseph Teran

We simulate sand dynamics using an elastoplastic, continuum assumption. We demonstrate that the Drucker-Prager plastic flow model combined with a Hencky-strain-based hyperelasticity accurately recreates a wide range of visual sand phenomena with moderate computational expense. We use the Material Point Method (MPM) to discretize the governing equations for its natural treatment of contact, topological change and history dependent constitutive relations. The Drucker-Prager model naturally represents the frictional relation between shear and normal stresses through a yield stress criterion. We develop a stress projection algorithm used for enforcing this condition with a non-associative flow rule that works naturally with both implicit and explicit time integration. We demonstrate the efficacy of our approach on examples undergoing large deformation, collisions and topological changes necessary for producing modern visual effects.

Drucker-Prager Elastoplasticity for Sand Animation

Xinxin Zhang, Minchen Li, Robert Bridson

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.

Resolving Fluid Boundary Layers with Particle Strength Exchange and Weak Adaptivity

SIGGRAPH 2016 papers:

• Ebb: A DSL for Physical Simulation on CPUs and GPUs
• Pose-Space Subspace Dynamics
• Surface-Only Liquids
• Generalized Non-reflecting Boundaries for Fluid Re-Simulation
• Fast Approximations for Boundary Element Based Brittle Fracture Simulation
• Resolving Fluid Boundary Layers with Particle Strength Exchange and Weak Adaptivity
• Drucker-Prager Elastoplasticity for Sand Animation
• A Semi-Implicit Material Point Method for the Continuum Simulation of Granular Materials
• Schrodinger’s Smoke
• Preserving Geometry and Topology for Fluid Flows with Thin Obstacles and Narrow Gaps
• Artist-Directed Dynamics for 2D Animation
• Physics-Driven Pattern Adjustment for Direct 3D Garment Editing
• Example-based Plastic Deformation of Rigid Bodies
• Multiphase SPH Simulation for Interactive Fluids and Solids

TOG presentations at SIGGRAPH 2016:

• Simit: A Language for Physical Simulation
• Interactively cutting and constraining nodes in a mesh by augmented matrices
• Efficient Fluid Simulation on the Surface of a Sphere
• Non-smooth developable geometry for interactively animating paper crumpling

Gilbert Bernstein, Chinmayee Shah, Crystal Lemire, Zachery DeVito, Matthew Fisher, Philip Levis, Pat Hanrahan

Designing programming environments for physical simulation is challenging because simulations rely on diverse algorithms and geometric domains. These challenges are compounded when we try to run efficiently on heterogeneous parallel architectures. We present Ebb, a domain-specific language (DSL) for simulation, that runs efficiently on both CPUs and GPUs. Unlike previous DSLs, Ebb uses a three-layer architecture to separate (1) simulation code, (2) definition of data structures for geometric domains, and (3) runtimes supporting parallel architectures. Different geometric domains are implemented as libraries that use a common, unified, relational data model. By structuring the simulation framework in this way, programmers implementing simulations can focus on the physics and algorithms for each simulation without worrying about their implementation on parallel computers. Because the geometric domain libraries are all implemented using a common runtime based on relations, new geometric domains can be added as needed, without specifying the details of memory management, mapping to different parallel architectures, or having to expand the runtime’s interface. We evaluate Ebb by comparing it to several widely used simulations, demonstrating comparable performance to hand-written GPU code where available, and surpassing existing CPU performance optimizations by up to 9x when no GPU code exists.

Ebb: A DSL for Physical Simulation on CPUs and GPUs

Marcos Sandim, Douglas Cedrim, Luis Gustavo Nonato, Paulo Pagliosa, and Afonso Paiva

This paper presents a novel method to detect free-surfaces on particle-based volume representation. In contrast to most particle-based free-surface detection methods, which perform the surface identification based on physical and geometrical properties derived from the underlying fluid flow simulation, the proposed approach only demands the spatial location of the particles to properly recognize surface particles, avoiding even the use of kernels. Boundary particles are identified through a Hidden Point Removal (HPR) operator used for visibility test. Our method is very simple, fast, easy to implement and robust to changes in the distribution of particles, even when facing large deformation of the free-surface. A set of comparisons against state-of-the-art boundary detection methods show the effectiveness of our approach. The good performance of our method is also attested in the context of fluid flow simulation involving free-surface, mainly when using level-sets for rendering purposes.

Boundary detection in particle-based fluids

Yu-Hong Yeung, Jessica Crouch, Alex Pothen

We present a finite element solution method that is well-suited for interactive simulations of cutting meshes in the regime of linear elastic models. Our approach features fast updates to the solution of the stiffness system of equations to account for real-time changes in mesh connectivity and boundary conditions. Updates are accomplished by augmenting the stiffness matrix to keep it consistent with the changes to the underlying model, without re-factoring the matrix at each step of cutting. The initial stiffness matrix and its Cholesky factors are used to implicitly form and solve a Schur complement system using an iterative solver. As changes accumulate over many simulation time steps, the augmented solution method slows down due to the size of the augmented matrix. However, by periodically re-factoring the stiffness matrix in a concurrent background process, fresh Cholesky factors that incorporate recent model changes can replace the initial factors. This controls the size of the augmented matrices and provides a way to maintain a fast solution rate as the number of changes to a model grows. We exploit sparsity in the stiffness matrix, the right-hand-side vectors and the solution vectors to compute the solutions fast, and show that the time complexity of the update steps is bounded linearly by the size of the Cholesky factor of the initial matrix. Our complexity analysis and experimental results demonstrate that this approach scales well with problem size. Results for cutting and deformation of 3D linear elastic models are reported for meshes representing the brain, eye, and model problems with element counts up to 167, 000; these show the potential of this method for real-time interactivity. An application to limbal incisions for surgical correction of astigmatism, where linear elastic models and small deformations are sufficient, is included.

Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices

Fredrik Kjolstad, Shoaib Kamil Jonathan Ragan-Kelley, David I.W. Levin,Shinjiro Sueda, Desai Chen, Etienne Vouga, Danny M. Kaufman, Gurtej Kanwar,Wojciech Matusik, and Saman Amarasinghe

Using existing programming tools, writing high-performance simulation code is labor intensive and requires sacrificing readability and portability. The alternative is to prototype simulations in a high-level language like Matlab, thereby sacrificing performance. The Matlab programming model naturally describes the behavior of an entire physical system using the language of linear algebra. However, simulations also manipulate individual geometric elements, which are best represented using linked data structures like meshes. Translating between the linked data structures and linear algebra comes at significant cost, both to the programmer and the machine. High-performance implementations avoid the cost by rephrasing the computation in terms of linked or index data structures, leaving the code complicated and monolithic, often increasing its size by an order of magnitude. In this paper, we present Simit, a new language for physical simulations that lets the programmer view the system both as a linked data structure in the form of a hypergraph, and as a set of global vectors, matrices and tensors depending on what is convenient at any given time. Simit provides a novel assembly construct that makes it conceptually easy and computationally efficient to move between the two abstractions. Using the information provided by the assembly construct, the compiler generates efficient in-place computation on the graph. We demonstrate that Simit is easy to use: a Simit program is typically shorter than a Matlab program; that it is high-performance: a Simit program running sequentially on a CPU performs comparably to hand-optimized simulations; and that it is portable: Simit programs can be compiled for GPUs with no change to the program, delivering 4-20x speedups over our optimized CPU code.

Simit: A Language for Physical Simulation

Jens Cornelis, Markus Ihmsen, Andreas Peer, Matthias Teschner

We propose a novel unified particle representation for fluids and solid boundaries in Implicit Incompressible SPH (IISPH). In contrast to existing particle representations, the proposed concept does not require a separate processing of fluid and boundary particles. On one hand, this results in a simplified solver implementation with improved efficiency. On the other hand, the unified fluid and boundary representation adds flexibility to IISPH which enables versatile effects. In particular, particles can now dynamically interchange their role between fluid and boundary which we therefore refer to as liquid boundary. The paper mainly focuses on the description of the unified representation and on the application of the concept to visual effects such as solidification and liquefaction. To support the realization of these effects, the concept of unified fluid and liquid boundary particles is extended to a third particle type, so-called candidate particles that are used in a transition phase between fluid and liquid boundaries.

Liquid boundaries for implicit incompressible SPH

Kui Wu, Cem Yuksel

We present a robust real-time hair simulation method using hair meshes. Leveraging existing simulation models for sheet-based cloth, we introduce a volumetric force model for incorporating hair interactions inside the hair mesh volume. We also introduce a position correction method that minimizes the local deformation of the hair mesh due to collision handling. We demonstrate the robustness of our hair simulation method using large time steps with fast motion, and we show that our method can recover the initial hair shape even when the hair mesh goes through substantial deformation.

Real-Time Hair Mesh Simulation