Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision
(CS 528)
Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles
Jonathan Shewchuk
Computer Science Division
University of California at Berkeley
April 9, 2007, 4:15PM
TCSeq 200
http://graphics.stanford.edu/ba-colloquium/
Abstract
The isosurface stuffing algorithm fills an isosurface with a uniformly
sized tetrahedral mesh whose dihedral angles are bounded between
10.7 degrees and 165 degrees. All vertices on the boundary of the mesh
lie on the isosurface. 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. Isosurface stuffing is the first algorithm that simultaneously
copes with boundaries of complex shape and rigorously guarantees the
suitability of its tetrahedra for finite element methods. Our angle
bounds are guaranteed by a computer-assisted proof. We illustrate the
use of isosurface stuffing for dynamic remeshing in a fluid simulation
with moving liquid surfaces.