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
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
Nuttapong Chentanez, Matthias Mueller, Tae-Yong Kim
We propose a new method to simulate large scale water phenomena by combining particle, 3D grid and height field methods. In contrast to most hybrid approaches that use particles to simulate foam and spray only, we also represent the bulk of water near the surface with both particles and a grid depending on the regions of interest and switch between those two representations during the course of the simulation. For the coupling we leverage the recent idea of tracking the water surface with a density field in grid based methods. Combining particles and a grid simulation then amounts to adding the density field of the particles and the one stored on the grid. For open scenes, we simulate the water outside of the 3D grid domain by solving the Shallow Water Equations on a height field. We propose new methods to couple these two domains such that waves travel naturally across the border. We demonstrate the effectiveness of our approach in various scenarios including a whale breaching simulation, all running in real-time or at interactive rates.
Coupling 3D Eulerian, Height Field and Particle Methods for the Simulation of Large Scale Liquid Phenomena
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
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
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
Weiwei Xu, Noboyuki Umetani, Qianwen Chao, Jie Mao, Xiaogang Jin, Xin Tong
We present a real-time solution for generating detailed clothing deformations from pre-computed clothing shape examples. Given an input pose, it synthesizes a clothing deformation by blending skinned clothing deformations of nearby examples controlled by the body skeleton. Observing that cloth deformation can be well modeled with sensitivity analysis driven by the underlying skeleton, we introduce a sensitivity based method to construct a pose-dependent rigging solution from sparse examples. We also develop a sensitivity based blending scheme to find nearby examples for the input pose and evaluate their contributions to the result. Finally, we propose a stochastic optimization based greedy scheme for sampling the pose space and generating example clothing shapes. Our solution is fast, compact and can generate realistic clothing animation results for various kinds of clothes in real time.
Sensitivity-optimized Rigging for Example-based Real-Time Clothing Synthesis
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
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.
Efﬁcient Denting and Bending of Rigid Bodies
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