1 2004
ta-
ma
K)
K)
ind
ind
ing
ra,
un
ing
of
ul,
rin
ita
ks,
OB
ers
jan
ri),
kin
An Original Way of Building a TIN with Complex Urban Structures
Rebecca, O.C., Tse^*, Christopher Gold? and Dave Kidner ?
“ School of Computing, University of Glamorgan, Mid Glamorgan, Wales, CF37 IDL, UK —
rtse(èglam.ac.uk*, dbkidner@àglam.ac.uk
° Department of Surveying and Geo-Informatics, The Hong Kong Polytechnic University, Hung Hom, Hong Kong SAR, China -
Iscgold(@pol
/u.edu.hk
Commission VI, WG VI/4
KEY WORDS: TIN, CAD, Euler Operators, Quad-Edge data structure
Abstract:
Geographical Information System (GIS) software often models a Digital Terrain Model (DTM) by using triangulations (TINs).
Computer Aided Design (CAD) is then used to model complex city structures and superimpose them on the TINs. Since the terrain
surface is not connected to the built-up structures, no further spatial analysis (for example, neighbourhood analysis, flow modelling)
is possible. Bridges and tunnels are parts of complex urban structures which may be difficult or impossible to be modeled in those
TING.
An original way of building the TIN model may help to solve this problem. The use of the *boundary-representation" structure from
CAD systems, the triangulation structure of TINs and the Quad-Edge structure from Computational Geometry are combined to
alleviate the problem. The Quad-Edge structure forms the base of the model and CAD-type Euler Operators are the intermediate level
operators for building the TIN model. To extend the TIN model with bridges, holes and buildings, additional Euler Operators are
used. This original way of building the terrain model not only permits the extrusion of buildings and the formation of bridges and
tunnels, but also the development of topological queries and analysis, for example, runoff modelling. It is a simple and reliable
method and is illustrated with examples of interactive modelling of part of the Hong Kong city.
l. INTRODUCTION
The TIN has been a well-known model for more than 20 years
in the GIS world. Most of the current GIS software visualizes
and models the terrain surface by using TINs. However the
traditional TIN is a 2.5 dimension (2.5D) model which cannot
handle non-planar networks and complex structures, for
example bridges, tunnels and buildings, from the real world.
Existing GIS systems make use of advanced technology from
CAD, like 3D graphics and objects created by 3D Studio MAX
(CAD software). They model the terrain surface by using
triangulation, and then 3D objects from CAD systems are
created and superimposed on top. Database matching is used to
locate those 3D objects, but no spatial analysis can be
implemented. Will it be possible to make use of the advanced
technology from CAD to build a connected TIN model for
further spatial analysis?
This paper aims at alleviating this problem by extending the
traditional TIN model. First, a terrain surface model should be
recognised as a more than a two-dimensional entity — it is an air
(or water-) earth interface, the boundary between the
“Polyhedral Earth” and the exterior (Tse & Gold, 2002). An
underneath surface is put on every TIN to give a polyhedral
model. We are interested in the simplicity of the Quad-Edge
data structure (Gold, 1998, Guibas & Stolfi, 1985) and the well-
developed tools for solid model representation from CAD
Systems (Baumgart, 1975, Mantyla, 1981).
Since the properties of the triangulation look similar to the
boundary-representation (b-rep) structure from CAD, the CAD-
type b-rep structure Euler Operators are used to create and
extend the TIN model with holes. The Quad-Edge structure
forms the base operators of the model. Euler Operators acts as
middle level operators to implement the basic triangulation
functions. Finally the TIN model is extended by using
additional Euler Operators while the topological connectivity is
preserved.
The work has been carrying out with five different stages (Tse
& Gold, 2002):
1. Definitions of three levels of operators to achieve our
desired system;
2. The implementation of CAD-type Euler Operators using
the Quad-Edge data structure;
3. The implementation of basic TIN functions using the Euler
Operators
4. The extension of the TIN model with additional Euler
Operators |
5. The implementation of the extended TIN model with real
data (Hong Kong map data)
2. EXISTING GIS SOFTWARE
Most of the existing GIS software create and display the terrain
surface by using triangulation and the 3D objects are put on top
of the existing triangulation. Fig 1 shows an example from
ArcView ESRI® of creating and visualising the DTM and fig 2
shows some 3D objects (buildings) pasted on top of the DTM,
which looks like playing “LEGOTM”. Further spatial analysis
can be performed because of a lack of topological connectivity.
Since the DTM and the buildings are not in the same layer, it
