kDet: Parallel Constant Time Collision Detection for Polygonal Objects

René Weller, Nicole Debowski and Gabriel Zachmann

We define a novel geometric predicate and a class of objects that enables us to prove a linear bound on the number of intersecting polygon pairs for colliding 3D objects in that class. Our predicate is relevant both in theory and in practice: it is easy to check and it needs to consider only the geometric properties of the individual objects – it does not depend on the configuration of a given pair of objects. In addition, it characterizes a practically relevant class of objects: we checked our predicate on a large database of real-world 3D objects and the results show that it holds for all but the most pathological ones. Our proof is constructive in that it is the basis for a novel collision detection algorithm that realizes this linear complexity also in practice. Additionally, we present a parallelization of this algorithm with a worst-case running time that is independent of the number of polygons. Our algorithm is very well suited not only for rigid but also for deformable and even topology-changing objects, because it does not require any complex data structures or pre-processing. We have implemented our algorithm on the GPU and the results show that it is able to find in real-time all colliding polygons for pairs of deformable objects consisting of more than 200k triangles, including self-collisions.

kDet: Parallel Constant Time Collision Detection for Polygonal Objects

Quasi-Newton Methods for Real-time Simulation of Hyperelastic Materials

Tiantian Liu, Sofien Bouaziz, Ladislav Kavan

We present a new method for real-time physics-based simulation supporting many different types of hyperelastic materials. Previous methods such as Position Based or Projective Dynamics are fast, but support only limited selection of materials; even classical materials such as the Neo-Hookean elasticity are not supported. Recently, Xu et al. [2015] introduced new “splinebased materials” which can be easily controlled by artists to achieve desired animation effects. Simulation of these types of materials currently relies on Newton’s method, which is slow, even with only one iteration per timestep. In this paper, we show that Projective Dynamics can be interpreted as a quasi-Newton method. This insight enables very efficient simulation of a large class of hyperelastic materials, including the Neo-Hookean, spline-based materials, and others. The quasi-Newton interpretation also allows us to leverage ideas from numerical optimization. In particular, we show that our solver can be further accelerated using L-BFGS updates (Limitedmemory Broyden-Fletcher-Goldfarb-Shanno algorithm). Our final method is typically more than 10 times faster than one iteration of Newton’s method without compromising quality. In fact, our result is often more accurate than the result obtained with one iteration of Newton’s method. Our method is also easier to implement, implying reduced software development costs.

Quasi-Newton Methods for Real-time Simulation of Hyperelastic Materials

Anisotropic Elastoplasticity for Cloth, Knit and Hair Frictional Contact

Chenfanfu Jiang, Theodore Gast, Joseph Teran

The typical elastic surface or curve simulation method takes a Lagrangian approach and consists of three components: time integration, collision detection and collision response. The Lagrangian view is beneficial because it naturally allows for tracking of the codimensional manifold, however collision must then be detected and resolved separately. Eulerian methods are promising alternatives because collision processing is automatic and while this is effective for volumetric objects, advection of a codimensional manifold is too inaccurate in practice. We propose a novel hybrid Lagrangian/Eulerian approach that preserves the best aspects of both views. Similar to the Drucker-Prager and Mohr-Coulomb models for granular materials, we define our collision response with a novel elastoplastic constitutive model. To achieve this, we design an anisotropic hyperelastic constitutive model that separately characterizes the response to manifold strain as well as shearing and compression in the directions orthogonal to the manifold. We discretize the model with the Material Point Method and a novel codimensional Lagrangian/Eulerian update of the deformation gradient. Collision intensive scenarios with millions of degrees of freedom require only a few minutes per frame and examples with up to one million degrees of freedom run in less than thirty seconds per frame.

Anisotropic Elastoplasticity for Cloth, Knit and Hair Frictional Contact

Dynamics-Aware Numerical Coarsening for Fabrication Design

Desai Chen, David I. W. Levin, Wojciech Matusik, Danny M. Kaufman

