US4996653A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Line generation in a display system
Assignee: International Business Machines Corp
•
Filing: 1987-12-28
•
Granted: 1991-02-26
•
Expires: 2007-12-28
Abstract
Abstract In a line generator and a method for determining the individual pixels to be plotted for a line to be drawn in a display system, coded representations of a plurality of lines are stored in a line definition table. The coded representation of each individual line is a string of data items representing the transitions between adjacent pixels to be plotted for drawing the individual line. Preferably, only coded representations of lines up to a predetermined size (i.e. the length of the line in the case of a straight line) are stored in the line definition table. Strings of data items for representing the pixels to be plotted for longer lines to be drawn are still calculated as in the prior art. In this case, control logic determines whether there are coded representations of a line to be drawn in the line definition table, or not, and passes control to appropriate processing logic for determining the pixels to be plotted. In a preferred embodiment, the string of data items forming the coded representation of a line to be drawn is a string of binary digits and the value of each bit in the string represents a transition in one of two directions. This provides a very compact representation of the line.
Inventors
- 👤 Nicholas D. Butler
- 👤 Adrian C. Gay
- 👤 Jack E. Bresenham
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 19:35
CPC Classifications
G; G09; G09G; G09G1/00; G09G1/06; G09G1/08; G09G1/10; G09G5/00; G09G5/20
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
189 words
A line generator for determining the individual pixels to be plotted for a line to be drawn on a display device in a display system, said display device having a plurality of discrete display points ("pixels") that are drawn by being illuminated in response to electrical control signals, said line generator comprising: line definition means for determining pixels to plot, said line definition means including: (a) a line definition table having a plurality of discrete entries representing a set of lines, in each of which is stored a coded representation of a respective one of said set of lines, the coded representation of each individual line comprising a series of data items representing transitions between adjacent pixels to be plotted for drawing said individual line; (b) address logic for accessing an appropriate entry in the line definition table for the coded representation of a line to be drawn in response to a line drawing order; and means for generating electrical control signals for causing pixels to be drawn on said display device, said electrical control signals generated in response to said coded representation of said line to be drawn.
Claim 2
Dependent Claim
189 words
A line generator for determining the individual pixels to be plotted for a line to be drawn on a display device in a display system, said display device having a plurality of discrete display points ("pixels") that are drawn by being illuminated in response to electrical control signals, said line generator comprising: line definition means for determining pixels to plot, said line definition means including: (a) a line definition table having a plurality of discrete entries representing a set of lines, in each of which is stored a coded representation of a respective one of said set of lines, the coded representation of each individual line comprising a series of data items representing transitions between adjacent pixels to be plotted for drawing said individual line; (b) address logic for accessing an appropriate entry in the line definition table for the coded representation of a line to be drawn in response to a line drawing order; and means for generating electrical control signals for causing pixels to be drawn on said display device, said electrical control signals generated in response to said coded representation of said line to be drawn.
Claim 3
Dependent Claim
89 words
A line generator as claimed in claim 1 wherein said set of lines comprises only lines up to a predetermined size and in which the line generator additionally comprises a second line definition means for automatically generating a coded representation of a line to be drawn as a string of data items representing said line to be drawn which is greater in size than said predetermined size, said line definitions means responsive to a line drawing order and said coded representation generated according to a prespecified line generation procedure.
Claim 4
Dependent Claim
55 words
A line generator as claimed in claim 2 further comprising initialization means for automatically determining whether the line to be drawn is greater than said predetermined size, and for enabling either the first mentioned line definition means if the line is not greater than said predetermined size or, otherwise, enabling the second line generation means.
Claim 5
Dependent Claim
86 words
A line generator as claimed in claim 3 further comprising third line definition means for automatically generating a coded representation of a line to be drawn as a string a data items representing said line which is in one of a set of predetermined directions and wherein said initialization means determines whether said line to be drawn is in one of said set of predetermined directions, and if so, enables the third line definition means in preference to said first or said second line definition means.
Claim 6
Dependent Claim
78 words
A line generator as set forth in claim 1, 2, 3 or 4, wherein said means for generating said electrical control signals comprises pixel position registers for identifying, at any one time, the location of a pixel to be plotted and plotting means for, in response to successive data items in a string of data items from a line definition means, updating said pixel registers to identify successive pixels to be plotted for a line to be drawn.
Claim 7
Dependent Claim
47 words
A line generator as set forth in claim 1, 2, 3 or 4, wherein each data item is a bit of information having either a first binary value indicating a transition in a first direction or a second binary value indicating a transition in a second direction.
Claim 8
Dependent Claim
65 words
A line generator as set forth in claim 6 wherein said set of lines comprise lines not greater than a predetermined length, the data items for each line being determined in accordance with Bresenham's Line Algorithm, and wherein said first direction is an axial direction along a first defined axis and said second direction is a diagonal direction in relation to said first defined axis.
Claim 9
Dependent Claim
50 words
A line generator as set forth in claim 1, 2, 3 or 4, wherein said address logic is arranged as a two level index structure to access the line definition table using major and minor axis line lengths of a line to be drawn as primary and secondary addressing parameters.
Claim 10
Independent Claim
111 words
A method of determining the individual pixels to be plotted for a line to be drawn in a computer controlled display system, the method comprising the steps of: accessing in response to a line drawing order a coded representation of the line from a line definition table having a plurality of discrete entries in each of which is stored a coded representation of a respective one of a set of lines, the coded representation of each individual line comprising a string of data items representing the transitions between adjacent pixels to be plotted for drawing said individual line; and generating electrical control signals causing said display system to display said line.
Claim 11
Independent Claim
111 words
A method of determining the individual pixels to be plotted for a line to be drawn in a computer controlled display system, the method comprising the steps of: accessing in response to a line drawing order a coded representation of the line from a line definition table having a plurality of discrete entries in each of which is stored a coded representation of a respective one of a set of lines, the coded representation of each individual line comprising a string of data items representing the transitions between adjacent pixels to be plotted for drawing said individual line; and generating electrical control signals causing said display system to display said line.
Claim 12
Dependent Claim
191 words
A display system comprising: a display device having a plurality of discrete display points ("pixels"), said pixels being drawn by being illuminated in response to electrical control signals; a line generator for determining individual pixels to be plotted for a line to be drawn on said display device, said line generator including: (a) line definition means for determining pixels to plot, said line definition means including: (1) a line definition table having a plurality of discrete entries representing a set of lines in each of which is stored a coded representation of a respective one of said set of lines, the coded representation of each individual line comprising a string of data items representing the transitions between adjacent pixels to be plotted for drawing said individual line; (2) address logic for accessing an appropriate entry in the line definition table for the coded representation of a line to be drawn in response to line drawing order; and (b) means for generating electrical control signals for causing pixels to be drawn on said display device, said electrical control signals generated in response to said coded representation of said line to be drawn.
Claim 13
Dependent Claim
191 words
A display system comprising: a display device having a plurality of discrete display points ("pixels"), said pixels being drawn by being illuminated in response to electrical control signals; a line generator for determining individual pixels to be plotted for a line to be drawn on said display device, said line generator including: (a) line definition means for determining pixels to plot, said line definition means including: (1) a line definition table having a plurality of discrete entries representing a set of lines in each of which is stored a coded representation of a respective one of said set of lines, the coded representation of each individual line comprising a string of data items representing the transitions between adjacent pixels to be plotted for drawing said individual line; (2) address logic for accessing an appropriate entry in the line definition table for the coded representation of a line to be drawn in response to line drawing order; and (b) means for generating electrical control signals for causing pixels to be drawn on said display device, said electrical control signals generated in response to said coded representation of said line to be drawn.
Claim 14
Dependent Claim
89 words
A display system as claimed in claim 10 wherein said set of lines comprises only lines up to a predetermined size and in which the line generator additionally comprises a second line definition means for automatically generating a coded representation of a line, said coded representation comprising a string of data items representing said line to be drawn which is greater in size than said predetermined size, said line definition means responsive to a line drawing order and said coded representation generated according to a prespecified line generation procedure.
Claim 15
Dependent Claim
55 words
A display system as claimed in claim 11 further comprising initialization means for automatically determining whether the line to be drawn is greater than said predetermined size, and for enabling either the first mentioned line definition means if the line is not greater than said predetermined size or, otherwise, enabling the second line generation means.
Claim 16
Dependent Claim
87 words
A display system as claimed in claim 12 further comprising third line definition means for automatically generating a coded representation of a line, said coded representation comprising a string of data items representing said line which is in one of a set of predetermined directions and wherein said initialization means determines automatically whether a line to be drawn is in one of said set of predetermined directions, and if so, enables the third line definition means in preference to said first or said second line definition means.
Claim 17
Dependent Claim
77 words
A display system as set forth in claims 10, 11, 12 or 13, wherein said means for generating electrical control signals comprises pixel position registers for identifying, at any one time, the location of a pixel to be plotted and plotting means for, in response to successive data items in a string of data items from a line definition means, updating said pixel registers to identify successive pixels to be plotted for a line to be drawn.
Claim 18
Dependent Claim
47 words
A display system as set forth in claims 10, 11, 12, or 13, wherein each data item is a bit of information having either a first binary value indicating a transition in a first direction or a second binary value indicating a transition in a second direction.
Claim 19
Dependent Claim
65 words
A display system as set forth in claim 15 wherein said set of lines comprise lines not greater than a predetermined length, the data items for each line being determined in accordance with Bresenham's Line algorithm, and wherein said first direction is an axial direction along a first defined axis and said second direction is a diagonal direction in relation to said first defined axis.
Claim 20
Dependent Claim
50 words
A line generator as set forth in claims 10, 11, 12 or 13, wherein said address logic is arranged as a two level index structures to access the line definition table using major and minor axis line lengths of a line to be drawn as primary and secondary addressing parameters.
References Cited (Backward Citations)
GB1224224A
Cited
US4330834A
Cited
US4319331A
Cited
US4827432A
Cited
US4831557A
Cited
US4819190A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-02-25 | 1994-08-27 | 1995-02-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-02-25 | 1998-08-27 | 1999-02-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-02-25 | 2002-08-27 | 2003-02-26 | $7700.00 | Window Closed / Lapsed |