Implementation of an Algorithm to Approximate Constrained Tetrahedrizations with Pre-specified Triangular Faces




Collins, Brian J.

Journal Title

Journal ISSN

Volume Title



A tetrahedrization is a decomposition of a region in space into tetrahedra. It is not always possible to construct a tetrahedrization that contains prespecified facets. There is an unimplemented algorithm for producing a reasonably efficient approximate solution. Given points and triangles that intersect in (possibly empty) mutual faces, a binary space partition is used to define subregions of the convex hull of the input. The planar boundary faces of these subregions are triangulated with constraints, and the subregions are covered with tetrahedra that preserve the boundary triangles. The constraints are such that the set of tetrahedra is a tetrahedrization and the specified triangles are unions of facets of tetrahedra. An Object-Oriented analysis, an Object-Oriented design, and a C++ implementation of an algorithm to split the convex hull of a finite set of points by a plane is presented.



tetrahedra, algorithms, surfaces, convex sets


Collins, B. J. (1997). Implementation of an algorithm to approximate constrained tetrahedrizations with pre-specified triangular faces (Unpublished thesis). Southwest Texas State University, San Marcos, Texas.


Rights Holder

Rights License

Rights URI