Graphics Reference
In-Depth Information
Figure 14.18.
Complications for the AddNewBoundPairs procedure.
Like in Section 3.3.5, the UpdateLMLandSBL procedure finds the bounds of
a polygon, adds them to LML, and also updates SBL. This time we will have an
adjacent trapezoid
associated to edges rather than an adjacent polygon. It may change
as we move from one scan beam to the next. Because horizontal edges complicate
matters, in order to make dealing with horizontal edges easier, we again assume that
the matching left and right bound pairs in the LML list are normalized (see Section
3.3.5 for a definition).
Next, consider the AddNewBoundPairs procedure. The task of this procedure is
to add those bounds that start at the current scan line into the AEL list. This is not
as straightforward as it may seem. Some of the complicating possibilities are shown
in Figure 14.18, which shows some of the events that can occur in the processing of
the scan beam between the two scan lines at yb and yt. As we deal with local minima
at the points
p1
and
p2
, we have to worry about potential “knots” for either new or
old trapezoids. By a
knot
for the top or bottom edge of a trapezoid we mean the x-
coordinate of a vertex of a polygon that must be included in any subdivision of the
trapezoid. Knots are needed because adjacent trapezoids might have only part of an
edge in common. Without keeping track of the knots, subdivisions of these adjacent
trapezoids might subdivide the part of the edge that they have in common in differ-
ent ways that would lead to gaps in the surface defined over these trapezoids. In Figure
14.18, when we process the local minimum at
p1
we have to add a top knot to trape-
zoid tz1. When we process
p2
, we must add two top knots corresponding to
p2
and
p3
to tz1. The knots corresponding to points
p4
,
p5
, and
p6
in the bottom edge of
trapezoid tz6 would have been specified when the scan beam below the current one
was processed and the local maxima were encountered. Only knots
interior
to an edge
are kept track of in the trapezoid data structure. Although the endpoints of the top
and bottom edges of a trapezoid clearly fall under the label of knots, we do
not
include
them in the knot arrays, because that would be redundant data.
After these comments, assume that the trapezoids use the data structure shown
in Data 14.4.1. The leftDx and rightDx fields are simply the increments by which leftX
and rightX changes as we move from one scan line to the next. Here is what we have
to do when we add the edges of a bound pair to the AEL list. In general, at a
left-
right
edge pair minimum, we
