Category: Deformables

Fast Quadrangular Mass-Spring Systems using Red-Black Ordering

Pontus Pall, Oskar Nylèn, Marco Fratarcangeli

We introduce a practical iterative solver for mass-spring systems which can be trivially mapped to massively parallel architectures, in particular GPUs.We employ our solver for the interactive animation of virtual cloth and show that it is computationally fast, robust and scalable, making it suitable for real-time graphics applications. Under the assumption that the input system is represented by a quadrangular network of masses connected by springs, we first partition the particles into two independent sets. Then, during the animation, the dynamics of all the particles belonging to each set is computed in parallel. This enables a full Gauss-Seidel iteration in just two parallel steps, leading to an approximated solution of large mass-spring systems in a few milliseconds. We use our solver to accelerate the solution of the popular Projective Dynamics framework, and compare it with other common iterative solvers in the current literature.

Fast Quadrangular Mass-Spring Systems using Red-Black Ordering

Laplacian Damping for Projective Dynamics

Jing Li, Tiantian Liu, Ladislav Kavan

Damping is an important ingredient in physics-based simulation of deformable objects. Recent work introduced new fast simulation methods such as Position Based Dynamics and Projective Dynamics. Explicit velocity damping methods currently used in conjunction with Position Based Dynamics or Projective Dynamics are simple and fast, but have some limitations. They may damp global motion or non-physically transport velocities throughout the simulated object. More advanced damping models do not have these limitations, but are slow to evaluate, defeating the benefits of fast solvers such as Projective Dynamics. We present a new type of damping model specifically designed for Projective Dynamics, which provides the quality of advanced damping models while adding only minimal computing overhead. The key idea is to define damping forces using Projective Dynamics’ Laplacian matrix. In a number of simulation examples we show that this damping model works very well in practice. When used with a modified Projective Dynamics solver that uses a non-dissipative implicit midpoint integrator, our damping method provides fully user-controllable damping, allowing the user to quickly produce visually pleasing and vivid animations.

Laplacian Damping for Projective Dynamics

Reformulating Hyperelastic Materials with Peridynamic Modeling

Liyou Xu, Xiaowei He, Wei Chen, Sheng Li, and Guoping Wang

Peridynamics is a formulation of the classical elastic theory that is targeted at simulating deformable objects with discontinuities, especially fractures. Till now, there are few studies that have been focused on how to model general hyperelastic materials with peridynamics. In this paper, we target at proposing a general strain energy function of hyperelastic materials for peridynamics. To get an intuitive model that can be easily controlled, we formulate the strain energy density function as a function parameterized by the dilatation and bond stretches, which can be decomposed into multiple one-dimensional functions independently. To account for nonlinear material behaviors, we also propose a set of nonlinear basis functions to help design a nonlinear strain energy function more easily. For an anisotropic material, we additionally introduce an anisotropic kernel to control the elastic behavior for each bond independently. Experiments show that our model is flexible enough to approximately regenerate various hyperelastic materials in classical elastic theory, including St.Venant-Kirchhoff and Neo-Hookean materi

Reformulating Hyperelastic Materials with Peridynamic Modeling

Accurate dissipative forces in optimization integrators

George E. Brown, Matthew Overby, Zahra Forootaninia, Rahul Narain

We propose a method for accurately simulating dissipative forces in deformable bodies when using optimization-based integrators. We represent such forces using dissipation functions which may be nonlinear in both positions and velocities, enabling us to model a range of dissipative effects including Coulomb friction, Rayleigh damping, and power-law dissipation. We propose a general method for incorporating dissipative forces into optimization-based time integration schemes, which hitherto have been applied almost exclusively to systems with only conservative forces. To improve accuracy and minimize artificial damping, we provide an optimization-based version of the second-order accurate TR-BDF2 integrator. Finally, we present a method for modifying arbitrary dissipation functions to conserve linear and angular momentum, allowing us to eliminate the artificial angular momentum loss caused by Rayleigh damping.

Accurate dissipative forces in optimization integrators

Analytic Eigensystems for Isotropic Distortion Energies

Breannan Smith, Fernando de Goes, Theodore Kim

Many strategies exist for optimizing non-linear distortion energies in geometry and physics applications, but devising an approach that achieves the convergence promised by Newton-type methods remains challenging. In order to guarantee the positive semi-definiteness required by these methods, a numerical eigendecomposition or approximate regularization is usually needed. In this paper, we present analytic expressions for the eigensystems at each quadrature point of a wide range of isotropic distortion energies. These systems can then be used to project energy Hessians to positive semi-definiteness analytically. Unlike previous attempts, our formulation provides compact expressions that are valid both in 2D and 3D, and does not introduce spurious degeneracies. At its core, our approach utilizes the invariants of the stretch tensor that arises from the polar decomposition of the deformation gradient. We provide closed-form expressions for the eigensystems for all these invariants, and use them to systematically derive the eigensystems of any isotropic energy. Our results are suitable for geometry optimization over flat surfaces or volumes, and agnostic to both the choice of discretization and basis function. To demonstrate the efficiency of our approach, we include comparisons against existing methods on common graphics tasks such as surface parameterization and volume deformation.

Analytic Eigensystems for Isotropic Distortion Energies

I-Cloth: Incremental Collision Handling for GPU-Based Interactive Cloth Simulation

