Category: Collisions

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

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

An Implicit Frictional Contact Solver for Adaptive Cloth Simulation

Jie Li, Gilles Daviet, Rahul Narain, Florence Bertails-Descoubes, Matthew Overby, George Brown, Laurence Boissieux

Cloth dynamics plays an important role in the visual appearance of moving characters. Properly accounting for contact and friction is of utmost importance to avoid cloth-body and cloth-cloth penetration and to capture typical folding and stick-slip behavior due to dry friction. We present here the first method able to account for cloth contact with exact Coulomb friction, treating both cloth self-contacts and contacts occurring between the cloth and an underlying character. Our key contribution is to observe that for a nodal system like cloth, the frictional contact problem may be formulated based on velocities as primary variables, without having to compute the costly Delassus operator. Then, by reversing the roles classically played by the velocities and the contact impulses, conical complementarity solvers of the literature can be adapted to solve for compatible velocities at nodes. To handle the full complexity of cloth dynamics scenarios, we have extended this base algorithm in two ways: first, towards the accurate treatment of frictional contact at any location of the cloth, through an adaptive node refinement strategy; second, towards the handling of multiple constraints at each node, through the duplication of constrained nodes and the adding of pin constraints between duplicata. Our method allows us to handle the complex cloth-cloth and cloth-body interactions in full-size garments with an unprecedented level of realism compared to former methods, while maintaining reasonable computational timings.

An Implicit Frictional Contact Solver for Adaptive Cloth Simulation

A Material Point Method for Thin Shells with Frictional Contact

Qi Guo, Xuchen Han, Chuyuan Fu, Theodore Gast, Rasmus Tamstorf, Joseph Teran

We present a novel method for simulation of thin shells with frictional contact using a combination of the Material Point Method (MPM) and subdivision finite elements. The shell kinematics are assumed to follow a continuum shell model which is decomposed into a Kirchhoff-Love motion that rotates the mid-surface normals followed by shearing and compression/extension of the material along the mid-surface normal. We use this decomposition to design an elastoplastic constitutive model to resolve frictional contact by decoupling resistance to contact and shearing from the bending resistance components of stress. We show that by resolving frictional contact with a continuum approach, our hybrid Lagrangian/Eulerian approach is capable of simulating challenging shell contact scenarios with hundreds of thousands to millions of degrees of freedom. Without the need for collision detection or resolution, our method runs in a few minutes per frame in these high resolution examples. Furthermore we show that our technique naturally couples with other traditional MPM methods for simulating granular and related materials.

A Material Point Method for Thin Shells with Frictional Contact

Eulerian-on-Lagrangian Cloth Simulation

Nicholas J. Weidner, Kyle Piddington, David I. W. Levin, Shinjiro Sueda

We resolve the long-standing problem of simulating the contact-mediated interaction of cloth and sharp geometric features by introducing an Eulerian-on-Lagrangian (EOL) approach to cloth simulation. Unlike traditional Lagrangian approaches to cloth simulation, our EOL approach permits bending exactly at and sliding over sharp edges, avoiding parasitic locking caused by over-constraining contact constraints. Wherever the cloth is in contact with sharp features, we insert EOL vertices into the cloth, while the rest of the cloth is simulated in the standard Lagrangian fashion. Our algorithm manifests as new equations of motion for EOL vertices, a contact-conforming remesher, and a set of simple constraint assignment rules, all of which can be incorporated into existing state-of-the-art cloth simulators to enable smooth, inequality-constrained contact between cloth and objects in the world.

Eulerian-on-Lagrangian Cloth Simulation

A Moving Least Squares Material Point Method with Displacement Discontinuity and Two-Way Rigid Body Coupling

Yuanming Hu, Yu Fang, Ziheng Ge, Ziyin Qu, Yixin Zhu, Andre Pradhana, Chenfanfu Jiang

In this paper, we introduce the Moving Least Squares Material Point Method (MLS-MPM). MLS-MPM naturally leads to the formulation of Affine Particle-In-Cell (APIC) [Jiang et al. 2015] and Polynomial Particle-In-Cell [Fu et al. 2017] in a way that is consistent with a Galerkin-style weak form discretization of the governing equations. Additionally, it enables a new stress divergence discretization that eortlessly allows all MPM simulations to run two times faster than before. We also develop a Compatible Particle-In-Cell (CPIC) algorithm on top of MLS-MPM. Utilizing a colored distance field representation and a novel compatibility condition for particles and grid nodes, our framework enables the simulation of various new phenomena that are not previously supported by MPM, including material cutting, dynamic open boundaries, and two-way coupling with rigid bodies. MLS-MPM with CPIC is easy to implement and friendly to performance optimization.

