Tetrahedral meshes from planar cross-sections

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 tetrahe dra for the solid bounded by the surface meshes for the purpose of finite e lement analysis. in Ref. [1] (C. Bajaj, E. Coyle and K. Lin. Graphical Mode ls and Image Processing 58 (6) (1996) 524-543), we provided a solution to t he 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 s olid can be of high genus (several through holes) as well as have complicat ed branching regions. We develop an algorithm to effectively reduce the sol id into prismatoids, and provide an approach to tetrahedralize the prismato ids. Our tetrahedralization approach is similar to the advancing Rent techn ique (AFT) for its flexible control of mesh quality. The main criticism of AFT ii that the remaining interior may be badly shaped or even untetrahedra lizable. The emphasis of our prismatoid tetrahedralization approach is on t he characterization and prevention of untetrahedralizable parts. Ruppert an d Seidel (J. Ruppert, R. Seidel, On the difficulty of tetrahedralizing thre e-dimensional non-convex polyhedra, in: Proceedings 5th Annual ACM Symposiu m 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 de sign one rule to reduce the chance of generating untetrahedralizable shapes . The characterization also leads to the classification of two common untet rahedralizable categories which can be better processed if they do occur. ( C) 1999 Elsevier Science S.A All rights reserved.