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


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.

About the Speaker

Jonathan Shewchuk is an Associate Professor in the Department of Electrical Engineering and Computer Sciences at UC Berkeley. He is best known for his Triangle software for high-quality triangular mesh generation, and his "Introduction to the Conjugate Gradient Method Without the Agonizing Pain".


Back to the Colloquium Page