Category: Deformables

Non-manifold Level Sets: A multivalued implicit surface representation with applications to self-collision processing

Nathan Mitchell, Mridul Aanjaneya, Rajsekhar Setaluri, Eftychios Sifakis

Level sets have been established as highly versatile implicit surface representations, with widespread use in graphics applications including modeling and dynamic simulation. Nevertheless, level sets are often presumed to be limited, compared to explicit meshes, in their ability to represent domains with thin topological features (e.g. narrow slits and gaps) or, even worse, material overlap. Geometries with such features may arise from modeling tools that tolerate occasional self-intersections, fracture modeling algorithms that create narrow or zero-width cuts by design, or as transient states in collision processing pipelines for deformable objects. Converting such models to level sets can alter their topology if thin features are not resolved by the grid size. We argue that this ostensible limitation is not an inherent defect of the implicit surface concept, but a collateral consequence of the standard Cartesian lattice used to store the level set values. We propose storing signed distance values on a regular hexahedral mesh which can have multiple collocated cubic elements and non-manifold bifurcation to accommodate non-trivial topology. We show how such non-manifold level sets can be systematically generated from convenient alternative geometric representations. Finally we demonstrate how this representation can facilitate fast and robust treatment of self-collision in simulations of volumetric elastic deformable bodies.

Non-manifold Level Sets: A multivalued implicit surface representation with applications to self-collision processing

TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds

Zhendong Wang, Min Tang , Ruofeng Tong, and Dinesh Manocha

We present a realtime and reliable continuous collision detection (CCD) algorithm between triangulated models that exploits the floating point hardware capability of current CPUs and GPUs. Our formulation is based on Bernstein Sign Classification that takes advantage of the geometry properties of Bernstein basis and Bézier curves to perform Boolean collision queries. We derive tight numerical error bounds on the computations and employ those bounds to design an accurate algorithm using finite-precision arithmetic. Compared with prior floatingpoint CCD algorithms, our approach eliminates all the false negatives and 90-95% of the false positives. We integrated our algorithm (TightCCD) with physically-based simulation system and observe speedups in collision queries of 5-15X compared with prior reliable CCD algorithms. Furthermore, we demonstrate its benefits in terms of improving the performance or robustness of cloth simulation systems.

TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds

Deformable Objects Collision Handling with Fast Convergence

Siwang Li, Zherong Pan, Jin Huang,  Hujun Bao, Xiaogang Jin

We present a stable and efficient simulator for deformable objects with collisions and contacts. For stability, an optimization derived from the implicit time integrator is solved in each timestep under the inequality constraints coming from collisions. To achieve fast convergence, we extend the MPRGP based solver from handling boxconstraints only to handling general linear constraints and prove its convergence. This generalization introduces a cost of solving dense linear systems in each step, but these systems can be reduced into diagonal ones for efficiency without affecting the general stability via pruning redundant collisions. Our solver is an order of magnitude faster, especially for elastic objects under large deformation compared with iterative constraint anticipation method (ICA), a typical method for stability. The efficiency, robustness and stability are further verified by our results.

Deformable Objects Collision Handling with Fast Convergence

Wetbrush: GPU-based 3D painting simulation at the bristle level

Zhili Chen, Byungmoon Kim, Daichi Ito, Huamin Wang

We present a real-time painting system that simulates the interactions among brush, paint, and canvas at the bristle level. The key challenge is how to model and simulate sub-pixel paint details, given the limited computational resource in each time step. To achieve this goal, we propose to define paint liquid in a hybrid fashion: the liquid close to the brush is modeled by particles, and the liquid away from the brush is modeled by a density field. Based on this representation, we develop a variety of techniques to ensure the performance and robustness of our simulator under large time steps, including brush and particle simulations in non-inertial frames, a fixed-point method for accelerating Jacobi iterations, and a new Eulerian-Lagrangian approach for simulating detailed liquid effects. The resulting system can realistically simulate not only the motions of brush bristles and paint liquid, but also the liquid transfer processes among different representations. We implement the whole system on GPU by CUDA. Our experiment shows that artists can use the system to draw realistic and vivid digital paintings, by applying the painting techniques that they are familiar with but not offered by many existing systems.

Wetbrush: GPU-based 3D painting simulation at the bristle level

A Chebyshev Semi-iterative Approach for Accelerating Projective and Position-based Dynamics

Huamin Wang

In this paper, we study the use of the Chebyshev semi-iterative approach in projective and position-based dynamics. Although projective dynamics is fundamentally nonlinear, its convergence behavior is similar to that of an iterative method solving a linear system. Because of that, we can estimate the “spectral radius” and use it in the Chebyshev approach to accelerate the convergence by at least one order of magnitude, when the global step is handled by the direct solver, the Jacobi solver, or even the Gauss-Seidel solver. Our experiment shows that the combination of the Chebyshev approach and the direct solver runs fastest on CPU, while the combination of the Chebyshev approach and the Jacobi solver outperforms any other combination on GPU, as it is highly compatible with parallel computing. Our experiment further shows position-based dynamics can be accelerated by the Chebyshev approach as well, although the effect is less obvious for tetrahedral meshes. The whole approach is simple, fast, effective, GPU-friendly, and has a small memory cost.

A Chebyshev Semi-iterative Approach for Accelerating Projective and Position-based Dynamics

A Unified Approach for Subspace Simulation of Deformable Bodies in Multiple Domains

Xiaofeng Wu, Rajaditya Mukherjee, Huamin Wang