The realistic simulation of highly-dynamic elastic objects is important for a broad range of applications in computer graphics, engineering and computational fabrication. However, whether simulating flipping toys, jumping robots, prosthetics or quickly moving creatures, performing such simulations in the presence of contact, impact and friction is both time consuming and inaccurate. In this paper we present Dynamics-Aware Coarsening (DAC) and the Boundary Balanced Impact (BBI) model which allow for the accurate simulation of dynamic, elastic objects undergoing both large scale deformation and frictional contact, at rates up to 79 times faster than state-of-the-art methods. DAC and BBI produce simulations that are accurate and fast enough to be used (for the first time) for the computational design of 3D-printable compliant dynamic mechanisms. Thus we demonstrate the efficacy of DAC and BBI by designing and fabricating mechanisms which flip, throw and jump over and onto obstacles as requested.

Dynamics-Aware Numerical Coarsening for Fabrication Design

Data-Driven Physics for Human Soft Tissue Animation

Meekyoung Kim, Gerard Pons-Moll, Sergi Pujades, Sungbae Bang, Jinwwok Kim, Michael Black, Sung-Hee Lee

Data driven models of human poses and soft-tissue deformations can produce very realistic results, but they only model the visible surface of the human body and cannot create skin deformation due to interactions with the environment. Physical simulations can generalize to external forces, but their parameters are difficult to control. In this paper, we present a layered volumetric human body model learned from data. Our model is composed of a data-driven inner layer and a physics-based external layer. The inner layer is driven with a volumetric statistical body model (VSMPL). The soft tissue layer consists of a tetrahedral mesh that is driven using the finite element method (FEM). Model parameters, namely the segmentation of the body into layers and the soft tissue elasticity, are learned directly from 4D registrations of humans exhibiting soft tissue deformations. The learned two layer model is a realistic full-body avatar that generalizes to novel motions and external forces. Experiments show that the resulting avatars produce realistic results on held out sequences and react to external forces. Moreover, the model supports the retargeting of physical properties from one avatar when they share the same topology.

Data-Driven Physics for Human Soft Tissue Animation

Regularized Kelvinlets: Sculpting Brushes based on Fundamental Solutions of Elasticity

Fernando de Goes, Doug L. James

We introduce a new technique for real-time physically based volume sculpting of virtual elastic materials. Our formulation is based on the elastic response to localized force distributions associated with common modeling primitives such as grab, scale, twist, and pinch. The resulting brush-like displacements correspond to the regularization of fundamental solutions of linear elasticity in infinite 2D and 3D media. These deformations thus provide the realism and plausibility of volumetric elasticity, and the interactivity of closed-form analytical solutions. To finely control our elastic deformations, we also construct compound brushes with arbitrarily fast spatial decay. Furthermore, pointwise constraints can be imposed on the displacement field and its derivatives via a single linear solve. We demonstrate the versatility and efficiency of our method with multiple examples of volume sculpting and image editing.

Regularized Kelvinlets: Sculpting Brushes based on Fundamental Solutions of Elasticity

A Stiffly Accurate Integrator for Elastodynamic Problems

Dominik L. Michels, Vu Thai Luan, Mayya Tokman

We present a new integration algorithm for the accurate and efficient solution of stiff elastodynamic problems governed by the second-order ordinary differential equations of structural mechanics. Current methods have the shortcoming that their performance is highly dependent on the numerical stiffness of the underlying system that often leads to unrealistic behavior or a significant loss of efficiency. To overcome these limitations, we present a new integration method which is based on a mathematical reformulation of the underlying differential equations, an exponential treatment of the full nonlinear forcing operator as opposed to more standard partially implicit or exponential approaches, and the utilization of the concept of stiff accuracy which ensures that the efficiency of the simulations is significantly less sensitive to increased stiffness. As a consequence, we are able to tremendously accelerate the simulation of stiff systems compared to established integrators and significantly increase the overall accuracy. The advantageous behavior of this approach is demonstrated on a broad spectrum of complex examples like deformable bodies, textiles, bristles, and human hair. Our easily parallelizable integrator enables more complex and realistic models to be explored in visual computing without compromising efficiency.

