Ce Order through the 
projection 
1 
Order over a 
surface 
Figure 10 An example of the agreement 
of the two kinds of edge orders 
IF 
ik 
Order through the projection; 1,2,3,4 
Order over a surface :1,34,2 
Figure 11 An example of the disagreement 
of the order through the projection with the 
order over a surface 
(2)A constraint condition on torsion angles of 
polygons 
À torsion angle of a polygon along a bounding 
edge is defined as an angle between two normal 
vectors neighboring along the bounding edge 
(figure 12). The torsion angle must be as small as 
possible. As shown in figure 13, the large torsion 
angle causes ambiguity in tracing edges to identify 
polygons. 
a torsion angle 
(0 - 90deg.) 
  
   
      
a,b,c ; edge vectors 
bounding a polygon 
m ; normal vector=axb 
n ;normal vector-bxc 
Figure 12 Definition of a torsion angle of a poygon 
B B 
n 
A—O0-—O0i1— B A-—O0—01—C 
Figure 13 An example of an ambiguity in identifying 
polygons by tracing an edge when a torsion angle is large 
(-90deg) 
2) A procedure to identify and interpolate 
polygons in 3D surfaces 
Under these constraint conditions, polygons 
whether planar or non-planar, can be identified in 
a 3D surface and their surfaces can be 
interpolated. The procedure is summarized as 
follows. 
(i)Preprocessing: 
Isolated points, and edges connected with 
less than two edge are all removed. Only points 
261 
where more than twó edges meet are recognized 
as points in the following process. 
(ii)Generation of the alternatives of the edge 
order at each point: 
Two alternatives of the edge order over a 
surface are generated at every point. In the case 
of three edges, there exist only two(=(3-1)!) 
alternatives of the edge order. In the case of 
more than three edges, two kinds of orders 
through projection, clockwise or 
counterclockwise, are generated as alternatives 
of the order over a surface. 
(iii)Determination of the edge order at each 
point: 
The order of edges at at least one point must 
be determined by a user as an initial condition. 
The order of edges at other points are 
determined by tracing edges from the points 
where the orders are already determined. 
Suppose the edges at the point O are already 
ordered in figure 14. The order of edges at O1 
must be determined. There are two alternatives 
of the edge order at O1. One is a clockwise 
order. With this order, a pair of edges, 
A,0,01,C and B,0,01,D will bound two 
polygons respectively. Another is a 
counterclockwise order. With this order, a pair 
of edges, A,0,01,D and B,0,01,C will bound 
two polygons respectively. 
   
  
a given mi 
order Ci A 4 Counterclockwise 
1 7 
' 
  
  
m 2 Clockwise order 
Figure 14 Determination of the order of edges at O: 
by tracing edge e 
Since the torsion angles( 0-90 deg.) of a 
pair of polygons bounded by A,0,01,C and 
B,0,01,D respectively is larger that those by 
A,0,01,D and B,0,01,C in this example, it 
can be concluded that the counterclockwise 
order is more likely. 
If the torsion angles are almost the same (it 
is very likely when the edges are contained in a 
single plane), normal vectors m1 and m2 at 
O1, which correspond with a counterclockwise 
order and a clockwise order respectively, are 
compared to normal vector n at O in terms of 
intersection angle (0-180 deg.). In this case, 
since the intersection angle of m1 and n is 
smaller, we can conclude that. the 
counterclockwise order is more likely. 
If the order do not coincide with the other 
determined from other neighboring points, a 
user is required to check the ordering result. 
(iv)Polygon identification in each 3D surface: 
By tracing edges according to the order of 
edges at each point, polygons can be identified 
in a 3D surface.