US5333250A — Method and apparatus for drawing antialiased line…

Claim 1

Independent Claim 189 words

In a graphics system in which a two-dimensional pixel image is generated for display by a raster-scan device, a method of generating intensity values for an antialiased pixel approximation of a line segment extending between a first point and a second point spaced from each other along major and minor coordinate axes, said method comprising the steps of: generating integer valued Bresenham parameters including a positive correction, a negative correction, and an initial determinant; iteratively generating a new value of the determinant for each pixel along said line segment as a function of the previous value of the determinant and the positive and negative corrections; generating an intensity value for said pixel along said line segment as a function of the value of the determinant generated for said pixel by performing the following steps:; generating a plurality of comparison values ranging between zero and a predetermined multiple of the spacing of said points along said major axis; comparing the value of the determinant generated for a pixel along said segment with each of said comparison values; and generating said intensity value in accordance with the results of said comparisons.

Claim 2

Dependent Claim 189 words

In a graphics system in which a two-dimensional pixel image is generated for display by a raster-scan device, a method of generating intensity values for an antialiased pixel approximation of a line segment extending between a first point and a second point spaced from each other along major and minor coordinate axes, said method comprising the steps of: generating integer valued Bresenham parameters including a positive correction, a negative correction, and an initial determinant; iteratively generating a new value of the determinant for each pixel along said line segment as a function of the previous value of the determinant and the positive and negative corrections; generating an intensity value for said pixel along said line segment as a function of the value of the determinant generated for said pixel by performing the following steps:; generating a plurality of comparison values ranging between zero and a predetermined multiple of the spacing of said points along said major axis; comparing the value of the determinant generated for a pixel along said segment with each of said comparison values; and generating said intensity value in accordance with the results of said comparisons.

Claim 3

Dependent Claim 62 words

A method as in claim 1 in which said Bresenham parameters are generated in accordance with the equations Pc=2A Nc=2A-2B Di=2A-B where Pc is the positive correction, Nc is the negative correction, Di is the initial determinant, A is the spacing of said points along said minor coordinate axis, and B is the spacing of said points along said major coordinate axis.

Claim 4

Dependent Claim 48 words

A method as in claim 2 in which the new value of said determinant Di is generated by incrementing the previous value Di by the negative correction Nc if the previous value Di is positive and by the positive correction Pc if the previous value Di is negative.

Claim 5

Dependent Claim 29 words

A method as in claim 3 in which the value of the determinant generated for a pixel along said segment is compared with each of said comparison values simultaneously.

Claim 6

Dependent Claim 32 words

A method as in claim 3 in which said comparison values range in absolute value between zero and 2B, where B is the spacing of said points along said major coordinate axis.

Claim 7

Dependent Claim 75 words

A method as in claim 3 in which intensity values are generated for pixels on one side of said line segment on a first iteration along said line segment and for pixels on the other side of said line segment on a second iteration along said line segment, each of said intensity values being generated in accordance with the results of said comparisons and in accordance with a signal indicating the first or second iteration.

Claim 8

Dependent Claim 86 words

A method as in claim 3 in which intensity values are generated for pixels on one side of said line segment on a first iteration along said line segment and for pixels on the other side of said line segment on a second iteration along said line segment, each of said intensity values being generated in accordance with the results of said comparisons and in accordance with a first signal indicating the first or second iteration and a second signal indicating the sign of the determinant.

Claim 9

Dependent Claim 40 words

A method as in claim 1 in which said graphics system includes a frame buffer for storing intensity values for each of said pixels, said method comprising the further step of storing said generated intensity values in said frame buffer.

Claim 10

Dependent Claim 30 words

A method as in claim 1 comprising the further step of providing said generated intensity values to said raster scan device to display said pixel approximation of said line segment.

Claim 11

Dependent Claim 185 words

In a graphics system in which a two-dimensional pixel image is generated for display by a raster-scan device, apparatus for generating intensity values for an antialiased pixel approximation of a line segment extending between a first point and a second point spaced from each other along major and minor coordinate axes, said apparatus comprising: means for generating integer valued Bresenham parameters including a positive correction, a negative correction, and an initial determinant; means for generating a new value of the determinant for each pixel along said line segment as a function of the previous value of the determinant and the positive and negative corrections; and means for generating an intensity value for said pixel along said line segment as a function of the new value of the determinant wherein said means for generating an intensity value includes: means for generating a plurality of comparison values of said determinant; means for comparing the value of the determinant generated for a pixel along said segment with each of said values of said determinant; means for generating said intensity values in accordance with the results of said comparisons.

