Graphics Reference
In-Depth Information
T
able 3.3.5.1
Rules that Classify the Intersection Point Between Edges
Unlike edges:
Like edges:
(1) (LC
«
LS)
or
(LS
«
LC)
Æ
LI
(5) (LC
«
RC)
or
(RC
«
LC)
Æ
LI
and
RI
(2) (RC
«
RS)
or
(RS
«
RC)
Æ
RI
(6) (LS
«
RS)
or
(RS
«
LS)
Æ
LI
and
RI
(3) (LS
«
RC)
or
(LC
«
RS)
Æ
MX
(4) (RS
«
LC)
or
(RC
«
LS)
Æ
MN
Figure 3.20.
Intersection rules.
a left intermediate vertex. Rules 1-4 are shown graphically in Figure 3.20(a). Figure
3.20(b) shows an example of how the rules apply to some real polygon intersections.
As one moves from scan beam to scan beam, one updates the x-values of all the
edges (unless they end at the top of the scan beam). Although the AEL is sorted as
one enters a new scan beam, if any intersections are found in a scan beam, the AEL
will no longer be sorted after the x-values are updated. The list must therefore be
resorted, but this can be done in the process of dealing with the intersections. Vatti
used a temporary
sorted edge list
(SEL) and an
intersection list
(IL) to identify and
store all the intersections in the current scan beam. The SEL is ordered by the x-coor-
dinate of the intersection of the edge with the
top
of the scan beam similarly to the
way that the AEL is ordered by the intersection values with the bottom of the scan
beams. The IL is a list of nodes specifying the two intersecting edges and also the
intersection itself. It is sorted in an increasing order by the y-coordinate of the inter-
section. The SEL is initialized to empty. One then makes a pass over the AEL com-
paring the top x-value of the current edge with the top x-values of the edges in the
SEL starting at the
right
of the SEL. There will be an intersection each time the AEL
edge has a smaller top x-value than the SEL edge. Note that the number of intersec-
tions that are found is the same as the number of edge exchanges in the AEL it takes
to bring the edge into its correct place at the
top
of the scan beam.
Intersection points of edges are basically treated as vertices. Such “vertices” will
be classified in a similar way as the regular vertices. If we get a local maximum, then
there are two cases. If two unlike edges intersect, then a contributing edge becomes
