The standard polygon fill computes x-intersections of polygon edges with successive scan-lines based on a simple coherence principle. If x is the intersection of a scan line with a (non-horizontal) edge with slope b, then the intersection between the same edge and the next scan-line up will be x+(1/b). Moreover, when the top of an edge has been reached by the current scan-line, that edge drops out, and (possibly) another takes its place. This algorithm is facilitated by the Edge Table (ET) and Active Edge Table (AET) data structures.
This same algorithm could be used to output trapezia, by only considering those scan-lines at y-coordinates corresponding to vertices. However, it produces more trapezia than are necessary, as shown in the figure below.
Mel Slater, November 1997.
