Hierarchical structure to winged-edge structure: A conversion algorithm (Q1107945)

A large number of geometric modelling systems are based on CSG (constructive solid geometry), whose internal data structures for representing objects boundaries are normally in hierarchical form. In this paper, the authors present a procedure for converting CSG representation to a boundary representation in winged-edge form. In the winged-edge data structure, a polyhedral object is represented as a list of records where each record is associated with an edge of the object. This record contains altogether eight pointers: two neighbouring faces, four immediate neighbouring edges and two bounding vertices of the edges. By means of this data structure, adjacency relationships between primitive geometric entities can be evaluated directly via their pointers instead of by global searching over the topological graph. The authors consider that the boundary representations in the winged-edge data structure are superior to hierarchical boundary representations, especially when the adjacency relationships of geometric entities are frequently required in a geometric operation. The efficiency and the flexibility of the algorithm are analyzed in some problems arised from non-manifold surfaces, disconnected surface regions and surfaces with holes.