Discrete approximations of a surface or volume are necessary in numerous computational applications that require models of geometric objects. These applications typically assume that the geometric domain under consideration is divided into small, simple pieces (typically triangles or quadrilaterals in two dimensions, and tetrahedra or hexahedra in three) called finite elements. The collection of finite elements is referred to as a mesh. One such important application area is medical imaging, where high-quality meshes for modeling anatomy, represented as voxel-based images, are critical for computer-assisted clinical analysis of medical data. Meshes made of quadrilateral/hexahedral (quad/hex) elements offer lower mesh complexity and better solution quality than their triangular/tetrahedral counterparts. However, the generation of quad/hex meshes for arbitrary three-dimensional geometries is a difficult problem, and algorithms to generate meshes with provable guarantees on quality are available only for some restricted types of input. This research addresses geometric, combinatorial, and algorithmic questions related to the generation of quadrilateral surface meshes and hexahedral volume meshes for three-dimensional geometries obtained from volumetric imaging data.
Tools from digital topology and graph theory will be exploited to design algorithms to generate quadrilateral meshes of guaranteed quality for surface representations of voxel-based images. Robust methods for hexahedral mesh generation for digital volumes will in turn be designed by utilizing quadrilateral surface meshing algorithms developed as part of this research. Many fundamental geometric questions related to quad/hex mesh generation remain unanswered. A formal understanding of these questions for the special types of geometries determined by volumetric imaging data is critical for the design of implementable algorithms that provide guarantees on mesh quality. This research project also involves collaboration with medical imaging experts, who will provide evaluation and validation of all meshing algorithms via finite element methods for three-dimensional, non-rigid image registration of volumetric MR images of human organs. Most image registration methods in current practice remain two-dimensional. Improved registration accuracy made possible by guaranteed-quality volume meshes would have enormous impact on clinical studies of medical data and greatly benefit medical practitioners.