Claim 12

Dependent Claim 185 words

In a graphics system in which a two-dimensional pixel image is generated for display by a raster-scan device, apparatus for generating intensity values for an antialiased pixel approximation of a line segment extending between a first point and a second point spaced from each other along major and minor coordinate axes, said apparatus comprising: means for generating integer valued Bresenham parameters including a positive correction, a negative correction, and an initial determinant; means for generating a new value of the determinant for each pixel along said line segment as a function of the previous value of the determinant and the positive and negative corrections; and means for generating an intensity value for said pixel along said line segment as a function of the new value of the determinant wherein said means for generating an intensity value includes: means for generating a plurality of comparison values of said determinant; means for comparing the value of the determinant generated for a pixel along said segment with each of said values of said determinant; means for generating said intensity values in accordance with the results of said comparisons.

Claim 13

Dependent Claim 61 words

Apparatus as in claim 10 in which said Bresenham parameters are generated in accordance with the equations Pc=2a Nc=2A=2b Di=2A-B where Pc is the positive correction, Nc is the negative correction, Di is the initial determinant, A is the spacing of said points along said minor coordinate axis, and B is the spacing of said points along said major coordinate axis.

Claim 14

Dependent Claim 47 words

Apparatus as in claim 11 in which the new value of said determinant Di is generated by incrementing the previous value Di by the negative correction Nc if the previous value Di is positive and by the positive correction Pc if the previous value Di is negative.

Claim 15

Dependent Claim 36 words

Apparatus as in claim 12 in which said comparing means comprises a plurality of comparators for simultaneously comparing the determinant generated for a pixel along said segment with each of said stored values of said determinant.

Claim 16

Dependent Claim 31 words

Apparatus as in claim 12 in which said comparison values range in absolute value between zero and 2B, where B is the spacing of said points along said major coordinate axis.

Claim 17

Dependent Claim 74 words

Apparatus as in claim 12 in which intensity values are generated for pixels on one side of said line segment on a first iteration along said line segment and for pixels on the other side of said line segment on a second iteration along said line segment, each of said intensity values being generated in accordance with the results of said comparisons and in accordance with a signal indicating the first or second iteration.

Claim 18

Dependent Claim 85 words

Apparatus as in claim 12 in which intensity values are generated for pixels on one side of said line segment on a first iteration along said line segment and for pixels on the other side of said line segment on a second iteration along said line segment, each of said intensity values being generated in accordance with the results of said comparisons and in accordance with a first signal indicating the first or second iteration and a second signal indicating the sign of the determinant.

Claim 19

Dependent Claim 38 words

Apparatus as in claim 10 in which said graphics system includes a frame buffer for storing intensity values for each of said pixels, said apparatus further comprising means for storing said generating intensity values in said frame buffer.

Claim 20

Dependent Claim 28 words

Apparatus as in claim 10 further comprising means for providing said generated intensity values to said raster scan device to display said pixel approximation of said line segment.

Claim 21

Dependent Claim 175 words

In a graphics system in which a two-dimensional pixel image is generated for display by a raster-scan device, a method of generating pixel positions for an antialiased pixel approximation of a line segment extending between a first point and a second point spaced from each other along minor and major coordinate axes, said method comprising the steps of: generating integer valued Bresenham parameters including a positive correction, a negative correction, and an initial determinant; iteratively generating a new value of the determinant for each pixel along said line segment as a function of the previous value of the determinant and the positive and negative corrections; and generating a pixel position for said pixel along said line segment as a function of the value of the determinant generated for said pixel wherein pixel positions for pixels on one side of said line segment are generated on a first performance of the method steps above and for pixels on the other side of said line segment are generated on a second performance of the method steps above.

Claim 22

Dependent Claim 175 words

In a graphics system in which a two-dimensional pixel image is generated for display by a raster-scan device, a method of generating pixel positions for an antialiased pixel approximation of a line segment extending between a first point and a second point spaced from each other along minor and major coordinate axes, said method comprising the steps of: generating integer valued Bresenham parameters including a positive correction, a negative correction, and an initial determinant; iteratively generating a new value of the determinant for each pixel along said line segment as a function of the previous value of the determinant and the positive and negative corrections; and generating a pixel position for said pixel along said line segment as a function of the value of the determinant generated for said pixel wherein pixel positions for pixels on one side of said line segment are generated on a first performance of the method steps above and for pixels on the other side of said line segment are generated on a second performance of the method steps above.

