Full text: XVIIIth Congress (Part B2)

  
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
	        
Waiting...

Note to user

Dear user,

In response to current developments in the web technology used by the Goobi viewer, the software no longer supports your browser.

Please use one of the following browsers to display this page correctly.

Thank you.