locally by low order, typically cubic polynomial functions.
Recently, a kind of B-Spline function, Non-Uniform
Rational B-Spline (NURBS), cause more attention in
CAD/CAM field. Beside the advantages of B-Spline, it has
no deformation after perspective and more shape control
ability, which is suitable for the representation of complex
surfaces in geoscience. An application has been
introduced by Fisher and Wales [1992]. However, if
some breaks exist in surface, NURBS is difficult to
represent.
The latter focus on the volume representations of 3-D
objects such as water body and geological construction.
Representations of 3-D objects are erected by their
volume descriptions. These data structures are suitable
for spatial manipulation and analysis. But more storage
space is needed. Within these data structures, 3-D array
is a Voxel model which is arranged closely over 3-D
space. Because of no data condensation in 3-D array,
huge storage space is needed and the speed of
computation is slow. Generally, 3-D array is used as a
mid-representation. Octree is a data structure that has
been studied and applied extensively. Octree is a
compact and efficient representation, which is a
hierarchical 3-D space subdivision instead of equal size
and regular arranged 3-D array . CSG represents an
object by a combination of predefined primitives which
are regular shape volumetric instances such as cube,
cylinder, etc. Relationships among these primitives
include geometric transformations and Boolean
operations. ‘Because model can be established
interactively by simple modeling words. CSG is one of the
most used modeling technique in CAD/CAM field and
often combined with BR in practice. TEN is a 3-D
extension of 2-D TIN and tetrahedron is a basic primitive.
Object is described by connected but not overlapped
tetrahedral network. Similar to 2-D TIN, TEN has many
advantages in manipulation, display and analysis. In next
Section, Octree and TEN will be discussed in detail and a
hybrid data structure will be introduced.
3. HYBRID DATA STRUCTURE
3.1 Octree
In tree structure of Octree, root represents a cube which
includes whole object. An Octree recursively subdivides
this cube into octants. Every cube would be subdivided if
they were found to be non-uniform or the size of cube
was larger than requirement. There have three kinds of
node in Octree : black, white and grey. If n represents the
depth of an Octree, it corresponds with a 2” x 2” x 2” 3-D
array. Figure 1 is a 2 simple object and its Octree
representation.
0
"
88 [D] 1 633 C3 O3] D3
(b)
Figure 1. Octree
Morton ATT Morton ATT
0 1 0 1
1 1 31 0
2 1 40 1
30 1 41 0
40 1
Table 1. LQ Table 2. 3DRE
Linear Octree (LQ) encoding is a generally used encoding
method, in which only addressing code and attribute of
black leaf node are stored. Morton code, which is a n
digits encoding, is used as addressing code in which the
location and size of leaf node are contained. Table 1 is
linear Octree encoding of Figure 1.
Another efficient Octree encoding method is Three-
Dimensional Run Encoding (3DRE), which can be
extended from 2DRE [Jean Paul Lauzon, etal. 1985]
easily. Similar to linear Octree encoding, Morton code is
used as addressing code in 3DRE. According to the size,
Morton codes are ordered in a set, which can be thought
as a group of subsets. Every subset corresponds with a
group of leaf nodes which have same attribute. In every
subset, only first element is remained and others are
deleted, then 3DRE of Octree is formed. Table 2 is 3DRE
of Octree in Figure 1. Within 3DRE the deleted elements
can be resumed by neighbor addressing codes.
Compared with linear Octree encoding, 3DRE saves
more storage space. It is convenient for some spatial
operations such as insert and delete. However, Octree
structure is not exist in 3DRE so that it only be used to
describe solid object.
Because Octree is a kind of middle data structure, it
cannot be generated from original observations directly.
The generation of Octree is transformed from other
structures such as 3-D array, BR, CSG.
504
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996
Com
adve
cons
trans
trans
as
