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.