Method and apparatus for area fill in a raster graphics system

Claim 2

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to pixel data for read-out to a display, a system for providing area fill for the objects, comprising: a) pixel memory means for storing a value for each pixel in a display object, including means for storing for separate identification a value for each marked edge pixel of the object; b) boundary means for generating the pixels comprising the boundary of said display object; c) first line generator means for generating marked edge pixels in said pixel memory means by processing pairs of said display object vertices by means of an operation that utilizes the value of the next pixel to be processed in processing a current pixel; d) second line generator means, responsive to said marked edge pixels, for generating the pixels of the interior of said display object; and e) processor means for controlling the operation of said memory means, said boundary means, said register means and said line generator means to generate and store the boundary pixels and the interior pixels in said pixel memory means.

Claim 3

A system according to Claim 1 wherein said marked pixel means comprises Bresenham pel means for generating pixels using the Bresenham algorithm operating on the end points of the vectors which comprise a polygon.

Claim 4

A system according to Claim 2 wherein said Bresenham pel means further comprises extraction means for generating pels only when, wherein the x and y values of the pel currently being processed are X and Y, respectively, and the x and y values of the next pel to be processed are Xʹ and Yʹ, respectively: Yʹ > Y; or Yʹ < Y, and (X,Y) is not the first pel in the line segment with this property; or the y-coordinate of the ending point is less then the y-coordinate of the beginning point and (X,Y) is the last pel in the line segment.

Claim 5

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to pixel data for read-out to a display, a system for providing area fill for the objects, comprising: a) pixel memory means for storing a value for each pixel in a display object, including means for storing for separate identification a value for each marked edge pixel of the object; b) boundary means for generating the pixels comprising the boundary of said display object; c) first line generator means for generating marked edge pixels in said pixel memory means by processing pairs of said display object vertices by means of an operation that utilizes the value of the next pixel to be processed in processing a current pixel; d) second line generator means, responsive to said marked edge pixels, for generating the pixels of the interior of said display object; e) register means for storing coordinate values corresponding to the coordinate extent of a limited portion of the screen containing an object to be displayed, and for controlling the operation of said second line generator means to limit the area of operation to said limited portion of the screen; and f) processor means for controlling the operation of said memory means, said boundary means, said register means and said line generator means to generate and store the boundary pixels and the interior pixels in said pixel memory means.

Claim 6

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to pixel data for read-out to a display, a system for providing area fill for the objects, comprising: a) pixel memory means for storing a value for each pixel in a display object, including means for storing for separate identification a value for each marked edge pixel of the object; b) boundary means for generating the pixels comprising the boundary of said display object; c) first line generator means for generating marked edge pixels in said pixel memory means by processing pairs of said display object vertices by means of an operation that utilizes the value of the next pixel to be processed in processing a current pixel; d) second line generator means, responsive to said marked edge pixels, for generating the pixels of the interior of said display object; e) register means for storing coordinate values corresponding to the coordinate extent of a limited portion of the screen containing an object to be displayed, and for controlling the operation of said second line generator means to limit the area of operation to said limited portion of the screen; and f) processor means for controlling the operation of said memory means, said boundary means, said register means and said line generator means to generate and store the boundary pixels and the interior pixels in said pixel memory means.

Claim 7

A system according to Claim 4, further comprising register logic means for storing coordinate values corresponding to the coordinate extent of a limited portion of the screen containing an object to be displayed, and for controlling the operation of said second line generator means to limit the area of operation to said limited portion of the screen.

Claim 8

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to raster scan data for raster scan read-out to a display, a system for providing area fill for the objects, comprising: a) pixel memory means for storing a value for each pixel in a display object, including means for storing for separate identification a value for each marked edge pixel of the object; b) boundary means for generating the pixels comprising the boundary of said display object; c) first line generator means for generating marked edge pixels in said pixel memory means; d) second line generator means, responsive to said marked edge pixels, for generating the pixels of the interior of said display object; e) register logic means for storing coordinate values corresponding to the coordinate extent of a limited portion of the screen containing an object to be displayed, and for controlling the operation of said second line generator means to limit the operation of said second line generator means to limit the area of operation to said limited portion of the screen; and f) processor means for controlling the operation of said memory means, said boundary means and said line generator means to generate and store the boundary pixels and the interior pixels in said pixel memory means.

Claim 9

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to raster scan data for raster scan read-out to a display, a system for providing area fill for the objects, comprising: a) pixel memory means for storing a value for each pixel in a display object, including means for storing for separate identification a value for each marked edge pixel of the object; b) boundary means for generating the pixels comprising the boundary of said display object; c) first line generator means for generating marked edge pixels in said pixel memory means; d) second line generator means, responsive to said marked edge pixels, for generating the pixels of the interior of said display object; e) register logic means for storing coordinate values corresponding to the coordinate extent of a limited portion of the screen containing an object to be displayed, and for controlling the operation of said second line generator means to limit the operation of said second line generator means to limit the area of operation to said limited portion of the screen; and f) processor means for controlling the operation of said memory means, said boundary means and said line generator means to generate and store the boundary pixels and the interior pixels in said pixel memory means.

Claim 10

A system according to Claim 6 wherein said register logic means comprises: a) means for determining the maximum and minimum x values for the end points of the vectors comprising a polygon; and b) register means for storing said maximum and minimum x values.

Claim 11

A system according to Claim 6, wherein said register logic means further comprises: a) means for determining the maximum and minimum y values for the end points of the vectors comprising a polygon; and b) register means for storing said maximum and minimum y values.

Claim 12

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to raster scan data for raster scan read-out to a display, a method for providing area fill for the objects, comprising the steps of: a) generating the pixels comprising the boundary of said display object; b) generating marked edge pixels by processing pairs of said display object vertices in a process that determines marked edge pixels in a sequence, but operation on the current pixel and on the next pixel in the sequence; and c) generating the pixels of the interior of said display object in response to said marked edge pixels.

Claim 13

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to raster scan data for raster scan read-out to a display, a method for providing area fill for the objects, comprising the steps of: a) generating the pixels comprising the boundary of said display object; b) generating marked edge pixels by processing pairs of said display object vertices in a process that determines marked edge pixels in a sequence, but operation on the current pixel and on the next pixel in the sequence; and c) generating the pixels of the interior of said display object in response to said marked edge pixels.

Claim 14

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to raster scan data for raster scan read-out to a display, a method for providing area fill for the objects, comprising the steps of: a) generating the pixels comprising the boundary of said display object; b) for generating marked edge pixels in bit plane means; c) storing coordinate values corresponding to the coordinate extent of a limited portion of the screen containing an object to be displayed; and d) generating the pixels of the interior of said display object in response to said marked edge pixels, by a scanning process that is limited by said stored coordinate values.

Claim 15

A computer graphics display system including system memory and a processor for converting data corresponding to the position of polygon display object vertices to raster scan data for raster scan read-out to a display, a method for providing area fill for the objects, comprising the steps of: a) generating the pixels comprising the boundary of said display object; b) for generating marked edge pixels in bit plane means; c) storing coordinate values corresponding to the coordinate extent of a limited portion of the screen containing an object to be displayed; and d) generating the pixels of the interior of said display object in response to said marked edge pixels, by a scanning process that is limited by said stored coordinate values.