Author: christopherbatty

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

Simulation of Bubbles in Foam with the Volume Control Method

“Liquid and gas interactions often contain bubbles that stay for a
long time without bursting on the surface, making a dry foam structure.
Such long lasting bubbles simulated by the level set method
can suffer from a slow but steady volume error that accumulates
to a visible amount of volume change. We propose to address this
problem by using the volume control method. We trace the volume
change of each connected region, and apply a carefully computed
divergence that compensates undesired volume changes. To
compute the divergence, we construct a mathematical model of the
volume change, choose control strategies that regulate the modeled
volume error, and establish methods to compute the control gains
that provide robust and fast reduction of the volume error, and (if
desired) the control of how the volume changes over time.”

Simulation of Bubbles in Foam with the Volume Control Method

SIGGRAPH papers list

Tim Rowley and Ke-Sen Huang jointly maintain an updated list of upcoming SIGGRAPH papers as they get posted. Apparently there were 108 papers accepted this year, so odds are a healthy chunk of those will be filed under physics-based animation.

SIGGRAPH 2007 papers on the web

So far:

Fast Animation of Lightning Using an Adaptive Mesh

 “We present a fast method for simulating, animating, and rendering lightning using adaptive grids. The “dielectric breakdown model” is an elegant algorithm for electrical pattern formation that we extend to enable animation of lightning. The simulation can be slow, particularly in 3D, because it involves solving a large Poisson problem. Losasso et al. recently proposed an octree data structure for simulating water and smoke, and we show that this discretization can be applied to the problem of lightning simulation as well. However, implementing the incomplete Cholesky conjugate gradient (ICCG) solver for this problem can be daunting, so we provide an extensive discussion of implementation issues. ICCG solvers can usually be accelerated using “Eisenstat’s trick,” but the trick cannot be directly applied to the adaptive case. Fortunately, we show that an “almost incomplete Cholesky” factorization can be computed so that Eisenstat’s trick can still be used. We then present a fast rendering method based on convolution that is competitive with Monte Carlo ray tracing but orders of magnitude faster, and we also show how to further improve the visual results using jittering.”

Fast Animation of Lightning Using an Adaptive Mesh

Fracturing Rigid Materials

“We propose a novel approach to fracturing (and denting) brittle materials. To avoid the computational burden imposed by the stringent time step restrictions of explicit methods or with solving nonlinear systems of equations for implicit methods, we treat the material as a fully rigid body in the limit of infinite stiffness. In addition to a triangulated surface mesh and level set volume for collisions, each rigid body is outfitted with a tetrahedral mesh upon which finite element analysis can be carried out to provide a stress map for fracture criteria. We demonstrate that the commonly used stress criteria can lead to arbitrary fracture (especially for stiff materials) and instead propose the notion of a time averaged stress directly into the FEM analysis. When objects fracture, the virtual node algorithm provides new triangle and tetrahedral meshes in a straightforward and robust fashion. Although each new rigid body can be rasterized to obtain a new level set, small shards can be difficult to accurately resolve. Therefore, we propose a novel collision handling technique for treating both rigid bodies and rigid body thin shells represented by only a triangle mesh.”

Fracturing Rigid Materials

A Survey on Hair Modeling: Styling, Simulation, and Rendering

“Realistic hair modeling is a fundamental part of creating virtual humans in computer graphics. This paper surveys the state of the art in the major topics of hair modeling: hairstyling, hair simulation, and hair rendering. Because of the difficult, often unsolved problems that arise in alt these areas, a broad diversity of approaches is used, each with strengths that make it appropriate for particular applications. We discuss each of these major topics in turn, presenting the unique challenges facing each area and describing solutions that have been presented over the years to handle these complex issues. Finally, we outline some of the remaining computational challenges in hair modeling.”

A Survey on Hair Modeling: Styling, Simulation, and Rendering