Primitives for the Manipulation of Three-Dimensional Subdivisions

Abstract:

A major impediment to the implementation of algorithms that manipulate 3-dimensional cell complexes and subdivisions is the non-existence of a suitable data structure. What is needed is a data structure which is powerful enough to model such objects while being simple enough to allow their manipulation in
well defined ways. We focus attention here on the development of such data structure. Our structure is analogous (though one dimension higher) to Baumgart's winged-edge and Guibas and Stolfi's quad-edge data structures which are widely accepted for modelling 2-manifolds. Just as these structures can be
used to represent both planar polygonal cell complexes in R3 and surfaces of 4-polyhedra, our results can be viewed as similar to the work done by Guibas and Stolfi in deriving the quad-edge structure, one dimension higher. What we attempt to achieve in this paper is a blend between a derivation of the
data structure and a small set of primitive operators for its manipulation, the development of macro operations from these primitives, and the use of these macros in the first two applications mentioned above. The results of this paper are implementable and an effort to build them is currently underway.