Mesh generation from imaging data

Digital images from computerized tomography (CT) and magnetic resonance (MR) scanners can be used to create computer models of anatomical shapes. These models are typically used in biomedical applications for the purpose of physical simulation and visualization. In this thesis, we describe new algorithms for creating models from 2D and 3D binary digital images. Our models are meshes of 2D shapes represented by 2D binary digital images, and meshes of the surface of 3D shapes represented by 3D binary digital images. More specifically, this thesis contains the following two contributions: First, we give an algorithm for converting constrained triangular meshes of polygonal domains into constrained and strictly convex quadrilateral meshes of the same domain. Our algorithm has linear time in the number of triangles of the input triangular mesh, produces a bounded number of quadrilaterals, offers better bounds than similar algorithms that also produce strictly convex quadrilateral meshes of bounded size, and tends to preserve the grading of the input triangular mesh. We also present examples to demonstrate that our algorithm can be successfully used to create quadrilateral meshes from 2D binary digital images of anatomical shapes, such as the human brain. Second, we provide a new algorithm for generating simplicial surface meshes that approximate the boundary of 3D shapes represented by 3D binary digital images. Our algorithm is based on a simplified version of one of two known algorithms for generating provably good quality simplicial approximations of smooth, implicit surfaces. Provably good quality simplicial surfaces are very desirable for visualization purposes, and the main advantage of our algorithm is to offer this provable quality guarantee