Interactive Space-Time Control of Deformable Objects

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

Adaptive Image-Based Intersection Volume

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

Fast Simulation of Skeleton-Driven Deformable Body Characters

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

Soft Body Locomotion

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

Interactive Editing of Deformable Simulations

Jernej Barbic, Funshing Sin, Eitan Grinspun

We present an interactive animation editor for complex deformable object animations. Given an existing animation, the artist directly manipulates the deformable body at any time frame, and the surrounding animation immediately adjusts in response. The automatic adjustments are designed to respect physics, preserve detail in both the input motion and geometry, respect prescribed bilateral contact constraints, and controllably and smoothly decay in spacetime. While the utility of interactive editing for rigid body and articulated figure animations is widely recognized, a corresponding approach to deformable bodies has not been technically feasible before. We achieve interactive rates by combining spacetime model reduction, rotation-strain coordinate warping, linearized elasticity, and direct manipulation. This direct editing tool can serve the final stages of animation production, which often call for detailed, direct adjustments that are otherwise tedious to realize by re-simulation or frame-by-frame editing.

Interactive Editing of Deformable Simulations

Stress Relief: Improving Structural Strength of 3D Printable Objects

Ondrej Stava, Juraj Vanek, Bedrich Benes, Nathan Carr, Radomir Mech

3D printing is a rapidly maturing area that has shown great progress over the past couple of years. It is now possible to produce 3D printed objects with exceptionally high fidelity and precision. However, while the quality of 3D printing has gone up, both the time to print and material costs have remained high. Moreover, there is no guarantee that a printed model is structurally sound. Many times, the printed product does not survive cleaning, transportation, or handling, or it even collapses under its own weight. We present a system that addresses this issue by providing automatic detection and correction of the problematic cases. The structural problems are detected by combining a lightweight structure analysis solver with 3D medial axis approximations. After areas with high structural stress are found, the model is corrected by combining three approaches: hollowing, thickening, and strut insertion. This detection and correction repeats until all problematic cases are corrected. Our process is designed to create a model that is visually similar to the original model, while possessing greater structural integrity

Stress Relief: Improving Structural Strength of 3D Printable Objects

Continuous Penalty Forces

Min Tang, Dinesh Manocha, Miguel Otaduy, Ruofeng Tong

We present a simple algorithm to compute continuous penalty forces to determine collision response between rigid and deformable models bounded by triangle meshes. Our algorithm provides a well-behaved solution in contrast to the traditional stability and robustness problems of penalty methods, induced by force discontinuities. We trace contact features along their deforming trajectories and accumulate penalty forces along the penetration time intervals between the overlapping feature pairs. Moreover, we present a closed-form expression to compute the continuous and smooth collision response. Our method has very small additional overhead compared to previous penalty methods, while significantly improves the stability and robustness. We highlight its benefits on several benchmarks.

Continuous Penalty Forces

Updated Sparse Cholesky Factors for Corotational Elastodynamics

Florian Hecht, Yeon Jin Lee, Jonathan Shewchuk, James O’Brien

We present warp-canceling corotation, a nonlinear finite element formulation for elastodynamic simulation that achieves fast performance by making only partial or delayed changes to the simulation’s linearized system matrices. Coupled with an algorithm for incremental updates to a sparse Cholesky factorization, the method realizes the stability and scalability of a sparse direct method without the need for expensive refactorization at each time step. This finite element formulation combines the widely used corotational method with stiffness warping so that changes in the per-element rotations are initially approximated by inexpensive per-node rotations. When the errors of this approximation grow too large, the per-element rotations are selectively corrected by updating parts of the matrix chosen according to locally measured errors. These changes to the system matrix are propagated to its Cholesky factor by incremental updates that are much faster than refactoring the matrix from scratch. A nested dissection ordering of the system matrix gives rise to a hierarchical factorization in which changes to the system matrix cause limited, well-structured changes to the Cholesky factor. We show examples of simulations that demonstrate that the proposed formulation produces results that are visually comparable to those produced by a standard corotational formulation. Because our method requires computing only partial updates of the Cholesky factor, it is substantially faster than full refactorization and outperforms widely used iterative methods such as preconditioned conjugate gradients. Our method supports a controlled trade-off between accuracy and speed, and unlike most iterative methods its performance does not slow for stiffer materials but rather it actually improves.

Updated Sparse Cholesky Factors for Corotational Elastodynamics

Adding Physics to Characters Using Oriented Particles

Matthias Muller, Nuttapong Chentanez

We present a method to enhance the realism of animated characters by adding physically based secondary motion to deformable parts such as cloth, skin or hair. To this end, we extend the oriented particles approach to incorporate animation information. In addition, we introduce techniques to increase the stability of the original method in order to make it suitable for the fast and sudden motions that typically occur in computer games. We also propose a method for the semi-automatic creation of particle representations from arbitrary visual meshes. This way, our technique allows us to simulate complex geometry such as hair, thick cloth with ornaments and multi-layered clothing, all interacting with each other and the animated character.

Adding Physics to Characters Using Oriented Particles

VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes

Min Tang, Dinesh Manocha, Sung-Eui Yoon, Peng Du, Jae-Pil Heo, Ruofeng Tong

We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. Moreover, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.

VolCCD: Fast Continuous Collision Culling Between Deforming Volume Meshes