Physics-Based Animation

Jan Bender, Tassilo Kugelstadt, Marcel Weiler, Dan Koschier

In this paper, we present a novel method for the robust handling of static and dynamic rigid boundaries in Smoothed Particle Hydrodynamics (SPH) simulations. We build upon the ideas of the density maps approach which has been introduced recently by Koschier and Bender. They precompute the density contributions of solid boundaries and store them on a spatial grid which can be efficiently queried during runtime. This alleviates the problems of commonly used boundary particles, like bumpy surfaces and inaccurate pressure forces near boundaries. Our method is based on a similar concept but we precompute the volume contribution of the boundary geometry and store it on a grid. This maintains all benefits of density maps but offers a variety of advantages which are demonstrated in several experiments. Firstly, in contrast to the density maps method we can compute derivatives in the standard SPH manner by differentiating the kernel function. This results in smooth pressure forces, even for lower map resolutions, such that precomputation times and memory requirements are reduced by more than two orders of magnitude compared to density maps. Furthermore, this directly fits into the SPH concept so that volume maps can be seamlessly combined with existing SPH methods. Finally, the kernel function is not baked into the map such that the same volume map can be used with different kernels. This is especially useful when we want to incorporate common surface tension or viscosity methods that use different kernels than the fluid simulation.

Volume Maps: An Implicit Boundary Representation for SPH

Michael Tao, Christopher Batty, Eugene Fiume, David IW Levin

Although geometry arising “in the wild” most often comes in the form of a surface representation, a plethora of geometrical and physical applications require the construction of volumetric embeddings either of the geometry itself or the domain surrounding it. Cartesian cut-cell-based mesh generation provides an attractive solution in which volumetric elements are constructed from the intersection of the input surface geometry with a uniform or adaptive hexahedral grid. This choice, especially common in computational fluid dynamics, has the potential to efficiently generate accurate, surface-conforming cells; unfortunately, current solutions are often slow, fragile, or cannot handle many common topological situations. We therefore propose a novel, robust cut-cell construction technique for triangle surface meshes that explicitly computes the precise geometry of the intersection cells, even on meshes that are open or non-manifold. Its fundamental geometric primitive is the intersection of an arbitrary segment with an axis-aligned plane. Beginning from the set of intersection points between triangle mesh edges and grid planes, our bottom-up approach robustly determines cut-edges, cut-faces, and finally cut-cells, in a manner designed to guarantee topological correctness. We demonstrate its effectiveness and speed on a wide range of input meshes and grid resolutions, and make the code available as open source.

Mandoline: Robust Cut-Cell Generation for Arbitrary Triangle Meshes

Stefan Reinhardt, Tim Krake, Bernhard Eberhardt, Daniel Weiskopf

We present a novel technique to correct errors introduced by the discretization of a fluid body when animating it with smoothed particle hydrodynamics (SPH). Our approach is based on the Shepard correction, which reduces the interpolation errors from irregularly spaced data. With Shepard correction, the smoothing kernel function is normalized using the weighted sum of the kernel function values in the neighborhood. To compute the correction factor, densities of neighboring particles are needed, which themselves are computed with the uncorrected kernel. This results in an inconsistent formulation and an error-prone correction of the kernel. As a consequence, the density computation may be inaccurate, thus the pressure forces are erroneous and may  cause instabilities in the simulation process.We present a consistent formulation by using the corrected densities to compute the exact kernel correction factor and, thereby, increase the accuracy of the simulation. Employing our method, a smooth density  distribution is achieved, i.e., the noise in the density field is reduced by orders of magnitude. To show that our method is independent of the SPH variant, we evaluate our technique on weakly compressible SPH and on divergence-free SPH. Incorporating the corrected density into the correction process, the problem cannot be stated explicitly anymore. We propose an efficient and easy-to-implement algorithm to solve the implicit problem by applying the power method. Additionally, we demonstrate how our model can be applied to improve the density distribution on rigid bodies when using a well-known rigid-fluid coupling approach.

Consistent Shepard Interpolation for SPH-Based Fluid Animation

Mengyuan Ding, Xuchen Han, Stephanie Wang, Theodore Gast, Joseph Teran

