Graphics Reference
In-Depth Information
Because the trapezoids tz2 and tz3 are already defined and do not change, we do not
include them in the table.
Next, we describe the AEL processing procedure. After adding any bottom edges
from local minima to the AEL, we process the edges of the AEL one at a time start-
ing from the left. If an edge extends past the current scan beam, then we simply update
the x-intersection field of the edge. If the edge ends at the top of the current scan
beam, then one or two trapezoids are closed and the edge is processed in one of two
ways depending on whether the top vertex is an intermediate vertex or a local
maximum. If the vertex is an intermediate vertex, then the edge is replaced in the AEL
by its successor edge and the left/right flag is passed on to the new edge. In the case
of a left intermediate vertex, the adjacent trapezoid is closed. In the case of a right
intermediate vertex, we close the trapezoid to its left if it is still open. If the top vertex
is a local maximum, then two bounds meet that may belong either to the same or to
different trapezoids. If the bounds belong to the same trapezoid, that is, the edge e
was a left edge, then the trapezoid adjacent to e is closed. If the bounds belonged to
different trapezoids, then two trapezoids (one to the left of e and the other to the right
of the second bound) must be closed and a new merged trapezoid T started. Knots
are a complicating factor in this last case. The top endpoint of e will contribute a
knot to the botKnots array of trapezoid T. We must also check if our local maximum
has a top horizontal edge because then a second knot will be added to the same bot-
Knots array. Table 14.4.2 gives an example of these steps using Figure 14.19(b) again.
Figures 14.20(a) and 14.21(a) show some sample polygons and their final trapezoidal
decompositions.
Returning to the topic of trimmed surfaces, once we get a trapezoidal decompo-
sition of their domain as described above, there is still work to be done when it comes
to displaying them. For one thing, the trapezoids may be large and may need to be
subdivided. Any subdivision has to take the knots into account to avoid gaps in the
image. We shall describe a scan line approach that would also be suitable in the
context of a z-buffer or related type display. Basically, we need to come up with a
convenient way to subdivide the trapezoidal u-v domain appropriately.
Assume that du and dv are the maximum u and v step sizes, respectively, that we
are to use. Assume that trapezoids have a Boolean doBottom field that specifies
whether or not the bottom edge of the trapezoid is to be drawn (we always draw the
top edge). The reason for this is that if two trapezoids are adjacent, then we might
not want to draw their common edge twice. Because of the way that trapezoids are
T able 14.4.2
Stages of the AEL processing procedure.
AEL
Trapezoid values
Edges
(topY,topKnots)
(x,adjacent trapezoid)
At beginning
{ e1 , e7 , e8 , e9 , e10 , e6 }
tz4 (yb,{})
e1 (x1b,tz4)
tz5 (yb,{})
tz6 (yb,{})
After e1
{ e1 , e7 , e8 , e9 , e10 , e6 }
no change
e1 (x1t,tz4)
After e8
{ e1 , e11 , e9 , e10 , e6 }
tz4 (yt,{xp7})
e1 (x1t,tz7)
tz7 (yt,{})
After e10
{ e1 , e11 , e10 , e6 }
no change
e10 (x10t,tz6)
Search WWH ::




Custom Search