The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Voi. XXXVII. Part BI. Beijing 2008 
467 
A simple approach is using the vertexes of convex hull to 
replace the whole data. Assume the data set in a node is S, and 
build a convex hull CH(S), in which the set of vertexes is P(S). 
For any point in P(S), compute its screen coordinates. Let the 
set of two-dimension point is P’(s’), compute its convex hull 
CH(P’(S)). If CH(P’(S)) is small enough, we will not show the 
node’s sub-node. 
But in fact, the complexity of computing convex hull is 
0(n*ln(n)), it means that the computing is also time consuming. 
Moreover, the convex hull would also have errors. As shown in 
Figure5, if the green points are vertexes of the convex hull, then 
the CH(P’(S)) is the region encircled by the green lines. But we 
can only guarantee the region that contains green points is 
actually the area we need. The gray area may have no any point 
to be projected to, which indicates the inaccurate area. 
To simplify calculation, we use smallest bounding box along 
the axis to replace convex hull, which makes the computation 
more imprecise (Figure 5). The area using bounding box is the 
region encircled by the red lines. Compared with convex hull, it 
generates four more squares (indicated as pink color). But this 
method may discard the cumbersome computing for convex 
hull, and effectively speed up the processing speed. 
Figure 5. The smallest bounding box along the axis 
would take the place of convex hull. 
The above approach can reduce the points on screen, and 
accelerate displaying speed. At the same time, some more 
improvement will make the effect more satisfactory. 
1) The KD tree is divided into three dimensions, after 
projecting to two dimensional planes, there will be many 
overlapping points projected to the same pixel. As a result, the 
larger the data set is, the more there are overlapped points. To 
enhance the efficiency further, we propose a BOOL screen 
buffer, which records whether the pixel on the screen has been 
correctly drawn. When we want to draw a point, examine the 
corresponding pixel on screen, if it has been drawn, we will not 
draw again. 
2) Based on the above improvements, it’s possible that we draw 
a point that is far from us first, and then when we want to draw 
a closer point, we find the pixel has been drawn, so we give up 
drawing. That is, the point isn’t drawn in a ‘correct’ way. In 
order to consider the depth of point, we can use the depth buffer, 
but it spends too much computing resources. A simple approach 
is to traverse the KJD tree in a “front to back” way. The order to 
traverse a node is: examine which sub-node contains the 
displayed point, traverse it, then draw the node’s split data, and 
then traverse other nodes. 
3) Classical KD tree defines the split axis of X, Y and Z in turn, 
which ensures the fairness and makes it convenient to deal with. 
But in this way, the different density on three dimensions may 
make the node’s region anomalous. The best definition for split 
axis is the dimension of largest spatial extent [6] , which can 
make node’s region nearly the same length in three dimensions 
and ensure a stable efficiency. 
4). After discussion on screen buffer, the standard of node’s 
split can be added as: if pixels in the region after node’s 
projection have all been drawn, the process ends. This standard 
will simplify point display in tremendous volumes of data. 
5. EXPERIMENTAL RESULTS 
In a computer with Pentium4 2.4GHz CPU, 1G memory, 
NVIDIA GeForce FX 5200 graphics card, we run the program 
in three ways. These respectively include the original method, 
the method using 1.5 pixels display precision, the method of 
using 1.5 pixels display precision and screen buffer. We utilize 
a data set of 3,200,079 points, with a disk size of 87.5M. Four 
pictures for experiment are shown below: 
Number of points: 237953; cost time (ms):6152.31 
Number of points: 49468; cost time (ms): 1588.09 
Number of points: 20202; cost time (ms): 757.467 
Figure 6. Experiments results 
As shown above, with the decrease of model’s percentage on 
screen, the number of points becomes smaller and the display 
time becomes shorter. The number of points and display time 
maintain a linear relationship. This is consistent with our 
original intention of using the points that will be shown and 
discard the points that need not be shown. 
With the increase of the length from viewpoint to model, the 
number and time become smaller and smaller. Compared with 
the way without screen buffer, the screen buffer reduces the 
number in screen but increases the display time, that’s because 
in this way it adds a judge of whether the pixel has been shown 
or not for each ‘big’ node. This drawback can be improved by 
the fourth improvement. 
Noted that the number of points and the display time maintain a 
linear relationship, we can get the result that, the display time in