formation, Beijing 
sa.edu.cn; 
ve the query 
s managed by 2D 
anized hierarchical 
large point image 
'S in Forbidden City. 
points with 
scattered point cloud 
scattered point cloud 
quired by scanning 
oned. Some scholars 
nage model and have 
construct TIN model 
. directed search and 
(LOP) is presented, 
»ency of network 
tion error and hole 
1g Xianfeng,2009);In 
| process, a spherical 
:pendence is used to 
es the time cost of 
nez, J.L, 2010). 
as a whole. They are 
ently, and the post- 
depend on the point 
ata is very high and 
of 3D points. It is 
of scanning stations. 
of Supreme Harmony 
ached to hundreds of 
risualize such a huge 
that must be solved at 
functions of edit, 
ersion of point cloud 
ve the problems from 
: and can't render the 
ie software can only 
:ss, then choose the 
s, which loses the 
t not only takes more 
> used conveniently. 
Forbidden City, they 
  
  
have features of components diversification , high query 
requirements and so on. So it has greater difficulties in 
organizing. storing. and managing the spatial data. 
In order to facilitate the scene rendering of overall point image 
model of buildings and improve the efficiency of processing 
and visualizing huge point image data, and ensure the safety of 
original data, this paper provides a new spatial index 
mechanism of huge point image model, which lays the 
foundation for post-processing and management of huge point 
cloud data. 
1.3 Present Status of Research on 3D Spatial Index 
In recent years, the research on spatial index of huge point 
cloud has made considerable development. In this section, we 
give a historical overview of the research in this field. 
Some researchers have also developed and used many ways to 
organize point image data, such as grid index (Wang Yanmin, 
2002a; Zheng Kun, 2006; Xia Yu, 2006), quadtree, octree, k-d 
tree (Shi Wenzhong,etc.,2007), three-dimensional R-tree and its 
variants (Guttman A,1984; Gong Jun, etc., 201 1). 
From evolution process of spatial index structure, some 
representative hybrid and integration spatial index are presented 
for various application requirements (Fu Yuchen, 2003; Xia Yu, 
etc, 2006). For example, in order to solve the problem of 
multidimensional point access, Robinson proposed Kd-b-tree 
index (Robinson, 1981); In order to solve the multi-path search 
problem which is caused by quadtree and R-tree index space 
overlap, Guo Jing, who mixed 2k-ary trees and R-tree index, 
presented the QR-tree spatial index. The spatial index improves 
search performance (Guo Jing, 2003). In order to manage 
massive point cloud data efficiently, some scholars have 
proposed a two-level hybrid method which is based on Hilbert 
code and R-tree index. The method clusters point cloud group 
by Hilbert space-filling curve and controls data volume of each 
group under the desired size (Lai Zulong,etc., 2009). In order to 
improve the generation and query efficiency of two-dimensional 
and three-dimensional target space index, Qing Zhu(Qing Zhu, 
2009;Gong Jun,201 l)invented a three-dimensional R-tree 
Spatial index method taking into account the multiple Levels Of 
Detail(LOD). The method uses the global optimum node 
selection algorithm and node shape factor of three-dimensional 
Cauchy value to ensure that the three-dimensional R-tree node 
distribution is more balanced. 
Most spatial index is based on Minimum Bounding Box (MBB) 
of point objects and spatial entities. However, the index 
granularity of spatial index basically reaches to a single point 
object. It is obvious that it can not apply to the amount of 
spatial data, especially huge point cloud data. Existing spatial 
index tend to support the LOD technology of the memory or 
external memory, which is copied to the point cloud data 
backup typically while generating spatial index and the LOD 
data. It uses the approach of "space for time" to select the 
desired level for processing and visualization. Current software 
Systems often use the program of hybrid and integration spatial 
index mechanism and the strategy of use from each other. There 
I$ not a spatial index is superior to others (Cheng Kun, 2006; 
Shi Wenzhong, 2007).It often needs to design an appropriate 
Spatial index depending on the different application. 
2, SPATIAL INDEX MECHANISM OF POINT IMAGE 
11 The Design Idea of Quad-MBB Tree 
The design of Quad-MBB(QMBB) tree uses the grid property 
of point Image. The building method is based on 2D quadtree 
space index in top-down way according to the point image's 
number of rows and columns. It carries on dichotomy on the 
basis of horizontal and vertical step angle respectively and does 
2D segmentation to the point image data. Every segment forms 
a 2-D Minimal Bounding Rectangle (MBR).As shown in the 
left column of Figure 2, it represents the quadtree segmentation 
based on 2D range image of point image. According to each of 
the corresponding point image of MBR, a Minimal Bounding 
Box (MBB) is calculated in 3D space, with 2D quadtree to form 
3D-MBB tree, as is shown in the right column of F igure 2.The 
2D quadtree and 3D-MBB tree integrate up and constitute the 
2D-3D spatial index:QMBB tree, which has both 2D and 3D 
features. 
  
  
  
  
  
Figure 1 The Data partition of QMBB-tree spatial index 
Index particle size of QMBB tree spatial index is a MBR and a 
MBB, which is a point set index actually. General quadtree 
nodes contain only 2D information, but the proposed QMBB 
tree in this paper contains both 2D and 3D properties. QMBB 
tree supports 2D and 
3D space query and 
retrieval, and the 
point image model 
after splitting has no 
overlap points. In 
addition, the 
sampling points 
within non-leaf node 
of OMBB tree are 
/ Quar dEBBTrecHode 
  
    
   
   
   
  
19 children 
2 Coord0ffset 
  
6.2 MER 
from the original mmr 
data without Ti pParent. 
interpolation B.» strCode orn 
operation to ensure | | ; ^ MAR rm creme 
data accuracy. Node 
data structure of 
QMBB tree spatial 
index is shown in 
Figure 3, consisting 
of the identification children pointing to the children node and 
the pParent logo pointing to the parent,3D coordinate offset 
named CoordOffset, 3D point ID migration called IDOffset, 3D 
point data ID called IdList, MBBox property of node MBB, 
MBR property for the ranks of the node location, the name of 
the node coding named strCode etc. The code of the node's 
name uses linear quadtree coding method,and encoded string 
length of each node name represents the node depth in QMBB 
spatial index tree. 
  
  
Figure 2 Data structure diagram of 
OMBB:-tree spatial index node