Energy Stability and Fracture for Frame Rate Rigid Body Simulations

Our goal is to design robust algorithms that can be used for building real-time systems, but rather than starting

with overly simplistic particle-based methods, we aim to modify higher-end visual effects algorithms. A major

stumbling block in utilizing these visual effects algorithms for real-time simulation is their computational intensity.

Physics engines struggle to fully exploit available resources to handle high scene complexity due to their need to

divide those resources among many smaller time steps, and thus to obtain the maximum spatial complexity we

design our algorithms to take only one time step per frame. This requires addressing both accuracy and stability

issues for collisions, contact, and evolution in a manner significantly different from a typical simulation in which

one can rely on shrinking the time step to ameliorate accuracy and stability issues. In this paper we present a

novel algorithm for conserving both energy and momentum when advancing rigid body orientations, as well as

a novel technique for clamping energy gain during contact and collisions. We also introduce a technique for fast

and realistic fracture of rigid bodies using a novel collision-centered prescoring algorithm.

Our goal is to design robust algorithms that can be used for building real-time systems, but rather than starting with overly simplistic particle-based methods, we aim to modify higher-end visual effects algorithms. A major stumbling block in utilizing these visual effects algorithms for real-time simulation is their computational intensity. Physics engines struggle to fully exploit available resources to handle high scene complexity due to their need to divide those resources among many smaller time steps, and thus to obtain the maximum spatial complexity we design our algorithms to take only one time step per frame. This requires addressing both accuracy and stability issues for collisions, contact, and evolution in a manner significantly different from a typical simulation in which one can rely on shrinking the time step to ameliorate accuracy and stability issues. In this paper we present a novel algorithm for conserving both energy and momentum when advancing rigid body orientations, as well as a novel technique for clamping energy gain during contact and collisions. We also introduce a technique for fast and realistic fracture of rigid bodies using a novel collision-centered prescoring algorithm.

Energy Stability and Fracture for Frame Rate Rigid Body Simulations

Thesis: Practical Water Animation Using Physics and Image Based Methods

Huamin Wang’s PhD thesis on liquid animation is available here:

Practical Water Animation Using Physics and Image Based Methods

Skipping Steps in Deformable Simulation with Online Model Reduction

Finite element simulations of nonlinear deformable models are computationally costly, routinely taking hours or days to compute the motion of detailed meshes. Dimensional model reduction can make simulations orders of magnitude faster, but is unsuitable for general deformable body simulations because it requires expensive precomputations, and it can suppress motion that lies outside the span of a pre-specified low-rank basis. We present an online model reduction method that does not have these limitations. In lieu of precomputation, we analyze the motion of the full model as the simulation progresses, incrementally building a reduced-order nonlinear model, and detecting when our reduced model is capable of performing the next timestep. For these subspace steps, full-model computation is “skipped” and replaced with a very fast (on the order of milliseconds) reduced order step. We present algorithms for both dynamic and quasistatic simulations, and a “throttle” parameter that allows a user to trade off between faster, approximate previews and slower, more conservative results. For detailed meshes undergoing low-rank motion, we have observed speedups of over an order of magnitude with our method.

Skipping Steps in Deformable Simulation with Online Model Reduction

Synthetic Turbulence using Artificial Boundary Layers

Turbulent vortices in fluid flows are crucial for a visually interesting appearance. Although there has been a significant amount of work on turbulence in graphics recently, these algorithms rely on the underlying simulation to resolve the flow around objects. We build upon work from classical fluid mechanics to design an algorithm that allows us to accurately precompute the turbulence being generated around an object immersed in a flow. This is made possible by modeling turbulence formation based on an averaged flow field, and relying on universal laws describing the flow near a wall. We precompute the confined vorticity in the boundary layer around an object, and simulate the boundary layer separation during a fluid simulation. Then, a turbulence model is used to identify areas where this separated layer will transition into actual turbulence. We sample these regions with vortex particles, and simulate the further dynamics of the vortices based on these particles. We will show how our method complements previous work on synthetic turbulence, and yields physically plausible results. In addition, we demonstrate that our method can efficiently compute turbulent flows around a variety of objects including cars, whisks, as well as boulders in a river flow. We can even apply our model to precomputed static flow fields, yielding turbulent dynamics without a costly simulation.

Synthetic Turbulence using Artificial Boundary Layers

Motion Field Texture Synthesis

