Category: Deformables

Continuous Penalty Forces

Min Tang, Dinesh Manocha, Miguel Otaduy, Ruofeng Tong

We present a simple algorithm to compute continuous penalty forces to determine collision response between rigid and deformable models bounded by triangle meshes. Our algorithm provides a well-behaved solution in contrast to the traditional stability and robustness problems of penalty methods, induced by force discontinuities. We trace contact features along their deforming trajectories and accumulate penalty forces along the penetration time intervals between the overlapping feature pairs. Moreover, we present a closed-form expression to compute the continuous and smooth collision response. Our method has very small additional overhead compared to previous penalty methods, while significantly improves the stability and robustness. We highlight its benefits on several benchmarks.

Continuous Penalty Forces

Updated Sparse Cholesky Factors for Corotational Elastodynamics

Florian Hecht, Yeon Jin Lee, Jonathan Shewchuk, James O’Brien

We present warp-canceling corotation, a nonlinear finite element formulation for elastodynamic simulation that achieves fast performance by making only partial or delayed changes to the simulation’s linearized system matrices. Coupled with an algorithm for incremental updates to a sparse Cholesky factorization, the method realizes the stability and scalability of a sparse direct method without the need for expensive refactorization at each time step. This finite element formulation combines the widely used corotational method with stiffness warping so that changes in the per-element rotations are initially approximated by inexpensive per-node rotations. When the errors of this approximation grow too large, the per-element rotations are selectively corrected by updating parts of the matrix chosen according to locally measured errors. These changes to the system matrix are propagated to its Cholesky factor by incremental updates that are much faster than refactoring the matrix from scratch. A nested dissection ordering of the system matrix gives rise to a hierarchical factorization in which changes to the system matrix cause limited, well-structured changes to the Cholesky factor. We show examples of simulations that demonstrate that the proposed formulation produces results that are visually comparable to those produced by a standard corotational formulation. Because our method requires computing only partial updates of the Cholesky factor, it is substantially faster than full refactorization and outperforms widely used iterative methods such as preconditioned conjugate gradients. Our method supports a controlled trade-off between accuracy and speed, and unlike most iterative methods its performance does not slow for stiffer materials but rather it actually improves.

Updated Sparse Cholesky Factors for Corotational Elastodynamics

Adding Physics to Characters Using Oriented Particles

Matthias Muller, Nuttapong Chentanez

We present a method to enhance the realism of animated characters by adding physically based secondary motion to deformable parts such as cloth, skin or hair. To this end, we extend the oriented particles approach to incorporate animation information. In addition, we introduce techniques to increase the stability of the original method in order to make it suitable for the fast and sudden motions that typically occur in computer games. We also propose a method for the semi-automatic creation of particle representations from arbitrary visual meshes. This way, our technique allows us to simulate complex geometry such as hair, thick cloth with ornaments and multi-layered clothing, all interacting with each other and the animated character.

Adding Physics to Characters Using Oriented Particles

VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes

Min Tang, Dinesh Manocha, Sung-Eui Yoon, Peng Du, Jae-Pil Heo, Ruofeng Tong

We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. Moreover, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.

VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes

Asynchronous Integration with Phantom Meshes

David Harmon, Qingnan Zhou, Denis Zorin

Asynchronous variational integration of layered contact models provides a framework for robust collision handling, correct physical behavior, and guaranteed eventual resolution of even the most difficult contact problems. Yet, even for low-contact scenarios, this approach is significantly slower compared to its less robust alternatives — often due to handling of stiff elastic forces in an explicit framework. We propose a method that retains the guarantees, but allows for variational implicit integration of some of the forces, while maintaining asynchronous integration needed for contact handling. Our method uses phantom meshes for calculations with stiff forces, which are then coupled to the original mesh through constraints. We use the augmented discrete Lagrangian of the constrained system to derive a variational integrator with the desired conservation properties.

Asynchronous Integration with Phantom Meshes

Eulerian Solid Simulation with Contact

David I. W. Levin, Joshua Litven, Garrett L. Jones, Shinjiro Sueda, Dinesh K. Pai

