anbul 2004
systems 1s
| objects is
e building
done each
vectorial
xample by
> present.
ith such a
irstly, the
ondly, the
modelling
ia! model
squares in
sentation).
represent
the whole
'osciences
X4 spatial
ually (the
r) and the
to have a
the latter
e indexed
be able to
nena. The
r and the
presented,
Ney even
| and this
presented
There are
Voronoi
; depends
r-defined
case with
Delaunay
d since
for most
ND
tions are
examples
je of an
o model.
convert a
voxels).
ased and
hey have
irregular
iat these
a. It has
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B2. Istanbul 2004
been shown that natural neighbour interpolation (Sibson, 1981)
avoids most of the problem of traditional methods and performs
well for irregularly distributed data (Gold, 1989; Watson,
1992). This is a method entirely based on the Voronoi diagram
for both selecting the neighbours and assigning a weight to each
of them; and it is valid in any dimensions. To interpolate at
location x in 3D, a temporary point x must be inserted into the
VD. The neighbours involved in the interpolation process are
the neighbours of x, and the weight of each is defined by the
volume that the Voronoi cell of x steals from the Voronoi cell
of the neighbour in the absence of x.
Although the method has been implemented with success for
2D applications (Watson, 1992), its use in 3D is quite limited
because its implementation is a complicated process that
requires the computation of two VD — one with x and another
one without — and also of the volume of Voronoi cells. An
algorithm that uses flipping and an incremental insertion
algorithm, as described in Sections 3.1 and 3.3, has recently
been developed by the authors of this paper (Ledoux and Gold,
2004). The algorithm is efficient (its time complexity is the
same as the one for inserting a single point in a VD/DT) and we
believe it to be considerably simpler to implement than other
known methods, as only an incremental algorithm based on
flips, with some minor modifications, is needed.
5.2 Extraction of Iso-Surfaces
It is notorious that three-dimensional data are very difficult to
visualise, even within a 3D environment that offers translation,
rotation and zoom functions. One of the best ways to better
understand a dataset is to extract and visualise in 3D an iso-
surface from it. An iso-surface (see Figure 6), also called an
implicit surface, is the three-dimensional analogous concept of
an iso-contour line in two dimensions: it represents the space
where the attribute of a dataset has the same value. The most
common algorithm to extract iso-surfaces, called marching
cubes (Lorensen and Cline, 1987), was designed to work with a
voxel input only. This algorithm can nevertheless be easily
rewritten to work with a set of adjacent tetrahedra instead of
cubes: each tetrahedron of a DT is visited and the intersections
between the implicit surface and each edge of the tetrahedron
are computed by linear interpolation. There are three possible
cases for each tetrahedron: no intersection; three edges intersect
and therefore a triangular face of the implicit surface is created;
or four intersections, in that case two triangular faces must be
created. The resulting implicit surface is formed of many
adjacent, but topologically unconnected, triangular faces, which
is ideal for fast rendering.
With the new techniques developed in recent years in computer
graphics, it is possible to draw many iso-surfaces and view them
all by using 'transparency' techniques, by assigning different
colours to each, by 'peeling off' surfaces and by navigating
inside and outside to see the shape. Visualisation therefore
plays an important role in understanding a dataset, as it
becomes a form of qualitative spatial analysis. Head ct al.
(1997) give more examples of how visualisation can help to
better understand an oceanographic dataset.
5.3 Temporal Data and Real-Time Applications
The VD permits insertion, deletion and movement of objects
with local modifications only; thus everv operation is reversible.
As shown in Gold (1996), by simply keeping a ‘log file' of every
operation done it is possible to rebuild each topological state of
a map, at any time. This solves a big problem with temporal
Figure 6. Example of an iso-surface extracted from 3D data
points.
data and GIS, and it is valid both in 2D and 3D. There is no
need to keep various ‘snapshots’ on the data at different time for
further analysis: when a map a at specific time is desired, it is
reconstructed from the original data from the log file. A map
can also be viewed like a 'movie' of the changes during a certain
period of time with for example boats and water moving.
This spatial model also permits 'real-time' applications, i.e. as
data are collected at sea, they can be quickly processed and
added to the system for analysis, without rebuilding the whole
topological relationships. This permits us to directly evaluate at
sea the quality of a survey done and to correct mistakes or add
new data while the boat is still near the site. Hatcher and Maher
(1999) present more examples of real-time GIS applications at
sca.
6. DISCUSSION
The main objective of our research is to build a complete spatial
model to manage and analyse oceanographic data. We have
presented the main properties of the 3D Voronoi
diagram/Delaunay tetrahedralization and showed that it can
indeed solve most of the problems arising when other methods
are used. We have already implemented many construction and
modification operators and we are planning to implement all the
algorithms discussed in this paper. We have also developed
some 3D spatial analysis functions and are currently working on
building a more complete list. Finally, the results of this
research are not only limited to oceanographic data, as the
needs for modelling these data are similar to the needs in other
fields, such as geology and atmospheric sciences.
7. ACKNOWLEDGEMENTS
The first author would like to thank the support from Hong
Kong's Research Grants Council through a research
studentship. The second author acknowledges the Research
Grants Council, Hong Kong, project PolyU 5068/00E for the
support of this research.
8. REFERENCES
Aurenhammer, F., 1987. Power diagrams: properties,
algorithms and applications. SIAM J. Comput. 16: 78-96.
Barber, C.B.. Dobkin, D.P. and Huhdanpaa, H.T., 1996. The
Quickhull algorithm for convex hulls. ACM Transactions on
Mathematical Software, 22(4): 469-483.
707
