Category: Deformables

Fast and Exact Continuous Collision Detection with Bernstein Sign Classification

Min Tang, Ruofeng Tong, Zhendong Wang, Dinesh Manocha

We present fast algorithms to perform accurate CCD queries between triangulated models. Our formulation uses properties of the Bernstein basis and Bezier curves and reduces the problem to evaluating signs of polynomials. We present a geometrically exact CCD algorithm based on the exact geometric computation paradigm to perform reliable Boolean collision queries. This algorithm is more than an order of magnitude faster than prior exact algorithms. We evaluate its performance for cloth and FEM simulations on CPUs and GPUs, and highlight the benefits.

Fast and Exact Continuous Collision Detection with Bernstein Sign Classification

Subspace Clothing Simulation Using Adaptive Bases

Fabian Hahn, Bernhard Thomaszewski, Stelian Coros, Robert W. Sumner, Forrester Cole, Mark Meyer, Tony DeRose, and Markus Gross

We present a new approach to clothing simulation using low-dimensional linear subspaces with temporally adaptive bases. Our method exploits full-space simulation training data in order to construct a pool of low-dimensional bases distributed across pose space. For this purpose, we interpret the simulation data as offsets from a kinematic deformation model that captures the global shape of clothing due to body pose. During subspace simulation, we select low-dimensional sets of basis vectors according to the current pose of the character and the state of its clothing. Thanks to this adaptive basis selection scheme, our method is able to reproduce diverse and detailed folding patterns with only a few basis vectors. Our experiments demonstrate the feasibility of subspace clothing simulation and indicate its potential in terms of quality and computational efficiency.

Subspace Clothing Simulation Using Adaptive Bases

An Adaptive Virtual Node Algorithm with Robust Mesh Cutting

Yuting Wang, Chenfanfu Jiang, Craig Schroeder, Joseph Teran

We present a novel virtual node algorithm (VNA) for changing tetrahedron mesh topology to represent arbitrary cutting triangulated surfaces. Our approach addresses a number of shortcomings in the original VNA of [MBF04]. First, we generalize the VNA so that cuts can pass through tetrahedron mesh vertices and lie on mesh edges and faces. The original algorithm did not make sense for these cases and required often ambiguous perturbation of the cutting surface to avoid them. Second, we develop an adaptive approach to the definition of embedded material used for element duplication. The original algorithm could only handle a limited number of configurations which restricted cut surfaces to have curvature at the scale of the tetrahedron elements. Our adaptive approach allows for cut surfaces with curvatures independent of the embedding tetrahedron mesh resolution. Finally, we present a novel, provably-robust floating point mesh intersection routine that accurately registers triangulated surface cuts against the background tetrahedron mesh without the need for exact arithmetic.

An Adaptive Virtual Node Algorithm with Robust Mesh Cutting

Augmented MPM for phase-change and varied materials

Alexey Stomakhin, Craig Schroeder, Chenfanfu Jiang, Lawrence Chai, Joseph Teran, Andrew Selle

In this paper, we introduce a novel material point method for heat transport, melting and solidifying materials. This brings a wider range of material behaviors into reach of the already versatile material point method. This is in contrast to best-of-breed fluid, solid or rigid body solvers that are difficult to adapt to a wide range of materials. Extending the material point method requires several contributions. We introduce a dilational/deviatoric splitting of the constitutive model and show that an implicit treatment of the Eulerian evolution of the dilational part can be used to simulate arbitrarily incompressible materials. Furthermore, we show that this treatment reduces to a parabolic equation for moderate compressibility and an elliptic, Chorin-style projection at the incompressible limit. Since projections are naturally done on marker and cell (MAC) grids, we devise a staggered grid MPM method. Lastly, to generate varying material parameters, we adapt a heat-equation solver to a material point framework.

Augmented MPM for phase-change and varied materials

Optimization Integrator for Large Time Steps

Theodore F. Gast, Craig Schroeder

Practical time steps in today’s state-of-the-art simulators typically rely on Newton’s method to solve large systems of nonlinear equations. In practice, this works well for small time steps but is unreliable at large time steps at or near the frame rate, particularly for difficult or stiff simulations. We show that recasting backward Euler as a minimization problem allows Newton’s method to be stabilized by standard optimization techniques with some novel improvements of our own. The resulting solver is capable of solving even the toughest simulations at the 24Hz frame rate and beyond. We show how simple collisions can be incorporated directly into the solver through constrained minimization without sacrificing efficiency. We also present novel penalty collision formulations for self collisions and collisions against scripted bodies designed for the unique demands of this solver.