A Moving Least Squares Material Point Method with Displacement Discontinuity and Two-Way Rigid Body Coupling

PSCC: Parallel Self-Collision Culling with Spatial Hashing on GPUs

Min Tang, Zhongyuan Liu,, Ruofeng Tong, Dinesh Manocha

We present a GPU-based self-collision culling method (PSCC) based on a combination of normal cone culling and spatial hashing techniques. We first describe a normal cone test front (NCTF) based parallel algorithm that maps well to GPU architectures. We use sprouting and shrinking operators to maintain compact NCTFs. Moreover, we use the NCTF nodes to efficient build an enhanced spatial hashing for triangles meshes and use that for inter-object and intra-object collisions. Compared with conventional spatial hashing, our approach provides higher culling efficiency and reduces the cost of narrow phrase culling. As compared to prior GPU-based parallel collision detection algorithm, our approach demonstrates 6?8X speedup. We also present an efficient approach for GPU-based cloth simulation based on PSCC. In practice, our GPU-based cloth simulation takes about one second per frame on complex scenes with tens or hundreds of thousands of triangles, and is about 4-6X faster than prior GPU-based simulation algorithms.

PSCC: Parallel Self-Collision Culling with Spatial Hashing on GPUs

Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring

X. L. Wang, M. Tang, D. Manocha, Ruo-Feng Tong

Bounding volume hierarchy (BVH) has been widely adopted as the acceleration structure in broad-phase collision detection. Previous state-of-the-art BVH-based collision detection approaches exploited the spatio-temporal coherence of simulations by maintaining a bounding volume test tree (BVTT) front. A major drawback of these algorithms is that large deformations in the scenes decrease culling efficiency and slow down collision queries. Moreover, for front-based methods, the inefficient caching on GPU caused by the arbitrary layout of BVH and BVTT front nodes becomes a critical performance issue. We present a fast and robust BVH-based collision detection scheme on GPU that addresses the above problems by ordering and restructuring BVHs and BVTT fronts. Our techniques are based on the use of histogram sort and an auxiliary structure BVTT front log, through which we analyze the dynamic status of BVTT front and BVH quality. Our approach efficiently handles inter- and intra-object collisions and performs especially well in simulations where there is considerable spatio-temporal coherence. The benchmark results demonstrate that our approach is significantly faster than the previous BVH-based method, and also outperforms other state-of-the-art spatial subdivision schemes in terms of speed.

Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring

An Adaptive Generalized Interpolation Material Point Method for Simulating Elastoplastic Materials

Ming Gao, Andre Pradhana Tampubulon, Chenfanfu Jiang, Eftychios Sifakis

We present an adaptive Generalized Interpolation Material Point (GIMP) method for simulating elastoplastic materials. Our approach allows adaptive refining and coarsening of different regions of the material, leading to an efficient MPM solver that concentrates most of the computation resources in specific regions of interest. We propose a C1 continuous adaptive basis function that satisfies the partition of unity property and remains nonnegative throughout the computational domain. We develop a practical strategy for particle-grid transfers that leverages the recently introduced SPGrid data structure for storing sparse multi-layered grids. We demonstrate the robustness and efficiency of our method on the simulation of various elastic and plastic materials. We also compare key kernel components to uniform grid MPM solvers to highlight performance benefits of our method.

An Adaptive Generalized Interpolation Material Point Method for Simulating Elastoplastic Materials

Physically-Based Droplet Interaction

Richard Jones, Richard Southern

In this paper we present a physically-based model for simulating realistic interactions between liquid droplets in an efficient manner. Our particle-based system recreates the coalescence, separation and fragmentation interactions that occur between colliding liquid droplets and allows systems of droplets to be meaningfully repre- sented by an equivalent number of simulated particles. By consid- ering the interactions specific to liquid droplet phenomena directly, we display novel levels of detail that cannot be captured using other interaction models at a similar scale. Our work combines experi- mentally validated components, originating in engineering, with a collection of novel modifications to create a particle-based interac- tion model for use in the development of mid-to-large scale droplet- based liquid spray effects. We demonstrate this model, alongside a size-dependent drag force, as an extension to a commonly-used ballistic particle system and show how the introduction of these interactions improves the quality and variety of results possible in recreating liquid droplets and sprays, even using these otherwise simple systems.

Physically-Based Droplet Interaction