Claim 23

Dependent Claim 85 words

A method as in claim 19 in which said Bresenham parameters are generated in accordance with the equations Pc=A Nc=De=A-B on the first performance of the steps and in accordance with the equations Pc=B-A Nc=Di=-A on the in the second performance of the steps, where Pc is the positive correction, Nc is the negative correction, Di is the initial determinant, A is the spacing of said points along said minor coordinate axis, and B is the spacing of said points along said major coordinate axis.

Claim 24

Dependent Claim 46 words

A method as in claim 19 in which said new value of said determinant is generated by incrementing the previous value by the positive correction if the current value is less than zero and by the negative correction if the current value is greater than zero.

Claim 25

Dependent Claim 45 words

A method as in claim 19 in which said pixel position is generated by moving along the major axis if the current value of the determinant is less than zero and by moving diagonally if the current value of the determinant is greater than zero.

Claim 26

Dependent Claim 181 words

In a graphics system in which a two-dimensional pixel image is generated for display by a raster-scan device, apparatus for generating pixel positions for an antialiased pixel approximation of a line segment extending between a first point and a second point spaced from each other along minor and major coordinate axes, said apparatus comprising: means for generating integer valued Bresenham parameters including a positive correction, a negative correction, and an initial determinant; means for iteratively generating a new value of the determinant for each pixel along said line segment as a function of the previous value of the determinant and the positive and negative corrections; and means for generating a pixel position for said pixel along said line segment as a function of the value of the determinant generated by said pixel wherein the pixel positions are generated for pixels on one side of said line segment by first using said apparatus with a first Bresenham parameter set and for pixels on the other side of said line segment by repeating use of said apparatus with a second Bresenham parameter set.

Claim 27

Dependent Claim 181 words

In a graphics system in which a two-dimensional pixel image is generated for display by a raster-scan device, apparatus for generating pixel positions for an antialiased pixel approximation of a line segment extending between a first point and a second point spaced from each other along minor and major coordinate axes, said apparatus comprising: means for generating integer valued Bresenham parameters including a positive correction, a negative correction, and an initial determinant; means for iteratively generating a new value of the determinant for each pixel along said line segment as a function of the previous value of the determinant and the positive and negative corrections; and means for generating a pixel position for said pixel along said line segment as a function of the value of the determinant generated by said pixel wherein the pixel positions are generated for pixels on one side of said line segment by first using said apparatus with a first Bresenham parameter set and for pixels on the other side of said line segment by repeating use of said apparatus with a second Bresenham parameter set.

Claim 28

Dependent Claim 77 words

Apparatus as in claim 23 in which said first Bresenham parameter set is generated in accordance with the equations Pc=A Nc=Di=A-B and said second Bresenham parameter set is generated in accordance with the equations Pc=B-A Nc=Di=-A where Pc is the positive correction, Nc is the negative correction, Di is the initial determinant, A is the spacing of said points along said minor coordinate axis, and B is the spacing of said points along said major coordinate axis.

Claim 29

Dependent Claim 45 words

Apparatus as in claim 23 in which said new value of said determinant is generated by incrementing the previous value by tile positive correction if the current value is less than zero and by the negative correction if the current value is greater than zero.

Claim 30

Dependent Claim 44 words

Apparatus as in claim 23 in which said pixel position is generated by moving along the major axis if the current value of the determinant is less than zero and by moving diagonally if the current value of the determinant is greater than zero.

Claim 31

Dependent Claim 86 words

Apparatus as in claim 23, further comprising: second means for generating integral Bresenham parameters including a positive correction, a negative correction, and an initial determinant; second means for generating a new value of the determinant for each pixel along said segment as a function of the previous value of the determinant and the positive and negative corrections; and means for generating an intensity value for each pixel along said segment as a function of the new value of the determinant generated by said second determinant-generating means.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1997-07-25	1998-01-24	1998-07-26	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2001-07-25	2002-01-24	2002-07-26	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2005-07-25	2006-01-24	2006-07-26	$7700.00	Window Closed / Lapsed

Method and apparatus for drawing antialiased lines on a raster display

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag