Scan line generator for area fill of extensible polygons

摘要

A scan line generator for area fill of a polygon defined by a left edge and a right edge includes a Bresenham-like mechanism in a left edge machine for selecting pixels to represent a left edge by determining, for each scan line, which pixel is either on the edge or immediately to the right thereof. A right edge machine contains an identical mechanism, which also does "to-the-right-of". Both edge machines operate in the first through fourth octants, and a coordination mechanism steps the two edge machines a scan line at a time, independent of the major and minor axis of each edge. When the pixel addresses for each edge's intersection with the next scan line are found their difference along the X axis is obtained to produce the length of a fill vector on that scan line. The intersection produced for the left edge is taken as the starting point of the fill vector. Left and right edges must initially start on the same scan line, but need not be of the same length in the Y axis. Polygons are extensible by appending additional left and right edges to form lists thereof as the fill operation proceeds. Scan line generation is suspended whenever the furthest extent in the Y axis is reached for either edge. The fill operation may be concluded gracefully when such a suspension occurs for both edges, regardless of whether or not it is for the same polygon vertex. The edge machines are equipped with programmable edge rule mechanisms that define whether to retain or discard a pixel that lies exactly on an edge of the polygon.