# Indoor Building Reconstruction from Occluded Point Clouds Using Graph-Cut and Ray-Tracing
## 3 Indoor Reconstruction Methodology
### Element Classification and Opening Detection  
Once all of the indoor structure is determined with wall elements the presence of the openings is investigated. Detecting the boundaries of openings, such as windows or doors in a wall is a complex task. While in facade reconstruction applications, windows are generally detected as holes in the facade point cloud [42], this does not generally hold for the indoor environment. Indeed, also occlusions and clutter produce significant holes in the point cloud which have to be distinguished from real openings. To this end ray-tracing labelling is performed and an occupancy map is generated [23].  
In this step each room and more specifically each surface is separately processed. Once having previously defined the wall surface, points representing inliers for the defined plane can be easily recognized. The detected plane is then discretized into cells of size \(\beta_{2}\times\beta_{2}\) and then an occupancy map (denoted as OM) is generated on the basis of whether inlier points are detected at each pixel location or not. Without additional information, it is not possible to distinguish between a pixel that is truly empty and one that is merely occluded. This problem can be solved by using ray-tracing labelling to detect occlusion between the sensor and the analyzed surface. For this reason the scanning locations (position) should be known.  
In particular, starting from the mobile scanner trajectory \(TR=\{trk\,|\,k\in\{1,\,\ldots,\,M\}\}\) it is easily possible to identify the scanning points belonging to each room (Figure 6).  
Let \(P=\{P_{1},\,P_{2},\,\ldots,\,P_{N}\}\) be the set of scanned point for the room to be modelled. For each scan position \(S_{K}\) a labelling \(L_{K}\) is generated by tracing a ray from the scan location to each pixel \(P_{i}(x,y,z)\) labeled as 'empty' in the occupancy map (OM).  
Having defined cell location and the scan location it is possible to verify if the defined ray is traversing a voxel (generated in the point cloud consolidation step) that is labelled as occupied. If so this means that \(P_{i}\) is occluded by some points in the scan and the cell is consequently labeled (Figure 7). On the other hand, if the ray is not traversing any occupied voxel the cell \(P_{i}\) is recognized as a real empty area.  
Figure 6: Subdivision of the acquisition path into sub-paths for each room (points belonging to each room are colored in a different way).  
For the discretization of the voxel space a cylindrical buffer of three voxels is considered around the identified ray. After this ray-tracing labelling for all scan positions, \(K\) labels for each pixel are obtained. Figure 8 presents an example of OM generation for a specific position \(P_{1}\) in Room 1 (Figure 8a). As can be appreciated from Figure 8b, the door and another piece of furniture (pink segment) occludes a portion of the wall close to the entrance (Wall 1). In a similar way radiators (blue segment) occlude a portion of the wall under the windows (Wall 3). Starting from position \(P_{1}\) OMs are generated for all the four detected walls of the room (Figure 8c-f). In particular, taking into consideration Wall 1 (Figure 8c) and Wall 3 (Figure 8e) it is possible to notice the classification of occluded areas (in red) and of openings (in green).  
Finally, all the labels are combined in a final occupancy map (LF) adopting the following labeling rule:  
\[If\ L_{0}=empty\ and\ L_{j}=occluded,\ \forall_{j}=1,2,\ldots,K=>L_{F}(i)=occluded \tag{11}\]  
In other words, a cell is considered occluded if it is occluded from every scan-point.  
Figure 8: _Cont._  
Figure 7: Ray-tracing labelling principle: point \(P\) is marked as occluded because the ray connecting it to the scanner position \(S\) traverses a voxel that is defined as occupied.