2.2 The Spatial Index Construction of Quad-MBB Tree 
The construction process for QMBB tree spatial index is as 
follows, firstly ID value of points are defined in turn in the 
process of reading each point coordinates. According to the ID 
value the points are inserted into leaves node of the QMBB tree 
index. If the number of points stored in a node is more than the 
threshold, the nodes will be split until all the spatial points are 
inserted into QMBB tree. After construction of QMBB tree, the 
action is calculating MBB of each leaf node, using the method 
of uniform sampling in the way of bottom-to-top to fill non-leaf 
node data of spatial index tree until the root node, that is to say, 
non-leaf node of the QMBB tree can also store multi-resolution 
point image data, but not real 3D coordinate data, and it only 
stores the ID data of 3D point coordinate. The construction 
algorithm diagram is shown in Figure 4,in which it acquires the 
number of rows and column for single viewpoint image at first, 
and build QMBB tree according to the ranks number 530 * 789 
from up to down, then insert every 3D point into corresponding 
leaf node in order, for instance the point of red dashed into 
"Level 3 leaf node 1", the point of blue dashed into "Level 3 
leaf node 2",and when each effective 3D point are inserted into 
QMBB leaf node, it starts re-sampling to fill in non-leaf nodes 
with point image data in turn from the leaves node, as is shown 
by green lines arrow in the Figure 4.Such a 3D spatial index 
structure-QMBB tree on the basis of quadtree is generated for 
one-time and real-time. In the process of reading data, at the 
same time, large scale of point image model are divided into 
multi-resolution LOD data block logically. 
  
   
   
  
   
Ey CE LE ee 
2» To Bulding OM BB Index Tep-down 
To Orgarize LOO Data Bottom-up « 
     
  
  
  
Figure 3 Construction algorithm diagram of QMBB-tree spatial 
index of point image 
2.3 Data Organization and Lossless Compression 
After the structure of QMBB tree spatial index is built, multi- 
resolution LOD point image data is expressed through the depth 
of QMBB tree, and each layer of QMBB tree represents point 
image data of different resolution, which depends on uniformity 
sampling rate at the time building QMBB tree spatial index. The 
structure of QMBB tree spatial index can only store ID number 
of 3D point as information pointer of real point coordinates and 
intensity, and point coordinate data stores only a single copy, 
and in retrieval the data is queried through the ID conversion 
for moving pointer, so as to avoid storage redundancy of multi- 
level data. When point image data is managed using 3D R-trees 
spatial index in every scanning station, all the leaf nodes of 3D 
R-tree store the root node MBB of QMBB tree, at the same time, 
each node of 3D R-trees also store uniformity sampling data in 
each point image, using the way of 2-level mixed spatial index 
to manage all the point image model. Using Depth-First 
Traversal to serialize and store spatial index, spatial index 
structure of point image can be quickly recovered after 
retrieving serialized data. 
   
   
   
   
  
   
   
   
   
  
   
   
  
   
  
    
   
  
    
   
    
   
   
   
   
    
    
   
   
  
   
  
Point image usually include such attribute information as ID 
geometric coordinate, intensity, texture (RGB) and so on. Each 
3D coordinates and the RGB texture of a point requires are 
recorded in three floating type data at least, a total of 24 bytes, 
while the ID and intensity value of a point needs one floating 
type data , 4 bytes. So the storage of a point object needs 32 
bytes 256 bits totally, and if the data volume of storing twenty 
million points reaches about 610 MB, while it cannot be render 
completely with current video card memory in reserved mode. 
In order to speed up network transmission of the point image 
data, we must compress the point image data. Different data 
type should apply different compression methods, for the 
intensity value and RGB texture value, we stretch their each 
component to the range of 0-255 positive integers, using one 
byte to store them respectively, and draw in the way of integer 
type directly with OpenGL tools, and the stretching method will 
not affect point image's textured display; Inspired by 47th 
reference (Wang Yanmin, 2002), using quantitative methods of 
spatial compression for the coordinates of 3D float type point. 
Generally the Z coordinate of block data is large, but it is in 
commonly less than 1000 m. In the experiment, point quantity 
stored in QMBB tree node of the spatial index structure is 
controlled in 16384, reaching the balance between reading 
speed of point image data and efficiency of index retrieval. With 
minimal point distance between each scanning point as 1 mm, 
16384 points in certain coordinate direction in space are at most 
in range of 16.384 m, and in general at X, Y direction can 
accurately express a point's direction coordinate using 14 bits; 
Because Z coordinates may be large, but generally can't be more 
than 1000 m. We adopt 20 bits to express Z-direction 
coordinates, and if the value is more than 1000 m it will be 
truncated and regarded as invalid points. Similarly we use two 
bytes to express the ID number of points. As shown in the Table 
1, overall compression ratio of the method reaches 37.5%, 
namely two thirds of the data is compressed nearly. 
  
  
  
  
  
  
  
E d ETT cns 
Coordinates 96 48 6 50% 
Intensity 32 8 1 25% 
RGB Texture 96 24 3 25% 
ID 32 16 2 50% 
Total 256 96 12 37.5% 
  
  
  
  
  
Table 1. Lossless compression statistics of point image Data 
3. EXPERIMENT AND ANALYSIS 
A prototype system is implemented for interactive visualization 
management with fast browsing and retrieval of the query 
function. The prototype system runs on a personal computer 
whose CPU is Intel(R) Core(TM)2 CPU6600 2.4GHz. Main 
memory is 3.00GB and graphics card is GeForce8500GT. We 
use Oraclellg database as the system's database management 
platform and design database object model and database table 
with database system design tool Power Designer. The 
experiment prototype system is developed in ODP.NET 
program environment and OpenGL 3D graphic library. 
The LOD display of point image and point image model is 
shown in the Figure 5. The left diagram is point image data of à 
Buddha’s head. The data file size is 18.52M, including 358062 
effective and colorful points. The rendering number of the 
points approximately is 150000 in the screen every time. We 
use OpenGL 3D graphics library to realize this article s 
algorithm on personal computer that has been introduced above, 
average frame rate is approximately 120 fps; the right diagram 
  
  
is a multi- 
269.14M. 
colorful po 
  
The red wi 
The MBB 
resolution i 
LOD level 
screen. Wh: 
frame rate | 
with the rer 
calculating 
refresh rate. 
What is ref] 
point image 
LOD select 
the basic pr 
or exceed | 
more than 
Long, ,ect,2 
16(L. Ren, € 
multi-statior 
culling. 
  
File 
Size/ 
M 
Dat 
Bloc 
  
18.52 1 
269.1 
421.6 
P 
Table 2.Re 
  
  
The algorithr 
point image | 
than a thresh 
R-Tree and Ç 
fate with acce 
the left is w 
Harmony in 
composed of 
JD points is | 
Zhonghedian, 
2038308028 | 
3940690,