d on
lysis
E
yvide
nt of
for a
ween
erent
on of
jyers,
10del
pling
ional
and
lized
lgary
alize
ures.
w 3D
stem
last
phics
and
tions,
night
gical
odels
f 3D
f GIS
ented
ones,
Depending on geometric characteristics, 3D objects can be
described by two groups of geometric representations, namely,
surface-based and volume-based representations (Li, 1994).
The surface-based 3D representations describe geometric
characteristics of objects by surface entities. There are four
types of them, namely, grids, shape models, facet models, and
boundary representations. Grids and shape models are in raster
format and the facet models and boundary representations are
in vector format. In general, the grids, shape models and facet
models are suited for describing object surfaces with irregular
shapes; while boundary representations give the exact surface
geometry of objects with regular shapes.
Volume-based representations describe the interior of objects
by using the solid information instead of surface information.
With these representations, the solid information of objects can
be presented, analyzed and visualized. 3D binary arrays, needle
models, octrees and CSG (Constructive Solid Geometry)
belong to this group. CSG is in vector format. Generally
speaking, 3D binary arrays, needle models and octrees are
capable of modeling objects with irregularly shaped objects;
while CSG is well suited for modeling regularly-shaped
objects.
Most of the data structures mentioned above, to some extent,
are characterized by a restricted domain of representable
objects, due to the fact that the objects are constructed from a
limited number of mathematically well-defined surfaces or
solid primitives (Meagher, 1982). For example, surface-based
representations may suffer from inefficiency when geometric
and Boolean operations are of high priority.
Being an extension of a 2D quadtree, an octree models 3D
volumetric objects by recursively subdividing the object space.
An object is represented by the root node in the form of a cube,
which is then subdivided into eight octants to form the first
level of the tree. Octants that are not entirely occupied by the
object are called partial octants and are further subdivided to
smaller octants until each suboctant is either empty, fully
occupied by the object, or until the desired resolution is
reached. Extended octrees can model objects of any shapes
(Laurini and Thompson, 1992). The storage requirement of
octrees is much low in comparison to traditional raster
methods. Octree remains also advantageous because of its
raster structure and efficient geometric and Boolean operations
based on spatial indexing and relational operations.
Furthermore, multi-resolution modeling is another important
characteristic of octrees.
Kavouras and Masry (1987) applied the octree method in a
geological environment. They demonstrated the use of linear
octrees for storing a model of a gold ore deposit, using a
System called Daedalus. Algorithms for octree-based geometric
Operations, such as translation, scaling, rotation, and
perspective transformation, have been investigated by Jackins
and Tanimoto (1980), Meagher (1982), and Laurini and
Thompson (1992).
In the presented research, octrees are adopted for geological
Subsurface modeling because of its aboved mentioned
advantages.
509
3. SPATIAL OPERATIONS BASED ON
PEANO KEYS
Indexing methods have a great impact on the efficiency of
octree based spatial operations. The relative merits of five
methods, including row, row prime, Hilbert, Morton (or Peano)
and Gray code, were assessed by Abel and Mark (1990). It was
concluded that the Morton ordering provides a great efficiency
in window searching and has been used in most linear quadtree
systems.
It is noted that a linear octree, a pointerless structure first
proposed by Gargantini (1982), locates any node in a tree bya
unique key which is obtained by interleaving binary
coordinates of X, Y and Z. This can be implemented by using
Peano coding. It reduces the amount of storage of octree
representations and provides an efficient spatial indexing
method. Spatial geological operations can be developed based
on Peano keys for geometric operations, Boolean operations
and visualization.
The Peano keys can be generated by interleaving binary
coordinates of (X, Y, Z). For example, an octant with P(O)-14
has decimal coordinates (1, 1, 2). The corresponding binary
coordinates are (01, 01, 10) Interleaving the binary
coordinates in the order of Z, Y, and X for every bit starting
from lower bits results in the binary Peano key 001110 which
is 14 in decimal. This nature of the Peano keys makes the
Storage of Peano keys compact and the conversions between
Peano keys and coordinates very efficient. In addition,
neighbourhood searching in a Peano encoded octree is efficient
because of the characteristics of the N curve (Laurini and
Thompson 1992). An octant with a Peano key of P and a size of
S is expressed as O(P, S).
Peano coding has been chosen for implementing octrees in this
project due to its efficiency in storage and spatial indexing,
inheritance of relationships with spatial geometry and its
capability of preserving spatial contiguity. Out of a number of
subsurface oriented algorithms, two particular ones based
directly on the Peano keys are presented in this paper. The first
algorithm is used for cutting an octree representation by a
plane with any orientation. The second one performs a
geological datum adjustment.
3.1 Plane cutting algorithm based on Peano codes
One of the important operations in the geological subsurface
modeling is to build a fence diagram along a defined path on
the subsurface model. The geologists are then able to visualize
the profiles along the fence diagram and analysis the
subsurface structures.
The basic component and a simplified case of the above-
mentioned operation is to define a cutting plane on the
subsurface model and to remove the front part of the model so
that the user is able to visualize the profile along the cutting
plane. An algorithm is developed to perform this function on
the octree representation of the subsurface model based
directly on the Peano codes. To explain the algorithm, the two
dimensional case (quadtree representation) is used. The plane
cutting algorithm is simplified to the line cutting.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996
