Physics-Based Animation

Yun Teng, Miguel Otaduy, Theodore Kim

We present an efficient new subspace method for simulating the self-contact of articulated deformable bodies, such as characters. Self-contact is highly structured in this setting, as the limited space of possible articulations produces a predictable set of coherent collisions. Subspace methods can leverage this coherence, and have been used in the past to accelerate the collision detection stage of contact simulation. We show that these methods can be used to accelerate the entire contact computation, and allow self-contact to be resolved without looking at all of the contact points. Our analysis of the problem yields a broader insight into the types of nonlinearities that subspace methods can efficiently approximate, and leads us to design a pose-space cubature scheme. Our algorithm accelerates self-contact by up to an order of magnitude over other subspace simulations, and accelerates the overall simulation by two orders of magnitude over full-rank simulations. We demonstrate the simulation of high resolution (100K – 400K elements) meshes
in self-contact at interactive rates (5.8 – 50 FPS).

Simulating Articulated Subspace Self-Contact

Essex Edwards, Robert Bridson

We present a new adaptive fluid simulation method that captures a high resolution surface with precise dynamics, without an inefficient fine discretization of the entire fluid volume. Prior adap- tive methods using octrees or unstructured meshes carry large over- heads and implementation complexity. We instead stick with coarse regular Cartesian grids, using detailed cut cells at boundaries, and discretize the dynamics with a p-adaptive Discontinuous Galerkin (DG) method. This retains much of the data structure simplicity of regular grids, more efficiently captures smooth parts of the flow, and offers the flexibility to easily increase resolving power where needed without geometric refinement.

Detailed Water with Coarse Grids: Combining Surface Meshes and  Adaptive Discontinuous Galerkin

Christian Schulz, Christoph von Tycowicz, Hans-Peter Seidel, Klaus Hildebrandt

We propose a scheme for animating deformable objects based on spacetime optimization. The main feature is that it robustly and quickly (within a few seconds) generates interesting motion from a sparse set of spacetime constraints. Providing only partial (as opposed to full) keyframes for positions and velocities is sufficient. The computed motion satisfies the constraints and the remaining degrees of freedom are determined by physical principles using elasticity and the spacetime constraints paradigm. Our modeling of the spacetime optimization problem combines dimensional reduction, modal coordinates, wiggly splines, and rotation strain warping. Controlling the warped motion requires the derivative of the warp map. We derive a representation of the derivative that can be efficiently and robustly evaluated. Our solver is based on a theorem that characterizes the solutions of the optimization problem and allows us to restrict the optimization to very low-dimensional search spaces. This treatment of the optimization problem avoids a time discretization and the resulting method can robustly deal with sparse input and wiggly motion.

Animating Deformable Objects using Sparse Spacetime Constraints

Hongyi Xu, Yili Zhao, and Jernej Barbic

The penalty method is a simple and popular approach to resolving contact in computer graphics and robotics. Penalty-based contact, however, suffers from stability problems due to the highly variable and unpredictable net stiffness, and this is particularly pronounced in simulations with time-varying distributed geometrically complex contact. We employ semi-implicit integration, exact analytical contact gradients, symbolic Gaussian elimination and a SVD solver to simulate stable penalty-based frictional contact with large, time-varying contact
areas, involving many rigid objects and articulated rigid objects in complex conforming contact and self-contact. We also derive implicit proportional-derivative control forces for real-time control of articulated structures with loops. We present challenging contact scenarios such as screwing a hexbolt into a hole, bowls stacked in perfectly conforming configurations, and manipulating many objects using actively controlled articulated mechanisms in real time.

Implicit Multibody Penalty-based Distributed Contact

Papers:

• Physically-based Human Neck Simulation
• Physically based character skinning
• Tridiagonal Matrix Factorization for Inextensible Hair Strand Simulation
• Parallel Collision Detection in Constant Time
• Connective Tissues Simulation on GPU
• Multi-level Cloth Simulation using GPU Surface Sampling
• Exploring the use of Adaptive Restrained Particles for Graphics Simulations

