An efficient data structure for three-dimensional triangulations


A three-dimensional tesselation can be described by four basic topological elements (vertices, edges, faces, and polyhedral cells) plus their mutual pairwise relations. We present a specific data structure for encoding a three-dimensional tesselation composed of a collection of quasi-disjoint tetrahedra, i.e., a three-dimensional triangulation, and discuss those structure accessing algorithms which retrieve the relations not explicitly stored in the structure. A set of primitive operators for building and manipulating a 3D triangulation are presented. Their use is demonstrated in connection with an algorithm for computing a 3D Delaunay triangulation.

CG International’90