Graphics Reference
In-Depth Information
trapezoid
=
record
real
leftX,
{ the x-coordinate of the bottom left vertex }
leftDx,
{ the reciprocal of the slope of the left edge }
rightX,
{ the x-coordinate of the bottom right vertex }
rightDx,
{ the reciprocal of the slope of the right edge }
bottomY,
{ the y-coordinate of the bottom edge }
topY;
{ the y-coordinate of the top edge }
real array
topKnots,
{ the
interior
knots for the top edge }
botKnots;
{ the
interior
knots for the bottom edge }
end
;
Data 14.4.1.
The trapezoid data structure.
(1) create a new trapezoid T with all fields defined, except that at this point it is
degenerate because the
topY
and
bottomY
fields are temporarily set to the
same value, and
(2) make T be the adjacent trapezoid of the two edges.
A local minimum at a
right-left
edge pair is more complicated. Basically, the
trapezoid below us is about to split. First of all, let us introduce some notation. Call
a trapezoid T
closable
if
(1) its
topY
and
bottomY
fields have the same value, and
(2) the common value of these two fields is less than the y-coordinate of the
bottom of the current scan beam.
The process of setting the
topY
field to a value larger than the value of the
bottomY
field (thereby making the trapezoid “nondegenerate”) will be referred to as
closing the
trapezoid
. Sometimes when a trapezoid is closed, we need to update its
rightX
and
rightDx
fields. A trapezoid whose
topY
and
bottomY
fields have distinct values is
said to be
closed
. Closed trapezoids may still have incomplete knot arrays however.
Dealing with a
right-left
edge pair (
e1
,
e2
) therefore involves three steps. Let
prevE
be the edge to the left of
e1
and let
belowTrap
be the trapezoid below this
one which is splitting. Let BottomX(
e
) of an edge
e
denote the x-coordinate of the
intersection of
e
with the horizontal line at the bottom of the current scan beam.
Step 1:
If the trapezoid adjacent to
prevE
is still open, then close it and create a
new trapezoid T1 for
e1
and
prevE
. For example, in Figure 14.19(a), when we get to
p1
, tz1 would be adjacent to
e1
. We would close it and create tz2 for
e1
and
e3
. On
the other hand, when we get to
p2
, we do
not
need to close tz3.
Step 2:
Create a new open trapezoid T2 and make it the adjacent trapezoid for
e2
and the edge that follows
e2
. Move any knots from the bottom of
prevE
's trape-
zoid that are bigger than BottomX(
e2
) to T2. For example, in Figure 14.19(b), tz4
would already have bottom knots corresponding to
p4
,
p5
, and
p6
as we start pro-
cessing the scan beam. At
p1
(and
p2
) the knots
p4
,
p5
, and
p6
would be shifted.
Step 3:
The new local minimum at BottomX(
e1
) creates a knot in the top of
belowTrap
. See point
p1
in Figure 14.19. If BottomX(
e2
) is larger than BottomX(
e1
),
then we get a second knot. See edge
p2p3
in Figure 14.19(b). These knots must be
added to the top knots of
belowTrap
.
