aps of
Memo-
n 3.0,
ology,
s and
Manu-
United
, USA.
HYBRID DATA STRUCTURE BASED ON OCTREE AND TETRAHEDRON IN 3-D GIS
Li Qingquan
Li Deren
Wuhan Technical University of Surveying and Mapping
39 Luoyu Road, Wuhan 430070
P.R.CHINA
Commission Ill, Working Group III/IV
KEY WORDS: Three-dimensional, GIS, Data structure, Octree, Tetrahedron
ABSTRACT
After a review of data structures in 3-D GIS, a hybrid data structure based on Octree and Tetrahedral Network (TEN) is
presented and a concept of 3-D GIS based on hybrid data structure is introduced in this paper. The problems about
generation of data structure, data organization, data conversion and application are discussed.
1. INTRODUCTION
In most geoscience applications, geometric information in
vertical direction is needed. It has the same significance
with horizontal extent such as in air pollutión monitoring.
However, in conventional 2-D GIS, it is usually
abstracting vertical information as an attribute such as
elevation data in DTM, then spatial manipulation and
analysis are carried out. If more than one observation are
taken in a vertical direction such as sampling data in
natural resource exploration along a vertical drilling, 2-D
GIS is difficult to process. A system that has ability of full
three-dimensional (3-D) manipulation and analysis is
required. Also, there has requirement of 3-D GIS in oil
exploration, mining, meteorology, hydrogeology,
geological modeling, environmental monitoring, civil
engineering, etc. Now, attention is focusing on the design
and implementation of 3-D GIS, in a range of
geoscientific application areas[ Raper and Kelk, 1991].
Within research works of 3-D GIS, data model and data
structure is one of the key problems. Before recent
years, most results based on CAD models, such as
Constructive Solid Geometry (CSG), Boundary
Representation (BR), and made some modifications and
extentions. It is obviously that CAD system cannot readily
be applied to geoscience modeling. It is different from
GIS in many aspects.
Despite lots of new results have been made by
researchers over the world [Molenaar, 1992; Rongxing Li,
1994; Xiaoyong C.,1994a]. Due to the complexity of 3-D
objects and applications, one data structure is difficult to
satisfy different requirements. There have two methods
for this problem. One is to develop hybrid data structure.
The other is to integrate different data structures in one
System. In this paper, authors present a hybrid data
structure and a concept of 3-D GIS based on it.
This paper is organized as follows: 3-D data structures
are reviewed in Section 2. In Section 3 after a discussion
of Octree and Tetrahedral Network (TEN), a hybrid data
structure based on Octree and TEN is presented. A
503
concept of 3-D GIS based on hybrid data structure is
introduced In Section 4. In Section 5 a conclusion of this
paper and an application experiment are introduced.
2. 3-D DATA STRUCTURE
Data structures that can be applied in 3-D GIS are
divided into two types [Rongxing Li, 1994]. One is based
on surface representations, include: rectangular grids,
triangulated irregular network (TIN), BR and parametric
functions. The other is based on volume
representations, include: 3-D array, Octree, CSG and
TEN.
The former focus on the surface representations of 3-D
objects such as surface of building and subsurface of
geology. Representations of 3-D Objects are formed by
their surface descriptions. These data structures are
convenient for visualization and updating, but is difficult
for many spatial analysises such as integral property
calculation. Within these data structures, rectangular
grids and TIN are in common used in DTM, which are
familiar with us. While BR is used, a solid is defined in
terms of the geometry of its bounding surfaces. Typically
this is described by polygonal facets, each of which is
defined by its edges, which are in turn defined by the
vertices. In geoscience applications, in order to convert
the observations into BR, the relationships among
elements must be identified. However, objects in
geoscience are usually unknown. These relationships are
difficult to be determined. According to the characteristics
of BR, therefore, CAD/CAM and engineering are the main
application fields. Parametric polynomial functions is one
of the useful method to represent free-form surface. The
x,y and z Cartesian coordinates become a function of two
parametries (u,v). An individual surface is described by a
function P(u,v), where
P(u,v)=[x(u,v),y(u,v),z(u,v)] (O<u<1,0<v<1)
Complex surface in geoscience can be subdivided to form
a contiguous set of patches, each of which is defined
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996
