Physics-Based Animation

Matthias Müller, Nuttapong Chentanez, Miles Macklin

In computer graphics, simulated objects typically have two or three different representations, a visual mesh, a simulation mesh and a collection of convex shapes for collision handling. Using multiple representations requires skilled authoring and complicates object handing at run time. It can also produce visual artifacts such as a mismatch of collision behavior and visual appearance. The reason for using multiple representation has been performance restrictions in real time environments. However, for virtual worlds, we believe that the ultimate goal must be WYSIWYS – what you see is what you simulate, what you can manipulate, what you can touch. In this paper we present a new method that uses the same representation for simulation and collision handling and an almost identical visualization mesh. This representation is very close and directly derived from a visual input mesh which does not have to be prepared for simulation but can be non-manifold, non-conforming and self-intersecting.

Simulating Visual Geometry

Miles Macklin, Matthias Muller, Nuttapong Chentanez

We address the long-standing problem of iteration count and time step dependent constraint stiffness in position-based dynamics (PBD). We introduce a simple extension to PBD that allows it to accurately and efficiently simulate arbitrary elastic and dissipative energy potentials in an implicit manner. In addition, our method provides constraint force estimates, making it applicable to a wider range of applications, such those requiring haptic user-feedback. We compare our algorithm to more expensive non-linear solvers and find it produces visually similar results while maintaining the simplicity and robustness of the PBD method.

XPBD: Position-Based Simulation of Compliant Constrained Dynamics

Matthias Muller, Jan Bender, Nuttapong Chentanez, Miles Macklin

We present a novel algorithm to extract the rotational part of an arbitrary 3×3 matrix. This problem lies at the core of two popular simulation methods in computer graphics, the co-rotational Finite Element Method and Shape Matching techniques. In contrast to the traditional method based on polar decomposition, degenerate configurations and inversions are handled robustly and do not have to be treated in a special way. In addition, our method can be implemented with only a few lines of code without branches which makes it particularly well suited for GPU-based applications. We demonstrate the robustness, coherence and efficiency of our method by comparing it to stabilized polar decomposition in several simulation scenarios.

A Robust Method to Extract the Rotational Part of Deformations

Nathan Mitchell, Michael Doescher, Eftychios Sifakis

We introduce a new numerical approach for the solution of grid-based discretizations of nonlinear elastic models. Our method targets the linearized system of equations within each iteration of the Newton method, and combines elements of a direct factorization scheme with an iterative Conjugate Gradient method. The goal of our hybrid scheme is to inherit as many of the advantages of its constituent approaches, while curtailing several of their respective drawbacks. In particular, our algorithm converges in far fewer iterations than Conjugate Gradients, especially for systems with less-than-ideal conditioning. On the other hand, our approach largely avoids the storage footprint and memory-bound nature of direct methods, such as sparse Cholesky factorization, while offering very direct opportunities for both SIMD and thread-based parallelism. Conceptually, our method aggregates a rectangular neighborhood of grid cells (typically a 16x8x8 subgrid) into a composite element that we refer to as a “macroblock”. Similar to conventional tetrahedral or hexahedral elements, macroblocks receive nodal inputs (e.g., displacements) and compute nodal outputs (e.g., forces). However, this input/output interface now only includes nodes on the boundary of the 16x8x8 macroblock; interior nodes are always solved exactly, by means of a direct, highly optimized solver. Models built from macroblocks are solved using Conjugate Gradients, which is accelerated due to the reduced number of degrees of freedom and improved robustness against poor conditioning thanks to the direct solver within each macroblock. We explain how we attain these benefits with just a small increase of the per-iteration cost over the simplest traditional solvers.

A Macroblock Optimization for Grid-Based Nonlinear Elasticity

Rene Winchenbach, Hendrik Hochstetter, Andreas Kolb

In this paper we present a new approach to create neighbor lists with strict memory bounds for incompressible Smoothed Particle Hydrodynamics (SPH) simulations. Our proposed approach is based on a novel efficient predictive-corrective algorithm that locally adjusts particle support radii in order to yield neighborhoods of a user-defined maximum size. Due to the improved estimation of the initial support radius, our algorithm is able to efficiently calculate neighborhoods in a single iteration in almost any situation. We compare our neighbor list algorithm to previous approaches and show that our proposed approach can handle larger particle numbers on a single GPU due to its strict guarantees and is able to simulate more particles in real time due to its benefits in regard to performance. Additionally we demonstrate the versatility and stability of our approach in several different scenarios, for example multi-scale simulations and with different kernel functions.

Constrained Neighbor Lists for SPH-based Fluid Simulations

