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.