Physics-Based Animation

We present a new shape-matching deformation model that allows for efficient handling of topological changes and dynamic adaptive selection of levels of detail. Similar to the recently presented Fast Lattice Shape Matching (FLSM), we compute the position of simulation nodes by convolution of rigid shape matching operators on many overlapping regions, but we rely instead on octree-based hierarchical sampling and an interval-based region definition. Our approach enjoys the efficiency and robustness of shape-matching deformation models, and the same algorithmic simplicity and linear cost as FLSM, but it eliminates its dense sampling requirements. Our method can handle adaptive spatial discretizations, allowing the simulation of more degrees of freedom in arbitrary regions of interest at little additional cost. The method is also versatile, as it can simulate elastic and plastic deformation, it can handle cuts interactively, and it reuses the underlying data structures for efficient handling of (self-)collisions. All this makes it especially useful for interactive applications such as videogames.

Fast Adaptive Shape Matching Deformations

The 2008 edition of the annual unofficial list of SIGGRAPH papers is up.

It’s looking like a big year for physics – just over 14% so far…

• Fast Viscoelastic Behavior with Thin Features
• Backward Steps in Rigid Body Simulations
• Bubbles Alive
• Porous Flow in Particle-Based Fluid Simulations
• Animating developable surfaces using nonconforming elements
• Spline Joints for Multibody Dynamics
• Feedback Control of Cumuliform Cloud Formation based on Computational Fluid Dynamics
• Discrete Elastic Rods
• Robust Treatment of Simultaneous Collisions
• Two-way Coupling of Fluids to Rigid and Deformable Solids and Shells
• A Mass Spring Model for Hair Simulation
• Wavelet Turbulence for Fluid Simulation
• Simulating Knitted Cloth at the Yarn Level

The list of papers accepted to the 2008 Symposium on Computer Animation is up here.

The physics-oriented subset of those papers:

• Evolving Sub-Grid Turbulence for Smoke Animation
• Low Viscosity Flow Simulations for Animation
• Visual Simulation of Shockwaves
• Fast Adaptive Shape Matching Deformations
• Two-way Coupling of Rigid and Deformable Bodies
• Flexible Simulation of Deformable Models Using Discontinuous Galerkin FEM
• Globally Coupled Impulse-Based Collision Handling for Cloth Simulation
• Image-based Collision Detection and Response between Arbitrary Volumetric Objects
• Interactive Terrain Modeling Using Hydraulic Erosion
• Density Contrast SPH Interfaces
• Accurate Viscous Free Surfaces for Buckling, Coiling and Rotating Liquids

We present a combination of techniques to simulate turbulent fluid flows in 3D. Flow in a complex domain is modeled using a regular rectilinear grid with a finite-difference solution to the incompressible Navier-Stokes equations. We propose the use of the QUICK advection algorithm over a globally high resolution grid. To calculate pressure over the grid, we introduce the Iterated Orthogonal Projection (IOP) framework. In IOP a series of orthogonal projections ensures that multiple conditions such as non-divergence and boundary conditions arising through complex domains shapes or moving objects will be satisfied simultaneously to specified accuracy. This framework allows us to use a simple and highly efficient multigrid method to enforce non-divergence in combination with complex domain boundary conditions. IOP is amenable to GPU implementation, resulting in over an order of magnitude improvement over a CPU-based solver. We analyze the impact of these algorithms on the turbulent energy cascade in simulated fluid flows and the resulting visual quality.

Low Viscosity Flow Simulations for Animation

To simulate multiple fluids realistically many important interaction effects have to be captured accurately.
Smoothed Particle Hydrodynamics (SPH) has shown to be a simple, yet flexible method to cope with many fluid simulation problems in a robust way. Unfortunately, the results obtained when using SPH to simulate miscible fluids are severely affected, especially if density ratios become large. The undesirable effects reach from unphysical density and pressure variations to spurious and unnatural interface tensions, as well as severe numerical instabilities. In this work, we present a formulation based on SPH which can handle density discontinuities at interfaces between multiple fluids correctly without increasing the computational costs compared to standard SPH. The basic idea is to replace the density computation in SPH by a measure of particle densities and consequently derive new formulations for pressure and viscous forces. The new method enables the user to select the desired amount of interface tension according to the simulation problem at hand. We succeed to stably simulate multiple fluids with high density contrasts without the above described artifacts apparent in standard SPH simulations.