A variety of animation effects such as herds and fluids contain detailed motion fields characterized by repetitive structures. Such detailed motion fields are often visually important, but tedious to specify manually or expensive to simulate computationally. Due to the repetitive nature, some of these motion fields (e.g. turbulence in fluids) could be synthesized by procedural texturing, but procedural texturing is known for its limited generality.

We apply example-based texture synthesis for motion fields. Our technique is general and can take on a variety of user inputs, including captured data, manual art, and physical/procedural simulation. This data-driven approach enables artistic effects that are difficult to achieve via previous methods, such as heart shaped swirls in fluid animation. Due to the use of texture synthesis, our method is able to populate a large output field from a small input exemplar, imposing minimum user workload. Our algorithm also allows the synthesis of output motion fields not only with the same dimension as the input (e.g. 2D to 2D) but also of higher dimension, such as 3D volumetric outputs from 2D planar inputs. This cross-dimension capability supports a convenient usage scenario, i.e. the user could simply supply 2D images and our method produces a 3D motion field with similar characteristics. The motion fields produced by our method are generic, and could be combined with a variety of large-scale low-resolution motions that are easy to specify either manually or computationally but lack the repetitive structures to be characterized as textures. We apply our technique to a variety of animation phenomena, including smoke, liquid, and group motion.

Motion Field Texture Synthesis

Stretching and Wiggling Liquids

This paper presents a novel framework for simulating the stretching and wiggling of liquids. We demonstrate that complex phase-interface dynamics can be effectively simulated by introducing the Eulerian vortex sheet method, which focuses on the vorticity at the interface (rather than the whole domain). We extend this model to provide user control for the production of visual effects. Then, the generated fluid flow creates complex surface details, such as thin and wiggling fluid sheets. To capture such high-frequency features efficiently, this work employs a denser grid for surface tracking in addition to the (coarser) simulation grid. In this context, the paper proposes a filter, called the liquid-biased filter, which is able to downsample the surface in the high-resolution grid into the coarse grid without unrealistic volume loss resulting from aliasing error. The proposed method, which runs on a single PC, realistically reproduces complex fluid scenes.

Stretching and Wiggling Liquids

SIGGRAPH Asia 2009

Ke-Sen’s list of SIGGRAPH Asia 2009 papers is starting to fill out.

Here’s some of the more physics-related ones:

• Stretching and Wiggling Liquids
• Skipping Steps in Deformable Simulation with Online Model Reduction
• Synthetic Turbulence using Artificial Boundary Layers
• Motion Field Texture Synthesis

Field3D

Sony has released an open source project that underpins their fluid simulation and volume rendering tools, called Field3D.

SCA 2009 Papers

The list of papers from the 2009 Symposium on Computer Animation have been up for a while at Ke-Sen Huang’s page.

Here’s the subset that fall most directly under physics-based animation:

• A Point-based Method for Animating Elastoplastic Solids
• Statistical Simulation of Rigid Bodies
• Anisotropic Friction for Deformable Surfaces and Solids
• Energy Stability and Fracture for Frame Rate Rigid Body Simulations
• Real-Time Deformation and Fracture in a Game Environment
• Guiding of Smoke Animations Through Variational Coupling of Simulations at Different Resolution
• Accurate Tangential Velocities For Solid Fluid Coupling
• Fast and Robust Tracking of Fluid Surfaces
• A Point-based Method for Animating Incompressible Flow

Guiding of Smoke Animations Through Variational Coupling of Simulations at Different Resolutions

We propose a novel approach to guiding of Eulerian-based smoke animations through coupling of simulations at different grid resolutions. Specifically we present a variational formulation that allows smoke animations to adopt the low-frequency features from a lower resolution simulation (or non-physical synthesis), while simultaneously developing higher frequencies. The overall motivation for this work is to address the fact that art-direction of smoke animations is notoriously tedious. Particularly a change in grid resolution can result in dramatic changes in the behavior of smoke animations, and existing methods for guiding either significantly lack high frequency detail or may result in undesired features developing over time. Provided that the bulk movement can be represented satisfactorily at low resolution, our technique effectively allows artists to prototype simulations at low resolution (where computations are fast) and subsequently add extra details without altering the overall “look and feel”. Our implementation is based on a customized multi-grid solver with memory-efficient data structures.

Guiding of Smoke Animations Through Variational Coupling of Simulations at Different Resolutions