Istanbul 2004
with endpoints
and define a
red along with
ces and planar
cess enter the
elow.
VTCHES
| 3D space. So
in parametric
requires plane
Reconstruction
1e intersection,
| the following
are not parallel
in one point if
fore, in regular
if they are not
"m, a system of
as exactly one
endent. More
>s are linearly
regular system
d in eq. 6:
(6)
stants. In order
rs, let:
1y independent
| has a unique
s rule (Pedoe,
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
x=A,/A y=A,/A =A JA
where :
[^m k, a, (8)
A =a, & ow,
nn Fa d.
d a M
A mi dac da ks
4 05 £5,
Every three planar faces of the model are intersected and the
intersection point, if there is one, is stored as a vertex for each
of the three faces.
42 Verification of vertices
Intersection of model faces may generate incorrect vertices.
Figure 2(B) shows an example of an incorrect vertex generated
from the intersection of three model faces. All generated
vertices, therefore, have to be verified, in order to identify and
remove incorrect ones. To identify incorrect vertices, two
constraints are used as follows:
o Constraint 1: A valid vertex lies either in or under any roof
plane.
Recall that each building part is assumed to have one of the
three presumed roof types: flat, gable and hipped. For these
building types, all model vertices lie either in or under any roof
plane. This property allows us to verify model vertices and
identify invalid ones. The verification is carried out by
evaluating the function of the roof plane with the coordinates of
the vertex of interest. This will result in Zero if the vertex lies in
the roof plane, otherwise the sign of the resulting value and the
direction of the plane normal vector determines whether the
vertex point is above or under the roof plane. Every vertex is
verified against all roof planes and is removed if it is higher
than any of roof planes.
Figure 2: Intersection of model faces may generate
incorrect vertices. A. A correct vertex; B. An
incorrect vertex.
Constraint 2: A valid vertex projects on or inside the
polygon of the ground plan.
This constraint is based on the assumption that roof caves do
not overshoot walls. Figure 3 illustrates the procedure to verify
whether a test point is on or inside a polygon. First vectors are
formed from the test point to every polygon vertex and then
cross product of every two adjacent vectors are computed. The
test point is determined inside the polygon, if all computed
cross products are non-zero and have the same sign. Otherwise
if cross products are non-zero with different signs, the test point
is outside the polygon. If any of the cross products is zero then
the test point is determined to fall on a polygon side or on the
extension of a polygon side. The distinction between the two
cases is made by checking the dot product of the corresponding
two vectors (which have a zero cross product). For a point on a
side of the polygon, one of the cross products is zero and the
corresponding dot product is negative, while for a point on the
extension of the polygon side the dot product is positive (figure
3).
1 1 “p 1 1
A B C D
7 P. A B C D
Pl, xb PX POI XE PR
P] m + : 2 : + +
P2 P3 + + 0 * 0 -
ps PA + + + + + +
ps Pl + + + * v
x _: Cross Product
O : Dot Product
Figure 3: Four possible positions of a point with respect to a
polygon. A. Point inside the polygon: all cross
products are non-zero and have the same sign; B.
Point outside the polygon: cross products are non-
zero but have different signs; C. Point on the
extension of a polygon side: a zeros cross product
with a positive dot product of the corresponding
vectors; D. Point on the polygon side: a zero cross
product but the dot product of the corresponding
vectors is negative.
A correct vertex is one that satisfies both constraints. An
incorrect vertex will fail to satisfy one or both constraints and
will be removed from corresponding planar faces.
4.3 Sorting of vertices
For graphical visualization of the reconstructed model, vertices
of each planar face must be given in order. To sort vertices a
simple algorithm is used, which is based on forming vectors
from the centre of gravity of vertices to each vertex and finding
the angle between each vector and a starting vector (figure 4).
The angle between vectors jj and y is given by the dot
product:
ov
cos(&) = 17] (9)
kal]
Since cosine function returns the same value for xa, the sign of
the cross product between the two vectors is used to determine
the direction of the angle. The algorithm starts with an arbitrary
vertex and sorts other vertices with respect to the angle of their