Min Tang, Tongtong Wang, Zhongyuan Liu, Ruofeng Tong, and Dinesh Manocha

We present an incremental collision handling algorithm for GPU-based interactive cloth simulation. Our approach exploits the spatial and temporal coherence between successive iterations of an optimization-based solver for collision response computation. We present an incremental continuous collision detection algorithm that keeps track of deforming vertices and combine it with spatial hashing. We use a non-linear GPU-based impact zone solver to resolve the penetrations. We combine our collision handling algorithm with implicit integration to use large time steps. Our overall algorithm, I-Cloth, can simulate complex cloth deformation with a few hundred thousand vertices at 2-8 frames per second on a commodity GPU. We highlight its performance on different benchmarks and observe up to 7-10X speedup over prior algorithms.

I-Cloth: Incremental Collision Handling for GPU-Based Interactive Cloth Simulation

Hybrid Grains: Adaptive Coupling of Discrete and Continuum Simulations of Granular Media

Yonghao Yue*, Breannan Smith*, Peter Yichen Chen*, Maytee Chantharayukhonthorn*, Ken Kamrin, Eitan Grinspun

We propose a technique to simulate granular materials that exploits the dual strengths of discrete and continuum treatments. Discrete element simulations provide unmatched levels of detail and generality, but prove excessively costly when applied to large scale systems. Continuum approaches are computationally tractable, but limited in applicability due to built-in modeling assumptions; e.g., models suitable for granular flows typically fail to capture clogging, bouncing and ballistic motion. In our hybrid approach, an oracle dynamically partitions the domain into continuum regions where safe, and discrete regions where necessary. The domains overlap along transition zones, where a Lagrangian dynamics mass-splitting coupling principle enforces agreement between the two simulation states. Enrichment and homogenization operations allow the partitions to evolve over time. This approach accurately and efficiently simulates scenarios that previously required an entirely discrete treatment.

Hybrid Grains: Adaptive Coupling of Discrete and Continuum Simulations of Granular Media

GPU Optimization of Material Point Methods

Ming Gao*, Xinlei Wang*, Kui Wu*, Andre Pradhana, Eftychios Sifakis, Cem Yuksel, Chenfanfu Jiang

The Material Point Method (MPM) has been shown to facilitate effective simulations of physically complex and topologically challenging materials, with a wealth of emerging applications in computational engineering and visual computing. Borne out of the extreme importance of regularity, MPM is given attractive parallelization opportunities on high-performance modern multiprocessors. Parallelization of MPM that fully leverages computing resources presents challenges that require exploring an extensive design-space for favorable data structures and algorithms. Unlike the conceptually simple CPU parallelization, where the coarse partition of tasks can be easily applied, it takes greater effort to reach the GPU hardware saturation due to its many-core SIMT architecture. In this paper we introduce methods for addressing the computational challenges of MPM and extending the capabilities of general simulation systems based on MPM, particularly concentrating on GPU optimization. In addition to our open-source high-performance framework, we also conduct performance analyses and benchmark experiments to compare against alternative design choices which may superficially appear to be reasonable, but can suffer from suboptimal performance in practice. Our explicit and fully implicit GPU MPM solvers are further equipped with a Moving Least Squares MPM heat solver and a novel sand constitutive model to enable fast simulations of a wide range of materials. We demonstrate that more than an order of magnitude performance improvement can be achieved with our GPU solvers. Practical high-resolution examples with up to ten million particles run in less than one minute per frame.

GPU Optimization of Material Point Methods

Methodology for Assessing Mesh-Based Contact Point Methods

Kenny Erleben

Computation of contact points is a critical sub-component of physics-based animation. The success and correctness of simulation results are very sensitive to the quality of the contact points. Hence, quality plays a critical role when comparing methods, and this is highly relevant for simulating objects with sharp edges. The importance of contact point quality is largely overlooked and lacks rigor and as such may become a bottleneck in moving the research field forward. We establish a taxonomy of contact point generation methods and lay down an analysis of what normal contact quality implies. The analysis enables us to establish a novel methodology for assessing and studying quality for mesh-based shapes. The core idea is based on a test suite of three complex cases and a small portfolio of simple cases. We apply our methodology to eight local contact point generation methods and conclude that the selected local methods are unable to provide correct information in all cases. The immediate benefit of the proposed methodology is a foundation for others to evaluate and select the best local method for their specific application. In the longer perspective, the presented work suggests future research focusing on semi-local methods.

Methodology for Assesing Mesh-Based Contact Point Methods

The Human Touch: Measuring Contact with Real Human Soft Tissues

D. K. Pai, A. Rothwell, P. Wyder-Hodge, A. Wick, Y. Fan, E. Larionov, D. Harrison, D. R. Neog, and C. Shing

Simulating how the human body deforms in contact with clothing, wearables, and other objects is of central importance to many fields. However, the tissue material properties needed to accurately simulate real human bodies had been sorely lacking. We showed that these mechanical properties can be directly measured using a novel hand-held device. We have developed a complete pipeline for measurement, modelling, parameter estimation, and simulation using the finite element method. Our unique data may be used to create personalized models of an individual human or of a population. Consequently, our methods may have many potential applications in apparel design, e-commerce, computer animation, and medicine.

The Human Touch: Measuring Contact with Real Human Soft Tissues