# A Simplification Method for Point Cloud of T-Profile Steel Plate for Shipbuilding
## 3 Octree Coding Algorithm Based on Neighborhood Point Search  
Due to the large amount of the point cloud of the T-profile plate, the time needed is often long and the search efficiency is low if the k-d tree algorithm is used for dividing regions [24]. Considering the shortcomings of applying the k-d tree to the neighborhood search of the T-profile plate point cloud [25; 26], the octree coding algorithm is used in this paper. This is more suitable for dividing the three-dimensional space of the T-profile plate point cloud in this study. This algorithm is simple, and its search efficiency is relatively high [27; 28]. As shown in Figure 3, in this study we developed a root model based on the topological relationship of the target object's point cloud [29; 30]. Firstly, when constructing the bounding box, all the point data is divided into eight sub-cubes with the same size. Secondly, each sub-cube is equally divided by the recursion method. Finally, the previous steps are repeated until the smallest side lengths of the sub-cubes are smaller than the specified point spacing. Since the minimum interval of the scanning point cloud of the Leica HD57000 [31] is set as 0.6 mm for the T-profile plate scanning, the specified distance is set to 4 mm in order to allow 50 to 100 point cloud data to be included in the smallest sub-cube. Additionally, each sub-cube obtained by the octree coding algorithm is coded based on its position. Each sub-cube is represented by a code, and the code corresponds to the root node under the octree. The sub-cube position in the root model can be represented by the octree code \(Q\), given as follows  
\[Q=q_{n-1}\cdots q_{m}\cdots q_{1}q_{0} \tag{1}\]  
where \(q_{m}\) is the number of this node at this level, \(m\in\{0,\,1,\ldots,\,n-1\}\), and it is octal; \(q_{m+1}\) is the node number of \(q_{m}\) at the parent level. Therefore, the path from each child node to the root in the octree can be represented by \(q_{0}\) to \(q_{n-1}\). The specific steps are as follows:  
1. Step (1): Determine the division number of the octree for the point cloud \[d_{0}*2_{n\geq d_{max}}\] (2) where \(d_{0}\) is the known point distance of the point cloud; \(d_{max}\) is the longest side length of the bounding box; \(n\) is the division number of the octree, which is the minimum integer in Equation (2). 2. Step (2): Determine the encoding of the sub-cubes, at which the point cloud data points are located. Assume that the data point is P (\(x\), \(y\), \(z\)), the spatial index of the sub-cube is (\(i\), \(j\), \(k\)), and \(Q\) is the octree coding of the corresponding node. The relationship among them is represented by Equations (3) to (5) \[\left\{ \begin{array}{l}i=\left[\left(x-x_{min}\right)/d_{0}\right]\\ j=\left[\left(y-y_{min}\right)/d_{0}\right]\\ k=\left[\left(z-z_{min}\right)/d_{0}\right]\end{array} \right.\] (3)  
Figure 3: Octree partition space model. where (\(x_{min}\), \(y_{min}\), \(z_{min}\)) is the minimum vertex coordinate of the bounding box corresponding to the root node. The procedure converting the index (\(i\), \(j\), \(k\)) to binary representation is as follows  
\[\left\{ \begin{array}{c}i=i_{0}2^{0}+i_{1}2^{1}+\cdots+i_{m}2^{m}+\cdots+i_{n- 1}2^{n-1}\\ j=j_{0}2^{0}+j_{1}2^{1}+\cdots+j_{m}2^{m}+\cdots+j_{n-1}2^{n-1}\\ k=k_{0}2^{0}+k_{1}2^{1}+\cdots+k_{m}2^{m}+\cdots+k_{n-1}2^{n-1}\end{array} \right. \tag{4}\]  
where \(i_{m}\), \(j_{m}\), \(k_{m}\) {0,1}, and \(m\) {0,1, \(\ldots\), \(n-1\)}. \[q_{m}=i_{m}+j_{m}2^{1}+k_{m}2^{2} \tag{5}\]  
Therefore, the octree encoding corresponding to the cube can be expressed by Equation (1). If we assume that the index of a sub-cube after partitioning is (\(i\), \(j\), \(k\)), the index of the 26 sub-cubes surrounding it can be represented by (\(i\pm\delta\), \(j\pm\delta\), \(k\pm\delta\)) (\(\delta\in\) {0,1}). After finding the point \(P_{i}\) in the point cloud that is closest to the gravity center of a sub-cube, 30 points are evenly selected in the sub-cube, ensuring that the point \(P_{i}\) is the gravity center of the 30 points.