Guaranteed Quality Tetrahedral Delaunay Meshing for Medical Images

In this paper, we present a Delaunay refinement algorithm for meshing 3D medical images. We prove that (a) all the tetrahedra of the output mesh have ratio less than 2, (b) all the boundary facets have planar angles larger than 30 degrees, (c) the symmetric (2-sided) Hausdorff distance between the object surface and mesh boundary is bounded from above by a user-specified parameter, and (d) the mesh boundary is ambient isotopic to the object surface. The first two guarantees assure that our algorithm removes most of the poorly shaped elements, making the mesh suitable for subsequent finite element analysis. The last two guarantees assure that the mesh boundary is a good geometrical and topological approximation of the object surface. Our long term goal is to develop a real time image-to-mesh conversion algorithm; towards that direction, our algorithm recovers the object surface and meshes the interior volume at the same time without sampling the object surface as a preprocessing step, unlike other Delaunay meshing techniques. Experimental evaluation of our algorithm on real medical data corroborates the theory.