The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part Bl. Beijing 2008 
465 
KDNODE* FindParent (Xtype* xO); 
KDNODE* Parent; 
KDNODE* Left; 
KDNODE* Right; 
}; 
template <typename Xtype> 
class KDTree 
{ 
public: 
KDNODE* Root; 
KDTreeO; 
bool 
void 
KDNODE* 
Xtype 
}; 
//Search node, return the parent node 
add(Xtype* x); 
insertToKD(Xtype* data); 
find_nearest(Xtype*xO); 
xjninfSD], x_max[SD]; 
// The function of add the non-leaf node 
//Find the nearest node 
//Set bounding box 
3. LOCAL KD TREE 
Building a KD tree for a whole set of LiDAR data in traditional 
way is less possible. One reason is the tremendous volume of 
data. Another reason is that it’s required to sort the whole data 
based on the coordinates in the three axial direction before 
building KD tree, whose complexity is 0(N*ln(N)). As large 
data set consumes too much time, data partition is necessary. In 
this way, we divide the data into small pieces and build local 
KD tree for each piece of data, to help the organization and 
management of data. 
3.1 Using octree to confirm the bound of local KD tree 
In order to avoid excessive search, we adopt the octree to 
partition space, which makes point’s location known in advance. 
It saves time of comparing with node’s key word during 
searching, and facilitates judging whether it’s in the view 
frustum. 
The standard for splitting octree’s node is defined as: if the 
node’s number of points is less than a pre-defined number, it 
needn’t to be split. The pre-defined number is determined by 
the capacity of KD tree. That can make the scale of KD tree 
uniform, which is convenient for post-processing. In order to 
get the balance between the octree’s depth and KD tree’s 
saturation, the number should be defined as 2 n . 
The definition of a local KD tree includes two steps. Firstly, the 
bound and density of the data should be determined to establish 
octree. Then, each node is split into eight sub-nodes through the 
center position of the bounding box until the node’s number of 
point is less than 2 n . The data of each leaf node in octree make 
up of a local KD tree. In the octree, the nodes only store their 
information about bounding box. Each leaf node is given an 
index value for the convenience of research. 
3.2 View frustum clipping 
According to the position of viewpoint and the frustum, we 
compute all octree’s nodes in view frustum. Read the data in 
each node and build local KD trees. 
The program that computes which nodes are in the view 
frustum can be like this: seek from the root, if the node’s 
bounding box and the view frustum have an intersection, seek 
for node’s two children, otherwise return. 
We note that in each vision, we need to identify the called KD 
trees, and then read data from database to build KD trees. The 
process is very cumbersome. In viewing frustum clipping, the 
general view transform only changes the edge of the scene. For 
local KD trees, a view transform is likely to retain most of KD 
trees, only a small part of the trees will be changed into or out 
of the view frustum. As the Figure 2 shows, when the view 
frustum moved right, only several green regions enter the 
frustum and several red regions quit. So, while the scene is 
redrawn, we only need to compute these special trees, destruct 
the red trees and construct the green trees. That will avoid 
destructing and reconstructing many trees. 
Figure 2. A view transform is likely to retain most of 
KD trees. In this picture, only the green regions 
enter the frustum and the red regions quit. 
3.3 Traverse the octree front to back 
For binary tree, a node has only two sub-nodes, the front to 
back traversing order can be directly derived by comparing the 
view position with the node’s key word. But for octree which 
has eight children, the order from front to back is not so simple. 
Consider the cube shown in the picture, it represents a node of 
octree and it has eight children. If the viewpoint is in node 1, 
it’s certain that we will traverse node 1 first and node 7 at the 
end, because node 1 is in front of any other nodes and node 7 is 
behind any others. 
Notice that, three nodes, node 2, 4 and 5, have a public plane 
with node 1 and only node 1 is in front of them. Moreover, they 
are separated by lines AB, CD and EF, any one of which isn’t 
in front of any other. There are three other nodes, i.e., node 3, 6 
and 8, that have a public line with node 1, they are in the back