SIGGRAPH Course: Data-Driven Simulation Methods in Computer Graphics: Cloth, Tissue, and Faces

Miguel Otaduy, Bernd Bickel, Derek Bradley, Huamin Wang

In recent years, the field of computer animation has witnessed the invention of multiple simulation methods that exploit pre-recorded data to improve the performance and/or realism of dynamic deformations. Various methods have been presented concurrently, and they present differences, but also similarities, that have not yet been analyzed or discussed. This course focuses on the application of data-driven methods to three areas of computer animation, namely dynamic deformation of faces, soft volumetric tissue, and cloth. The course describes the particular challenges tackled in a data-driven manner, classifies the various methods, and also shares insights for the application to other settings.

The explosion of data-driven animation methods and the success of their results make this course extremely timely. Up till now, the proposed methods have remained familiar only at the research context, and have not made their way through computer graphics industry. This course aims to fit two main purposes. First, present a common theory and understanding of data-driven methods for dynamic deformations that may inspire the development of novel solutions, and second, bridge the gap with industry, by making data-driven approaches accessible. The course targets an audience consisting of both researchers and programmers in computer animation.

Data-Driven Simulation Methods in Computer Graphics: Cloth, Tissue, and Faces

SIGGRAPH Course: FEM Simulation of 3D Deformable Solids: A practitioner's guide to theory, discretization and model reduction

Eftychios Sifakis and Jernej Barbic

A practical guide to finite-element-method (FEM) simulation of 3D deformable solids reviews essential offline FEM simulation techniques: complex nonlinear materials, invertible treatment of elasticity, and model-reduction techniques for real-time simulation.

Simulations of deformable solids are important in many applications in computer graphics, including film special effects, computer games, and virtual surgery. FEM has become a popular method in many applications. Both offline simulation and real-time techniques have matured in computer graphics literature.

This course is designed for attendees familiar with numerical simulation in computer graphics who would like to obtain a cohesive picture of the various FEM simulation methods available, their strengths and weaknesses, and their applicability in various simulation scenarios. The course is also a practical implementation guide for the visual-effects developer, offering a very lean yet adequate synopsis of the underlying mathematical theory. The first section introduces FEM deformable-object simulation and its fundamental concepts, such as deformation gradient, strain, stress, and elastic energy, discusses corotational FEM models, isotropic hyperelasticity, and numerical methods such as conjugate gradients and multigrid. The second section presents the state of the art in model reduction techniques for real-time FEM solid simulation. Topics include linear modal analysis, modal warping, subspace simulation, domain decomposition, and which techniques are suitable for which application.

FEM Simulation of 3D Deformable Solids: A practitioner’s guide to theory, discretization and model reduction

Controlling Liquids Using Meshes

Karthik Raveendran, Nils Thuerey, Chris Wojtan, Greg Turk

We present an approach for artist-directed animation of liquids using multiple levels of control over the simulation, ranging from the overall tracking of desired shapes to highly detailed secondary effects such as dripping streams, separating sheets of fluid, surface waves and ripples. The first portion of our technique is a volume preserving morph that allows the animator to produce a plausible fluid-like motion from a sparse set of control meshes. By rasterizing the resulting control meshes onto the simulation grid, the mesh velocities act as boundary conditions during the projection step of the fluid simulation. We can then blend this motion together with uncontrolled fluid velocities to achieve a more relaxed control over the fluid that captures natural inertial effects. Our method can produce highly detailed liquid surfaces with control over sub-grid details by using a mesh-based surface tracker on top of a coarse grid-based fluid simulation. We can create ripples and waves on the fluid surface attracting the surface mesh to the control mesh with spring-like forces and also by running a wave simulation over the surface mesh. Our video results demonstrate how our control scheme can be used to create animated characters and shapes that are made of water.

Controlling Liquids Using Meshes

Smoke Sheets for Graph-Structured Vortex Filaments

Alfred Barnat, Nancy S. Pollard

Smoke is one of the core phenomena which fluid simulation techniques in computer graphics have attempted to capture. It is both well understood mathematically and important in lending realism to computer generated effects. In an attempt to overcome the diffusion inherent to Eulerian grid-based simulators, a technique has recently been developed which represents velocity using a sparse set of vortex filaments. This has the advantage of providing an easily understandable and controllable model for fluid velocity, but is computationally expensive because each filament affects the fluid velocity over an unbounded region of the simulation space. We present an alternative to existing techniques which merge adjacent filament rings, instead allowing filaments to form arbitrary structures,and we develop a new set of reconnection criteria to take advantage of this filament graph. To complement this technique, we also introduce a method for smoke surface tracking and rendering designed to minimize the number of sample points without introducing excessive diffusion or blurring. Though this representation lends itself to straightforward real-time rendering, we also present a method which renders the thin sheets and curls of smoke as diffuse volumes using any GPU capable of supporting geometry shaders.

Smoke Sheets for Graph-Structured Vortex Filaments

Simulating Free Surface Flow with Very Large Timesteps

Michael Lentine, Matthew Cong, Saket Patkar, Ron Fedkiw

We provide a novel simulation method for incompressible free surface flows that allows for large time steps on the order of 10-40 times bigger than the typical explicit time step restriction would allow. Although semi-Lagrangian advection allows for this from the standpoint of stability, large time steps typically produce significant visual errors. This was addressed in previous work for smoke simulation using a mass and momentum conserving version of semi-Lagrangian advection, and while its extension to water for momentum conservation for small time steps was addressed, pronounced issues remain when taking large time steps. The main difference between smoke and water is that smoke has a globally defined velocity field whereas water needs to move in a manner uninfluenced by the surrounding air flow, and this poses real issues in determining an appropriate extrapolated velocity field. We alleviate problems with the extrapolated velocity field by not using it when it is incorrect, which we determine via conservative advection of a color function which adds forwardly advected semi-Lagrangian rays to maintain conservation when mass is lost. We note that one might also use a more traditional volume-of-fluid method which is more explicitly focused on the geometry of the interface but can be less visually appealing — it is also unclear how to extend volume-of-fluid methods to have larger time steps. Finally, we prefer the visual smoothness of a particle level set method coupled to a traditional backward tracing semi-Lagrangian advection where possible, only using our forward traced color function solution in areas of the flow where the particle level set method fails due to the extremely large time steps.

