A data structure for manipulating three-dimensional subdivisions

Abstract

A major impediment to the implementation of algorithms that manipulate polyhedral subdivisions is the lack of a suitable data structure that is powerful enough to model such objects while being simple enough to allow their manipulation in well defined ways. This dissertation describes such a data structure. The structure is analogous (though one dimension higher) to Baumgart's winged-edge, and Guibas and Stolfis' quad-edge data structures which are widely accepted for modelling polygonal subdivisions. We focus upon a set of primitives for querying the data structure (corresponding to traversal of a polyhedral subdivision), and implementation of the data structure. We also describe primitives for building the data structure (corresponding to construction of a subdivision), define higher-level construction operators, and present applications.