Multi-domain subspace simulation can efficiently and conveniently simulate the deformation of a large deformable body, by constraining the deformation of each domain into a different subspace. The key challenge in implementing this method is how to handle the coupling among multiple deformable domains, so that the overall effect is free of gap or locking issues. In this paper, we present a new domain decomposition framework that connects two disjoint domains through coupling elements. Under this framework, we present a unified simulation system that solves subspace deformations and rigid motions of all of the domains by a single linear solve. Since the coupling elements are part of the deformable body, their elastic properties are the same as the rest of the body and our system does not need stiffness parameter tuning. To quickly evaluate the reduced elastic forces and their Jacobian matrices caused by the coupling elements, we further develop two cubature optimization schemes using uniform and non-uniform cubature weights. Our experiment shows that the whole system can efficiently handle large and complex scenes, many of which cannot be easily simulated by previous techniques without limitations

A Unified Approach for Subspace Simulation of Deformable Bodies in Multiple Domains

Expediting Precomputation for Reduced Deformable Simulation

Yin Yang, Dingzeyu Li, Weiwei Xu, Yuan Tian, Changxi Zheng

Model reduction has popularized itself for simulating elastic deformation for graphics applications. While these techniques enjoy orders-of-magnitude speedups at runtime simulation, the efficiency of precomputing reduced subspaces remains largely overlooked. We present a complete system of precomputation pipeline as a faster alternative to the classic linear and nonlinear modal analysis. We identify three bottlenecks in the traditional model reduction precomputation, namely modal matrix construction, cubature training, and training dataset generation, and accelerate each of them. Even with complex deformable models, our method has achieved orders-of-magnitude speedups over the traditional precomputation steps, while retaining comparable runtime simulation quality.

Expediting Precomputation for Reduced Deformable Simulation

Fully Momentum-Conserving Reduced Deformable Bodies with Collision, Contact, Articulation, and Skinning

Rahul Sheth, Wenlong Lu, Yue Yu, Ronald Fedkiw

We propose a novel framework for simulating reduced deformable bodies that fully accounts for linear and angular momentum conservation even in the presence of collision, contact, articulation, and other desirable effects. This was motivated by the observation that the mere excitation of a single mode in a reduced degree of freedom model can adversely change the linear and angular momentum. Although unexpected changes in linear momentum can be avoided during basis construction, adverse changes in angular momentum appear unavoidable, and thus we propose a robust framework that includes the ability to compensate for them. Enabled by this ability to fully account for linear and angular momentum, we introduce an impulse-based formulation that allows us to precisely control the velocity of any node in spite of the fact that we only have access to a lower-dimensional set of degrees of freedom. This allows us to model collision, contact, and articulation in a robust and high visual fidelity manner, especially when compared to penalty-based forces that merely aim to coerce local velocities. In addition, we propose a new “deformable bones” framework wherein we leverage standard skinning technology for “bones,” “bone” placement, blending operations, etc. even though each of our “deformable bones” is a fully simulated reduced deformable model.

Fully Momentum-Conserving Reduced Deformable Bodies with Collision, Contact, Articulation, and Skinning

A New Sharp-Crease Bending Element for Folding and Wrinkling Surfaces and Volumes

Saket Patkar, Ning Jin, Ronald Fedkiw

We present a novel sharp-crease bending element for the folding and wrinkling of surfaces and volumes. Based on a control curve specified by an artist or derived from internal stresses of a simulation, we create a piecewise linear curve at the resolution of the computational mesh. Then, the key idea is to cut the object along the curve using the virtual node algorithm creating new degrees of freedom, while subsequently reattaching the resulting pieces eliminating the translational degrees of freedom so that adjacent pieces may only rotate or bend about the cut. Motivated by an articulated rigid body framework, we utilize the concepts of pre-stabilization and post-stabilization in order to enforce these reattachment constraints. Our cuts can be made either razor sharp or relatively smooth via the use of bending springs. Notably, our sharp-crease bending elements can not only be used to create pleats in cloth or folds in paper but also to create similar buckling in volumetric objects. We illustrate this with examples of forehead wrinkles and nasolabial folds for facial animation. Moreover, our sharp-crease bending elements require minimal extra simulation time as compared to the underlying mesh, and tend to reduce simulation times by an order of magnitude when compared to the alternative of mesh refinement.

A New Sharp-Crease Bending Element for Folding and Wrinkling Surfaces and Volumes

Data-Driven Finite Elements for Geometry and Material Design

Desai Chen, David I.W. Levin, Shinjiro Sueda, Wojciech Matusik

Crafting the behavior of a deformable object is difficult—whether it is a biomechanically accurate character model or a new multimaterial 3D printable design. Getting it right requires constant iteration, performed either manually or driven by an automated system. Unfortunately, previous algorithms for accelerating three-dimensional finite element analysis of elastic objects suffer from expensive precomputation stages that rely on a priori knowledge of the object’s geometry and material composition. In this paper we introduce Data-Driven Finite Elements as a solution to this problem. Given a material palette, our method constructs a metamaterial library which is reusable for subsequent simulations, regardless of object geometry and/or material composition. At runtime, we perform fast coarsening of a simulation mesh using a simple table lookup to select the appropriate metamaterial model for the coarsened elements. When the object’s material distribution or geometry changes, we do not need to update the metamaterial library—we simply need to update the metamaterial assignments to the coarsened elements. An important advantage of our approach is that it is applicable to non-linear material models. This is important for designing objects that undergo finite deformation (such as those produced by multimaterial 3D printing). Our method yields speed gains of up to two orders of magnitude while maintaining good accuracy. We demonstrate the effectiveness of the method on both virtual and 3D printed examples in order to show its utility as a tool for deformable object design.

Data-Driven Finite Elements for Geometry and Material Design