Physics-Based Animation

Marek Misztal, Andreas Baerentzen

We present a novel, topology-adaptive method for deformable interface tracking, called the Deformable Simplicial Complex (DSC). In the DSC method, the interface is represented explicitly as a piecewise linear curve (in 2D) or surface (in 3D) which is a part of a discretization (triangulation/tetrahedralization) of the space, such that the interface can be retrieved as a set of faces separating triangles/tetrahedra marked as inside from the ones marked as outside (so it is also given implicitly). This representation allows robust topological adaptivity and, thanks to the explicit representation of the interface, it suffers only slightly from numerical diffusion. Furthermore, the use of an unstructured grid yields robust adaptive resolution. Also, topology control is simple in this setting. We present the strengths of the method in several examples: simple geometric flows, fluid simulation, point cloud reconstruction, and cut locus construction.

Topology Adaptive Interface Tracking using the Deformable Simplicial Complex

Changxi Zheng, Doug James

In this paper, we accelerate self-collision detection (SCD) for a deforming triangle mesh by exploiting the idea that a mesh cannot self collide unless it deforms enough. Unlike prior work on subspace self-collision culling which is restricted to low-rank deformation subspaces, our energy-based approach supports arbitrary mesh deformations while still being fast. Given a bounding volume hierarchy (BVH) for a triangle mesh, we precompute Energy-based Self-Collision Culling (ESCC) certificates on bounding-volume-related sub-meshes which indicate the amount of deformation energy required for it to self collide. After updating energy values at runtime, many bounding-volume self-collision queries can be culled using the ESCC certificates. We propose an affine-frame Laplacian-based energy definition which sports a highly optimized certificate preprocess, and fast runtime energy evaluation. The latter is performed hierarchically to amortize Laplacian energy and affine-frame estimation computations. ESCC supports both discrete and continuous SCD with detailed and nonsmooth geometry. We demonstrate significant culling on various examples, with SCD speed-ups up to 26X.

Energy-Based Self-Collision Culling for Arbitrary Mesh Deformation

Klaus Hildebrandt, Christian Schulz, Christoph von Tycowicz, Konrad Polthier

Creating motions of objects or characters that are physically plausible and follow an animator’s intent is a key task in computer animation. The spacetime constraints paradigm is a valuable approach to this problem, but it suffers from high computational costs. Based on spacetime constraints, we propose a framework for controlling the motion of deformable objects that offers interactive response times. This is achieved by a model reduction of the underlying variational problem, which combines dimension reduction, multipoint linearization, and decoupling of ODEs. After a preprocess, the cost for creating or editing a motion is reduced to solving a number of one-dimensional spacetime problems, whose solutions are the wiggly splines introduced by Kass and Anderson [2008]. We achieve interactive response times through a new fast and robust numerical scheme for solving the one-dimensional problems that is based on a closed-form representation of the wiggly splines.

Interactive Space-Time Control of Deformable Objects

Nadir Akinci, Markus Ihmsen, Gizem Akinci, Barbara Solenthaler, Matthias Teschner

We propose a momentum-conserving two-way coupling method of SPH fluids and arbitrary rigid objects based on hydrodynamic forces. Our approach samples the surface of rigid bodies with boundary particles that interact with the fluid, preventing deficiency issues and both spatial and temporal discontinuities. The problem of inhomogeneous boundary sampling is addressed by considering the relative contribution of a boundary particle to a physical quantity. This facilitates not only the initialization process but also allows the simulation of multiple dynamic objects. Thin structures consisting of only one layer or one line of boundary particles, and also non-manifold geometries can be handled without any additional treatment. We have integrated our approach into WCSPH and PCISPH, and demonstrate its stability and flexibility with several scenarios including multiphase flow.

Versatile Rigid-Fluid Coupling for Incompressible SPH

Bin Wang, Francois Faure, Dinesh Pai

A method for image-based contact detection and modeling, with guaranteed precision on the intersection volume, is presented. Unlike previous image-based methods, our method optimizes a non-uniform ray sampling resolution and allows precise control of the volume error. By cumulatively projecting all mesh edges into a generalized 2D texture, we construct a novel data structure, the Error Bound Polynomial Image (EBPI), which allows efficient computation of the maximum volume error as a function of ray density. Based on a precision criterion, EBPI pixels are subdivided or clustered. The rays are then cast in the projection direction according to the non-uniform resolution. The EBPI data, combined with ray-surface intersection points and normals, is also used to detect transient edges at surface intersections. This allows us to model intersection volumes at arbitrary resolution, while avoiding the geometric computation of mesh intersections. Moreover, the ray casting acceleration data structures can be reused for the generation of high quality images.

