Graphics Reference
In-Depth Information
(a)
(b)
Figure 14.20.
Trapezoidal decompositions of polygons.
(a)
(b)
Figure 14.21.
More trapezoidal decompositions of polygons.
generated they never have common side edges. Incorporating this
doBottom
field in
the trapezoid generation algorithm is easy. It is set to true for all trapezoids whose
bottom edge comes from a local minimum horizontal edge or that meet a local
maximum horizontal edge.
Given a trapezoid we first want to subdivide it into horizontal slices that are at
most dv units high and then to subdivide each of these slices into rectangular or tri-
angular patches whose top and bottom edges are at most du units wide. Furthermore,
any knots that the trapezoid may have must appear as vertices for the patches. Getting
the horizontal slices is easy. The tricky part is to divide those slices vertically in a way
that will include the knots in the division. One can do this by dealing with various
cases separately. The three types of generic cases are shown in Figure 14.22 and one
basically divides the trapezoids along the dotted lines shown in the figure, except that
the existence of knots may mean that the actual lines along which the trapezoids are
divided may be a slightly perturbed version of those. In the end, drawing a slice is
