Physics-Based Animation

Haozhe Su*, Tao Xue*, Chengguizi Han, Chenfanfu Jiang, Mridul Aanjaneya (*Joint first authors)

We assume that the viscous forces in any liquid are simultaneously local and non-local, and introduce the extended POM-POM model [Mcleish and Larson 1998; Oishi et al. 2012; Verbeeten et al. 2001] to computer graphics to design a unified constitutive model for viscosity that generalizes prior models, such as Oldroyd-B, the Upper-convected Maxwell (UCM) model [Sadeghy et al. 2005], and classical Newtonian viscosity under one umbrella, recovering each of them with different parameter values. Implicit discretization of our model via backward Euler recovers the variational Stokes solver of [Larionov et al. 2017] for Newtonian viscosity. For greater accuracy, however, we introduce the second-order accurate Generalized Single Step Single Solve (GS4) scheme [Tamma et al. 2000; Zhou and Tamma 2004] to computer graphics, which recovers all prior second-order accurate time integration schemes to date. Using GS4 and our generalized constitutive model, we present a Material Point Method (MPM) for simulating various viscoelastic liquid behaviors, such as classical liquid rope coiling, buckling, folding, and shear thinning/thickening. In addition, we show how to couple our viscoelastic liquid simulator with the recently introduced non-Fourier heat diffusion solver [Xue et al. 2020] for simulating problems with phase change, such as melting chocolate and digital fabrication with 3D printing. While the discretization of heat diffusion is slightly different within GS4, we show that it can still be efficiently solved using an assembly-free Multigrid-preconditioned Conjugate Gradients solver. We present end-to-end 3D simulations to demonstrate the versatility of our framework.

A Unified Second-Order Accurate in Time MPM Formulation for Simulating Viscoelastic Liquids with Phase Change

Yuanming Hu, Jiafeng Liu, Xuanda Yang, Mingkuan Xu, Ye Kuang, Weiwei Xu, Qiang Dai, William T. Freeman, Fredo Durand

High-resolution simulations can deliver great visual quality, but they are often limited by available memory, especially on GPUs. We present a compiler for physical simulation that can achieve both high performance and significantly reduced memory costs, by enabling flexible and aggressive quantization. Low-precision (“quantized”) numerical data types are used and packed to represent simulation states, leading to reduced memory space and bandwidth consumption. Quantized simulation allows higher resolution simulation with less memory, which is especially attractive on GPUs. Implementing a quantized simulator that has high performance and packs the data tightly for aggressive storage reduction would be extremely labor-intensive using traditional programming languages. To make the creation of quantized simulation practical, we have developed a new set of language abstractions and a compilation system. A suite of tailored domain-specific optimizations ensure quantized simulators often run as fast as the full-precision simulators, despite the overhead of encoding-decoding the packed quantized data types. Our programming language and compiler, based on Taichi, allow developers to effortlessly switch between different full-precision and quantized simulators, to explore the full design space of quantization schemes, and ultimately to achieve a good balance between space and precision. The creation of quantized simulation with our system has large benefits in terms of memory consumption and performance. For example, on a single GPU, we can simulate a Game of Life with 20 billion cells (8× compression per pixel), an Eulerian fluid system with 421 million active voxels (1.6× compression per voxel), and a hybrid Eulerian-Lagrangian elastic object simulation with 235 million particles (1.7× compression per particle). At the same time, quantized simulations create physically plausible results. Our quantization techniques are complementary to existing acceleration approaches of physical simulation: they can be used in combination with these existing approaches, such as sparse data structures, for even higher scalability and performance.

QuanTaichi: A Compiler for Quantized Simulations

Egor Larionov, Ye Fan, Dinesh K. Pai

Frictional contact between deformable elastic objects remains a difficult simulation problem in computer graphics. Traditionally, contact has been resolved using sophisticated collision detection schemes and methods that build on the assumption that contact happens between polygons. While polygonal surfaces are an efficient representation for solids, they lack some intrinsic properties that are important for contact resolution. Generally, polygonal surfaces are not equipped with an intrinsic inside and outside partitioning or a smooth distance field close to the surface. Here we propose a new method for resolving frictional contacts against deforming implicit surface representations that addresses these problems. We augment a moving least squares (MLS) implicit surface formulation with a local kernel for resolving contacts, and develop a simple parallel transport approximation to enable transfer of frictional impulses. Our variational formulation of dynamics and elasticity enables us to naturally include contact constraints, which are resolved as one Newton-Raphson solve with linear inequality constraints. We extend this formulation by forwarding friction impulses from one time step to the next, used as external forces in the elasticity solve. This maintains the decoupling of friction from elasticity thus allowing for different solvers to be used in each step. In addition, we develop a variation of staggered projections, that relies solely on a non-linear optimization without constraints and does not require a discretization of the friction cone. Our results compare favorably to a popular industrial elasticity solver (used for visual effects), as well as recent academic work in frictional contact, both of which rely on polygons for contact resolution. We present examples of coupling between rigid bodies, cloth and elastic solids.