Optimization Integrator for Large Time Steps

A Peridynamic Perspective on Spring-Mass Fracture

Joshua A. Levine, Adam W. Bargteil, Christopher Corsi, Jerry Tessendorf, Robert Geist 

The application of spring-mass systems to the animation of brittle fracture is revisited. The motivation arises from the recent popularity of peridynamics in the computational physics community. Peridynamic systems can be regarded as spring-mass systems with two specific properties. First, spring forces are based on a simple strain metric, thereby decoupling spring stiffness from spring length. Second, masses are connected using a distance-based criterion. The relatively large radius of influence typically leads to a few hundred springs for every mass point. Spring-mass systems with these properties are shown to be simple to implement, trivially parallelized, and well-suited to animating brittle fracture.

A Peridynamic Perspective on Spring-Mass Fracture

Efficient Denting and Bending of Rigid Bodies

Saket Patkar, Mridul Aanjaneya, Aric Bartle, Minjae Lee, Ronald Fedkiw

We present a novel method for the efficient denting and bending of rigid bodies without the need for expensive finite element simulations. Denting is achieved by deforming the triangulated surface of the target body based on a dent map computed on-the-fly from the projectile body using a Z-buffer algorithm with varying degrees of smoothing. Our method accounts for the angle of impact, is applicable to arbitrary shapes, readily scales to thousands of rigid bodies, is amenable to artist control, and also works well in combination with prescoring algorithms for fracture. Bending is addressed by augmenting a rigid body with an articulated skeleton which is used to drive skinning weights for the bending deformation. The articulated skeleton is simulated to include the effects of both elasticity and plasticity. Furthermore, we allow joints to be added dynamically so that bending can occur in a nonpredetermined way and/or as dictated by the artist. Conversely, we present an articulation condensation method that greatly simplifies large unneeded branches and chains on-the-fly for increased efficiency.

Efficient Denting and Bending of Rigid Bodies

Physics-Inspired Adaptive Fracture Refinement

Zhili Chen, Miaojun Yao, Renguo Feng, Huamin Wang

Physically based animation of detailed fracture effects is not only computationally expensive, but also difficult to implement due to numerical instability. In this paper, we propose a physics-inspired approach to enrich low-resolution fracture animation by realistic fracture details. Given a custom-designed material strength field, we adaptively refine a coarse fracture surface into a detailed one, based on a discrete gradient descent flow. Using the new fracture surface, we then generate a high-resolution fracture animation with details on both the fracture surface and the exterior surface. Our experiment shows that this approach is simple, fast, and friendly to user design and control. It can generate realistic fracture animations within a few seconds.

Physics-Inspired Adaptive Fracture Refinement

Defending Continuous Collision Detection against Errors

Huamin Wang

Numerical errors and rounding errors in continuous collision detection (CCD) can easily cause collision detection failures if they are not handled properly. A simple and effective approach is to use error tolerances, as shown in many existing CCD systems. Unfortunately, finding the optimal tolerance values is a difficult problem for users. Larger tolerance values will introduce false positive artifacts, while smaller tolerance values may cause collisions to be undetected. The biggest issue here is that we do not know whether or when CCD will fail, even though failures are extremely rare. In this paper, we demonstrate a set of simple modifications to make a basic CCD implementation failure-proof. Using error analysis, we prove the safety of this method and we formulate suggested tolerance values to reduce false positives. The resulting algorithms are safe, automatic, efficient, and easy to implement.

Defending Continuous Collision Detection against Errors

Active Volumetric Musculoskeletal Systems

Ye Fan, Joshua Litven, Dinesh Pai

We introduce a new framework for simulating the dynamics of musculoskeletal systems, with volumetric muscles in close contact and a novel data-driven muscle activation model. Muscles are simulated using an Eulerian-on-Lagrangian discretization that handles volume preservation, large deformation, and close contact between adjacent tissues. Volume preservation is crucial for accurately capturing the dynamics of muscles and other biological tissues. We show how to couple the dynamics of soft tissues with Lagrangian multibody dynamics simulators, which are widely available. Our physiologically based muscle activation model utilizes knowledge of the active shapes of muscles, which can be easily obtained from medical imaging data or designed to meet artistic needs. We demonstrate results with models derived from MRI data and models designed for artistic effect.

Active Volumetric Musculoskeletal Systems