# A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree
## 4 Results
### Verification  
To verify the performance of hybrid structure proposed in this paper, randomly generate different sizes of 3D points: 1K, 4K, 16K, 64K, 256K, (1K = 1000), octree \(depth=2\), number of neighbors k = \(1,4,8,16,32,64\) and \(Children_{min}=8\cdot k\). In this section, construction time was not taken into account. The \(kNN\) searching time is shown in Figure 6. We can find that when \(k\) is small, searching time is relatively stable, because \(Children_{min}\) is increasing with the increasing of \(k\). When \(k\) becomes bigger, \(Children_{min}\) becomes bigger, too. Implying that the capacity of an octant is larger and more points are contained. So, if the query point lies around the center of the octant, the searching time is still stable. When more points near the face, even the corner of an octant, the time will be increasing dramatically. However, in this paper, octree's \(depth\) is limited, so the \(octant\) of the octree is bigger, the probability of points near the face or corner of octant is much smaller. A normal estimation experiment has been made to show the superiority of the hybrid structure proposed in this paper utilizing Point Cloud data _table_scene_lms400.pcd_ mentioned earlier. Firstly, we downsampled the Point Cloud data from 460,400 points to 3309 points. Secondly, estimating normal for each resampled point in Point Cloud. The normal of a point \(p\) is the eigenvector corresponding to the minimum eigenvalue computed by point \(p\) and its neighbors (\(kNN\)). Computing normal of each point in Point Cloud will conduct \(n\) times of \(kNN\) searching, but construct the tree once, where \(n\) is the number of points in Point Cloud. The results are shown in Figure 7. The left visualizes the normal of each point, whose direction mostly is downwards. We estimated the normals with 32-\(NN\). It is easy to understand that the smaller \(k\) is, the less time to search \(kNN\), but the less accurate the normal is. Figure 5: Thresholds analyzing. The _depth_ of octree is an important threshold that influences the performance of the hybrid structure. As shown in Figure 8, it is a 3D R*-tree when \(depth=1\) and an octree when \(depth=11\). The used data is the same as the normal estimation, downsampled _table_scene_lms400.pcd_ with 3309 points. The 3D R*-tree spends more time than octree to construct the structure but less time to search neighbors. When \(depth=2,\ 3,\cdots,8,\)  
Figure 6: NN-searching time of hybrid structure. Figure 7: Visualization of Point Cloud with normal and time used by three structures computing normals. The **left** is the visualization of Point Cloud with normals, and the **right** is the time used by different structures computing normals. Blue bars represent octree, light green bars represent 3D R*-tree, and yellow bars represent the hybrid method proposed in this paper. the hybrid structure is constructed. We can see that construction time changes with a small magnitude and \(kNN\) searching time keeps increasing with the \(depth\) increases. A greater \(depth\) means more time to construct octree and more candidate 3D R*-trees to search neighbors, because when \(depth\) is greater, \(leaf\_size\) is less, which implies the \(octant\) is smaller and more \(octants\) intersect with the search ball \(B_{r}\). A comparative experiment was conducted applying octree and 3D R*-tree. As shown in Figure 9, the real-world Point Cloud data was collected by an RGB-D camera scanning a laboratory with 888393 points. We test the depth of the tree and the time consumption of tree constructing and \(kNN\) searching. The results are shown in Table 1, which reveals that the hybrid method proposed in this paper performs better in \(kNN\) searching and similar to octree in tree constructing. The 3D R*-tree spends a considerable amount of time in tree constructing but less time in \(kNN\) searching than octree. Because R*-tree adopts series of optimizations, unlike octree splits points into eight sub-nodes regardless of the spatial relationship between points.