Frictional Contact on Smooth Elastic Solids

Ryoichi Ando, Christopher Batty

We propose a new adaptive liquid simulation framework that achieves highly detailed behavior with reduced implementation complexity. Prior work has shown that spatially adaptive grids are efficient for simulating large-scale liquid scenarios, but in order to enable adaptivity along the liquid surface these methods require either expensive boundary-conforming (re-)meshing or elaborate treatments for second order accurate interface conditions. This complexity greatly increases the difficulty of implementation and maintainability, potentially making it infeasible for practitioners. We therefore present new algorithms for adaptive simulation that are comparatively easy to implement yet efficiently yield high quality results. First, we develop a novel staggered octree Poisson discretization for free surfaces that is second order in pressure and gives smooth surface motions even across octree T-junctions, without a power/Voronoi diagram construction. We augment this discretization with an adaptivity-compatible surface tension force that likewise supports T-junctions. Second, we propose a moving least squares strategy for level set and velocity interpolation that requires minimal knowledge of the local tree structure while blending near-seamlessly with standard trilinear interpolation in uniform regions. Finally, to maximally exploit the flexibility of our new surface-adaptive solver, we propose several novel extensions to sizing function design that enhance its effectiveness and flexibility. We perform a range of rigorous numerical experiments to evaluate the reliability and limitations of our method, as well as demonstrating it on several complex high-resolution liquid animation scenarios.

A Practical Octree Liquid Simulator with Adaptive Surface Resolution

Gilles Daviet

Frictional contacts are the primary way by which physical bodies interact, yet they pose many numerical challenges. Previous works have devised robust methods for handling collisions in elastic bodies, cloth, or fiber assemblies such as hair, but the performance of many of those algorithms degrades when applied to objects with different topologies or constitutive models, or simply cannot scale to high-enough numbers of contacting points.
In this work we propose a unified approach, able to handle a large class of dynamical objects, that can solve for millions of contacts with nonlinear Coulomb friction while keeping computation time and memory usage reasonable. Our method allows seamless coupling between the various simulated components that comprise virtual characters and their environment.

Simple and Scalable Frictional Contacts for Thin Nodal Objects

Mohammad Sina Nabizadeh, Ravi Ramamoorthi, Albert Chern

Solving partial differential equations (PDEs) on infinite domains has been a challenging task in physical simulations and geometry processing. We introduce a general technique to transform a PDE problem on an unbounded domain to a PDE problem on a bounded domain. Our method uses the Kelvin Transform, which essentially inverts the distance from the origin. However, naive application of this coordinate mapping can still result in a singularity at the origin in the transformed domain. We show that by factoring the desired solution into the product of an analytically known (asymptotic) component and another function to solve for, the problem can be made continuous and compact, with solutions significantly more efficient and well-conditioned than traditional finite element and Monte Carlo numerical PDE methods on stretched coordinates. Specifically, we show that every Poisson or Laplace equation on an infinite domain is transformed to another Poisson (Laplace) equation on a compact region. In other words, any existing Poisson solver on a bounded domain is readily an infinite domain Poisson solver after being wrapped by our transformation. We demonstrate the integration of our method with finite difference and Monte Carlo PDE solvers, with applications in the fluid pressure solve and simulating electromagnetism, including visualizations of the solar magnetic field. Our transformation technique also applies to the Helmholtz equation whose solutions oscillate out to infinity. After the transformation, the Helmholtz equation becomes a tractable equation on a bounded domain without infinite oscillation. To our knowledge, this is the first time that the Helmholtz equation on an infinite domain is solved on a bounded grid without requiring an artificial absorbing boundary condition.

Kelvin Transformations for Simulations on Infinite Domains

Mihail Francu, Árni Gunnar Ásgeirsson, Erleben, Kenny, Mads J. L. Rønnow

The simulation of incompressible materials suffers from locking when us-ing the standard finite element method (FEM) and coarse linear tetrahedral meshes. Locking increases as the Poisson ratio?gets close to0.5and often lower Poisson ratio values are used to reduce locking, affecting volume preservation. We propose a novel mixed FEM approach to simulating in-compressible solids that alleviates the locking problem for tetrahedra. Our method uses linear shape functions for both displacements and pressure and adds one scalar per node. It can accommodate nonlinear isotropic materials described by a Young’s modulus and any Poisson ratio value by enforcing a volumetric constitutive law. The most realistic such material is Neo-Hookean and we focus on adapting it to our method. For?=0.5we can obtain full volume preservation up to any desired numerical accuracy. We show that standard Neo-Hookean simulations using tetrahedra are often locking which in turn affects accuracy. We show that our method gives better results and that our Newton solver is more robust. As an alternative, we propose a dual ascent solver that is simple and has a good convergence rate. We validate these results using numerical experiments and quantitative analysis

Locking-Proof Tetrahedra

