Month: May 2007

Continuous Collision Detection for Articulated Models using Taylor Models and Temporal Culling

“We present a fast continuous collision detection (CCD) algorithm for articulated models using Taylor models and temporal culling. Our algorithm is a generalization of conservative advancement (CA) from convex models [Mirtich 1996] to articulated models with non-convex links. Given the initial and final configurations of a moving articulated model, our algorithm creates a continuous motion with constant translational and rotational velocities for each link, and checks for interferences between the articulated model under continuous motion and other models in the environment and for self-collisions. If collisions occur, our algorithm reports the first time of contact (TOC) as well as collision witness features. We have implemented our CCD algorithm and applied it to several challenging scenarios including locomotion generation, articulated body dynamics and character motion planning. Our algorithm can perform CCDs including self-collisions for articulated models consisting of many links and tens of thousands of triangles in 1.22 ms on average running on a 3.6 GHz Pentium 4 PC. This is an improvement on the performance of prior algorithms of more than an order of magnitude.”

Continuous Collision Detection for Articulated Models using Taylor Models and Temporal Culling

Adaptively Sampled Particle Fluids

“We present novel adaptive sampling algorithms for particle-based
fluid simulation. We introduce a sampling condition based on geometric
local feature size that allows focusing computational resources
in geometrically complex regions, while reducing the number
of particles deep inside the fluid or near thick flat surfaces. Further
performance gains are achieved by varying the sampling density
according to visual importance. In addition, we propose a novel
fluid surface definition based on approximate particle–to–surface
distances that are carried along with the particles and updated appropriately.
The resulting surface reconstruction method has several
advantages over existing methods, including stability under
particle resampling and suitability for representing smooth flat surfaces.
We demonstrate how our adaptive sampling and distancebased
surface reconstruction algorithms lead to significant improvements
in time and memory as compared to single resolution particle
simulations, without significantly affecting the fluid flow behavior.”

Adaptively Sampled Particle Fluids

Isosurface Stuffing: Fast Tetrahedral Meshing with Good Dihedral Angles

“The isosurface stuffing algorithm fills an isosurface with a uniformly
sized tetrahedral mesh whose dihedral angles are bounded
between 10.7◦ and 164.8◦, or (with a change in parameters) between
8.9◦ and 158.8◦. The algorithm is whip fast, numerically robust,
and easy to implement because, like Marching Cubes, it generates
tetrahedra from a small set of precomputed stencils. A variant
of the algorithm creates a mesh with internal grading: on the boundary,
where high resolution is generally desired, the elements are fine
and uniformly sized, and in the interior they may be coarser and
vary in size. This combination of features makes isosurface stuffing
a powerful tool for dynamic fluid simulation, large-deformation
mechanics, and applications that require interactive remeshing or
use objects defined by smooth implicit surfaces. It is the first algorithm
that rigorously guarantees the suitability of tetrahedra for
finite element methods in domains whose shapes are substantially
more challenging than boxes. Our angle bounds are guaranteed by
a computer-assisted proof. If the isosurface is a smooth 2-manifold
with bounded curvature, and the tetrahedra are sufficiently small,
then the boundary of the mesh is guaranteed to be a geometrically
and topologically accurate approximation of the isosurface.”

Isosurface Stuffing: Fast Tetrahedral Meshing with Good Dihedral Angles

Again, although this is a geometry paper at heart, it has obvious applications to fluids and finite element simulation, so it’s definitely relevant. And allow me to editorialize for a moment and say, wow, that’s fast.

A Finite Element Method for Animating Large Viscoplastic Flow

“We present an extension to Lagrangian finite element methods to allow for large plastic deformations of solid materials. These behaviors are seen in such everyday materials as shampoo, dough, and clay as well as in fantastic gooey and blobby creatures in special effects scenes. To account for plastic deformation, we explicitly update the linear basis functions defined over the finite elements during each simulation step. When these updates cause the basis functions to become ill-conditioned, we remesh the simulation domain to produce a new high-quality finite-element mesh, taking care to preserve the original boundary. We also introduce an enhanced plasticity model that preserves volume and includes creep and work hardening/softening. We demonstrate our approach with simulations of synthetic objects that squish, dent, and flow. To validate our methods, we compare simulation results to videos of real materials.”

A Finite Element Method for Animating Large Viscoplastic Flow

A Fast Variational Framework for Accurate Solid-Fluid Coupling

“Physical simulation has emerged as a compelling animation technique, yet current approaches to coupling simulations of fluids and solids with irregular boundary geometry are inefficient or cannot handle some relevant scenarios robustly. We propose a new variational approach which allows robust and accurate solution on relatively coarse Cartesian grids, allowing possibly orders of magnitude faster simulation. By rephrasing the classical pressure projection step as a kinetic energy minimization, broadly similar to modern approaches to rigid body contact, we permit a robust coupling between fluid and arbitrary solid simulations that always gives a well-posed symmetric positive semi-definite linear system. We provide several examples of efficient fluid-solid interaction and rigid body coupling with sub-grid cell flow. In addition, we extend the framework with a new boundary condition for free-surface flow, allowing fluid to separate naturally from solids.”

A Fast Variational Framework for Accurate Solid-Fluid Coupling

A Variational Approach to Eulerian Geometry Processing

“We present a purely Eulerian framework for geometry processing of surfaces and foliations. Contrary to current Eulerian methods used in graphics, we use conservative methods and a variational interpretation, offering a unified framework for routine surface operations such as smoothing, offsetting, and animation. Computations are performed on a fixed volumetric grid without recourse to Lagrangian techniques such as triangle meshes, particles, or path tracing. At the core of our approach is the use of the Coarea Formula to express area integrals over isosurfaces as volume integrals. This enables the simultaneous processing of multiple isosurfaces, while a single interface can be treated as the special case of a dense foliation. We show that our method is a powerful alternative to conventional geometric representations in delicate cases such as the handling of high-genus surfaces, weighted offsetting, foliation smoothing of medical datasets, and incompressible fluid animation.”

 A Variational Approach to Eulerian Geometry Processing

While ostensibly a geometry processing paper, it would appear to have applications to surface tracking for liquid animation, so I’m going include it.

Curl-Noise for Procedural Fluid Flow

“Procedural methods for animating turbulent fluid are often preferred over simulation, both for speed and for the degree of animator control. We offer an extremely simple approach to efficiently generating turbulent velocity fields based on Perlin noise, with a formula that is exactly incompressible (necessary for the characteristic look of everyday fluids), exactly respects solid boundaries (not allowing fluid to flow through arbitrarily-specified surfaces), and whose amplitude can be modulated in space as desired. In addition, we demonstrate how to combine this with procedural primitives for flow around moving rigid objects, vortices, etc.”

 Curl-Noise for Procedural Fluid Flow