Graphics Reference
In-Depth Information
Figure 3.19.
Merging polygons.
ning of the vertex list of
P
. If
e
1
is a right edge of
P
(Figures 3.19(c) and (d)), then we
append the vertices of
P
to the end of the vertex list of
Q
. Note that each of the poly-
gons has two top contributing edges. In either case, after combining the vertices of
P
and
Q
, the two edges
e
1
and
f
1
become noncontributing. If
e
1
was a left edge, then
f
2
will
be contributing to
P
and the adjacent polygon of
f
2
will become
P
. If
e
1
was a right edge,
then
e
2
will be contributing to
Q
. Therefore, the adjacent polygon of
e
2
will become
Q
.
When we find a local maximum we know two top edges right away, but if these
have different adjacent polygons, then we need to find the other two top edges for
these polygons. There are two ways to handle this. One could maintain pointers in
the polygons to their current top edges, or one could do a search of the AEL. The first
method gives us our edges without a search, but one will have to maintain the point-
ers as we move from one edge to the next. Which method is better depends on the
number of edges versus the number of local maxima. Since there probably are rela-
tively few local maxima, the second method is the recommended one.
Finally, we look at how one deals with intersections of edges within a scan beam.
The way that these intersections are handled depends on whether we have like or
unlike edges. Like intersections need only be considered if both edges are contribut-
ing and in that case the intersection point should be treated as both a left and right
intermediate vertex. (Note that in the case of like intersections, if one edge is con-
tributing, then the other one will be also.) Unlike intersections must always be
handled. How their intersection point is handled depends on their type, side, and rel-
ative position in the AEL.
It is possible to give some precise rules on how to classify intersection points. The
classification rules
are shown in Table 3.3.5.1 in an encoded form. Edges have been
specified using the following two-letter code: The first letter indicates whether the edge
is a left (L) or right (R) edge, and the second letter specifies whether it belongs to the
subject (S) or clip (C) polygon. The resulting vertex type is also specified by a two-letter
code: local minimum (MN), local maximum (MX), left intermediate (LI), and right inter-
mediate (RI). Edge codes are listed in the order in which their edges appear in the AEL.
For example, Rule 1 translates into the following: The intersection of a left clip edge and
a left subject edge, or the intersection of a left subject edge and a left clip edge, produces