• Revisiting Integration in the Material Point Method: A Scheme for Easier Separation and Less Dissipation
• Mechanics-Aware Deformation of Yarn Pattern Geometry
• Kelvin Transformations for Simulations on Infinite Domains
• QuanTaichi: A Compiler for Quantized Simulations
• A Unified Second-Order Accurate in Time MPM Formulation for Simulating Viscoelastic Liquids with Phase Change
• Bijective and Coarse High-Order Tetrahedral Meshes
• Physical validation of simulators in Computer Graphics: A new framework dedicated to slender elastic structures and frictional contact
• Stream-Guided Smoke Simulations
• Solid-Fluid Interaction with Surface-Tension-Dominant Contact
• Fire in Paradise: Mesoscale Simulation of Wildfires
• Systematically Differentiating Parametric Discontinuities
• Thin-Film Smoothed Particle Hydrodynamics Fluid
• Clebsch Gauge Fluid
• Incompressible Flow Simulation on Vortex Segment Clouds
• Codimensional Incremental Potential Contact
• Intersection-free Rigid Body Dynamics
• Medial IPC: Accelerated Incremental Potential Contact With Medial Elastics
• High-order Differentiable Autoencoder for Nonlinear Model Reduction
• Fast Linking Numbers for Topology Verification
• of Loopy Structures
• Learning Contact Corrections for Handle-Based Subspace Dynamics
• The Shape Matching Element Method: Direct Animation of Curved Surface Models
• GPU-Based Simulation of Cloth Wrinkles at Submillimeter Levels
• Multiscale Cholesky Preconditioning for Ill-conditioned Problems
• A Momentum-Conserving Implicit Material Point Method for Surface Tension with Contact Angles and Spatial Gradients
• SANM: A Symbolic Asymptotic Numerical Solver with Applications in Mesh Deformation
• Learning Meaningful Controls for Fluids
• Unified Particle System for Multiple-fluid Flow and Porous Material
• Constrained Projective Dynamics: Real-time Simulation of Deformable Objects With Energy-momentum Conservation

TOG papers to be presented:

• Dynamic Upsampling of Smoke through Dictionary-based Learning
• Frictional Contact on Smooth Elastic Solids
• A Safe and Fast Repulsion Method for GPU-based Cloth Self Collisions
• Optimized Refinement for Spatially Adaptive SPH
• SIERE: A Hybrid Semi-implicit Exponential Integrator for Efficiently Simulating Stiff Deformable Objects

Jingwei Tang, Vinicius C. Azevedo, Guillaume Cordonnier, Barbara Solenthaler

Fluid control often uses optimization of control forces that are added to a simulation at each time step, such that the final animation matches a single or multiple target density keyframes provided by an artist. The optimization problem is strongly under-constrained with a high-dimensional parameter space, and finding optimal solutions is challenging, especially for higher resolution simulations. In this paper, we propose two novel ideas that jointly tackle the lack of constraints and high dimensionality of the parameter space. We first consider the fact that optimized forces are allowed to have divergent modes during the optimization process. These divergent modes are not entirely projected out by the pressure solver step, manifesting as unphysical smoke sources that are explored by the optimizer to match a desired target. Thus, we reduce the space of the possible forces to the family of strictly divergence-free velocity fields, by optimizing directly for a vector potential. We synergistically combine this with a smoothness regularization based on a spectral decomposition of control force fields. Our method enforces lower frequencies of the force fields to be optimized first by filtering force frequencies in the Fourier domain. The mask-growing strategy is inspired by Kolmogorov’s theory about scales of turbulence. We demonstrate improved results for 2D and 3D fluid mcontrol especially in higher-resolution settings, while eliminating the need for manual parameter tuning. We showcase various applications of our method, where the user effectively creates or edits smoke simulations.

Honey, I Shrunk the Domain: Frequency-aware Force FieldReduction for Efficient Fluids Optimization

Kai Bai, Wei Li, Mathieu Desbrun, Xiaopei Liu

Simulating turbulent smoke flows with fine details is computationally intensive. For iterative editing or simply faster generation, efficiently upsampling a low-resolution numerical simulation is an attractive alternative. We propose a novel learning approach to the dynamic upsampling of smoke flows based on a training set of flows at coarse and fine resolutions.Our multiscale neural network turns an input coarse animation into a sparse linear combination of small velocity patches present in a precomputed over-complete dictionary. These sparse coefficients are then used to generate a high-resolution smoke animation sequence by blending the fine counterparts of the coarse patches. Our network is initially trained from a sequence of example simulations to both construct the dictionary of corresponding coarse and fine patches and allow for the fast evaluation of a sparse patch encoding of any coarse input. The resulting network provides an accurate upsampling when the coarse input simulation is well approximated by patches present in the training set (e.g., for re-simulation), or simply visually-plausible upsampling when input and training set differ significantly. We show a variety of examples to ascertain the strengths and limitations of our approach, and offer comparisons to existing approaches to demonstrate its quality and effectiveness.

Dynamic Upsampling of Smoke through Dictionary-based Learning