# A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree
## 3 Materials and Methods
### Octree Encoding/Decoding  
Generally, octree includes regular octree and linear octree [22]. The former stores data in leaf nodes and non-leaf nodes, while the latter only stores data in leaf nodes. Reasonable thresholds can limit the depth of the tree. At the same time, when the octree is constructed, Morton-code [23] is used to encode and sort leaf nodes of octree, aiming at improving the efficiency of Point Cloud data retrieval. Currently, the octree's threshold (depth or leaf size) setting is usually fixed or adaptive experientially. In the data structure research, through the judgment of threshold conditions and related recursive loops, the final goal of 3D Point Cloud data integration is to achieve a fast query. Octree is a 3D extension of Quad-tree [24] and inherits the fast partition of Quad-tree. It can be used to model 3D geometry and space, which is essential in space planning [25], computer animation, and machine vision [26]. Octree subdivides 3D space into \(2^{n}\times 2^{n}\times 2^{n}\) subspaces, where \(n\) is the octree depth. Data space is divided into eight subspaces if the space contains geometric object entities, and each subspace is subdivided into eight sub-subspaces if there are entities in subspace, so on and so forth until the terminating condition is reached. Octree is considered as an important revolution of data structure in real 3D space partition. When the tree is constructed, leaf nodes are encoded with a certain regularity to achieve efficient retrieval of Point Cloud data, such as Morton-code [27], Gray-code [28], Hilbert-code [14], etc. Regular octree occupies a vast amount of memory. The recursively generating and querying operation makes it very time-consuming, especially when the volume of data is so large that the tree is deep. Linear octree [22] improves regular octree and speeds up query operation. It only stores data in leaf nodes. One of the most important things is that the nodes are stored in linear arrays or linear chains according to locate code. Linear octree's nodes are generated fast and don't need to change tree greatly when a particular node is divided into smaller sub cubes. Since a linear table is created corresponding to the node, it is more suitable for massive Point Cloud data processing and modeling. For computing locate code, Morton-code is used widely benefiting from the implementation easily by bit operation. Octree's leaf nodes are encoded by Morton-code. Assuming the depth of octree is \(n\), an \(n\) bits _octal_ number can represent a node uniquely. For convenience, an \(n\) bits _decimal_ number is used. In fact, \(M=m_{n-1}\cdots m_{k}\cdots m_{2}m_{1}m_{0}\) is the same regardless of octal or decimal. The code of a node consists of the code of its parent node's and its own. If a node with code \(m_{p}\) is split into eight sub-nodes, the code of sub-nodes can be calculated by \(M=10\cdot m_{p}+m_{i}\), where \(m_{i}\) is the code of \(i\)-th sub-node and decided by the z-order as shown in Figure 1. Figure 2 shows the Morton-code of octree nodes. As mentioned earlier, octree will become unbalanced when processing non-uniformly distributed data. We limit the depth of octree and build 3D R*-tree at each leaf node. Figure 1 shows the process of how octree splits the data space and Morton-code encodes nodes. The location code (Morton-code) represents the identifier (id) of the 3D R*-tree. Compared with kd-tree, octree reduces the height of the tree. Given a point, we can quickly locate the node in which it lays by computing its Morton-code other than traverse the whole tree like kd-tree does. For robots or unmanned aerial vehicles (UAV), the distribution of Point Cloud is non-uniformly, which is obtained by LiDAR or RGB-D  
Figure 1: The process of octree splitting data space and encoding. Figure 2: Morton-code encoding octree’s nodes. camera and represents the environment model of the real world. The threshold _leaf_size_ setting is crucial to the performance of octree.