can be found in Mäntylä (1988). The papers by Li (1993)
and Rikkers et al. (1994) are also interesting in this
context.
2.1 Basics of Boundary Models
Boundary models describe 3-D objects using a hierarchy
of vertices, edges and faces. The object's surface is a
collection of faces that intersect each other only at the
common edge. Each face is made of edges and vertices
that bound the surface patch itself. The representation of
the solid object is formed when the set of faces is closed.
The edge of the face does not have to be a straight line,
nor does the face of the object have to be a planar
surface. Instead of lines and planes it is possible to use
parametric curves and surfaces to describe the shapes
of the elements. The positions and shapes of these
geometric elements are usually referred to as the
geometry of the boundary model. On the other hand, the
connections and relationships between the elements are
referred to as the topology of the boundary model.
Many different data structures have been proposed for
representing boundary models. These include polygon-
based, vertex-based, edge-based and face-based
boundary models. An example of a polygon-based model
is the polyhedral model, which contains only a set of
planar face elements but no topological information about
them. On the other hand, the vertex-, edge- and face-
based models inherently enable the representation of
topological information. They differ from each other on the
basis of how the topological information is maintained
inside the data structure. The most common data
structures are called the winged-edge data structure and
the half-edge data structure.
A valid boundary model defines solid objects that fulfil the
following validity criteria (Mäntylä, 1988):
1. The set of faces is closed.
2. Faces intersect each other only at common edges and
vertices.
3. Edges of the faces do not intersect themselves.
The first two criteria exclude self-intersecting objects,
and the third criterion rules out objects that are open. The
first criterion ensures the topological integrity of a
boundary model. This condition is fulfilled when each
edge belongs to exactly two faces. In other words, the
surface forms a 2-manifold, i.e. a surface where every
point has a two-dimensional neighbourhood with all other
points of the surface (Mäntylä, 1988). The second and
third validity conditions ensure the geometric integrity of
a boundary model. Note that the geometric integrity
cannot be enforced directly with the help of the chosen
data structure. Instead it has to be guaranteed through
comparisons between each element of the model, or
alternatively by limiting the scope for creating or editing a
boundary model.
2.2 Construction of a Boundary Model
Boundary models are often formed by a sequence of local
incremental operations that guarantee the topological
integrity of the model within each modification step. Here
the model is updated with the help of special tools called
Euler-operators. These construction tools are based on
the Euler-Poincaré formula (Mäntylä, 1988). This formula
states that the numbers of vertices (v), edges (e), faces
214
( f£), shells (5), rings ( r) and holes( h) in a valid boundary
model are balanced through the following equation
v-e+f=2(s-h)+r. (1)
In the model construction phase the use of Euler-
operators guarantees that the above formula is valid in
every step. A boundary model that is constructed with
Euler-operators is always topologically valid.
Euler-operators work in much the same way as humans
draw graphical objects. A common set of Euler-operators
contains 10 different tools for building a boundary model.
These 10 operators are called mvfs, mev, mef, mekr,
mfkrh, kev, kef, kvfs, kemr and kfmrh. Here the letter "m"
means "Make" and the letter "k" means "Kill". The other
letters are as in the Euler-Poincaré formula. For instance
the operator "meV" is read as "Make Edge and Vertex".
Euler-operators as such are too primitive for users of
graphical systems. Normally, Euler-operators are hidden
inside high-level tools containing several operators
organized into a meaningful sequence. These high-level
tools include operations like formation of a face from a
sequence of vertices or sweeping of a set of face
elements through space to form a solid.
2.3 Example of Euler-operators
Figure 1 illustrates the incremental creation of a boundary
model of a simple building. The upper set describes the
sequence of construction steps used to create the
geometric model. The lower set in the figure shows the
Euler-operators that correspond to the editing steps
shown in the upper set. The lower set also shows two-
dimensional plane models that describe the topological
properties of three-dimensional objects (Mántylà, 1988).
Note that in practice many operators can be grouped
together, and some of the operations are done
automatically after an editing step. It is obvious that the
boundary model in the figure can also be constructed
using a different combination of Euler-operators. It is also
easy to imagine a situation where the topological
properties of the object are valid but the resulting model
no longer describes a solid object.
3. IMPLEMENTATION OF TOOLS FOR
BUILDING EXTRACTION
The semi-automatic feature extraction is a tractable
approach to building extraction, especially when the goal
is to create detailed geometric models of buildings. Semi-
automatic tools are used to make the extraction work
more fluent and more efficient. An important part in the
implementation of these tools is image matching. With
efficient matching tools the work-load of the user can be
reduced significantly. The basic geometric primitives in
this extraction work are points, lines and planes. In the
following, we concentrate on the image matching of lines.
A method for the constrained multiphoto matching of a
line is described in detail. The matching method is a
variant of the well-known least squares matching
(Fórstner, 1982). In the present paper, least squares
matching is done by search techniques, instead of least
squares adjustment. The search is done in object space
in a way similar to works by Wrobel (1987), Helava (1988),
Gruen and Baltsavias (1988). The theoretical principles of
least squares matching by search are described in
Sarjakoski and Lammi (1996).
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996
Figu
mod
the t
