Claus Brenner
e Semiautomatic systems have been reported (Grün and Wang, 1998, Gülch et al., 1999) which use aerial images and
reduce the number of manual interactions required to acquire buildings compared to the fully manual case.
e It can be doubted that automatic systems can achieve success rates comparable to human operators within the next
few decades (this statement is due to W. Förstner, (Förstner, 1999)).
e Companies which nowadays collect three-dimensional city models still rely almost exclusively on manual measure-
ment, even though the measured models are not very detailed and/or relatively low accuracies are obtained.
Considering the last two statements, it is our opinion that semiautomatic systems are the only way to serve todays needs.
They can be used in large, practical projects, so feedback from users should lead to a fast evolution towards productive
systems. They can also be taken as a kernel of a system where fully automatic algorithms can be incrementally tested
and integrated. In our opinion, it is not only desirable to have semiautomatic systems which try to reduce the number of
operator interactions per building. Rather, one would like to have a system which reconstructs a considerable number of
buildings without any operator interference at all. Also, the system should point the operator to those buildings where
the automatic reconstruction has possibly failed. Thus, it is our goal to increase the number of buildings amenable to an
automatic reconstruction while of course keeping in mind that there will always be a certain percentage left which needs
an additional operator-assisted treatment.
In the past, we have reported on our fully automatic building reconstruction system, which relies on a laser scanning
DSM and existing ground plans (Brenner and Haala, 1998). The major reconstruction steps of this system were (a) the
subdivision of the ground plan into rectangular (2D) primitives, (b) selection of a three-dimensional primitive for each 2D
rectangle based on analysis of the DSM (c) estimation of the parameters for each 3D primitive, and (d) assembly of all 3D
primitives in order to obtain the model of the entire building. Considering the hierarchy of models in figure 1, the class of
buildings that can be reconstructed this way (combined parametric) lies in between the class of parametric and the class
of general polyhedral models. Naturally, if one wants to enlarge the number of buildings that can be modelled correctly,
a more general building class has to be chosen.
BEd DT
Parametric Combined Prismatic Polyhedral Ruled Freeform
Parametric
Figure 1: Classes of building models.
2 CONSTRUCTING ROOFS FROM GROUNDPLANS
2.1 Medial axis and straight skeleton
Suppose a ground plan is given in form of a polygon P (a single, simple, planar polygon with no holes). One can imagine
that from each polygon segment there emanates one plane with a given slope, inclined towards the interior of P (assume
for the moment that all planes have identical slope). The intersections of the planes will yield crest lines (where two
planes meet) and points (where three planes meet). When projected down into the plane of P, a planar graph G results.
As the graph edges are projections of straight lines in 3D, they are themselves straight lines in 2D.
The medial axis M(P) of P is the set of points inside P which have more than one closest point on the boundary of
P. At a first glance, it seems that the points covered by a drawing of G and M(P) are identical. However, this is only
true for convex P, since the medial axis for polygons with reflex vertices contains curved pieces, which cannot be part
of G (Fig. 2(a)). Instead, the graph G can be constructed as straight skeleton S(P) (Fig. 2(b)). In order to define the
straight skeleton, we can think of a "shrinking process" where the points of the original polygon P move inwards along
their angular bisectors until either an “edge event” or a “split event” occurs ((Aichholzer and Aurenhammer, 1995), see
also Fig. 2(c,d)). Following these events, one or two new bisectors are generated. Interestingly, the straight skeleton can
neither be defined by a distance measure nor can its construction use a divide-and-conquer approach. An O(N log N)
time complexity algorithm (which would be optimal) has not yet been found (Eppstein and Erickson, 1999). However,
we shall not be concerned about time complexity here, since in our application, N is typically small.
Given the polygon P and the slopes of all planes, the graph G — S(P) is determined uniquely. The class of roofs defined
by the straight skeleton lies in between parametric and polyhedral models. By setting all slopes to zero, prismatic models
can be handled. Saddleback roofs are obtained by setting the slope of two roof faces to infinity. However, straight skeleton
roofs have only one single eaves height whereas combined parametric roofs may have multiple eaves heights.
86 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.