Adaptive Image-Based Intersection Volume

Junggon Kim, Nancy Pollard

We propose a fast physically based simulation system for skeleton-driven deformable body characters. Our system can generate realistic motions of self-propelled deformable body characters by considering the two-way interactions among the skeleton, the deformable body, and the environment in the dynamic simulation. It can also compute the passive jiggling behavior of a deformable body driven by a kinematic skeletal motion. We show that a well-coordinated combination of (1) a reduced deformable body model with nonlinear finite elements, (2) a linear-time algorithm for skeleton dynamics, and (3) explicit integration can boost simulation speed to orders of magnitude faster than existing methods, while preserving modeling accuracy as much as possible. Parallel computation on the GPU has also been implemented to obtain an additional speedup for complicated characters. Detailed discussions of our engineering decisions for speed and accuracy of the simulation system are presented in the paper. We tested our approach with a variety of skeleton-driven deformable body characters, and the tested characters were simulated in real-time or near real-time.

Fast Simulation of Skeleton-Driven Deformable Body Characters

Jie Tan, Greg Turk, Karen Liu

We present a physically-based system to simulate and control the locomotion of soft body characters without skeletons. We use the finite element method to simulate the deformation of the soft body, and we instrument a character with muscle fibers to allow it to actively control its shape. To perform locomotion, we use a variety of intuitive controls such as moving a point on the character, specifying the center of mass or the angular momentum, and maintaining balance. These controllers yield an objective function that is passed to our optimization solver, which handles convex quadratic program with linear complementarity constraints. This solver determines the new muscle fiber lengths, and moreover it determines whether each point of contact should remain static, slide, or lift away from the floor. Our system can automatically find an appropriate combination of muscle contractions that enables a soft character to fulfill various locomotion tasks, including walking, jumping, crawling, rolling and balancing.

Soft Body Locomotion

Morten Bojsen-Hansen, Hao Li, Chris Wojtan

We present a method for recovering a temporally coherent, deforming triangle mesh with arbitrarily changing topology from an incoherent sequence of static closed surfaces. We solve this problem using the surface geometry alone, without any prior information like surface templates or velocity fields. Our system combines a proven strategy for triangle mesh improvement, a robust multi-resolution non-rigid registration routine, and a reliable technique for changing surface mesh topology. We also introduce a novel topological constraint enforcement algorithm to ensure that the output and input always have similar topology. We apply our technique to a series of diverse input data from video reconstructions, physics simulations, and artistic morphs. The structured output of our algorithm allows us to efficiently track information like colors and displacement maps, recover velocity information, and solve PDEs on the mesh as a post process.

Tracking Surfaces with Evolving Topology

Gizem Akinci, Markus Ihmsen, Nadir Akinci, Matthias Teschner

This paper presents a novel method that improves the efficiency of high-quality surface reconstructions for particle-based fluids using Marching Cubes. By constructing the scalar field only in a narrow band around the surface, the computational complexity and the memory consumption scale with the fluid surface instead of the volume. Furthermore, a parallel implementation of the method is proposed. The presented method works with various scalar field construction approaches. Experiments show that our method reconstructs high-quality surface meshes efficiently even on single-core CPUs. It scales nearly linearly on multi-core CPUs and runs up to fifty times faster on GPUs compared to the original scalar field construction approaches.

Parallel Surface Reconstruction for Particle-Based Fluids

Markus Ihmsen, Nadir Akinci, Gizem Akinci, Matthias Teschner

We present a new model for diffuse material, i.e. water–air mixtures, that can be combined with particle-based fluids. Diffuse material is uniformly represented with particles which are classified into spray, foam and air bubbles. Physically motivated rules are employed to generate, advect and dissipate diffuse material. The approach is realized as a post-processing step which enables efficient processing and versatile handling. As interparticle forces and the influence of diffuse material onto the fluid are neglected, large numbers of diffuse particles are efficiently processed to realize highly detailed small-scale effects. The presented results show that our approach can significantly improve the visual realism of large-scale fluid simulations.

Unified Spray, Foam, and Bubbles for Particle-Based Fluids