ed 
nt 
nd 
u- 
oi, 
int 
le. 
‘he 
IS 
ns 
ies 
To substitute this order-relation for the edges of the triangula- 
tion, Choi uses the given distinct point. In our approach 
another - more intrinsic - property of the surface is utilized: the 
surface-normal in the data-points. 
With the use of the normal a left/right-criterion can be 
established: Let k be an edge of the triangulation with the 
endpoints A and B, with coordinate-vectors a and b. Let n be 
the surface-normal in A, and P, coordinate-vector p, the point 
to be inserted. P lies to the right of the edge k, if 
d = ((kxn),(p—a) > 0 (figure 2). 
  
  
A kxn 
Fig. 2: Order-criterion using the surface-normal. 
This order-criterion is repeatedly applied to the edges of the 
triangulation, until the correct triangle is found. 
The surface-normal in a data-point is estimated with the use of 
the neighbours of the point. A common method is to build the 
normals on every triangle the point belongs to. The normal in 
the point results as a weighted sum of these triangle-normals. 
Whenever the triangulation changes, all concerned normals 
will be refined. Sometimes the normals are given a priori, in 
that case these vectors will be used - e.g. in automatic image 
matching the object-normals easily can be estimated. 
Nevertheless, the estimated normals sometimes are only rough 
approximations of the actual normals what may lead to errors 
in the locating-step. 
If additional information exists - such as break-lines or 
contour-lines -, they will be utilized for the locating of the 
triangle, as well as for the estimation of the normals. Finally, it 
is planned to check the correctness of the integration with 
regard to blunder detection. 
3.3 Integration of the point 
As soon as the correct triangle has been found, the point will 
be inserted, i.e. all necessary edges are build. The point can 
also lie outside the triangulated region. In that case the point 
has to be connected with the „visible“ part of the boundary. 
3.4 Optimization 
As mentioned above, the topological relations between the 
data-points are not uniquely determined. Nor is the triangula- 
tion of the point-set. One has to formulate a criterion to de- 
termine the result of the triangulation. Such criterions are 
known as optimization-criterions, as the criterion optimizes the 
triangulation in a specific sense. 
Commonly, as in this work, the optimization-criterion is 
applied edgewise (Cline, 1984 and Choi, 1988): an existing 
edge of the triangulation will be tested, whether the criterion is 
hurt or not. If. the edge doesn't match the criterion, it will be 
swapped in the corresponding quadrilateral - see figure 3. 
B 
RU 
SU 
Fig. 3: Swapping of an edge. 
The best-known optimizing-criterion is the circle-criterion, 
which is equivalent to the max-min criterion. This criterion 
leads to the well-known Delaunay-triangulation. This triangu- 
lation is optimal in the sense that it produces regular triangles, 
near to equilateral triangles. Unfortunately, these algorithms 
are 2D only. 
For our 3D-triangulation several criterions have been imple- 
mented and tested: 
'  3D-Delaunay' - the minimum angle of two adjacent tri- 
angles is maximized. 
‘Smoothness1' - the angle between the planes of two 
adjacent triangles is maximized, thus to gain a smooth 
surface. 
'Smoothness2' - the minimum angle between the planes 
of the two adjacent triangles and the four neighbour- 
triangles is maximized. This method was presented in 
Choi, 1988. 
'Smoothness3' - a combination of Smoothnessl and 
Smoothness2. 
‘Greedy' - the sum of the length of the edges is 
minimized. The greedy-triangulation is a widley used 
method. 
2D-Delaunay' - the triangulation is optimized by 
applying the Delaunay-criterion to the ground-pro- 
jection of the points. Naturally, all other 2D-criterions 
could be used also. . 
combinations - all above criterions can be combined by 
a target function to form new criterions. 
The optimization-criterions can be - or have to be - extended 
with further constraints, e.g. conditions to avoid irregular 
swaps, which would lead to overlapping triangles. 
3.5 Constraints 
For a flexible modelling of surfaces, it should be possible to 
apply topological constraints on the triangulation. A prominent 
example are lines, which are included as a chain of edges. 
These edges must exist within the triangulation. In the last step 
of the insertion of a point such constraints are introduced. 
Figure 4 shows an example for a constraint-edge. The building 
of this edge works again with the use of the local order- 
criterion. 
409 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996