We present a Material Point Method for visual simulation of baking breads, cookies, pancakes and similar materials that consist of dough or batter (mixtures of water flour, eggs, fat, sugar and leavening agents). We develop a novel thermomechanical model using mixture theory to resolve interactions between individual water, gas and dough species. Heat transfer with thermal expansion is used to model thermal variations in material properties. Water- based mass transfer is resolved through the porous mixture, gas represents carbon dioxide produced by leavening agents in the baking process and dough is modeled as a viscoelastoplastic solid to represent its varied and complex rheological properties. Water content in the mixture reduces during the baking process according to Fick’s Law which contributes to drying and cracking of crust at the material boundary. Carbon dioxide gas produced by leavening agents during baking creates internal pressure that causes rising. The viscoelastoplastic model for the dough is temperature dependent and is used to model melting and solidification. We discretize the governing equations using a novel Material Point Method designed to track the solid phase of the mixture.

A Thermomechanical Material Point Method for Baking and Cooking

Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Ragan-Kelley, Fredo Durand

3D visual computing data are often spatially sparse. To exploit such sparsity, people have developed hierarchical sparse data structures, such as multi-level sparse voxel grids, particles, and 3D hash tables. However, developing and using these high-performance sparse data structures is challenging, due to their intrinsic complexity and overhead. We propose Taichi, a new data-oriented programming language for efficiently authoring, accessing, and maintaining such data structures. The language offers a high-level, data structure-agnostic interface for writing computation code. The user independently specifies the data structure. We provide several elementary components with different sparsity properties that can be arbitrarily composed to create a wide range of multi-level sparse data structures. This decoupling of data structures from computation makes it easy to experiment with different data structures without changing computation code, and allows users to write computation as if they are working with a dense array. Our compiler then uses the semantics of the data structure and index analysis to automatically optimize for locality, remove redundant operations for coherent accesses, maintain sparsity and memory allocations, and generate efficient parallel and vectorized instructions for CPUs and GPUs. Our approach yields competitive performance on common computational kernels such as stencil applications, neighbor lookups, and particle scattering. We demonstrate our language by implementing simulation, rendering, and vision tasks including a material point method simulation, finite element analysis, a multigrid Poisson solver for pressure projection, volumetric path tracing, and 3D convolution on sparse grids. Our computation-data structure decoupling allows us to quickly experiment with different data arrangements, and to develop high-performance data structures tailored for specific computational tasks. With 1/10th as many lines of code, we achieve 4.55× higher performance on average, compared to hand-optimized reference implementations.

Taichi: A Language for High-Performance Computation on Spatially Sparse Data Structures

Tuanfeng Y. Wang, Tianjia Shao, Kai Fu, Niloy Mitra

Authoring dynamic garment shapes for character animation on body motion is one of the fundamental steps in the CG industry. Established workflows are either time and labor consuming (i.e., manual editing on dense frames with controllers), or lack keyframe-level control (i.e., physically-based simulation). Not surprisingly, garment authoring remains a bottleneck in many production pipelines. Instead, we present a deep-learning-based approach for semi-automatic authoring of garment animation, wherein the user provides the desired garment shape in a selection of keyframes, while our system infers a latent representation for its motion-independent intrinsic parameters (e.g., gravity, cloth materials, etc.). Given new character motions, the latent representation allows to automatically generate a plausible garment animation at interactive rates. Having factored out character motion, the learned intrinsic garment space enables smooth transition between keyframes on a new motion sequence. Technically, we learn an intrinsic garment space with an motion-driven autoencoder network, where the encoder maps the garment shapes to the intrinsic space under the condition of body motions, while the decoder acts as a differentiable simulator to generate garment shapes according to changes in character body motion and intrinsic parameters. We evaluate our approach qualitatively and quantitatively on common garment types. Experiments demonstrate our system can significantly improve current garment authoring workflows via an interactive user interface. Compared with the standard CG pipeline, our system significantly reduces the ratio of required keyframes from 20% to 1 − 2%.

Learning an Intrinsic Garment Space for Interactive Authoring of Garment Animation