Simulating Free Surface Flow with Very Large Timesteps

Mass-Conserving Eulerian Liquid Simulation

Nuttapong Chentanez, Matthias Mueller

We present a GPU friendly, Eulerian, free surface fluid simulation method that conserves mass locally and globally without the use of Lagrangian components. Local mass conservation prevents small scale details of the free surface from disappearing, a problem that plagues many previous approaches, while global mass conservation ensures that the total volume of the liquid does not decrease over time. Our method handles moving solid boundaries as well as cells that are partially filled with solids. Due to its stability, it allows the use of large time steps which makes it suitable for both off-line and real-time applications. We achieve this by using density based surface tracking with a novel, unconditionally stable, conservative advection scheme and a novel interface sharpening method. While our approach conserves mass, volume loss is still possible but only temporarily. With constant mass, local volume loss causes a local increase of the density used for surface tracking which we detect and correct over time. We also propose a density post-processing method to reveal sub-grid details of the liquid surface. We show the effectiveness of the proposed method in several practical examples all running either at interactive rates or in real-time.

Mass-Conserving Eulerian Liquid Simulation

Efficient Collision Detection for Brittle Fracture

Loiez Glondu, Sarah Schvartzman, Maud Marchal, Georges Dumon, Miguel Otaduy

In complex scenes with many objects, collision detection plays a key role in the simulation performance. This is particularly true for fracture simulation, where multiple new objects are dynamically created. In this paper, we present novel algorithms and data structures for collision detection in real-time brittle fracture simulations. We build on a combination of well-known efficient data structures, namely distance fields and sphere trees, making our algorithm easy to integrate on existing simulation engines. We propose novel methods to construct these data structures, such that they can be efficiently updated upon fracture events and integrated in a simple yet effective self-adapting contact selection algorithm. Altogether, we drastically reduce the cost of both collision detection and collision response. We have evaluated our global solution for collision detection on challenging scenarios, achieving high frame rates suited for hard real-time applications such as video games or haptics. Our solution opens promising perspectives for complex brittle fracture simulations involving many dynamically created objects.

Efficient Collision Detection for Brittle Fracture

Mass-Splitting for Jitter-Free Parallel Rigid Body Simulation

Richard Tonge, Feodor Benevolenski, Andrey Voroshilov

We present a parallel iterative rigid body solver that avoids common artifacts at low iteration counts. In large or real-time simulations, iteration is often terminated before convergence to maximize scene size. If the distribution of the resulting residual energy varies too much from frame to frame, then bodies close to rest can visibly jitter. Projected Gauss-Seidel (PGS) distributes the residual according to the order in which contacts are processed, and preserving the order in parallel implementations is very challenging. In contrast, Jacobi-based methods provide order independence, but have slower convergence. We accelerate projected Jacobi by dividing each body mass term in the effective mass by the number of contacts acting on the body, but use the full mass to apply impulses. We further accelerate the method by solving contacts in blocks, providing wallclock performance competitive with PGS while avoiding visible artifacts. We prove convergence to the solution of the underlying linear complementarity problem and present results for our GPU implementation,which can simulate a pile of 5000 objects with no visible jittering at over 60 FPS.

Mass-Splitting for Jitter-Free Parallel Rigid Body Simulation

Deformable Objects Alive!

Stelian Coros, Sebastian Martin, Bernhard Thomaszewski, Christian Schumacher, Robert Sumner, Markus Gross

We present a method for controlling the motions of active deformable characters. As an underlying principle, we require that all motions be driven by internal deformations. We achieve this by dynamically adapting rest shapes in order to induce deformations that, together with environment interactions, result in purposeful and physically-plausible motions. Rest shape adaptation is a powerful concept and we show that by restricting shapes to suitable subspaces, it is possible to explicitly control the motion styles of deformable characters. Our formulation is general and can be combined with arbitrary elastic models and locomotion controllers. We demonstrate the efficiency of our method by animating curve, shell, and solid-based characters whose motion repertoires range from simple hopping to complex walking behaviors.

Deformable Objects Alive!

Energetically Consistent Invertible Elasticity

Alexey Stomakhin, Russell Howes, Craig Schroeder, Joseph Teran

We provide a smooth extension of arbitrary isotropic hyperelastic energy density functions to inverted confi gurations. This extension is designed to improve robustness for elasticity simulations with extremely large deformations and is analogous to the extension given to the first Piola-Kircho ff stress in [ITF04]. We show that our energy-based approach is signi ficantly more robust to large deformations than the first Piola-Kircho ff . Furthermore, we show that the robustness and stability of a hyper-elastic model can be predicted from a characteristic contour, which we call its primary contour. The extension to inverted con figurations is de fined via extrapolation from a convex threshold surface that lies in the uninverted portion of the principal stretches space. The extended hyperelastic energy density yields continuous stress and unambiguous stress derivatives in all inverted con figurations, unlike in [TSIF05]. We show that our invertible energy-density-based approach outperforms the popular hyperelastic corotated model, and we also show how to use the primary contour methodology to improve the robustness of this model to large deformations.

Energetically Consistent Invertible Elasticity