A Stiffly Accurate Integrator for Elastodynamic Problems

Botanical Materials Based on Biomechanics

Bohan Wang, Yili Zhao, Jernej Barbic

Botanical simulation plays an important role in many fields including visual effects, games and virtual reality. Previous plant simulation research has focused on computing physically based motion, under the assumption that the material properties are known. It is too tedious and impractical to manually set the spatially-varying material properties of complex trees. In this paper, we give a method to set the mass density, stiffness and damping properties of individual tree components (branches and leaves) using a small number of intuitive parameters. Our method is rooted in plant biomechanics literature and builds upon power laws observed in real botanical systems. We demonstrate our materials by simulating them using offline and model-reduced FEM simulators. Our parameters can be tuned directly by artists; but we also give a technique to infer the parameters from ground truth videos of real trees. Our materials produce tree animations that look much more similar to real trees than previous methods, as evidenced by our user study and experiments.

Botanical Materials Based on Biomechanics

Phace: Physics-based Face Modeling and Animation

Alexandru-Eugen Ichim, Petr Kadlecek, Ladislav Kavan, Mark Pauly

We present a novel physics-based approach to facial animation. Contrary to commonly used generative methods, our solution computes facial expressions by minimizing a set of non-linear potential energies that model the physical interaction of passive flesh, active muscles, and rigid bone structures. By integrating collision and contact handling into the simulation, our algorithm avoids inconsistent poses commonly observed in generative methods such as blendshape rigs. A novel muscle activation model leads to a robust optimization that faithfully reproduces complex facial articulations. We show how person-specific simulation models can be built from a few expression scans with a minimal data acquisition process and an almost entirely automated processing pipeline. Our method supports temporal dynamics due to inertia or external forces, incorporates skin sliding to avoid unnatural stretching, and offers full control of the simulation parameters, which enables a variety of advanced animation effects. For example, slimming or fattening the face is achieved by simply scaling the volume of the soft tissue elements. We show a series of application demos, including artistic editing of the animation model, simulation of corrective facial surgery, or dynamic interaction with external forces and objects.

Phace: Physics-based Face Modeling and Animation

Example-Based Damping Design

Hongyi Xu, Jernej Barbič

To date, material modeling in physically based computer animation has largely focused on mass and stiffness material properties. However, deformation dynamics is largely affected also by the damping properties. In this paper, we propose an interactive design method for nonlinear isotropic and anisotropic damping of complex three-dimensional solids simulated using the Finite Element Method (FEM). We first give a damping design method and interface whereby the user can set the damping properties so that motion aligned with each of a few chosen example deformations is damped by an independently prescribed amount, whereas the rest of the deformation space follows standard Rayleigh damping, or any viscous damping. Next, we demonstrate how to design nonlinear damping that depends on the magnitude of the deformation along each example deformation, by editing a single spline curve for each example deformation. Our user interface enables an art-directed and intuitive approach to controlling damping in solid simulations. We mathematically prove that our nonlinear anisotropic damping generalizes the frequency-dependent Caughey damping model, when starting from the Rayleigh damping. Finally, we give an inverse design method whereby the damping curve parameters can be inferred automatically from high-level user input, such as the amount of amplitude loss in one oscillation cycle along each of the chosen example deformations. To minimize numerical damping for implicit integration, we introduce an accurate and stable implicit integrator, which removes spurious high-frequency oscillations while only introducing a minimal amount of numerical damping. Our damping can generate effects not possible with previous methods, such as controllable nonlinear decaying envelopes whereby large deformations are damped faster or slower than small deformations, and damping anisotropic effects. We also fit our damping to videos of real-world objects undergoing large deformations, capturing their nonlinear and anisotropic damping dynamics.

Example-Based Damping Design