David Hahn, Pol Banzet, James M. Bern, Stelian Coros

This paper presents a method for optimizing visco-elastic material parameters of a finite element simulation to best approximate the dynamic motion of real-world soft objects. We compute the gradient with respect to the material parameters of a least-squares error objective function using either direct sensitivity analysis or an adjoint state method. We then optimize the material parameters such that the simulated motion matches real-world observations as closely as possible. In this way, we can directly build a useful simulation model that captures the visco-elastic behaviour of the specimen of interest. We demonstrate the effectiveness of our method on various examples such as numerical coarsening, custom-designed objective functions,and of course real-world flexible elastic objects made of foam or 3D printed lattice structures, including a demo application in soft robotics

Real2Sim: Visco-elastic parameter estimation from dynamic motion

Juyong Zhang, Yue Peng, Wenqing Ouyang, Bailin Deng

The alternating direction method of multipliers (ADMM) is a popular approach for solving optimization problems that are potentially non-smooth and with hard constraints. It has been applied to various computer graphics applications, including physical simulation, geometry processing, and image processing. However, ADMM can take a long time to converge to a solution of high accuracy. Moreover, many computer graphics tasks involve non-convex optimization, and there is often no convergence guarantee for ADMM on such problems since it was originally designed for convex optimization. In this paper, we propose a method to speed up ADMM using Anderson acceleration, an established technique for accelerating fixed-point iterations. We show that in the general case, ADMM is a fixed-point iteration of the second primal variable and the dual variable, and Anderson acceleration can be directly applied. Additionally, when the problem has a separable target function and satisfies certain conditions, ADMM becomes a fixed-point iteration of only one variable, which further reduces the computational overhead of Anderson acceleration. Moreover, we analyze a particular non-convex problem structure that is common in computer graphics, and prove the convergence of ADMM on such problems under mild assumptions. We apply our acceleration technique on a variety of optimization problems in computer graphics, with notable improvement on their convergence speed.

Accelerating ADMM for Simulation and Optimization

Jiong Chen, Max Budninskiy, Houman Owhadi, Hujun Bao, Jin Huang, Mathieu Desbrun

In this paper, we introduce a hierarchical construction of material-adapted refinable basis functions and associated wavelets to offer efficient coarse-graining of linear elastic objects. While spectral methods rely on global basis functions to restrict the number of degrees of freedom, our basis functions are locally supported; yet, unlike typical polynomial basis functions, they are adapted to the material inhomogeneity of the elastic object to better capture its physical properties and behavior. In particular, they share spectral approximation properties with eigenfunctions, offering a good compromise between computational complexity and accuracy. Their construction involves only linear algebra and follows a fine-to-coarse approach, leading to a block-diagonalization of the stiffness matrix where each block corresponds to an intermediate scale space of the elastic object. Once this hierarchy has been precomputed, we can simulate an object at runtime on very coarse resolution grids and still capture the correct physical behavior, with orders of magnitude speedup compared to a fine simulation. We show on a variety of heterogeneous materials that our approach outperforms all previous coarse-graining methods for elasticity.

Material-adapted Refinable Basis Functions for Elasticity Simulation

Sehee Min, Jungdam Won, Seunghwan Lee, Jungnam Park, Jehee Lee

We present a novel and general framework for the design and control of underwater soft-bodied animals. The whole body of an animal consisting of soft tissues is modeled by tetrahedral and triangular FEM meshes. The contraction of muscles embedded in the soft tissues actuates the body and limbs to move. We present a novel muscle excitation model that mimics the anatomy of muscular hydrostats and their muscle excitation patterns. Our deep reinforcement learning algorithm equipped with the muscle excitation model successfully learned the control policy of soft-bodied animals, which can be physically simulated in real-time, controlled interactively, and resilient to external perturbations. We demonstrate the effectiveness of our approach with various simulated animals including octopuses, lampreys, starfishes, stingrays and cuttlefishes. They learn diverse behaviors such as swimming, grasping, and escaping from a bottle. We also implemented a simple user interface system that allows the user to easily create their creatures.

SoftCon: Simulation and Control of Soft-Bodied Animals with Biomimetic Actuators