Tetrahedral mesh generation for solids based on alternating sum of volumes

Decomposition of a three-dimensional non-convex polyhedral object into tetr ahedra using few or no 'Steiner' points assumes both theoretical and practi cal importance. It has been known that the determination of whether a polyh edron can be tetrahedralized is NP-complete. This prompts the investigation of the tetrahedralization of special classes of polyhedra, including conve x, star-shaped, monotone, and isothetic. This paper identifies a special cl ass of polyhedra that can be tetrahedralized without using 'Steiner' points . The proposed tetrahedralization algorithm utilizes a structure provided b y the alternating sum of volumes process (a convex decomposition method) so that a complex solid object can first be decomposed into a set of simpler objects, namely conjuncts. The concatenation of the tetrahedralization of t hese conjuncts gives rise to the tetrahedralization of the original solid o bject. (C) 2000 Elsevier Science B.V. AU rights reserved.