Graphics Reference
In-Depth Information
When we begin processing a scan beam, before we look at any of the edges of the
AEL, we check the LML to see if any of its bound pairs start at this level. These bounds
correspond to local minima. Each of these will start a trapezoid or break an existing
one into two depending on whether the local minimum starts with a left-right or right-
left edge pair. The first nonhorizontal edge from each bound of a local minimum is
added to the AEL. Note that horizontal edges are never put on the AEL. Intermedi-
ate horizontal edges basically are skipped but they do create “knots” as will be
described later. After any new edges from the LML are added to the AEL, we process
the edges of the AEL one at a time starting from the left. See Algorithm 14.4.1 for a
more precise description of the top-level algorithm described so far. Compare this
algorithm with Algorithm 3.3.5.1.
{Global variables}
real list
SBL;
{an
ordered
list of
distinct
reals thought of as a stack}
bound pair list
LML;
{a list of pairs of matching polygon bounds}
edge list
AEL;
{a list of
nonhorizontal
edges ordered by x-intercept
with the current scan line}
trapezoid list
TRAPS;
{the trapezoids are stored here as algorithm progresses}
trapezoid list function
ConvertToTrapezoids (
curve list
PL)
{The list PL represents a polygon with holes. The first curve in the list is the outer boundary
of the polygon and the others, if any, are the holes. The procedure partitions the polygon
into trapezoids. The list of these trapezoids is returned to the calling procedure.}
begin
real
yb, yt;
Initialize LML, SBL to empty;
{Define LML and the initial SBL}
for each curve
P
in
PL
do
UpdateLMLandSBL (P);
Initialize TRAPS, AEL to empty;
yb := PopSBL ();
{ bottom of current scan beam }
repeat
AddNewBoundPairs (yb);
yt := PopSBL ();
{ top of current scan beam }
ProcessEdgesInAEL (yb,yt);
yb := yt;
until
Empty (SBL);
return
(TRAPS);
end
;
Algorithm 14.4.1.
The trapezoid creation algorithm.
