Physics-Based Animation

We introduce a new method for simulating frictional contact between volumetric objects using interpenetration volume constraints. When applied to complex geometries, our formulation results in dramatically simpler systems of equations than those of traditional mesh contact models. Contact between highly detailed meshes can be simplified to a single unilateral constraint equation, or accurately processed at arbitrary geometry-independent resolution with simultaneous sticking and sliding across contact patches.
We exploit fast GPU methods for computing layered depth images, which provides us with the intersection volumes and gradients necessary to formulate the contact equations as linear complementarity problems. Straightforward and popular numerical methods, such as projected Gauss-Seidel, can be used to solve the system.
We demonstrate our method in a number of scenarios and present results involving both rigid and deformable objects at interactive rates.

Volume Contact Constraints at Arbitrary Resolution

We show how to greatly accelerate self-collision detection (SCD) for reduced deformable models. Given a triangle mesh and a set of deformation modes, our method precomputes Subspace Self-Collision Culling (SSCC) certificates which, if satisfied, prove the absence of self-collisions for large parts of the model. At runtime, bounding volume hierarchies augmented with our certificates can aggressively cull overlap tests and reduce hierarchy updates. Our method supports both discrete and continuous SCD, can handle complex geometry, and makes no assumptions about geometric smoothness or normal bounds. It is particularly effective for simulations with modest subspace deformations, where it can often verify the absence of self-collisions in constant time. Our certificates enable low amortized costs, in time and across many objects in multi-body dynamics simulations. Finally, SSCC is effective enough to support self-collision tests at audio rates, which we demonstrate by producing the first sound simulations of clattering objects.

Subspace Self-Collision Culling

We propose a finite element simulation method that addresses the full range of material behavior, from purely elastic to highly plastic, for physical domains that are substantially reshaped by plastic flow, fracture, or large elastic deformations. To mitigate artificial plasticity, we maintain a simulation mesh in both the current state and the rest shape, and store plastic offsets only to represent the non-embeddable portion of the plastic deformation. To maintain high element quality in a tetrahedral mesh undergoing gross changes, we use a dynamic meshing algorithm that attempts to replace as few tetrahedra as possible, and thereby limits the visual artifacts and artificial diffusion that would otherwise be introduced by repeatedly remeshing the domain from scratch. Our dynamic mesher also locally refines and coarsens a mesh, and even creates anisotropic tetrahedra, wherever a simulation requests it. We illustrate these features with animations of elastic and plastic behavior, extreme deformations, and fracture.

Dynamic Local Remeshing for Elastoplastic Simulation

This paper describes a method for animating the appearance of clothing, such as pants or a shirt, that fits closely to a figure’s body. Compared to flowing cloth, such as loose dresses or capes, these types of garments involve nearly continuous collision contact and small wrinkles, that can be troublesome for traditional cloth simulation methods. Based on the observation that the wrinkles in close-fitting clothing behave in a predominantly kinematic fashion, we have developed an example-based wrinkle synthesis technique. Our method drives wrinkle generation from the pose of the figure’s kinematic skeleton. This approach allows high quality clothing wrinkles to be combined with a coarse cloth simulation that computes the global and dynamic aspects of the clothing motion. While the combined results do not exactly match a high-resolution reference simulation, they do capture many of the characteristic fine-scale features and wrinkles. Further, the combined system runs at interactive rates, making it suitable for applications where high-resolution offline simulations would not be a viable option. The wrinkle synthesis method uses a precomputed database built by simulating the high-resolution clothing as the articulated figure is moved over a range of poses. In principle, the space of poses is exponential in the total number of degrees of freedom; however clothing wrinkles are primarily affected by the nearest joints, allowing each joint to be processed independently. During synthesis, mesh interpolation is used to consider the influence of multiple joints, and combined with a coarse simulation to produce the final results at interactive rates.

Example-Based Wrinkle Synthesis for Clothing Animation

In this paper, we propose a simple and efficient framework for simulating dispersed bubble flow. Instead of modeling the complex hydrodynamics of numerous small bubbles explicitly, our method approximates the average motion of these bubbles using a continuum multiphase solver. Then, the subgrid interactions among bubbles are computed using our new stochastic solver. Using the proposed scheme, we can efficiently simulate complex scenes with millions of bubbles.

A Practical Simulation of Dispersed Bubble Flow

Collision detection is a problem that has often been addressed efficiently with the use of hierarchical culling data structures. In the subproblem of self-collision detection for triangle meshes, however, such hierarchical data structures lose much of their power, because triangles adjacent to each other cannot be distinguished from actually colliding ones unless individually tested. Shape regularity of surface patches, described in terms of orientation and contour conditions, was proposed long ago as a culling criterion for hierarchical self-collision detection. However, to date, algorithms based on shape regularity had to trade conservativeness for efficiency, because there was no known algorithm for efficiently performing 2D contour self-intersection tests. In this paper, we introduce a star-contour criterion that is amenable to hierarchical computations. Together with a thorough analysis of the tree traversal process in hierarchical self-collision detection, it has led us to novel hierarchical data structures and algorithms for efficient yet conservative self-collision detection. We demonstrate the application of our algorithm to several example animations, and we show that it consistently outperforms other approaches.

Star-Contours for Efficient Hierarchical Self-Collision Detection

We propose a mesh-based surface tracking method for fluid animation that both preserves fine surface details and robustly adjusts the topology of the surface in the presence of arbitrarily thin features like sheets and strands. We replace traditional re-sampling methods with a convex hull method for connecting surface features during topological changes. This technique permits arbitrarily thin fluid features with minimal re-sampling errors by reusing points from the original surface. We further reduce re-sampling artifacts with a subdivision-based mesh-stitching algorithm, and we use a higher order interpolating subdivision scheme to determine the location of any newly-created vertices. The resulting algorithm efficiently produces detailed fluid surfaces with arbitrarily thin features while maintaining a consistent topology with the underlying fluid simulation.

Physics-Inspired Topology Changes for Thin Fluid Features

We present an approach to simulate flows driven by surface tension based on triangle meshes. Our method consists of two simulation layers: the first layer is an Eulerian method for simulating surface tension forces that is free from typical strict time step constraints. The second simulation layer is a Lagrangian finite element method that simulates sub-grid scale wave details on the fluid surface. The surface wave simulation employs an unconditionally stable, symplectic time integration method that allows for a high propagation speed due to strong surface tension. Our approach can naturally separate the grid- and sub-grid scales based on a volume-preserving mean curvature flow. As our model for the sub-grid dynamics enforces a local conservation of mass, it leads to realistic pinch off and merging effects. In addition to this method for simulating dynamic surface tension effects, we also present an efficient non-oscillatory approximation for capturing damped surface tension behavior. These approaches allow us to efficiently simulate complex phenomena associated with strong surface tension, such as Rayleigh-Plateau instabilities and crown splashes, in a short amount of time.

A Multiscale Approach to Mesh-based Surface Tension

We develop an accurate, unified treatment of elastica. Following the method of resultant-based formulation to its logical extreme, we derive a higher-order integration rule, or elaston, measuring stretching, shearing, bending, and twisting along any axis. The theory and accompanying implementation do not distinguish between forms of different dimension (solids, shells, rods), nor between manifold regions and non-manifold junctions. Consequently, a single code accurately models a diverse range of elastoplastic behaviors, including buckling, writhing, cutting and merging. Emphasis on convergence to the continuum sets us apart from early unification efforts.

Unified Simulation of Elastic Rods, Shells, and Solids