Antonio Ruiz
3 DESIGN
The TIN model is more complex than the grid model. We have to store on one side the geometric properties and on
the other side the combinatorial properties: We need a list of vertices with 3 coordinates each and a list of pointers that
describe explicitly how the vertices join to form the edges and how the edges join to form the triangles. Many structures
have been used to store triangulations and between them we have chosen the Double Connnected Edges List (DCEL)
introduced by Muller and Preparata in 1978 ((Preparata and Shamos, 1985)).
ru
«* dnext
> = right
left onext o
Figure 1: DCEL data structure
Edges in DCEL are oriented, but the orientation is arbitrary. Each edge has six pointers: one to the origin vertex and
another to the destination, one pointer to the next edge that is found rotating counterclockwise around the origin and
another to the next around the destination. Two more pointers are usually reserved to the left and to the right triangles,
The space required to store the triangulation is |P| — 6|E| = 18|V| where we have taken into account the Euler relation
and |P| is the number of pointers, | Æ| the number of edges and |V | the number of vertices.
We can find in constant time which vertices belong to a triangle and which are its neighbouring triangles. With the DCEL
it is possible to represent any plannar graph and in particular we can represent intermediate states of the triangulation that
appear while updating it. We can also store edge attributes without redundancy.
By default our surface will be the polyhedral surface formed by the flat triangles and we will not store the triangles
explicitly. In the general case the triangles will not hold any information and they can be recovered from their boundary
edges in constant time. For that reason our pointers to triangles will usually be null pointers but we reserve these pointer
for the extension of the polyhedrical surface model as will be shown later in this report.
3.1 Triangulation in external memory
There are many algorithms to construct the contrained Delaunay triangulation. The sweep line algorithm for the CDT
(Seidel, 1988) is a generalization of Fortune's algorithm for DT (Fortune, 1987). There is also a divide and conquer
algorithm for CDT (Paul Chew, 1989) that generalizes the algorithm by Lee and Schacter (Lee and Schachter, 1980).
Those algorithms are optimal within the real RAM model of computation (Preparata and Shamos, 1985) but they are not
dynamic. They require to sort all the points prior to triangulate them because they work on ordered sets of points. We
prefer for our application the incremental construction algorithm because it is fully dynamic, i.e. we can insert and delete
vertices and required edges at any time. This method is O(n?) in the worst case but the average cost is low with the
data distributions found in practice. Melhorn et al. showed in 1990 that randomized insertion of points is O(n log n) on
average with the advantage of being fully dynamic.
The real RAM computational model is not appropriate for our application. One better approximation for our case is the
two level memory model (Goodrich et al., 1993). In this model of computation two kinds of memory are considered: one
very fast that represents the computer RAM memory and another very slow that represents the disk storage. Operations
in the fast memory can be considered as instantaneous (^ 10 ns) in comparison to the external memory operations (^ 10
ms) that are a million times slower. We are aware of the optimal external memory algorithm for the computation of the
convex hull in 3D and this problem is equivalent to Delaunay triangulation but this algorithm is not dynamic and is Very
complex. We have not gone further in this direction. Instead we have followed a more heuristic approach.
The TIN data is irregular. In case our data set is very large it will not fit in core memory and when the program follows
pointers from one edge to another many page faults can take place. It is not affordable that each pointer access gives raise
to one I/O operation. To increase the performance of our algorithms we must minimize the number of VO operations and
reduce page faults. The technique available to do that is bucketing. Points and edges that are close in terrain should be
stored also close into disk because most of the operations that are performed on the TIN are local. Usually we are going
to recover or to update the information of a region corresponding to a photogrammetric model or to a sheet map. We are
not interested in the insertion of points distributed at random anywhere on the domain. If the information for this region
spans on a few pages on disk, a small number of I/O operations can be enough and the operation will be faster.
786 International Archives of Photogrammetry and Remote Sensing. Vol, XXXIII, Part B3. Amsterdam 2000.
3.2
The c
point
Point
distril
increl
becau
set. C
point
If the
We hé
The t
which
locati
The ic
but th
A BP]
contai
the cc
data s
of 40(
We ha
close t
we sez
startin
The al
maxin
space
void a
did a ı
——