Category: Deformables

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

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

Rahul Narain, Matthew Overby, George E. Brown

We apply the alternating direction method of multipliers (ADMM) optimization algorithm to implicit time integration of elastic bodies, and show that the resulting method closely relates to the recently proposed projective dynamics algorithm. However, as ADMM is a general-purpose optimization algorithm applicable to a broad range of objective functions, it permits the use of nonlinear constitutive models and hard constraints while retaining the speed, parallelizability, and robustness of projective dynamics. We demonstrate these benefits on several examples that include cloth, collisions, and volumetric deformable bodies with nonlinear elasticity.

ADMM ⊇ Projective Dynamics: Fast Simulation of General Constitutive Models

Hongyi Xu, Jernej Barbic

We enrich character animations with secondary soft-tissue Finite Element Method (FEM) dynamics computed under arbitrary rigged or skeletal motion. Our method optionally incorporates pose-space deformation (PSD). It runs at milliseconds per frame for complex characters, and fits directly into standard character animation pipelines. Our simulation method does not require any skin data capture; hence, it can be applied to humans, animals, and arbitrary (real-world or fictional) characters. In standard model reduction of three-dimensional nonlinear solid elastic models, one builds a reduced model around a single pose, typically the rest configuration. We demonstrate how to perform multi-model reduction of Finite Element Method (FEM) nonlinear elasticity, where separate reduced models are precomputed around a representative set of object poses, and then combined at runtime into a single fast dynamic system, using subspace interpolation. While time-varying reduction has been demonstrated before for offline applications, our method is fast and suitable for hard real-time applications in games and virtual reality. Our method supports self-contact, which we achieve by computing linear modes and derivatives under contact constraints.

Pose-Space Subspace Dynamics

Yunfei Bai, Danny M. Kaufman, C.Karen Liu, Jovan Popović

Animation artists enjoy the benefits of simulation but do not want to be held back by its constraints. Artist-directed dynamics seeks to resolve this need with a unified method that combines simulation with classical keyframing techniques. The combination of these approaches improves upon both extremes: simulation becomes more customizable and keyframing becomes more automatic. Examining our system in the context of the twelve fundamental animation principles reveals that it stands out for its treatment of exaggeration and appeal. Our system accommodates abrupt jumps, large plastic deformations, and makes it easy to reuse carefully crafted animations.

Artist-Directed Dynamics for 2D Animation