ding
e of
an
| the
1 is
ree-
be
985]
le is
Size,
ught
ith a
very
are
DRE
ents
des.
aves
atial
tree
d to
e, it
ctly.
ther
3.2 Tetrahedral Network (TEN)
TEN has been concerned as a useful data structure in 3-
D GIS by many researchers for a long time [Raper and
Kelk, 1991]. It may be a powerful vector structure in 3-D
GIS. The concept of TEN can be readily formed from 2-D
TIN. Firstly, 2-D Voronoi is extended to 3-D forming 3-D
Voronoi, then TEN can be derived from the 3-D Voronoi
polyhedrons in the same way as deriving TIN from
Voronoi polygons. TEN is shown in Figure 2 and Table 3
is a kind of data organization of TEN, in which complete
3-D spatial topological relations and attribute data are
contained.
Figure 2. Tetrahedral Network (TEN)
Node Line
PN X YJOZI-ATT LN Points ATT
101 X401 Y101 Z 401 a 101,102
102 X402 Y102 Z102 b 102,103
103 X403 Yıos Z103 C 101,103
d 104,103
104 X104 Y104 Z104
Triangle
TN Segms Tetra1 Tetra2 ATT
«Q
9,
h
ÆA > X
0
Il
, 1
0
0
|
dj |
09090»
Table 3. Data Organization of TEN
Comparing with other solid structure, TEN has some
advantages [Xiaoyong C., 1994b] such as:
TEN is one of the simplest data structures and
consists of point, line, area and volume.
TEN is a linear combination of tetrahedrons, that
transformation of TEN equals to the combination of
transformed tetrahedrons.
TEN not only has advantages of solid structure such
as rapid geometric transformation but also has
505
advantages of BR such as fast topological relations
processing.
TEN is convenient for rapid visualization. During
display tetrahedrons are arranged depending on
front/back relations, then drawing from back to front.
However, TEN is not applied extensively until now
because of difficulty in generation. Now two algorithms
are developed. One is based on 3-D Mathematical
Morphology (MM) and raster-vector hybrid processing
[Xiaoyong C., 1994b]. The basic idea is that 3-D space is
represented by 3-D array completely and spatial points
are represented by voxels after a vector to raster
conversion, then sequential dilation algorithm in MM is
used to form 3-D Voronoi polyhedrons from which TEN is
derived. The other is based on 3-D Distance
Transformation (DT) [ Morakot Pilouk, etal. 1994].
Distance Transformation that was introduced by
Borgefors,G. [1984,1986] has been used in construction
of 2-D TIN [Tang, L., 1992]. The difference between
these two algorithms is dilation algorithm in MM or 3-D
Distance Transformation used.
3.3 Hybrid Data Structure
According to the discussion in last two parts, we can find
that storage space increases rapidly along with the
increasement of an resolution in Octree so that the
resolution cannot be in a high level. Also, Octree is an
approximate representation forever. However, Octree has
simple structure and convenient for spatial analysis such
as integral property computation and visualization. At the
same time, TEN has ability to represent object accurately
and describe complicated spatial topological relations
completely. Also, original obsverations are stored. But
TEN is difficult to be erected and has complicated
structure, and in some cases large storage space is
needed.
In this paper, authors present a hybrid data structure
based on Octree and TEN which is similar to hybrid data
structure in DTM [Fritsch and Pfannenestein, 1992]. In
which Octree and TEN are combined and advantages of
each are integrated such as a more accurate
representation of object by hybrid data structure without
storage space increased. Hybrid data structure is shown
in Figure 3. Table 4 is a kind of data organization of
hybrid data structure.
Within hybrid data structure, Octree used as whole
description and TEN as part description. A special
attribute of Octree is used to integrate Octree and TEN
together, which is "SX" in Table 4, where "S" is an
identification and "X" is a pointer. If attribute of an Octree
code is "SX" such as "73" in Table 4, it implies that a part
TEN is connected with this Octree code and pointer can
be used to find TEN data in TEN structure. On the other
hand, eight vertices of the cube which is represented by
the Octree code can be got easily such as (3,3,2) and
(3,4,2) in Figure 4, then TEN structure in this cube is
established by these vertices and feature points such as
201 and 202 in Figure 4. The realization of hybrid data
structure increases the adaptability of 3-D data structure.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996
