Graphics Reference
In-Depth Information
a noncontributing edge and vice versa. This is implemented by simply swapping the
output polygon pointers. If two like edges intersect, then a left edge becomes a right
edge and a right edge becomes a left edge. One needs to swap the intersecting edges
in the AEL to maintain the x-sort.
This finishes our discussion of the Vatti algorithm in the case where there are no
horizontal edges. Now we address the more complicated general case that allows hor-
izontal edges to exist. (However, we never allow edges to overlap, that is, where they
share a common segment.) The only changes we have to make are in procedure
ProcessEdgesInAEL. On an abstract level, it is easy to see how horizontal edges should
be handled. The classification of vertices described above should proceed as if such
edges were absent (had been shrunk to a point). Furthermore, if horizontal edges do
not intersect any other edge, then for all practical purposes they could be ignored.
The problems arise when intersections exist.
Imagine that the polygons were rotated slightly so that there were no horizontal
edges. The edges that used to be horizontal would now be handled without any
problem. This suggests how they should be treated when they are horizontal. One
should handle horizontal edges the same way that intersections are handled. Note that
horizontal edge intersections occur only at the bottom or top of a scan beam. Hori-
zontal edges at local minima should be handled in the AddNewBoundPairs procedure.
The others are handled as special cases in that part of the algorithm that tests whether
or not an edge ends in the current scan beam. If it does, we also need to look for hor-
izontal edges at the top of the current scan beam and the type classification of a vertex
should then distinguish between a local maximum, left intermediate vertex, or right
intermediate vertex cases. The corresponding procedures need to continue scanning
the AEL for edges that intersect the horizontal edge until one gets past it. One final
problem occurs with horizontal edges that are oriented to the left. These would be
detected too late, that is, by the time one finds the edge to which they are the suc-
cessor, we would have already scanned past the AEL edges that intersected them. To
avoid this, the simplest solution probably is to make an initial scan of the AEL for all
such edges before one checks events at the top of the scan beam and put them into a
special left-oriented horizontal edge list (LHL) ordered by the x-values of their left
endpoints. Then as one scans the AEL one needs to constantly check the top x-value
of an edge for whether it lies inside one of these horizontal edges.
This completes our description of the basic Vatti algorithm. The algorithm can be
optimized in the common case of rectangular clip bounds. Another optimization is pos-
sible if the clip polygon is fixed (rectangular or not) by computing its bounds only once
and initializing the LML to these bounds at the beginning of a call to the clip algorithm.
An attractive feature of Vatti's algorithm is that it can easily be modified to gen-
erate trapezoids. This is particularly convenient for scan line-oriented rendering algo-
rithms. Each local minimum starts a trapezoid or breaks an existing one into two
depending on whether the local minimum starts with a left-right (contributing case)
or right-left (noncontributing case) edge pair. At a contributing local minimum we
create a trapezoid. Trapezoids are output at local maxima and left or right interme-
diate vertices. A noncontributing local minimum should output the trapezoid it is
about to split and update the trapezoid pointers of the relevant edges to the two new
trapezoids. Vatti compared the performance of the trapezoid version of his algorithm
to the Sutherland-Hodgman algorithm and found it to be roughly twice as fast for
clipping (the more edges, the more the improvement) and substantially faster if one
