Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles
Abstract
The isosurface stuffing algorithm fills an isosurface with a uniformly sized tetrahedral mesh whose dihedral angles are bounded between 10.7o and 164.8o, or (with a change in parameters) between 8.9o and 158.8o. 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.
Citation
François Labelle and Jonathan Richard Shewchuk. "Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles". ACM Transactions on Graphics, 26(3):57.1–57.10, July 2007. Special issue on Proceedings of SIGGRAPH 2007.