The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part Bl. Beijing 2008 
466 
of node 1, 2, 4 and 5, and are separated by the three lines too. 
Thus, the traversing sequence should be: 
[1] [2, 4, 5] [3, 6, 8] [7] 
Figure 3. A cube which has a root and eight sub 
nodes. 
Add a variable i for marking the traversing sequence and the 
initial value is 0. Test the three-dimensional coordinates 
respectively, if a coordinate of viewpoint is not in the node’s 
bound, the node’s i will add one. When traversing the eight 
sub-nodes, variable i gives the sequence. 
The pseudo-code is below: 
int node.calculateFrontOrBack() 
{ int i=0; 
for(intj=0;j<3;j++) 
if(!(eye[i] Enode. bound)) 
i++; 
return i; 
} 
tree.walkNode() 
{... 
for(intj=0;j<4;j++) 
for(int k=0;k<8;k++) 
if(subNode[i], i==j) 
tree. walkNode(subNode[i]); 
...} 
For the issue of managing large volume of LiDAR data using 
local KD trees, we choose octree to determine the bound of 
local KD trees. Data are put into RDBMS in specific order in 
pre-process, the KD trees are computed during run time, and 
local KD trees can be quickly built by reading data from the 
database. We also make some improvements on other details. 
These methods are suitable for large amount of data, and can 
achieve a satisfactory processing speed. 
representational point instead of drawing all of them. The small 
area usually to be defined as a pixel and the representational 
point can be the point that splits the node into two. 
Based on this idea, it’s needed to get two-dimension 
coordinates on screen from any point after projection. The 
region’s size consisting of the points’ two-dimension 
coordinates on screen will determine whether its sub-nodes will 
been shown or not. 
Calculating screen coordinates is very simple in orthographic 
projection. In perspective projection, the formula for 
calculating is shown below. 
Let eye position to be eye[3], view[3] means the direction of 
view, and up[3] indicates which direction is up. Calculating the 
vector multiplication exterior, make a coordinate system, eye[3] 
as the origin, exterior as X axis, up as Y axis, view as Z axis. 
For any data P, its projection is indicated in Figure 4. So the 
point P’ will be the mapped point of P on screen. The lengths of 
E’P’ and A’P’ will be the X and Y coordinates of P’. 
Figure 4. The eye position is point O, view is Z-axis, 
up is Y-axis, and exterior is X-axis. 
OD’ is the distance from P’ to the XY plane, its length can be 
count by the frustum and the size of scene. Because of 
FE' _ A'D' _ AD _ PE 
OD' ~ OD'~ OD~^4B 
FÄ _ OÄ _ OD' OD' 
PA ~ OA~ ~OD ~ ~AB 
4. DISPLAY PRECISION 
In displaying LiDAR data using local KD trees, there may be 
some trees or nodes which are far from the viewpoint. Drawing 
these trees or their nodes has less effect to the observer. 
Consider a node far from the viewpoint that the region of data’s 
projection on screen is only one pixel, despite how many points 
the node contains. So only one point can be drawn instead of 
drawing hundreds, even thousands of points from the node. 
Based on this principle, we use the concept of screen precision 
to control display based on local KD tree. That is, if a small 
area on the screen contains many points, we only draw a 
, we can get: 
P'E'= — *OD' P' E'= OD' 
AB AB 
? 
PA, PE and AB respectively are the distance from P to plane 
XZ, YZ and XY. So we could get the length of E’P’ and A’P’. 
In order to examine a node’s precision, we need to calculate all 
points in it, he process is time-consuming and very expensive.