Density Contrast SPH Interfaces

We propose a framework for the full two-way coupling of rigid and deformable bodies, which is achieved with both a unified time integration scheme as well as individual two-way coupled algorithms at each point of that scheme. As our algorithm is two-way coupled in every fashion, we do not require ad hoc methods for dealing with stability issues or interleaving parts of the simulation. We maintain the ability to treat the key desirable aspects of rigid bodies (e.g. contact, collision, stacking, and friction) and deformable bodies (e.g. arbitrary constitutive models, thin shells, and self-collisions). In addition, our simulation framework supports more advanced features such as proportional derivative controlled articulation between rigid bodies. This not only allows for the robust simulation of a number of new phenomena, but also directly lends itself to the design of deformable creatures with proportional derivative controlled articulated rigid skeletons that interact in a life-like way with their environment.

Two-way Coupling of Rigid and Deformable Bodies

We propose a novel solid/fluid coupling method that treats the coupled system in a fully implicit manner making it stable for arbitrary time steps, large density ratios, etc. In contrast to previous work in computer graphics, we derive our method using a simple back-of-the-envelope approach which lumps the solid and fluid momenta together, and which we show exactly conserves the momentum of the coupled system. Notably, our method uses the standard Cartesian fluid discretization and does not require (moving) conforming tetrahedral meshes or ALE frameworks. Furthermore, we use a standard Lagrangian framework for the solid, thus supporting arbitrary solid constitutive models, both implicit and explicit time integration, etc. The method is quite general, working for smoke, water, and multiphase fluids as well as both rigid and deformable solids, and both volumes and thin shells. Rigid shells and cloth are handled automatically without special treatment, and we support fully one-sided discretizations without leaking. Our equations are fully symmetric, allowing for the use of fast solvers, which is a natural result of properly conserving momentum. Finally, for simple explicit time integration of rigid bodies, we show that our equations reduce to a form similar to previous work via a single block Gaussian elimination operation, but that this approach scales poorly, i.e. as though in four spatial dimensions rather than three.

Two-Way Coupling of Fluids to Rigid and Deformable Solids and Shells

We introduce a simple turbulence model for smoke animation, qualitatively capturing the transport, diffusion, and spectral cascade of turbulent energy unresolved on a typical simulation grid. We track the mean kinetic energy per octave of turbulence in each grid cell, and a novel “net rotation” variable for modeling the self-advection of turbulent eddies. These additions to a standard fluid solver drive a procedural post-process, layering plausible dynamically evolving turbulent details on top of the large-scale simulated motion. Finally, to make the most of the simulation grid before jumping to procedural sub-grid models, we propose a new multistep predictor to alleviate the nonphysical dissipation of angular momentum in standard graphics fluid solvers.

Evolving Sub-Grid Turbulence for Smoke Animation

We present a new image-based method to process contacts between objects bounded by triangular surfaces. Unlike previous methods, it relies on image-based volume minimization, which eliminates complex geometrical computations and robustly handles deep intersections.  The surfaces are rasterized in three orthogonal directions, and intersections are detected based on pixel depth and normal orientation. Per-pixel contact forces are computed and accumulated at the vertices. We show how to compute pressure forces which serve to minimize the intersection volume, as well as friction forces. No geometrical precomputation is required, which makes the method efficient for both deformable and rigid objects. We demonstrate it on rigid, skinned, and particle-based physical models with detailed surfaces in contacts at interactive frame rates.

Image-based Collision Detection and Response between Arbitrary Volume Objects

In this paper we simulate high resolution cloth consisting of up to 2 million triangles which allows us to achieve highly detailed folds and wrinkles. Since the level of detail is also influenced by object collision and self collision, we propose a more accurate model for cloth-object friction. We also propose a robust history-based repulsion/collision framework where repulsions are treated accurately and efficiently on a per time step basis. Distributed memory parallelism is used for both time evolution and collisions and we specifically address Gauss-Seidel ordering of repulsion/collision response. This algorithm is demonstrated by several high-resolution and high-fidelity simulations.

Robust High-Resolution Cloth using Parallelism, History-Based Collisions and Accurate Friction