Method and apparatus for filling polygons displayed by a raster graphic system

• US 4,481,594 A
• Filed: 01/18/1982
• Issued: 11/06/1984
• Est. Priority Date: 01/18/1982
• Status: Expired due to Fees

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell Information Systems, Inc. (Honeywell International Inc.)
• Inventors: Staggs, Kevin P., Clarke, Charles J. Jr., Huntington, James C.
• Primary Examiner(s): Ruggiero, Joseph F.
• Assistant Examiner(s): Harkcom, Gary V.
• Application Number:
  US06/340,143
• Time in Patent Office: 1,023 Days
• Field of Search: 364/521, 364/522, 364/718, 364/719, 340/701, 340/703, 340/747, 340/751
• US Class Current: 345/589
• CPC Class Codes: G09G 5/42 characterised by the display of patterns using a display memory without fixed position correspondence between the display memory contents and the display position on the screen

Abstract

Method and apparatus for filling polygons displayed by a color CRT monitor of a raster graphic system. A graphic controller produces control signals which control the mode of operation of the system, two of which are a fast polygon write, or fast-fill write, mode and a fast polygon display, or display fast-fill, mode. When the system is in the fast polygon write mode, the graphic controller reads fast-fill toggle bits from a frame memory of boundary pixels defining initial and terminal pixels of each fill element. The fast-fill toggle bits of boundary pixels are set if the toggle bit read from memory was not set and, if set, it will reset it. In the fast polygon display mode, the system senses the initial boundary pixel of each fill element by its fast-fill toggle bit being set and applies the color address of the initial boundary pixel to a color look-up memory until the terminal pixel of the fill element is read from the memory. Thereafter, the color address of each pixel of a horizontal scan line is applied to the color look-up memory in synchronization with the raster scan until another initial boundary pixel of another fill element is sensed, etc., or until the end of the horizontal scan line is reached.

Claims

1. Apparatus for filling polygons displayed by a color CRT monitor of a computer generated raster graphic system, said system having a frame memory adapted to store color addresses and fast-fill toggle bits at memory locations whose addresses correspond to those of the pixels of the CRT of the monitor, raster scan logic for reading from the frame memory and, for producing in synchronism with the raster scan of the CRT, the color address and fast-fill toggle bit for each pixel, a color look-up memory adapted to store color control signals in memory locations, the addresses of which correspond to color addresses stored in the frame memory;

a graphic controller having the capability of writing data into addressed locations of the frame memory, of reading data from said locations and of determining the initial and terminal pixels of a fill element of a horizontal scan line of a polygon, and of producing control signals for controlling the mode of operation of said system, said system having a fast polygon write mode and a fast polygon display mode;

said apparatus comprising;

means for reading, when the system is in fast polygon write mode, the fast-fill toggle bits from memory locations in the frame memory of boundary pixels defining the initial and terminal pixels of each fill element of each horizontal scan line, for setting the fast-fill toggle bits of boundary pixels of each fill element if and only if the fast-fill toggle bit read from the memory location for each such boundary pixel is not set, and, if set, for resetting it and for writing the fast-fill toggle bits of boundary pixels of each fill element, and

means for applying, when the system is in the fast polygon display mode, the color address stored at the initial boundary pixel of each fill element of each horizontal scan line to the color look-up memory in synchronization with the scan thereof until the terminal pixel of the fill element is read from the frame memory, thereafter for applying the color address of each pixel of the horizontal scan line to the color look-up memory in synchronization with the raster scan until another initial boundary pixel of another fill element of the horizontal scan line is is read from memory, or until the end of the horizontal scan line is reached, as long as the system is in its fast polygon display mode.

2. The method of filling polygons displayed by a color CRT monitor of a computer generated raster graphic system, said system having a frame memory adapted to store color addresses and fast-fill toggle bits at memory locations whose addresses correspond to those of the pixels of the CRT of the monitor, raster scan logic for reading from the frame memory and for producing in synchronism with the raster scan of the CRT, the color address and fast-fill toggle bit for each pixel, a color look-up memory adapted to store color control signals in memory locations, the addresses of which correspond to color addresses stored in the frame memory;

a graphic controller having the capability of writing data into addressed locations of the frame memory, of reading data from said locations and of determining the initial and terminal pixels of a fill element of a horizontal scan line of a polygon, and of producing control signals for controlling the mode of operation of said system, said system having a fast polygon write mode and a fast polygon display mode;

said method comprising the steps of;

reading, when the system is in fast polygon write mode, the fast-fill toggle bits from memory locations in the frame memory of boundary pixels defining the initial and terminal pixels of each fill element of each horizontal scan line, setting the fast-fill toggle bits of boundary pixels of each fill element if and only if the fast-fill toggle bit read from the memory location for each such boundary pixel is not set, and if set, resetting it, and writing the fast-fill toggle bits into memory locations of the frame memory corresponding to the boundary pixels of each fill element; and

