International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
2. RECONSTRUCTION METHOD
In general, buildings show a large diversity in their geometry.
Therefore, it is impractical to expect that one strategy can
handle all types of complex buildings. In this study, we only
focus on building with right angle corners. We first reconstruct
roofs and then reconstruct walls of the building, where the
former is the focus of our discussion below.
The main idea of roof reconstruction is that most roofs with
right angle corners in their horizontal base can be decomposed
into an aggregation of simple roof types. Therefore our strategy
for 3-D roof reconstruction is to deal with a complex roof as a
CSG model. The CSG model can be divided into one or more
primitive roof models. Each of the primitive roof models
consists of a horizontal rectangular base and the roof can be
either one-ridge point, two-ridge points or four-ridge points roof
(Figure 1). To reconstruct the primitive model, we need to form
a (horizontal) rectangular base and generate polyhedral roof
surfaces. The workflow of primitive models reconstruction
starts by dividing points in the 3-D space into many 2-D
horizontal levels according to the height. Then we connect
points in each 2-D level to form rectangle bases. For those
points that cannot form rectangles, we classify them as roof
ridge points. The next is to reconstruct 3-D primitive models by
determining the corresponding rectangle bases for roof points in
3-D space. After reconstructing all possible primitive models,
we apply operations such as union and intersection to combine
them as a complete building roof.
To reconstruct walls of a building, we need to determine the
boundary outline from the roof and project the outline to the
ground. These detail steps are described in the following
sections.
one-ridge point ——-——* roof point
“— rectangular base
two-ridge points |
four-ridge points
Figure 1. Primitive roof models.
2.1 Finding 2-D rectangular bases
To decompose a complex roof into primitive roofs, the first step
is to find rectangular bases of primitives. This process is
working on each 2-D horizontal level. The roof outlines with
perpendicular edges can be treated as 2-D polygons. Essentially,
it is a process of rectangulating the points as opposed to the
well-known triangulation, namely rectangulation.
Rectangulation involves rectangles produced from a set of
points from a polygon with only perpendicular edges, with the
restriction that overlapping rectangles are not allowed. The
hypothesis is that such polygon can always be partitioned into a
set of rectangles. The purpose of rectangulation here is to find a
feasible combination of rectangles for roof outlines. Our
approach is described below.
554
There are two initial steps for rectangulation. The first is that the
building data, which is represented by a set of points with 3-D
coordinates (Figure 2a), should be separated into different levels
based upon height information in their z-coordinates. The
second is to rotate the dominant directions of a building align
with x and y-axis. Since our building outlines are perpendicular
edges, we can find two dominant directions of the building
perpendicular to each other. It starts from finding lines among
all points by using slope-intercept representation in each level.
Loop over the process for all levels. A reasonable assumption is
that dominant perpendicular lines are consistent across all the
levels and represent dominant directions of the entire building.
Once these directions are found, the building can be rotated to
align dominant directions with x and y-axis, respectively.
Figure 2a). 3-D points of a building.
We now can proceed to rectangulation in each horizontal level
separately. Processing starts by examining the set of points in
the i-th level, which is denoted by L;. If |L;| < 4, this level is
categorized as a set of roof points L. (Figure 2b). If |L;| 24,
the level is classified as an intermediate level (Figure 2c). Points
in intermediate level could be either roof points or base points,
therefore, further processing is needed. We decompose points in
intermediate level into rectangular bases automatically as below.
We start from the lower left point p,(x,,y,) specified by
Eq (1), where P; € L; represents the point set during the /-
th round of rectangulation process on the i-th level.
(1)
p,(x,,,) = min{min{P, (x, »)} }
After p,(x,,y,) is determined, we start looking for the
closest points located along the east and north direction,
which are denoted as p,(x.»,) and p,(x,»,).
respectively. Their coordinates are determined via
y, Qa)
P LL inf ^ = X =
X, E? mint (x, y) D, i , Y. =
x =
n
X, > Ya = minif, (x, y) TI Ds} (2b)
After p, and p, are identified, move toward the
corresponding perpendicular direction to find p;(x;.y;)
which is diagonal to p, and determined by
Xj PEE, (2c)