# Indoor Building Reconstruction from Occluded Point Clouds Using Graph-Cut and Ray-Tracing
## 3 Indoor Reconstruction Methodology  
### Overview  
As previously anticipated, in this paper we present a technique for automatic indoor modelling (AIR) of buildings starting from point cloud data acquired with a mobile laser scanner (MLS). One of the key-points of the methodology is the capability to cope with a large amount of clutter and missing data. The developed methodology takes as input a point cloud from indoor MLS (\(x\)-\(y\)-\(z\) coordinates), its trajectory, and a defined vertical direction (that generally coincides with the \(Z\) axis). From a formal point of view, the point cloud can be represented as a set of points \(P=\{p_{i}\mid i\in\{1,\,\ldots\,,N\}\}\) in \(R^{3}\) while the continuous trajectory of the mobile laser scanner can be discretized into a set of points \(TR=\{tr_{k}\mid k\in\{1,\,\ldots\,,M\}|\}\) representing the scanner position during the acquisition process. These prerequisites can be easily obtained in practice. Indeed, commercial and scientific MLS generally provide both point clouds of the crossed rooms and the scanner trajectory as an output of the acquisition step. In addition, the point clouds are provided with the \(z\) axis aligned to the vertical direction. The presented methodology uses the previously listed inputs to reconstruct the indoor scene through a planar primitive detection and an indoor component reconstruction process. The adopted workflow is summarized in Figure 1.  
In particular, since point clouds recorded with MLS are often corrupted with noise and outliers a first smoothing is carried out by using some statistical analysis and morphological operators (removal of isolated points). The consolidation of the raw point cloud reduces noise and increases the accuracy of the subsequent reconstruction steps. The normal for each point is then estimated using local plane fitting. The core of the presented methodology is the transformation of the indoor reconstruction into the labelling problem of structural cells in the 2D floor plan. More precisely, the first step is the detection and estimation of the surfaces to be modelled (i.e., walls, ceilings, and floors). In particular, the extraction of the potential indoor primitives is detected by using a modified RANSAC implementation for extraction of planar surfaces. The extracted primitives are then refined to reduce under- and over-segmentation issues. The refined primitives are then considered as the input for the subsequent indoor component reconstruction. However, due to occlusions and clutters, some walls may be missing in the data set. For this reason, an automated procedure is implemented to look for pending elements in a plausible way. To achieve this, the developed algorithm incorporates some architectural priors on indoor scenes, notably the prevalence of orthogonal intersection between walls--the Legolan building assumption [29]. In particular, the indoor reconstruction is formulated as an energy minimization problem using graph cuts to finalize the creation of walls. Once the wall elements are defined, the remaining steps operate on each surface individually. In this phase, each planar surface is analyzed to identify and to distinguish between occluded regions and openings by using a ray-tracing algorithm [30]. This enables the identification and labeling of doors and windows, so that finally the occluded regions may be reconstructed in a realistic way. The output of the methodology consists of a set of labeled planar patches (walls, floor, and ceiling), adjacency maps indicating connection between planes, and a set of openings detected within each planar patch. These patches are intersected one with another to form a simple surface-based model of the room. The transformation of a surface-based model into a volumetric based one is carried out by means of the commercial software Rhinoceros(r). The geometric nodes of the room, along with any semantic information may be combined together to derive a semantically enriched model in CityGML and/or IFC format [31].