applying, when the system is in its fast polygon display mode, the color address stored at the address in the frame memory of the initial boundary pixel of each fill element of each horizontal scan line to the color look-up memory in synchronization with the scan thereof until the terminal pixel of the fill element is read from the frame memory, thereafter applying the color address of each pixel of the horizontal scan line to the color look-up memory in synchronization with the raster scan until the next initial boundary pixel of the next adjacent fill element of the horizontal scan line is read from memory, and repeating this step for each horizontal scan line until the end of each horizontal scan line is reached, and repeating this step for each horizontal scan line as scanned as long as the system is in its fast polygon display mode.

3. A computer generated raster graphic system comprising:

a CRT monitor including a raster scanned color cathode ray tube having a rectangular array of pixels;

a frame memory adapted to store a color address and a fast-fill toggle bit at memory locations whose addresses correspond to those of the pixels of the cathode ray tube;

raster scan logic means for reading from the frame memory and for producing in synchronism with the raster scan of the cathode ray tube the color address and fast-fill toggle bit for each pixel;

a color look-up memory adapted to store color control signals in memory locations, the addresses of which correspond to color addresses stored in the frame memory;

first-circuit means for applying the color addresses of each pixel produced in synchronism with the raster scan to the color look-up memory;

graphic controller means for writing a color address and a toggle fill bit into addressed locations of the frame memory, for reading data from said locations, for determining the addresses of initial and terminal pixels of fill elements with which a polygon is adapted to be filled, each fill element lying on a horizontal scan line of the raster, and for producing a fast polygon write mode control signal and a fast polygon display mode control signal;

ambiguity resolution circuit means for setting the fast-fill toggle bit of a boundary pixel under certain conditions;

said graphic controller means, after having produced a fast polygon write mode control signal and while this control signal is produced, reading from the frame memory the fast-fill toggle bits from memory locations in the frame memory of boundary pixels defining the initial and terminal pixels of each fill element, and applying said fast-fill toggle bits to the ambiguity resolution circuit means, said graphic controller means applying to the ambiguity resolution circuit means a fast-fill toggle bit having a logical value of 1 representing that the addressed memory location is that of a boundary pixel;

said ambiguity resolution circuit means for setting the fast-fill toggle bit stored in the addressed memory location if, and only if, the logical value of the fast-fill toggle bit for that location read from the frame memory is not a logical 1; and

said first circuit means applying to the color look-up memory while the graphic controller produces the fast polygon display mode control signal, the color address stored at the address of the initial boundary pixel of each fill element until the terminal pixel of the fill element is read from the frame memory, thereafter applying the color address of each pixel of the horizontal scan line to the color look-up memory in synchronization with the raster scan until another initial boundary pixel of another fill element of the horizontal scan line is produced, or a terminal pixel or the end of a horizonal scan line is reached.

4. The raster graphic system of claim 3 in which the ambiguity resolution circuit includes an exclusive OR gate.

5. The raster graphic system of claim 4 in which the first circuit means includes a transparent latch.

6. Method of filling polygons displayed by a raster scan color cathode ray tube of CRT monitor of a raster graphic system, said CRT tube having an array of pixels with each pixel having a unique binary address, comprising the steps of:

a. writing into a frame random-access memory at addresses corresponding to the address of each pixel of the array a fast-fill toggle bit and a color address of a color look-up memory;

b. in a first mode of operation of the system, setting the fast-fill toggle bit of the boundary pixels defining a polygon, the interior of which is to be filled by color fill elements if, and only if, the fast-fill toggle bit of the boundary pixel was not previously set, and, if the fast-fill toggle bit of the boundary was set, resetting the fast-fill toggle bit of said boundary pixel;

c. in a second mode of operation of the system, applying the color address of each pixel in each horizontal scan line of the raster to a color look-up memory in synchronism with the raster scan of the cathode ray tube of the CRT monitor until an odd-numbered boundary pixel is sensed;

d. applying the color address of the initial boundary pixel of a color fill element sensed in step (c) to the color look-up memory until an even-numbered boundary pixel, the terminal pixel of the color fill element, is sensed;

e. repeating steps (c) and (d) until the end of the scan of each horizontal line is completed; and

f. repeating steps (c), (d) and (e) for each horizontal line of the raster as long as the system is in its second mode of operation.

7. The method of claim 6 in which the boundary pixels are sensed by their fast-fill toggle bits having been set.

8. The method of claim 7 in which a color fill element is defined by the initial and terminal boundary pixels of polygons lying on the same horizontal scan line of the raster.