Tetrahedral meshes from planar cross-sections (Q1976169)

Conclusion: We present a new approach to build a three-dimensional triangular mesh from planar contours. There are two main contributions in this paper. The first contribution is the characterization, prevention, and postprocessing of untetrahedralizable parts. The tetrahedralizability characterization of a general polyhedron is shown to be NP-complete. Under reasonable constraints on degenerate problem domain, we characterize this problem based on a group operator, and develop a rule to reduce the chance of generating untetrahedralizable remaining parts. The characterization also helps the postprocessing of untetrahedralizable parts if they occur. The second contribution is an algorithm to reduce a non-prismatoid into one or more prismatoids. This algorithm is guaranteed to work on the non-prismatoids generated by a surface construction program.