Patent US4878182A successfully refreshed from Google Patents.
US4878182A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiple pixel generator
Assignee: International Business Machines Corp
•
Filing: 1987-10-30
•
Granted: 1989-10-31
•
Expires: 2007-10-30
Abstract
Abstract A system for generating multiple pixels in a single machine cycle employs a plurality of parallel vector generators. Each of the parallel generators is initialized with an error term which is calcualted in accordance with Bresenham's algorithm. The signs of these error terms are then used to determine the region within the first octant of the coordinate system which contains the function for which the pixels are to be generated. The region data, in turn, determine two selectable values for an increment which is to be added to a running error term for each of the parallel generators as multiple pixels are simultaneously generated. The choice of the two possible values to be added to the error term is dependent upon the sign of the error term itself. The sign of the running error term for each vector generator is utilized to form a sequence of binary data which represents the incremental changes in the pixel positions as the pixels are being generated. In a preferred embodiment, the binary data is translated into pixel position data which is then stored in a memory device. Any generated pixel data which cannot be stored in the machine cycle in which it is generated is re-routed for storage in later cycles.
Inventors
- 👤 Michael A. Aranda
- 👤 Timothy J. Ebbers
- 👤 Yoshio Iida
- 👤 Terence W. Lindgren
- 👤 Taggart H. Robertson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 14:18
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/23
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
193 words
A method for generating positioning values for a plurality of line points or pixels in a single machine cycle of a line generating system, wherein said positioning values represent the integer change in position relative to a previous pixel position necessary to represent an approximation of a linear function of at least one of the coordinates of said pixels, said method comprising: generating error terms according to Bresenham's algorithm for each of a plurality of contiguous pixels, with the number of said contiguous pixels being equal to the number of pixels which are to be generated during said single machine cycle; and generating, during said machine cycle, the positioning values for said plurality of pixels in a plurality of vector generators which are connected in parallel with one another and which are arranged so that each of said vector generators provides the positioning value for an associated one of said plurality of pixels, with the positioning value for each said pixel being determined, at least on part, as a function of the number of pixels being generated in one cycle and as a function of said error terms generated according to Bresenham's algorithm.
Claim 2
Independent Claim
193 words
A method for generating positioning values for a plurality of line points or pixels in a single machine cycle of a line generating system, wherein said positioning values represent the integer change in position relative to a previous pixel position necessary to represent an approximation of a linear function of at least one of the coordinates of said pixels, said method comprising: generating error terms according to Bresenham's algorithm for each of a plurality of contiguous pixels, with the number of said contiguous pixels being equal to the number of pixels which are to be generated during said single machine cycle; and generating, during said machine cycle, the positioning values for said plurality of pixels in a plurality of vector generators which are connected in parallel with one another and which are arranged so that each of said vector generators provides the positioning value for an associated one of said plurality of pixels, with the positioning value for each said pixel being determined, at least on part, as a function of the number of pixels being generated in one cycle and as a function of said error terms generated according to Bresenham's algorithm.
Claim 3
Dependent Claim
28 words
The method of claim 1 further comprising translating the positioning values provided by said vector generators into pixel position data which represents said approximation of said linear function.
Claim 4
Dependent Claim
25 words
The method of claim 1 further comprising storing in a memory device at least some of the positioning values generated during said single machine cycle.
Claim 5
Dependent Claim
40 words
The method of claim 3 wherein said storing step comprises storing during said machine cycle, those of the generated positioning values which meet the memory access constraints of the memory device, and regenerating unstored positioning values in subsequent machine cycles.
Claim 6
Dependent Claim
44 words
The method of claim 3 wherein said storing step comprises storing, during said machine cycle, those of the generated data values which meet the memory access constraints of the memory device, and designating the remaining generated data values for storage in subsequent machine cycles.
Claim 7
Dependent Claim
95 words
The method of claim 1 further comprising: dividing a two dimensional grid of possible pixel coordinates into octants so that, for a first one of said octants, the change in pixel coordinates which represent said linear function in the second dimension are greater than or equal to zero and also less than or equal to the change in pixel coordinates in said first dimension which serves as the argument for said linear function; and normalizing the parameters for said linear function so that the pixel coordinates for said function are contained in said first octant.
Claim 8
Dependent Claim
72 words
The method of claim 6 further comprising: dividing said first octant into a plurality of regions, with the number of regions being equal to the number of pixels which are to be generated during said single machine cycle; and determining, as a function of the sign of one or more of said error terms generated according to Bresenham's algorithm, which of said regions contains the pixel coordinates which represent said linear function.
Claim 9
Dependent Claim
28 words
The method of claim 7 wherein the determination of the positioning values for each said pixel is further a function of said region which contains said pixel coordinates.
Claim 10
Independent Claim
227 words
A method for generating the x and y coordinates of multiple pixel locations for a parameter defined line to be rasterized during a given single machine cycle of the pixel generating system, wherein the number of said pixels to be generated in said cycle is designated by n, said method comprising: dividing a two dimensional grid of possible pixel coordinates into octants so that, in a first one of said octants, the change in y-coordinate values of said parameter defined line is greater than or equal to zero and also less than or equal to the change in x-coordinate values thereof; normalizing the parameters which define said line so that the pixel coordinates for said line are contained in said first octant; dividing said first octant into a plurality of regions, with the number of regions being equal to n; generating error terms for the first n pixel locations by applying Bresenham's algorithm to each of n contiguous pixels; and generating in parallel, during said single machine cycle, n error terms which correspond to pixel locations other than said first n pixel locations, by adding a selectable increment to each of said error terms for said first n pixel locations, said increment having two possible values with the value selected being determined by the sign of the error term to which said increment is to be added.
Claim 11
Independent Claim
227 words
A method for generating the x and y coordinates of multiple pixel locations for a parameter defined line to be rasterized during a given single machine cycle of the pixel generating system, wherein the number of said pixels to be generated in said cycle is designated by n, said method comprising: dividing a two dimensional grid of possible pixel coordinates into octants so that, in a first one of said octants, the change in y-coordinate values of said parameter defined line is greater than or equal to zero and also less than or equal to the change in x-coordinate values thereof; normalizing the parameters which define said line so that the pixel coordinates for said line are contained in said first octant; dividing said first octant into a plurality of regions, with the number of regions being equal to n; generating error terms for the first n pixel locations by applying Bresenham's algorithm to each of n contiguous pixels; and generating in parallel, during said single machine cycle, n error terms which correspond to pixel locations other than said first n pixel locations, by adding a selectable increment to each of said error terms for said first n pixel locations, said increment having two possible values with the value selected being determined by the sign of the error term to which said increment is to be added.
Claim 12
Dependent Claim
62 words
The method of claim 9 further comprising determining, from the sign of one or more of said error terms for said first n pixel locations, which of said n regions contains the pixel coordinates for said rasterized line, and wherein the two possible values of said increment are determined as a function of said region which contains said rasterized line pixel coordinates.
Claim 13
Dependent Claim
79 words
The method of claim 10 wherein said two possible values of said increment are 2n(dy)-2(r+1)(dx) and 2n(dy)-2(r)(dx), for positive and negative signs, respectively, of the error term to which said increment is to be added, where r designates the region containing the rasterized line, dx designates the difference between the x-coordinate values of the ending and starting points of the line, and dy designates the difference between the y-coordinate values of the ending and starting points of the line.
Claim 14
Dependent Claim
33 words
The method of claim 10 wherein said values of said increment are determined during one or more of the machine cycles used to generate said error terms for said first n pixel locations.
Claim 15
Dependent Claim
49 words
The method of claim 9 further comprising translating the signs of the respective error terms into a sequence of binary bits which represent the incremental changes in the y-coordinate of the rasterized line pixel locations, as the rasterized line is traversed from its beginning coordinates to its ending coordinates.
Claim 16
Dependent Claim
56 words
The method of claim 13 wherein said binary bits are determined, at least in part, as a function of the binary bits previously appearing in said sequence, as a function of the region which contains said rasterized line pixel coordinates, and as a function of the limitations imposed on the sequence of bits for that region.
Claim 17
Dependent Claim
72 words
The method of claim 9 further comprising storing in a memory device having access rules at least some of the rasterized pixel locations generated in a given machine cycle, by determining which of said generated pixel locations meet the access rules of said memory device, storing said generated pixels which meet said rules in said device during said machine cycle, and regenerating in subsequent machine cycles those pixels which were not stored.
Claim 18
Dependent Claim
74 words
The method of claim 9 further comprising storing in a memory device having access rules at least some of the rasterized pixel locations generated in a given machine cycle, by determining which of said generated pixel locations meet the access rules of said memory device, storing said generated pixels which meet said rules in said device during said machine cycle, and designating for storage in subsequent machine cycles those pixels which were not stored.
Claim 19
Dependent Claim
200 words
Apparatus for generating positioning values for a plurality of pixels in a single given machine cycle of a pixel generating system, wherein said positioning values represent the integer change in position relative to a previous pixel position necessary to represent an approximation of a linear function of at least one of the coordinates of said pixels, said apparatus comprising: means for generating error terms according to Bresenham's algorithm for each of a plurality of contiguous pixels, with the number of said contiguous pixels being equal to the number of pixels which are to be generated during said single machine cycle; and a plurality of vector generators for generating, during said single machine cycle, the positioning values for said plurality of pixels, said vector generators being connected in parallel with one another and arranged so that each of said vector generators provides the positioning value for an associated one of said plurality of pixels, said vector generators being further configured so that the positioning value for each said pixel are determined, at least in part, as a function of the number of pixels being generated in one cycle and as a function of said error terms generated according to Bresenham's algorithm.
Claim 20
Dependent Claim
200 words
Apparatus for generating positioning values for a plurality of pixels in a single given machine cycle of a pixel generating system, wherein said positioning values represent the integer change in position relative to a previous pixel position necessary to represent an approximation of a linear function of at least one of the coordinates of said pixels, said apparatus comprising: means for generating error terms according to Bresenham's algorithm for each of a plurality of contiguous pixels, with the number of said contiguous pixels being equal to the number of pixels which are to be generated during said single machine cycle; and a plurality of vector generators for generating, during said single machine cycle, the positioning values for said plurality of pixels, said vector generators being connected in parallel with one another and arranged so that each of said vector generators provides the positioning value for an associated one of said plurality of pixels, said vector generators being further configured so that the positioning value for each said pixel are determined, at least in part, as a function of the number of pixels being generated in one cycle and as a function of said error terms generated according to Bresenham's algorithm.
Claim 21
Dependent Claim
30 words
The apparatus of claim 17 further comprising means for translating the positioning values provided by said vector generators into pixel position data which represents said approximation of said linear function.
Claim 22
Dependent Claim
23 words
The apparatus of claim 17 further comprising means for storing at least some of the positioning values generated during said single machine cycle.
Claim 23
Dependent Claim
44 words
The apparatus of claim 19 wherein said storage means comprises means for storing, during said machine cycle, those of the generated positioning values which meet the memory access constraints of said storage means, and means for regenerating unstored positioning values in subsequent machine cycles.
Claim 24
Dependent Claim
46 words
The apparatus of claim 19 wherein said storage means comprises means for storing, during said machine cycle, those of the generated data values which meet the memory access constraints of said storage means, and means for designating unstored data values for storage in subsequent machine cycles.
Claim 25
Dependent Claim
99 words
The apparatus of claim 17 therein a two dimensional grid of possible pixel coordinates is divided into octants so that, for a first one of said octants, the change in pixel coordinates which represents said linear function in the second dimension are greater than or equal to zero but also less than or equal to the change in pixel coordinates which serve as the argument for said linear function in said first dimension, and further comprising means for normalizing the parameters for said linear function so that the pixel coordinates for said function are contained in said first octant.
Claim 26
Dependent Claim
76 words
The apparatus of claim 22 wherein said first octant is divided into a plurality of regions, with the number of regions being equal to the number of pixels which are to be generated during said single machine cycle, and further comprising means for determining, as a function of the sign of one or more of said error terms generated according to Bresenham's algorithm, which of said regions contains the pixel coordinates which represent said linear function.
Claim 27
Dependent Claim
36 words
The apparatus of claim 23 wherein said vector generators are further disposed so that the determination of the positioning values for each said pixel is further a function of said region which contains said pixel coordinates.
Claim 28
Dependent Claim
232 words
Apparatus for generating the x and y coordinates of multiple pixel locations for a parameter defined line to be rasterized during a given single machine cycle of the pixel generating system, wherein the number of said pixels to be generated in said cycle is designated by n and wherein a two dimensional grid of possible pixel coordinates is divided into octants so that, in a first one of said octants, the change in y-coordinate value of said parameter defined line is greater than or equal to zero and also less than or equal to the change in x-coordinate value thereof, said first octant being further divided into n regions, said apparatus comprising: means for normalizing the parameters which define said line so that the pixel coordinates for said line are contained in said first octant; means for generating error terms for the first n pixel locations by applying Bresenham's algorithm to each of n contiguous pixels; and means for generating in parallel, during said single machine cycle, n error terms which correspond to pixel locations other than said first n pixel locations, said means being configured so that a selectable increment is added to each of said error terms for said first n pixel locations, said increment having two possible values with the value selected being determined by the sign of the error term to which said increment is to be added.
Claim 29
Dependent Claim
232 words
Apparatus for generating the x and y coordinates of multiple pixel locations for a parameter defined line to be rasterized during a given single machine cycle of the pixel generating system, wherein the number of said pixels to be generated in said cycle is designated by n and wherein a two dimensional grid of possible pixel coordinates is divided into octants so that, in a first one of said octants, the change in y-coordinate value of said parameter defined line is greater than or equal to zero and also less than or equal to the change in x-coordinate value thereof, said first octant being further divided into n regions, said apparatus comprising: means for normalizing the parameters which define said line so that the pixel coordinates for said line are contained in said first octant; means for generating error terms for the first n pixel locations by applying Bresenham's algorithm to each of n contiguous pixels; and means for generating in parallel, during said single machine cycle, n error terms which correspond to pixel locations other than said first n pixel locations, said means being configured so that a selectable increment is added to each of said error terms for said first n pixel locations, said increment having two possible values with the value selected being determined by the sign of the error term to which said increment is to be added.
Claim 30
Dependent Claim
64 words
The apparatus of claim 25 further comprising means for determining, from the sign of one or more of said error terms for said first n pixel locations, which of said n regions contains the pixel coordinates for said rasterized line, and wherein the two possible values of said increment are determined as a function of said region which contains said rasterized line pixel coordinates.
Claim 31
Dependent Claim
80 words
The apparatus of claim 26 wherein said two possible values of said increment are 2n(dy)-2(r+1) (dx) and 2n(dy)-2(r)(dx), for positive and negative signs, respectively, of the error term to which said increment is to be added, where r designates the region containing the rasterized line, dx designates the difference between the x-coordinate values of the ending and starting points of the line, and dy designates the difference between the y-coordinate values of the ending and starting points of the line.
Claim 32
Dependent Claim
46 words
The apparatus of claim 26 wherein said means for generating error terms in parallel is further configured so that said values of said increment are determined during one or more of the machine cycles used to generate said error terms for said first n pixel locations.
Claim 33
Dependent Claim
51 words
The apparatus of claim 25 further comprising means for translating the signs of the respective error terms into a sequence of binary bits which represent the incremental changes in the y-coordinate of the rasterized line pixel locations, as the rasterized line is traversed from its beginning coordinates to its ending coordinates.
Claim 34
Dependent Claim
63 words
The apparatus of claim 29 wherein said translation means is further configured so that said binary bits are determined, at least in part, as a function of the binary bits previously appearing in said sequence, as a function of the region which contains said rasterized line coordinates, and as a function of the limitations imposed on the sequence of bits for that region.
Claim 35
Dependent Claim
18 words
The apparatus of claim 30 wherein said translation means comprises a combination of cascaded and Boolean logic elements.
Claim 36
Dependent Claim
72 words
The apparatus of claim 25 further comprising means for storing at least some of the rasterized pixel locations generated in a given machine cycle, said storage means having access means and including means for determining which of said generated pixel locations meet the access rules of said storage means during said machine cycle and means for regenerating in subsequent machine cycles those pixels which were not storable in said given machine cycle.
Claim 37
Dependent Claim
74 words
The apparatus of claim 25 further comprising means for storing at least some of the rasterized pixel locations generated in a given machine cycle, said storage means including means having access rules and for determining which of said generated pixel locations meet the access rules of said storage means during said machine cycle and means for designating for storage in subsequent machine cycles those pixels which were not storable in said given machine cycle.
References Cited (Backward Citations)
US4626838A
Cited
US4623880A
Cited
US4586037A
Cited
US4736330A
Cited
US4742343A
Cited
US4736201A
Cited
US4737921A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-10-30 | 1993-05-01 | 1993-10-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-10-30 | 1997-05-01 | 1997-10-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-10-30 | 2001-05-01 | 2001-10-31 | $7700.00 | Window Closed / Lapsed |