## 3 Space Matching Process Using Multi-Resolution Cube Grid
### Application of Multi-Resolution Cube Grid Method and Setting the Application Conditions  
This study aims to analyze the space by converting the 3D point cloud into the space grid. Space was converted into the grid mode so as to divide the space, to search free space by separating cases with point existing in grid and point not existing in grid, and to determine whether an equipment can be arranged in the free space depending on the equipment specifications.  
The object sizes of the space and equipment must be adjusted to apply the multi-resolution cube grid method to the data acquired through a 3D laser scanner. This is because the unit sizes (\(n\)) must be identical in order for us to check the interference of the space and equipment in the process of dividing them into small nodes using the multi-resolution cube grid method. Figure 1 below shows the node applicable model.  
The data simplification process starts first by removing the noises. Noise refers to unnecessary data other than equipment and on-site environmental information (pre-installed equipment, structures, etc.), and the target of noise may vary depending on the purpose. A node exists if data exist at any point in the node in the simplification process based on 3D shape information under the assumption that noises have been removed. This can be checked by referring to cell no.4 of the facilities model in Figure 2. Figure 2 shows a simplified example of transforming space and equipment into grid forms only considering the horizontal and vertical (x, y) coordinates to illustrate the concept. As the final goal of this study was space analysis based on 3D grid method, all three coordinates of x, y, z including the height were analyzed. The grids labeled A1 to H8 in Figure 2 represent the total space of the site environment for equipment installation indicated as grid, and grids labeled 1 to 16 illustrate an example of converting the equipment to be installed into 3D grids.  
Figure 1: Node applicable model.  
There are a few constraints in deciding the unit size (\(n\)) of the node. In collecting point cloud, the point count size, accuracy, and time vary depending on the resolution of instrument used. In this study, a Leica C5 laser scanner was used and the resolutions were classified into High, Mid, and Low. Using the instrument as a reference point, the resolution of the laser scanner was classified into High, Mid, or Low according to the point interval that can be obtained at a distance of 100 m from the reference. In case of Leica C5 used in this study, the accuracy is Low when the point interval obtained from the 100 m distance was 20 cm, Mid accuracy when interval was 10 cm, and High accuracy when the point interval was 5 cm. This study divided the space into grids and recognized unoccupied space by identifying whether a point was included in the grid or not. Consequently, as in Figure 3, the resolution affected node size setting since error of recognizing as an empty space can occur if the node size is smaller than the interval of the points from 100 m distance  
If the node size is smaller than the size of the photographing resolution in the used equipment, the following problem arises. The left and right nodes among the three nodes in the figure are perceived as effective because they contain points, but the middle node is perceived as non-existent because it contains no point.  
However, the time required for checking the space sharply increases if the node size is diminished to a degree that the distance between points is considered in the actual experiment. If the node size is halved in the process, the number of objects perceived in the test increases by eight times. Therefore, choosing an appropriate node size is critical in algorithm optimization.