Graphics Reference
In-Depth Information
(a)
(b)
Figure 14.19.
Closing and splitting trapezoids.
T
able 14.4.1
Stages of the AddNewBoundPairs procedure.
AEL
Trapezoid values
At beginning
{
e1
,
e6
}
tz4 (x1b,dx1,x6b,dx6,yb,yb,{},{xp4,xp5,xp6})
tz5, tz6, and tz7 not yet defined
topKnots of tz1: {}
After (
e7
,
e8
) pair
{
e1
,
e7
,
e8
,
e6
}
tz4 (x1b,dx1,xp1,dx7,yb,yb,{},{})
tz5 (xp1,dx8,x6b,dx6,yb,yb,{},{xp4,xp5,xp6})
tz6 and tz7 not yet defined
topKnots of tz1: {xp1}
After (
e9
,
e10
) pair
{
e1
,
e7
,
e8
,
e9
,
e10
,
e6
}
tz4 (x1b,dx1,xp1,dx7,yb,yb,{},{})
tz5 (xp1,dx8,xp2,dx9,yb,yb,{},{})
tz6 (xp3,dx10,x6b,dx6,yb,yb,{},{xp4,xp5,xp6})
tz7 not yet defined
topKnots of tz1: {xp1,xp2,xp3}
By the way, keeping track of the trapezoid below the current position in the scan
line is not hard, because trapezoids are added to TRAPS in a bottom-up, left-to-right
manner, so that we merely need to keep moving a pointer to the right appropriately.
One determines whether an edge is a left or right edge at the time that it is put
on the AEL. This is done by a parity-type argument. If there are an even number of
edges on the AEL to the left of the new edge, then this edge is a left edge, otherwise,
it is a right edge.
Figure 14.19(b) and Table 14.4.1 should clarify how the AddNewBoundPairs
procedure works. We use the notation shown in Figure 14.19(b) and the following
abbreviations:
xpi is the x-coordinate of point
pi
.
dxi is the value of the dx field in edge
ei
.
xib is the x-coordinate of the point where edge
ei
meets scan line at yb.
xit is the x-coordinate of the point where edge
ei
meets scan line at yt.