Kesen’s full list is here.

Papers:

• Efficient Enforcement of Hard Articulation Constraints in the Presence of Closed Loops and Contacts
• IISPH-FLIP for Incompressible Fluids
• Efficient GPU Data Structures and Methods to Solve Sparse Linear Systems in Dynamics Applications

STAR:

• Physically-based Simulation of Cuts in Deformable Bodies: A Survey
• SPH Fluids in Computer Graphics

Robin Tomcin, Dominik Sibbing, Leif Kobbelt

In rigid body simulation, one must distinguish between contacts (so-called unilateral constraints) and articulations (bilateral constraints). For contacts and friction, iterative solution methods have proven most useful for interactive applications, often in combination with Shock-Propagation in cases with strong interactions between contacts (such as stacks), prioritizing performance and plausibility over accuracy. For articulation constraints, direct solution methods are preferred, because one can rely on a factorization with linear time complexity for tree-like systems, even in ill-conditioned cases caused by large mass-ratios or high complexity. Despite recent advances, combining the advantages of direct and iterative solution methods wrt. performance has proven difficult and the intricacy of articulations in interactive applications is often limited by the convergence speed of the iterative solution method in the presence of closed kinematic loops (i.e. auxiliary constraints) and contacts. We identify common performance bottlenecks in the dynamic simulation of unilateral and bilateral constraints and are able to present a simulation method, that scales well in the number of constraints even in ill-conditioned cases with frictional contacts, collisions and closed loops in the kinematic graph. For cases where many joints are connected to a single body, we propose a technique to increase the sparsity of the positive definite linear system. A solution to these bottlenecks is presented in this paper to make the simulation of a wider range of mechanisms possible in real-time without extensive parameter tuning.

Efficient Enforcement of Hard Articulation Constraints in the Presence of Closed Loops and Contacts

Markus Ihmsen, Jens Orthmann, Barbara Solenthaler, Andreas Kolb, and Matthias Teschner

Smoothed Particle Hydrodynamics (SPH) has been established as one of the major concepts for fluid animation in computer graphics. While SPH initially gained popularity for interactive free-surface scenarios, it has emerged to be a fully fledged technique for state-of-the-art fluid animation with versatile effects. Nowadays, complex scenes with millions of sampling points, one- and two-way coupled rigid and elastic solids, multiple phases and additional features such as foam or air bubbles can be computed at reasonable expense. This state-of-the-art report summarizes SPH research within the graphics community.

SPH Fluids in Computer Graphics

B. Jones, S. Ward, A. Jallepalli, J. Perenia, and A. W. Bargteil

We present a straightforward, easy-to-implement, point-based approach for animating elastoplastic materials. The core idea of our approach is the introduction of embedded space, the least-squares best fit of the material’s rest state into three dimensions. Nearest neighbor queries in the embedded space efficiently update particle neighborhoods to account for plastic flow. These queries are simpler and more efficient than remeshing strategies employed in mesh-based finite element methods. We also introduce a new estimate for the volume of a particle, allowing particle masses to vary spatially and temporally with fixed density. Our approach can handle simultaneous extreme elastic and plastic deformations. We demonstrate our approach on a variety of examples that exhibit a wide range of material behaviors.

Deformation Embedding for Point-Based Elastoplastic Simulation

Dan Gerszewski, Ladislav Kavan, Peter-Pike Sloan, Adam W. Bargteil

We present several enhancements to model-reduced fluid simulation that allow improved simulation bases and two-way solid-fluid coupling. Specifically, we present a basis enrichment scheme that allows us to combine data driven or artistically derived bases with more general analytic bases derived from Laplacian Eigenfunctions. We handle two-way solid-fluid coupling in a time-splitting fashion—we alternately timestep the fluid and rigid body simulators, while taking into account the effects of the fluid on the rigid bodies and vice versa. We employ the vortex panel method to handle solid-fluid coupling and use dynamic pressure to compute the effect of the fluid on rigid bodies.

Enhancements to Model-Reduced Fluid Simulation