Graphics Reference
In-Depth Information
the appropriate action based on the vertices that are encountered, we shall see that
it therefore basically reduces to a careful analysis of the following three cases:
(1) The vertex is a local minimum.
(2) The vertex is a left or right intermediate vertex.
(3) The vertex is a local maximum.
Local minima are encountered when elements on the LML become active. Interme-
diate vertices and local maxima are encountered when scanning the AEL. Intersec-
tions of edges also give rise to these three cases.
Returning to Algorithm 3.3.5.1, the first thing that happens in the main loop is to
check for new bound pairs that start at the bottom of the current scan beams. If any
such pairs exist, then we have a case of two bounds starting at a vertex
p
that is a
local minimum. We add their first nonhorizontal edges to the AEL and the top y-values
of these to the SBL. The edges are flagged as being a
left
or
right
edge. We determine
if the edges are
contributing
by a parity test and flag them accordingly. An edge of
the subject polygon is contributing if there are an odd number of edges from the clip
polygon to its left in the AEL. Similarly, an edge of the clip polygon is contributing if
there are an odd number of edges from the subject polygon to its left in the AEL. If
the vertex is contributing, then we create a new partial polygon P[
p
] and associate
this polygon to both edges. Note that to determine whether or not an edge is con-
tributing or noncontributing we actually have to look at the geometry only for the first
nonhorizontal edge of each bound. The bound's other edges will be of the same type
as that one.
The central task of the main loop in the Vatti algorithm is to process the edges
on the AEL. If edges intersect, we shall have to do some preprocessing (procedure
ProcessIntersections), but right now let us skip that and describe the actual process-
ing, namely, procedure ProcessEdgesInAEL. Because horizontal edges cause sub-
stantial complications, we separate the discussion into two cases. We shall discuss the
case where there are no horizontal edges first.
If an edge does not end at the top of the current scan beam, then we simply update
its x-value to the x-coordinate of the intersection of the edge with the scan line at the
top of the scan beam. If an edge
does
end at the top of the scan beam, then the action
we take is determined by the type of the top end vertex
p
. The vertex can either be an
intermediate vertex or a local maximum.
If the vertex
p
is a left or right intermediate vertex, then the vertex is added at the
beginning or end of the vertex list of its adjacent polygon, depending on whether it is
a left or right edge, respectively. The edge is replaced on the AEL by its successor edge
which inherits the adjacent polygon and left/right flag of the old edge.
If the vertex
p
is a local maximum of the original clip or subject polygons, then a
pair of edges from two bounds meet in the point
p
. If
p
is a contributing vertex, then
the two edges may belong either to the same or different (partial) polygons. If they have
the same adjacent polygons, then this polygon will now be closed once the point
p
is
added. If they belong to different polygons, say
P
and
Q
, respectively, then we need to
merge these polygons. Let
e
1
and
e
2
be the top edges for
P
and
f
1
and
f
2
, the top edges
for
Q
, so that
e
1
and
f
1
meet in
p
with
f
1
the successor to
e
1
in the AEL. See Figure 3.19.
Figures 3.19(a) and (c) show specific examples and (b) and (d) generic cases. If
e
1
is a
left edge of
P
(Figures 3.19(a) and (b)), then we append the vertices of
Q
to the begin-
