International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
may be difficult or impossible to model bridges and tunnels on 
the terrain surface. 
  
Figure 1 A DTM from ArcView 
  
3. DIFFERENT LEVELS OF OPERATORS 
3.1. Why these operators? 
CAD modelling techniques do not seem attraction at first. The 
Boolean operators, the union, intersection, and difference of 
cubes and tubes in Constructive Solid Geometry structure (CSG) 
are hard to apply to terrain models. The data structure for 
modelling a non-manifold solid is too complex (Lee, 1999), 
therefore only manifold-based b-rep CAD models will be 
considered in enhancing the TIN model. Euler Operators, with 
the help of the Euler Poincaré formula is a good indicator of the 
topological validity of the boundary surface (Mantyla, 1981). 
Euler Operators are used to ensure the integrity of the extended 
TIN models, since the TIN is a set of triangles represented by a 
group of boundary edges and vertices. 
Implementations of Euler Operators used various kinds of edge- 
type data structures, for example, half-edge (Weiler, 1985) and 
winged-edge (Baumgart, 1972) data structures. They seem too 
complicated for modelling triangulations, and the TIN does not 
need to represent holes in an individual triangle. The simplicity 
of the Quad-Edge structure (Guibas & Stolfi, 1985) is used to 
implement the Euler Operators. Therefore we use the Quad- 
Edge as the basic structure used to implement a set of Euler 
Operators in the TIN model. The implementation of 
triangulation operators using the Euler Operators will be the 
highest level. 
3.2. The Quad-Edge Data Structure 
Weiler (Weiler, 1985) gave a topology representation with 
enough information to recreate nine adjacency relationships 
without error or ambiguity. Figs 3 and 4 show the only two 
operators, “Make-Edge” and “Splice”, used on the Quad-Edge 
structure. Make-Edge creates an individual edge with four 
connected “Quad” objects and every Quad has three pointers. 
Splice splits a face into two pieces or merges two faces into one. 
e ptl 
  
x Rot Quad 
‘ — 
I 
! Next Quad 
cux o 
1 
{ Vertex or Face 
, I. 
i— — 
\ 
  
  
  
€ pt2 
Figure 3 Make-Edge 
  
Vertex or Face 
  
-— 
Figure 4 Splice 
3.3. The Implementation of Euler Operators Using 
Quad-Edge Structure 
According to Braid (Braid et al., 1978) five spanning Euler 
Operators suffice to create a valid b-rep model. The six 
elements of every b-rep solid model are: vertices, edges, faces, 
loops (or rings), holes and bodies (or shells), however loops (a 
hole in an individual face) will not be considered in the TIN 
model. Therefore only five elements will be used in the 
extended TIN model. Thus four spanning Euler Operators 
suffice for modelling the extended triangulation. 
Similarly three Euler Operators are needed to create a simple 
TIN model without any holes or bridges because only four 
elements are including in the model. They are: vertices, edges, 
faces and bodies. Figs 5 to 7 show the three operators for 
creating the TIN model. In the figures below, the dash lines 
represent the connectivity bétween edges in a face or a vertex. 
Every edge is represented by one of the four Quads which 1s 
  
    
   
    
   
  
  
  
   
    
  
  
  
  
  
  
  
  
  
   
    
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   
  
   
  
  
   
  
  
  
   
  
  
  
   
     
Inte 
nam 
“NI 
obje 
3. 
Fact 
obje 
“pti 
Verl 
«En 
3.3 
by c 
(KE 
crea 
kill 
3.3.3 
in fig 
and 
by ki 
to re 
are a 
reshe