Physics-Based Animation

Nuttapong Chentanez, Matthias Mueller, Miles Macklin, Tae-Yong Kim

We present the first mesh-based surface tracker that runs entirely on the GPU. The surface tracker is both completely grid-free and fast which makes it suitable for the use in a large, unbounded domain. The key idea for handling topological changes is to detect and delete overlapping triangles as well as triangles that lie inside the volume. The holes are then joined or closed in a robust and efficient manner. Good mesh quality is maintained by a mesh improvement algorithm. In this paper we describe how all these steps can be parallelized to run effi- ciently on a GPU. The surface tracker is guaranteed to produce a manifold mesh without boundary. Our results show the quality and efficiency of the method in both Eulerian and Lagrangian liquid simulations. Our parallel implementation runs more than an order of magnitude faster than the CPU version.

Grid-Free Surface Tracking on the GPU

Markus Huber, Stefan Reinhardt, Daniel Weiskopf, and Bernhard Eberhardt

We evaluate surface tension models in particle-based fluid simulation systems using smoothed particle hydrodynamics (SPH) with a benchmark test. Our benchmark consists of three experiments and a set of analysis methods that are useful for the comparison of surface tension models. Although visual quality is of major interest and is considered as well, we suggest quantification methods for the properties of these models. The goal is to identify if a certain model is suitable for a given scenario and to be able to control the results in the creation of animations. We apply the proposed evaluation methods to three existing surface tension models in combination with different SPH techniques (WCSPH, PCISPH, and IISPH) and perform systematic tests to show the influence of different settings and parameter choices. The surface tension models are chosen from different classes: a pure inter-particle force model, a model based on surface curvature, and a model using a combination of these. Additionally, we present a simple modification to improve the quality of inter-particle force models.

Evaluation of Surface Tension Models for SPH-Based Fluid Animations Using a Benchmark Test

Prashant Sachdeva, Shinjiro Sueda, Susanne Bradley, Mikhail Fain, Dinesh K. Pai

The tendons of the hand and other biomechanical systems form a complex network of sheaths, pulleys, and branches. By modeling these anatomical structures, we obtain realistic simulations of coordination and dynamics that were previously not possible. First, we introduce Eulerian-on-Lagrangian discretization of tendon strands, with a new selective quasistatic formulation that eliminates unnecessary degrees of freedom in the longitudinal direction, while maintaining the dynamic behavior in transverse directions. This formulation also allows us to take larger time steps. Second, we introduce two control methods for biomechanical systems: first, a general-purpose learning-based approach requiring no previous system knowledge, and a second approach using data extracted from the simulator. We use various examples to compare the performance of these controllers.

Biomechanical Simulation and Control of Hands and Tendinous Systems

Pierre-Luc Manteaux, Wei-Lun Sun, Francois Faure, Marie-Paule Cani, James F. O’Brien

In this paper we propose a method for the interactive detailed cutting of deformable thin sheets. Our method builds on the ability of frame-based simulation to solve for dynamics using very few control frames while embedding highly detailed geometry – here an adaptive mesh that accurately represents the cut boundaries. Our solution relies on a non-manifold grid to compute shape functions that faithfully adapt to the topological changes occurring while cutting. New frames are dynamically inserted to describe new regions. We provide incremental mechanisms for updating simulation data, enabling us to achieve interactive rates. We illustrate our method with examples inspired by the traditional Kirigami artform.

Interactive Detailed Cutting of Thin Sheets

Zherong Pan, Hujun Bao, Jin Huang

In this paper, we propose a full featured and efficient subspace simulation method in the rotation-strain (RS) space for elastic objects. Sharply different from previous methods using the rotation-strain space, except for the ability to handle non-linear elastic materials and external forces, our method correctly formulates the kinetic energy, centrifugal and Coriolis forces which significantly reduces the dynamic artifacts. We show many techniques used in the Euclidean space methods, such as modal derivatives, polynomial and cubature approximation, can be adapted to our RS simulator. Carefully designed experiments show that the equation of motion in RS space has less non-linearity than its Euclidean counterpart, and as a consequence, our method has great advantages of lower dimension and computational complexity than state-of-the-art methods in the Euclidean space.

Subspace Dynamic Simulation Using Rotation-Strain Coordinates

Ľubor Ladický, SoHyeon Jeong, Barbara Solenthaler, Marc Pollefeys, and Markus Gross

Traditional fluid simulations require large computational resources even for an average sized scene with the main bottleneck being a very small time step size, required to guarantee the stability of the solution. Despite a large progress in parallel computing and efficient algorithms for pressure computation in the recent years, realtime fluid simulations have been possible only under very restricted conditions. In this paper we propose a novel machine learning based approach, that formulates physics-based fluid simulation as a regression problem, estimating the acceleration of every particle for each frame. We designed a feature vector, directly modelling individual forces and constraints from the Navier-Stokes equations, giving the method strong generalization properties to reliably predict positions and velocities of particles in a large time step setting on yet unseen test videos. We used a regression forest to approximate the behaviour of particles observed in the large training set of simulations obtained using a traditional solver. Our GPU implementation led to a speed-up of one to three orders of magnitude compared to the state-of-the-art position-based fluid solver and runs in real-time for systems with up to 2 million particles.

Data-Driven Fluid Simulations using Regression Forests

Rasmus Tamstorf, Toby Jones, Stephen F. McCormick

Existing multigrid methods for cloth simulation are based on geometric multigrid. While good results have been reported, geometric methods are problematic for unstructured grids, widely varying material properties, and varying anisotropies, and they often have difficulty handling constraints arising from collisions. This paper applies the algebraic multigrid method known as smoothed aggregation to cloth simulation. This method is agnostic to the underlying tessellation, which can even vary over time, and it only requires the user to provide a fine-level mesh. To handle contact constraints efficiently, a prefiltered preconditioned conjugate gradient method is introduced. For highly efficient preconditioners, like the ones proposed here, prefiltering is essential, but, even for simple preconditioners, prefiltering provides significant benefits in the presence of many constraints. Numerical tests of the new approach on a range of examples confirm 6-8X speedups on a fully dressed character with 371k vertices, and even larger speedups on synthetic examples.

Smoothed Aggregation Multigrid for Cloth Simulation

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

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

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