Modelling and analysing 3D building interiors with the dual half-edge data structure

Abstract

While many systems and standards like CAD systems or CityGML permit the user to represent the geometry and the semantics of building interior models, their use for applications where spatial analysis and/or real-time modifications are required are limited since they lack the possibility to store topological relationships between the elements. In this thesis a new topological data structure, the dual half-edge (DHE) is presented. It permits the representation of the topology of building models with the interior included. It is based on the idea of simultaneously storing a graph in 3D space and its dual graph, and to link the two. Euler-type operators for incrementally constructing 3D models (for adding individual edges, faces and volumes to the model while updating the dual structure simultaneously), and navigation operators (for example to navigate from a given point to all the connected planes or polyhedra) are proposed. The DHE also permits the assigning of attributes to any element. This technique
allows the handling of important query types and performs analysis based on the building structure, for example finding the nearest exterior exit to a given room, as in disaster management planning. As the structure is locally modifiable the model may be adapted whenever a particular pathway is no longer available. The proposed DHE structure adds significant analytic value to the increasingly popular CityGML model, and to the CAD field where the dual structure is of growing interest.

Date of Award	Mar 2011
Original language	English