US4646076A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for high speed graphics fill
Assignee: Unisys Corp
•
Filing: 1983-04-27
•
Granted: 1987-02-24
•
Expires: 2003-04-27
Abstract
Abstract A method and apparatus for performing high speed graphics fill is provided. Any closed line geometric shape or polygon that can be defined by pixel position is stored in memory. The memory pixel positions are stored in address locations corresponding to row and column positions. A first sequential examination of the data is made in reverse raster scan order to make a preliminary determination of the pixel positions inside the closed polygon. A second sequential examination of the data is made in forward or regular raster scan order and a final determination is made whether the pixel positions are inside the polygon and shall be filled. The final determination of pixel positions to be filled is stored shortly before the graphics fill operation is performed so that the fill operation is performed in raster scan time at high speed.
Inventors
- 👤 Gregory B. Wiedenman
- 👤 Kenneth S. Morley
- 👤 Gary H. Frederickson
- 👤 Jeffrey L. Williams
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 08:15
CPC Classifications
G; G09; G09G; G09G5/00; G09G5/36; G09G5/39; G09G5/393; G06; G06T; G06T11/00; G06T11/40
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
277 words
A high speed graphics fill raster scan method of generating fill data bits for positions within a gaphics polgon on a graphics display of the type having a pixel graphics memeory having addresses that define each pixel position and provide a pixel data word in said graphics memory comprising a pixel line data bit and a pixel fill data bit for each pixel position, comprising the steps of: erasing said pixel line and fill data bits in said pixel data word, writing into said said pixel graphics memory pixel line data bits to define said graphics polygon, reading in reverse raster scan sequence order each pixel data word, making a preliminary determination based on the presence of a pixel line data bit at each pixel position whether a boundary of said graphics polygon has been crossed and whether said pixel position exist inside of said graphics polygon and would require a pixel fill data bit, writing a preliminary pixel fill data bit in said pixel data word in accordance with said preliminary determination, reading in forward raster scan sequence order each pixel data word, making a final determination at each pixel position whether a boundary of said graphics polygon has been crossed based on the presence of a combination of pixel line data bits and whether said pixel position would require a pixel fill data bit as being inside said graphics polygon, and writing a final pixel fill data bit in said pixel data word based on the presence of a pixel fill data bit already existing in said pixel data word and the absence of a pixel line data bit existing in said pixel data word.
Claim 2
Dependent Claim
277 words
A high speed graphics fill raster scan method of generating fill data bits for positions within a gaphics polgon on a graphics display of the type having a pixel graphics memeory having addresses that define each pixel position and provide a pixel data word in said graphics memory comprising a pixel line data bit and a pixel fill data bit for each pixel position, comprising the steps of: erasing said pixel line and fill data bits in said pixel data word, writing into said said pixel graphics memory pixel line data bits to define said graphics polygon, reading in reverse raster scan sequence order each pixel data word, making a preliminary determination based on the presence of a pixel line data bit at each pixel position whether a boundary of said graphics polygon has been crossed and whether said pixel position exist inside of said graphics polygon and would require a pixel fill data bit, writing a preliminary pixel fill data bit in said pixel data word in accordance with said preliminary determination, reading in forward raster scan sequence order each pixel data word, making a final determination at each pixel position whether a boundary of said graphics polygon has been crossed based on the presence of a combination of pixel line data bits and whether said pixel position would require a pixel fill data bit as being inside said graphics polygon, and writing a final pixel fill data bit in said pixel data word based on the presence of a pixel fill data bit already existing in said pixel data word and the absence of a pixel line data bit existing in said pixel data word.
Claim 3
Dependent Claim
49 words
A high speed graphics fill method as set forth in claim 1 which further includes the steps of: providing color data bits in said pixel data word, and writing color data bits in said data word where final pixel fill data bits have been written in said data word.
Claim 4
Dependent Claim
48 words
A high speed graphics fill method as set forth in claim 2 which further includes the step of: reading said color data bits in said data words, and generating color control signals for controlling the electron beams of a color CRT in accrdance with said color data bits.
Claim 5
Dependent Claim
50 words
A high speed graphics fill method as set forth in claim 1 which further includes the steps of: reading said final pixel fill data bit in said pixel data word, and using said fill data bit to generate a write signal for controlling the electron beam of a color CRT.
Claim 6
Dependent Claim
40 words
A high speed graphics fill method as set forth in claim 3 which further includes the steps of: reading said final pixel fill data bit, and simultaneously generating said color control signals for controlling said election beam of said CRT.
Claim 7
Dependent Claim
57 words
A high speed graphics fill method as set forth in claim 1 which further includes the step of reading some of said final pixel fill data bits in said pixel data words for current use concurrently while making a final determination to write a final pixel fill data bit in other pixel data words for subsequent use.
Claim 8
Dependent Claim
74 words
A high speed graphics fill method as set forth in claim 1 wherein said step of making a preliminary determination at each pixel position comprises the step of: determining that a pixel line data bits exists in the previous pixel position and that a pixel line data bit exists in the pixel position in the line below as a condition for writing a preliminary pixel fill data bit in the present pixel data word.
Claim 9
Dependent Claim
57 words
A high speed graphics fill method as set forth in claim 1 wherein said step of making a preliminary determination at each pixel position comprises the step of: determining that a pixel fill data bit exists in the previous pixel position as a condition for writing a preliminary pixel fill data bit in the present data word.
Claim 10
Dependent Claim
72 words
A high speed graphics fill method as set forth in claim 1 wherein said step of making a preliminary determination at each pixel position comprises the step of: determining that a pixel line data bit exists in the previous pixel position and that a pixel data bit exists in the pixel position in the line below as a condition for writing a preliminary pixel fill data bit in the present data word.
Claim 11
Dependent Claim
70 words
A high speed graphics fill method as set forth in claim 1 wherein said step of making a preliminary determination at each pixel position comprises the step of: determining that a pixel fill data bit and a pixel line data bit exists in the previous pixel position AND that the present pixel position exists as a condition for writing a preliminary pixel fill data bit in the present data word.
Claim 12
Dependent Claim
71 words
A high speed graphics fill method as set forth in claim 1 wherein the step of making a preliminary determination at each pixel position comprises the step of: determining that a pixel line data bit exists in the previous pixel position AND that a pixel fill data bit exists in the previous pixel position as a condition for NOT writing a preliminary pixel fill data bit in the present data word.
Claim 13
Dependent Claim
72 words
A high speed graphics fill method as set forth in claim 1 wherein the step of making a preliminary determination at each pixel comprises the step of: determining that a pixel line data bit exists in the present pixel position AND that a pixel fill data bit exists in the pixel position in the line below as a condition for writing a preliminary pixel fill data bit in the present data word.
Claim 14
Dependent Claim
233 words
A high speed graphics fill raster scan method of generating fill data bits for positions within a graphics polygon on a graphics display of the type havng a pixel graphics memory having addresses that define each pixel position and provide a pixel data word in said graphics memory comprising a pixel line data bit, a pixel fill data bit and color data bit for each pixel position, comprising the steps of: erasing said pixel line and fill data bits of said data word, writing into said pixel graphics memory pixel line data bits to define said graphics polygon, reading in reverse TV type raster scan sequence order each pixel data word, reading in forward TV type raster scan sequence order each pixel data word, making a preliminary determination at each pixel position whether a boundary of said graphics polygon has been crossed and whether said pixel position exist inside said graphics polygon and would not require a pixel fill data bit, writing a preliminary inhibit pixel fill data bit in said word in accordance with said preliminary determination, reading each pixel data word in raster scan sequence, determining that no inhibit pixel fill data bits have been written during the last raster scan sequence, and, writing final color bits in said pixel data words in all pixel positions not inhibited by a pixel line data bit or an inhibit pixel fill data bit.
Claim 15
Dependent Claim
233 words
A high speed graphics fill raster scan method of generating fill data bits for positions within a graphics polygon on a graphics display of the type havng a pixel graphics memory having addresses that define each pixel position and provide a pixel data word in said graphics memory comprising a pixel line data bit, a pixel fill data bit and color data bit for each pixel position, comprising the steps of: erasing said pixel line and fill data bits of said data word, writing into said pixel graphics memory pixel line data bits to define said graphics polygon, reading in reverse TV type raster scan sequence order each pixel data word, reading in forward TV type raster scan sequence order each pixel data word, making a preliminary determination at each pixel position whether a boundary of said graphics polygon has been crossed and whether said pixel position exist inside said graphics polygon and would not require a pixel fill data bit, writing a preliminary inhibit pixel fill data bit in said word in accordance with said preliminary determination, reading each pixel data word in raster scan sequence, determining that no inhibit pixel fill data bits have been written during the last raster scan sequence, and, writing final color bits in said pixel data words in all pixel positions not inhibited by a pixel line data bit or an inhibit pixel fill data bit.
References Cited (Backward Citations)
US3821796A
Cited
US4155095A
Cited
US4139838A
Cited
US4217577A
Cited
US4303986A
Cited
US4368461A
Cited
US4492956A
Cited
US4425559A
Cited
US4437092A
Cited
US4528642A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1990-02-23 | 1990-08-25 | 1991-02-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1994-02-23 | 1994-08-25 | 1995-02-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1998-02-23 | 1998-08-25 | 1999-02-24 | $7700.00 | Window Closed / Lapsed |