AUGMENTED QUAD-EDGE - 3D DATA STRUCTURE FOR MODELLING OF BUILDING INTERIORS
Paweł Bogusławski · 2006
This work presents a new approach towards the construction and manipulation of 3D cells complexes, stored in the Augmented Quad-Edge (AQE) data structure. Each cell of a complex is constructed using the usual Quad-Edge structure, and the cells are then linked together by the dual edge that penetrates the face shared by two cells. We developed a new set of atomic operators that allow for a significant improvement of the related construction and navigation algorithms in terms of computational complexity. The idea is based on simultaneous construction of both the 3D Voronoi Diagram and its dual the Delaunay Triangulation. We expect that the increase of the efficiency related to the simultaneous manipulation of the both duals will allow for many new applications, like real-time analysis and simulation of modelled structures.