A central tool in scientific computing and computer animation is the finite element method, whose success depends on the quality of the meshes used to model the complicated underlying geometries. We develop two new methods for creating high-quality tetrahedral meshes: one with guaranteed good dihedral angles, and one that in practice produces far better dihedral angles than any prior method. 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. 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. Our angle bounds are guaranteed by a computer-assisted proof. Our second contribution is a mesh improvement method that uses optimization-based smoothing, topological transformations, and vertex insertions and deletions to achieve extremely high quality tetrahedra.

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, which won the 2003 James Hardy Wilkinson Prize in Numerical Software, and his 'Introduction to the Conjugate Gradient Method Without the Agonizing Pain'.