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

Statistical Simulation of Rigid Bodies

We describe a method for replacing certain stages of rigid body simulation with a statistically-based approximation. We begin by collecting statistical data regarding changes in linear and angular momentum for collisions of a given object. From this data we extract a statistical “signature” for the object, giving a compact representation of the object’s response to collision events. During object simulation, both the collision detection and the collision response calculations are replaced by simpler calculations based on the statistical signature. Using this approach, we are able to achieve significant improvement in the performance of rigid body simulation. The statistical behavior of the simulation is maintained, including achieving valid resting positions. We present results from a variety of simulations that demonstrate the method and its performance improvement. The method is appropriate for rigid body simulation situations requiring significant performance improvement, and allowing for some loss in fidelity

Statistical Simulation of Rigid Bodies