Graphics Reference
In-Depth Information
Figure 5.37.
Winged edge representation.
boundary, and the others are holes in the face. In terms of implementing this, one
uses a face table that consists of a list of edges where one has taken one edge from
each edge cycle. Each vertex belongs to a circularly ordered set of edges. These sets
are represented by one edge that is chosen from each. For each edge one lists
(1) the incident vertices,
(2) the left and right face,
(3) the preceding and succeeding edge in clockwise (cw) order with respect to the
exterior of the solid, and
(4) the preceding and succeeding edge in counter-clockwise (ccw) order with
respect to the exterior of the solid
See Figure 5.37(a). Figure 5.37(b) shows the relations which are involved, although
V Æ E and F Æ E are only partial relations in this case.
Weiler ([Weil85]) showed that although the Baumgart structure represents the
topology completely, certain algorithms for querying the data structure became com-
plicated if self-looping edges were allowed (the two endpoints are the same point). He
defined three improvements. One added a little to the structure and the other two split
the edge structure into two.
Returning to [NiBl94], one finds the following conclusions:
(1) The best single relations are V Æ E and F Æ E. These relations are also ade-
quate to describe the topology completely provided that the sets {E
j
} are
ordered in a circularly coherent manner.
(2) When one is given a pair of adjacency relations, this is the first time that one
can, with an appropriate choice, answer all possible adjacency queries. The
best pair of relations is V Æ E and F Æ E.
(3) The two adjacency relation combinations shown in Figure 5.38(a) are the best
combinations when one uses three adjacency relations.
(4) Figure 5.38(b) shows the best combination of four adjacency relations. This
relation was discovered by [WooT85].
(5) The winged data structure shown in Figure 5.37(b) and some of its variants
are worse than the combination in Figure 5.38(b).