Florian Canezin, Gael Guennebaud, Loïc Barthe

Particle based simulations are widely used in computer graphics. In this field, several recent results have improved the simulation itself or improved the tension of the final fluid surface. In current particle based implementations, the particle neighborhood is computed by considering the Euclidean distance between fluid particles only. Thus particles from different fluid components interact, which generates both local incorrect behavior in the simulation and blending artifacts in the reconstructed fluid surface. Our method introduces a better neighborhood computation for both the physical simulation and surface reconstruction steps. We track and store the local fluid topology around each particle using a graph structure. In this graph, only particles within the same local fluid component are neighbors and other disconnected fluid particles are inserted only if they come into contact. The graph connectivity also takes into account the asymmetric behavior of particles when they merge and split, and the fluid surface is reconstructed accordingly, thus avoiding their blending at distance before a merge. In the simulation, this neighborhood information is exploited for better controlling the fluid density and the force interactions at the vicinity of its boundaries. For instance, it prevents the introduction of collision events when two distinct fluid components are crossing without contact, and it avoids fluid interactions through thin waterproof walls. This leads to an overall more consistent fluid simulation and reconstruction.

Topology-Aware Neighborhoods for Point-Based Simulation and Reconstruction

Aaron Demby Jones, Pradeep Sen, Theodore Kim

Subspace fluid simulations, also known as reduced-order simulations, can be extremely fast, but also require basis matrices that consume an enormous amount of memory. Motivated by the extreme sparsity of Laplacian eigenfunctions in the frequency domain, we design a frequency-space codec that is capable of compressing basis matrices by up to an order of magnitude. However, if computed naively, decompression can be highly inefficient and dominate the running time, effectively negating the advantage of the subspace approach. We show how to significantly accelerate the decompressor by performing the key matrix-vector product in the sparse frequency domain. Subsequently, our codec only adds a factor of three or four to the overall runtime. The compression preserves the overall quality of the simulation, which we show in a variety of examples.

Compressing Fluid Subspaces

Danyong Zhao, Yijing Li, Jernej Barbic

In standard deformable object simulation in computer animation, all the mesh elements or vertices are timestepped synchronously, i.e., under the same timestep. Previous asynchronous methods have been largely limited to explicit integration. We demonstrate how to perform spatially-varying timesteps for the widely popular implicit backward Euler integrator. Spatially-varying timesteps are useful when the object exhibits spatially-varying material properties such as Young’s modulus or mass density. In synchronous simulation, a region with a high stiffness (or low mass density) will force a small timestep for the entire mesh, at a great computational cost, or else, the motion in the stiff (or low mass density) region will be artificially damped and inaccurate. Our method can assign smaller timesteps to stiffer (or lighter) regions, which makes it possible to properly resolve (sample) the high-frequency deformable dynamics arising from the stiff (or light) materials, resulting in greater accuracy and less artificial damping. Because soft (or heavy) regions can continue using a large timestep, our method provides a significantly higher accuracy under a fixed computational budget.

Asynchronous Implicit Backward Euler Integration

Nuttapong Chentanez, Matthias Müller, Miles Macklin

Shape matching is a popular method for simulating deformable objects in real time as it is fast and stable at large time steps. Although shape matching can simulate large elastic deformation and ductile fracturing, until now, they are limited to scenarios with relatively small plastic deformation. In this work, we present a method for simulating deformable solids undergoing large plastic deformation and topological changes using shape matching within the position based dynamics (PBD) framework. This expands the versatility of PBD which was previously shown to be able to simulate rigid bodies, liquids, gases, cloth, and deformable solids with moderate plastic deformation. Our novel contributions include local particle re-sampling, cluster re-sampling and skinning of an explicitly tracked surface mesh.

Real-time Simulation of Large Elasto-Plastic Deformation with Shape Matching

Sheng Yang Xiaowei He Huamin Wang Sheng Li Guoping Wang Enhua Wu Kun Zhou

Capillary waves are difficult to simulate due to their fast traveling speed and high frequency. In this paper, we propose to approximate capillary wave effects by surface compression waves under the SPH framework. To achieve this goal, we present a method to convert surface tension energy changes measured from SPH simulation into high-frequency density variations. Based on the compression wave propagation model, we present an approximate technique to simulate capillary wave propagation in a high-frequency particle density field. To address noise issues in wave simulation, we develop a simple way to apply the zero pressure condition on free surfaces in projection-based incompressible SPH. Our experiment shows that the developed algorithm can produce realistic capillary wave effects on both thin liquid features and large liquid bodies. Its computational overhead is also small.

Enriching SPH Simulation by Approximate Capillary Waves