David Heitzinger
All approaches define measures for evidence and functions for propagation of evidence, where four types of propaga-
tion are necessary:
l. Propagation by conjugation (and).
2. Propagation by disjunction (or).
3. Propagation by inference, i.e. determination of evidence, when applying a rule.
4. Combination of evidences: when several rules assign different evidences to a diagnosis, an overall evidence has to
be computed.
3.3 Inference of decisions
For the application of the rules several different techniques are possible. These approaches differ in their strategy to
select rules from the rule-base to evaluate. Mainly two approaches are used:
e Forward Reasoning: a data- or symptom-driven approach. All rules, whose pre-conditions are fulfilled by the data,
are selected and executed.
e Backward Reasoning: a task- or diagnosis-driven approach, where all rules are selected and executed which contain
the task in their consequent-part.
Both approaches can be refined, to minimise the amount of rules executed: by the use of given priorities, a certain order
of the rules, content of the rules or an organisation of the rules, due to some semantic context. In this approach a For-
ward Reasoning method has been implemented following a rather fixed strategy of rule selection: a so-called rule-tree.
4 3D-TRIANGULATION
In the presented approach the triangulation is performed in two steps: at first a tetrahedral tessellation is calculated and
secondly those triangles will be extracted from the tessellation, which belong to the surface.
4.1 Tetrahedral tessellation
The use of a tetrahedral tessellation (calculation see Edelsbrunner and Miicke 1994 or Hoschek and Lasser 1992) as the
base of the triangulation has several reasons:
e The amount of possible triangles is reduced to the ones, contained in the tessellation.
* Lines are already contained as constraints in the tetrahedral tessellation.
* Intersecting triangles are impossible, hence it is easier to ensure a valid triangulation.
e A tetrahedral tessellation is a topological structure which allows efficient analysis of the data. Also many calcula-
tions and queries are supported by this structure.
Due to the expected large amounts of data, it had been necessary to implement the tessellation algorithm with a paging-
mechanism. The tessellation is divided into tiles of different size by the use of an Octree-structure. Tiles, which are
currently not used by the algorithm, will be written temporarily onto hard-disk. Thus, large amounts of data can be
processed.
4.2 Extraction of triangles
From the triangles, included in the tetrahedral tessellation, the ones belonging to the surface are extracted by application
of the rules. This is done step by step, always adding one triangle after the other to the already extracted surface. This
incremental approach has the advantage that properties of the triangle, related to its neighbour on the surface, can be
exploited, e.g. the angle between these two triangles. A similar, stepwise
algorithm is presented by Boissonnat (1984) or by Mencl and Müller (19972),
only the set of triangles to be tested is limited otherwise. i 7 Ss
For each step the inference mechanism is applied for all candidate triangles Y
and the one with the highest evidence is added to the extracted surface. A set
of candidate triangles is defined as all triangles belonging to one edge of the
border of the already extracted surface. Figure 3 shows an intermediate step
for a simple closed surface. About half of the triangles are already extracted
from the tetrahedrons.
5 RULE-BASE
The rules, which are used to separate the triangles of the surface from the
other ones, are the most important part of the program. These rules should — Figure 3, an intermediate step in sur-
include the knowledge we want to use for extraction. Corresponding to the face extraction.
384 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
