US 5,673,379 A · Scan line generator for area fill of extensible polygons

Abstract

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.

Claims8

Dependent claims

A method of describing pixel locations that represent a polygon edge as a sequence of STEPs and JUMPs upon a pixel grid whose pixel locations therein are indicated by integer Cartesian coordinates (X, Y), a STEP being a one pixel location change along a major axis accompanied by no change in the pixel location along a minor axis and a JUMP being a one pixel location change along the major axis that is accompanied by a one pixel location change along the minor axis, the polygon edge having X as a major axis and Y as a minor axis and the polygon to be displayed by illuminating selected pixels belonging to the pixel grid, the method comprising the steps of:

(a) determining from an (X.sub.start, Y.sub.start) and from an (X.sub.end, Y.sub.end) describing a polygon edge a dx=X.sub.end -X.sub.start and a dy=Y.sub.end =Y.sub.start ;
(b) initially assigning to an iteration variable d.sub.i the value dy-dx, where i is an integer indicating
the ordinal number of the iteration to be performed next and the initial value of i is one;
(c) if d.sub.i <0 indicating a STEP and assigning d.sub.i+1 the value d.sub.i +dy;
(d) if d.sub.i >0 indicating a JUMP and assigning d.sub.i+1 the value d.sub.i +dy-dx;
(e) if d.sub.i =0 performing either step (c) or step (d) in accordance with the slope of the polygon edge;
(f) repeating steps (c) through (e) until the entire polygon edge has been described;
and
(g) illuminating those pixels in the pixel grid visited by the sequence of STEPs and JUMPs produced by steps (c), (d) and (e), the sequence starting at the pixel location (X.sub.start, Y.sub.start).

6 more elements

A method of describing pixel locations that represent a polygon edge as a sequence of STEPs and JUMPs upon a pixel grid whose pixel locations therein are indicated by integer Cartesian coordinates (X, Y), a STEP being a one pixel location change along a major axis accompanied by no change in the pixel location along a minor axis and a JUMP being a one pixel location change along the major axis that is accompanied by a one pixel location change along the minor axis, the polygon edge having X as a minor axis and Y as a major axis and the polygon to be displayed by illuminating selected pixels belonging to the pixel grid, the method comprising the steps of:

(a) determining from an (X.sub.start, Y.sub.start) and from an (X.sub.end, Y.sub.end) describing a polygon edge a dx=X.sub.end -X.sub.start and a dy=Y.sub.end -Y.sub.start ;
(b) initially assigning to an iteration variable d.sub.i the value dx-dy, where i is an integer indicating the ordinal number of the iteration to be performed next and the initial value of i is one;
(c) if d.sub.i <0 indicating a STEP and assigning d.sub.i+1 the value d.sub.i +dx;
(d) if d.sub.i >0 indicating a JUMP and assigning d.sub.i+1 the value d.sub.i +dx-dy;
(e) if d.sub.i =0 performing either step (c) or step (d) in accordance with the slope of the polygon edge;
(f) repeating steps (c) through (e) until the entire polygon edge has been described;
and
(g) illuminating those pixels in the pixel grid visited by the sequence of STEPs and JUMPs produced by steps (c), (d) and (e), the sequence starting at the pixel location (X.sub.start, Y.sub.start).

5 more elements

Apparatus for describing pixel locations that represent a polygon edge as a sequence of STEPs and JUMPs upon a pixel grid whose pixel locations therein are indicated by integer Cartesian coordinates (X, Y), a STEP being a one pixel location change along a major axis accompanied by no change in the pixel location along a minor axis and a JUMP being a one pixel location change along the major axis that is accompanied by a one pixel location change along the minor axis, the polygon to be displayed by illuminating selected pixels belonging to the pixel grid, the apparatus comprising:

first through fourth input registers that respectively receive pixel location coordinates X.sub.start, Y.sub.start, X.sub.end and Y.sub.end ;
a first circuit, coupled to the first through fourth input registers, that computes dx=X.sub.end -X.sub.start and dy=Y.sub.end -Y.sub.start ;
a second circuit, coupled to the values of dy and dx, that produces a major axis signal indicating, according to whichever of dy and dx has the larger absolute value, which of the X or Y axes is the major axis;
a third circuit, coupled to the values of dy and dx and to the axis signal, that computes an initial value of an iteration variable d.sub.i, the initial value being dy-dx if X is the major axis and being dx-dy if Y is the major axis;
and
a fourth circuit, coupled to the major axis signal and to the values of dy and dx, that indicates STEPs and JUMPs and that computes successive values d.sub.i+1 of the iteration variable d.sub.i according to the sign of d.sub.i and according to which axis is the major axis:
if X is the major axis and d.sub.i >0 then d.sub.i+1 =di+dy-dx and indicate a JUMP;
if X is the major axis and d.sub.i <0 then d.sub.i+1 =d.sub.i +dy and indicate a STEP;
if Y is the major axis and d.sub.i >0 then d.sub.i+1 =d.sub.i +dx-dy and indicate a JUMP;
and
if Y is the major axis and d.sub.i <0 then d.sub.i+1 =d.sub.i +dx and indicate a STEP.

8 more elements

Dependencies are inferred from the claim text.

Scan line generator for area fill of extensible polygons

Life of this patent

Scan line generator for area fill of extensible polygons

Life of this patent

Abstract

Claims8