705 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008 
Fig4 Recursive algorithm of Growth Triangles Classification 
contiguous relations of major surfaces are lost, which actually 
exist between the real surfaces. So this method use these small 
surfaces (considered as noise) transfer the contiguous relations 
between the major surfaces. Like Fig8 shows that, surface 4, 5, 
6 are noise surfaces, and the contiguous relations between 
major surfaces 1, 2, 3 are lost. As an example of this method, 
the noise surface 4 is the contiguous surface of major surface 1 
and 2. So the surface 4 will transfer this contiguous relation to 
the major surface 1 and 2. In this way, the surface contiguous 
relations among the major surfaces can be restored. 
Fig7 3D spatial index 
Fig5 shows the result of Recursive algorithm of Growth 
Triangles Classification. Different blue level in Fig5 represent 
different surface (one class in the triangle classification) of the 
object. 
Fig5 examples of Growth Triangles Classification 
2,2 Surface contiguous relations restoration 
Due to the unorganized discrete sampling of point cloud data, 
the major surfaces extracted in the Triangles classification and 
Surface extraction (2.1) lack the contiguous relations. But these 
relations are significant and basic information to get the 
geometric features and building the model of the object. 
There are two methods used in this paper to help restore the 
surface contiguous relations. The first method is based on a 3D 
spatial index. Like Fig7 shows that, the space, containing the 
point cloud, is first subdivided into small commensurate cubes, 
whose size is determined by sampling density. Under this 
circumstance, every surface of the polyhedron penetrates a set 
of cubes, therefore the spatial range of each surface, known as 
its buffer could be expressed by the very set of cubes. Finally, 
the contiguous relations of the surfaces could be obtained 
through comparison among buffers, if two buffers include same 
cubes, the two surfaces are contiguous; else they are not. (The 
contiguous relations cannot be directly taken out from the 
contiguous relations of the triangles, because data might get lost 
in the sampling process of point cloud at the vertices and edges 
of the polyhedron.) In Fig7, the contiguous relations of the three 
3D surfaces (not plane) can be built by the spatial index. 
The second method is based on the transfer of surface 
contiguous relations. Because there are many small surfaces 
(considered as noise) between the major surfaces, the 
Fig8 transfer of surface contiguous relations 
2.3 Polyhedron Vertices solution and Polyhedron model 
Reconstruction. 
After the twice step, the contiguous relations of polyhedron 
surfaces could reveal that which two surfaces share an edge and 
which three or more surfaces share a vertex. Then the 
coordinates of all vertices, together with the equations of all 
edges, could be calculated based on the equations of the 
surfaces 161 . Furthermore, the contiguous relations of polyhedron 
surfaces helps to determine which two vertices of the 
polyhedron are the terminal points of a certain edge, and which 
edges of the polyhedron surround a certain surface [7][X l At this 
point, the whole polyhedron model is built from the point cloud. 
The geometric features, containing vertices, edges and surfaces, 
are already extracted from the point cloud data. And the 
topological relationships among the geometric features are also 
obtained. The results are expressed in Section 3 Examples. 
3. EXAMPLES 
In this section, the research of extracting geometric information 
from the point cloud of building in this paper is proved by 
several examples. The geometric features, containing vertices, 
edges and surfaces, and the topological relationships among 
them are extracted from the point cloud data. In Fig9, there are 
four examples of the combination of the polyhedrons (from 
example 1 to 4), and one of car as contrast. And the related 
information is showed in Tabl. From these five examples, to 
the object, this can be approximately considered as polyhedron, 
the method introduced in this paper can effectively extract the 
geometric features. To the object (like the car in example 5), 
whose surface is the curved surface, the result is not complete.