Tetrahedral meshes from planar cross-sections ☆

Abstract In biomedicine, many three-dimensional (3D) objects are sampled in terms of slices such as computed tomography (CT), magnetic resonance imaging (MRI), and ultrasound imaging. It is often necessary to construct surface meshes from the cross sections for visualization, and thereafter construct tetrahedra for the solid bounded by the surface meshes for the purpose of finite element analysis. In Ref. [1] (C. Bajaj, E. Coyle and K. Lin, Graphical Models and Image Processing 58 (6) (1996) 524–543), we provided a solution to the construction of a surface triangular mesh from planar -section contours. Here we provide an approach to tetrahedralize the solid region bounded by planar contours and the surface mesh. It is a difficult task because the solid can be of high genus (several through holes) as well as have complicated branching regions. We develop an algorithm to effectively reduce the solid into prismatoids, and provide an approach to tetrahedralize the prismatoids. Our tetrahedralization approach is similar to the advancing front technique (AFT) for its flexible control of mesh quality. The main criticism of AFT is that the remaining interior may be badly shaped or even untetrahedralizable. The emphasis of our prismatoid tetrahedralization approach is on the characterization and prevention of untetrahedralizable parts. Ruppert and Seidel (J. Ruppert, R. Seidel, On the difficulty of tetrahedralizing three-dimensional non-convex polyhedra, in: Proceedings 5th Annual ACM Symposium Comput. Geom., 1989, p. 380–392) have shown that the problem of deciding whether a polyhedron is tetrahedralizable without adding Steiner points is NP-complete. We characterize this problem under certain constraints, and design one rule to reduce the chance of generating untetrahedralizable shapes. The characterization also leads to the classification of two common untetrahedralizable categories which can be better processed if they do occur.