ul 2004 
  
th four 
ointers. 
1to one. 
; Using 
g Euler 
[he six 
s, faces, 
loops (a 
he TIN 
in the 
perators 
| simple 
ly four 
, edges, 
tors for 
sh lines 
vertex. 
vhich is 
   
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
named in the following figures. For example, in fig 9 the name 
^NI" represents the whole edge with four invisible “Quad” 
objects. 
3.3.1 MEVVFS «&» KEVVFS: Make Edge Vertex Vertex 
Face Shell (MEV VFS) in fig 5 is an initial operator to create an 
object (body or shell) with an edge and two vertices (points 
“pt1” and “pt2”), and its inverse operator Kill Edge Vertex 
Vertex Face Shell (KEV VFS) kills the only edge on an object. 
    
   
   
. \ Rot Quad 
Next ond 
MEVVFS 
«Empty Model» , KEVVFS 
* pt2 
Figure 5 MEVVFS  KEVVFS 
332 MEF «€» KEF: Make Edge Face (MEF) splits a face 
by creating an edge and a face, and its inverse Kill Edge Face 
(KEF) merges faces by killing a face and an edge. Edge “e” is 
created to split the face into two pieces and two faces merge by 
killing this edge. 
[e 
Als 
  
    
   
I 
Se ex (^ 
SS UJ 
Figure 6 MEF © KEF 
3.3.3 SEMV €» JEKV: Split Edge Make Vertex (SEMV) 
in fig 7 splits an edge by adding a vertex and an edge (edge “a”), 
and its inverse Join Edge Kill Vertex (JEKV) joins two edges 
by killing a vertex and an edge. SEMV is acting as an operator 
to reshape the polygon into a triangle. Edge “a” and point “pt” 
are added to split edge “e” into two pieces, and the polygon is 
reshaped into triangle. 
+ =e 
SEMV 
  
e 0 
s mkv AO 
  
pt 
Figure 7 Split Edge Make Vertex 
    
3.4. The Implementation of Triangulation Operators 
Using The Euler Operators 
Big Triangle, Insert Point and Swap are the three operators used 
to create a triangulation, as show in figs 8 to 10. All of the 
triangulation operators have their inverses. 
3.4.1 Big Triangle: Big Triangle is an initial operator for 
creating the first triangle and it should be big enough to contain 
all the data points. To create the first triangle in the triangulation, 
three Euler Operators are needed: “MEVVFS”, “MEF” and 
“SEMV”. “MEVVFS” creates the first edge “el” with two 
points “pt1” and “pt2”. “MEF” creates a face by adding edge 
“e3”. “SEMV” splits edge “e3” into two pieces and reshapes the 
polygon into a triangle. To kill the big triangle, “JEKV” joins 
edge “e2” and “e3”. “KEF” kills edge “e2” and a face. 
“KEVVFS” kills the last edge “el”, returning to an empty space. 
3.4.2 Insert Point: Suppose the triangle which contains 
the new inserted point is located in fig 9. A new edge “N4” is 
created by using "MEF" and reshaped to point "pt" by using 
"SEMV". "MEF" is used again to split the face with an edge 
"N6". Three new edges and a point are created inside the 
triangle. Delete Point is the inverse operator. “KEF” and 
"JEKV" are used to kill the point inside the triangle. 
3.4.3 Swap: Swap is used to swap a common edge 
between two triangles. The “In-circle” test is used to test the 
triangle in a Delaunay Triangulation and the swap operator is 
used to change the failed edges. The empty circumcircle 
criterion is described in (Guibas & Stolfi, 1985). Input edge "e", 
the common edge between two triangles, is swapped in fig 10. 
"KEF" kills edge "e" and “MEF” creates edge “e” again. 
<empty model> 
MEVVFS | | KEVVFS 
. 
Nee. 
0 
  
  
  
  
  
Figure 8 Big Triangle Operator