Simulating viscoelastic solids undergoing large, nonlinear deformations in close contact is challenging. In addition to inter-object contact, methods relying on Lagrangian discretizations must handle degenerate cases by explicitly remeshing or resampling the object. Eulerian methods, which discretize space itself, provide an interesting alternative due to the fixed nature of the discretization. In this paper we present a new Eulerian method for viscoelastic materials that features a collision detection and resolution scheme which does not require explicit surface tracking to achieve accurate collision response. Time-stepping with contact is performed by the efficient solution of large sparse quadratic programs; this avoids constraint sticking and other difficulties. Simulation and collision processing can share the same uniform grid, making the algorithm easy to parallelize. We demonstrate an implementation of all the steps of the algorithm on the GPU. The method is effective for simulation of complicated contact scenarios involving multiple highly deformable objects, and can directly simulate volumetric models obtained from medical imaging techniques such as CT and MRI.

Eulerian Solid Simulation with Contact

Physics-inspired Upsampling for Cloth Simulation in Games

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

We propose a method for learning linear upsampling operators for physically-based cloth simulation, allowing us to enrich coarse meshes with mid-scale details in minimal time and memory budgets, as required in computer games. In contrast to classical subdivision schemes, our operators adapt to a specific context (e.g. a flag flapping in the wind or a skirt worn by a character), which allows them to achieve higher detail. Our method starts by pre-computing a pair of coarse and fine training simulations aligned with tracking constraints using harmonic test functions. Next, we train the upsampling operators with a new regularization method that enables us to learn mid-scale details without overfitting. We demonstrate generalizability to unseen conditions such as different wind velocities or novel character motions. Finally, we discuss how to re-introduce high frequency details not explainable by the coarse mesh alone using oscillatory modes.

Physics-inspired Upsampling for Cloth Simulation in Games

Element-Wise Mixed Implicit-Explicit Integration for Stable Dynamic Simulation of Deformable Objects

Basil Fierz, Jonas Spillman, Matthias Harders

In order to evolve a deformable object in time, the underlying equations of motion have to be numerically integrated. This is commonly done by employing either an explicit or an implicit integration scheme. While explicit methods are only stable for small time steps, implicit methods are unconditionally stable. In this paper, we present a novel methodology to combine explicit and implicit linear integration approaches, based on element-wise stability considerations. First, we detect the ill-shaped simulation elements which hinder the stable explicit integration of the element nodes as a pre-computation step. These nodes are then simulated implicitly, while the remaining parts of the mesh are explicitly integrated. As a consequence, larger integration time steps than in purely explicit methods are possible, while the computation time per step is smaller than in purely implicit integration. During modifications such as cutting or fracturing, only newly created or modified elements need to be reevaluated, thus making the technique usable in real-time simulations. In addition, our method reduces problems due to numerical dissipation.

Element-Wise Mixed Implicit-Explicit Integration for Stable Dynamic Simulation of Deformable Objects

SPH Granular Flow with Friction and Cohesion

Ivan Alduan, Miguel Otaduy

Combining mechanical properties of solids and fluids, granular materials pose important challenges for the design of algorithms for realistic animation. In this paper, we present a simulation algorithm based on smoothed particle hydrodynamics (SPH) that succeeds in modeling important features of the behavior of granular materials. These features are unilateral incompressibility, friction and cohesion. We extend an existing unilateral incompressibility formulation to be added at almost no effort to an existing SPH-based algorithm for fluids. The main advantages of this extension are the ease of implementation, the lack of grid artifacts, and the simple two-way coupling with other objects. Our friction and cohesion models can also be incorporated in a seamless manner in the overall SPH simulation algorithm.

SPH Granular Flow with Friction and Cohesion

Physics-based Character Skinning using Multi-Domain Subspace Deformations

Theodore Kim, Doug L. James

We propose a domain-decomposition method to simulate articulated deformable characters entirely within a subspace framework. The method supports quasistatic and dynamic deformations, nonlinear kinematics and materials, and can achieve interactive time-stepping rates. To avoid artificial rigidity, or “locking,” associated with coupling low-rank domain models together with hard constraints, we employ penalty-based coupling forces. The multi-domain subspace integrator can simulate deformations efficiently, and exploits efficient subspace-only evaluation of constraint forces between rotated domains using the so-called Fast Sandwich Transform (FST). Examples are presented for articulated characters with quasistatic and dynamic deformations, and interactive performance with hundreds of fully coupled modes. Using our method, we have observed speedups of between three and four orders of magnitude over full-rank, unreduced simulations.

Physics-based Character Skinning using Multi-Domain Subspace Deformations