This approach is called 2.5D and is condemned to fail for
arbitrary surfaces.
The modelling of real three-dimensional surfaces needs a 3D-
datamodel for the exact geometric and thematic representation.
Whereby the meaning of '3D' not only implies the usage of
three coordinates, but furthermore complete independence of
position and orientation of the surface in space, i.e. indepen-
dence from the coordinate-system.
This can be achieved by decomposing the surface into simple
pieces, thus obtaining high flexibility concerning the shape of
the surface. In our approach the surface is described and mo-
delled only with few basic topological elements. These are the
commonly used simplices: node, edge, triangle and tetrahedron
(Frank, 1986, Molenaar, 1994). These simplices are the basic
geometric entities of the respective dimension, see figure 1.
0-simplex node: 0
1-simplex edge: Q0
ds
2-simplex triangle:
3-simplex tetrahedron:
Fig. 1: Simplices of respective dimension.
The adjacency and incidence relations among these basic ele-
ments determine the topology of the surface (Neureither,
1992). The simplices together with their topological relations
form a skeleton of the surface. But it is not sufficient to
describe a surface only with topological relations. The surface
also has to be determined geometrically. This geometric de-
termination is done by relating the nodes uniquely to the mea-
sured data-points.
The topological structure automatically can be used for mathe-
matical representation of the surface, which can be done, for
example, with cubic Bézier-patches - which is not part of this
paper (Pfeifer, 1996).
An important element in the modelling of surfaces are lines.
These lines are used to model discontinuities of tangent-planes,
to exclude regions and for many other tasks. How to include
these lines into the basic concept? Lines can be described as an
ordered, connected aggregation of nodes and edges, i.e. a for-
mal sum of nodes and edges called 'chain' in Frank, 1986.
Lines are topological constraints which have to be kept and
preserved in the triangulation.
2.3 Discussion
The presented approach has some advantages in comparison to
former concepts in surface modelling (refer to the requirements -
in chapter 2.1):
+ The simplices, as well as the topological relations are
completely independent of the coordinate-system.
The topological relations determine the situation of
adjacent elements. These neighbourhood-relations can
be instantly used for local algorithms.
The concept is flexible enough for the modelling of
arbitray surfaces.
The concept is general in the sense that it can be used
to model lines, surfaces and bodies. Hence different
dimensions can be combined.
The topological relations can be used immediately for
the mathematic representation of the surface, e.g. with
triangular patches.
The geometric decomposition of the surface can also be
extended to thematic attributes related to the surface,
thus to model non-geometric information.
The main disadvantage of the approach is the problem to find
the topological relations which are not known a priori. A solu-
tion to this problem is presented in the following chapter.
3. BUILDING THE TOPOLOGICAL RELATIONS
3.1 Triangulation
In general the topological relations between the data-points are
not ,, measured”, i.e. no further informations than the coordina-
tes are sampled. The topological relations have to be deduced
from an unorganized cloud of points in space. Furthermore they
are not uniquely determined, i.e. it depends on someones inter-
pretation which points can be seen as neighbours on the sur-
face and which can not.
A well known method to establish these relations is a triangu-
lation of the data-points (Cline 1984). A triangulation is a
partition of the surface into triangles with the data-points as
vertices. The triangles mustn't overlap, nor are holes allowed.
There exist many solutions to the triangulation of points in the
plane, but only few for triangulation of points of N°. Three
different approaches for 3D-triangulations can be suggested:
* Tessellation with tetrahedrons and extraction of the
desired surface.
Triangulation of the 3D-points by utilizing additional
information or properties of the surface.
Projection of the problem into N°, e.g. triangulation in
a plane, such as the ground plane.
A method of the second approach has been presented in Choi,
1988. But this method has a big disadvantage: a distinct point
is necessary, from which the whole surface has to be visible.
Such an outstanding point can not always be guaranteed. The
method presented here is a further development of Choi's
method, without the necessity of the above mentioned point.
The developed method works locally and incrementally - to
support progressive sampling. The insertion of a point happens
in four steps:
Locating the triangle the point belongs to.
Integrating the point within the triangle.
Optimizing the triangulation.
Establishing constraints (lines).
3.2 Locating the triangle
The first step of inserting a point is to find the correct triangle
the point belongs to. This is done by using an order-criterion.
Order is a relation, which stands between geometric and topo-
logical relation (Schlieder, 1995). In the plane a point lies
inside a triangle, if it lies left of every edge of the triangle
(assuming the edges are ordered in anticlockwise manner).
This left/right-relation is clear in the plane. But in 3D-space no
such relation exists between edges and points.
408
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996
ap
If
CO!
tri:
dat
tion
teri
knc
tria
