Manipulating three-dimensional triangulations


The three-dimensional symmetric data structure is a topological model of a three-dimensional triangulation. It is a generalization of the symmetric structure proposed by Woo [Woo85] for describing the boundary of a solid object. In the paper, we present the basic topological elements of a 3D triangulation and their mutual relations. We describe the 3D symmetric structure and present structure accessing algorithms for retrieving those relations which are not explicitly encoded in the structure. Finally, a minimal set of primitive operators for building and manipulating a 3D triangulation are discussed. Such operators are independent of the underlying data structure.

Foundations of Data Organization and Algorithms