Patent US6329977B1 successfully refreshed from Google Patents.
US6329977B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pre-filtered antialiased lines using distance functions
Assignee: Hewlett Packard Development Co LP
•
Filing: 1998-03-10
•
Granted: 2001-12-11
•
Expires: 2018-03-10
Abstract
Abstract A computer graphics system renders an image on a display device using improved pre-filtering techniques that minimize aliasing artifacts in the image, particularly at the endpoints of lines. To anti-alias the image, a plurality of edges are placed near a line in the image. An edge function represents the edge. This edge function is multiplied by a scale factor to produce a distance function. This scale factor is the reciprocal of the Euclidean length of the line. The distance function is evaluated to determine the distance of selected pixels from each edge in units of pixels. These distances determine the intensity value for each selected pixel. Pixels on or beyond an edge, with respect to the line, are given a minimum intensity value; pixels inside all edges are given intensity values corresponding to their distances from the edge. An intensity function describing a relationship between pixel distances from the edges and their corresponding intensity values is developed. The intensity function can be implemented in a look-up table or approximated with hardware.
Inventors
- 👤 Robert S. McNamara
- 👤 Joel J. McCormack
- 👤 Norman P. Jouppi
- 👤 James T. Claffey
- 👤 James M. Knittel
- 👤 Larry D. Seiler
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:51
CPC Classifications
G; G09; G09G; G09G5/00; G09G5/20; G06; G06T; G06T11/00; G06T11/20; G06T11/23
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
114 words
A computerized method for rendering an image defined by pixels, comprising the steps of: placing a mask a predetermined distance outside of a line of the image, the mask including a plurality of edges which bound the line, each of the plurality of edges being defined by distance evaluators; selecting a pixel within the mask; determining a distance value representing a distance of the selected pixel from a corresponding edge of the mask; and determining an intensity value for the selected pixel based upon the distance value, the determined intensity value improving the perceived quality of the images by reducing aliasing artifacts when the selected pixel is intensified according to the determined intensity value.
Claim 2
Dependent Claim
114 words
A computerized method for rendering an image defined by pixels, comprising the steps of: placing a mask a predetermined distance outside of a line of the image, the mask including a plurality of edges which bound the line, each of the plurality of edges being defined by distance evaluators; selecting a pixel within the mask; determining a distance value representing a distance of the selected pixel from a corresponding edge of the mask; and determining an intensity value for the selected pixel based upon the distance value, the determined intensity value improving the perceived quality of the images by reducing aliasing artifacts when the selected pixel is intensified according to the determined intensity value.
Claim 3
Dependent Claim
45 words
The method of claim 1 , further comprising the step of: determining a distance from the image at which pixels are to be given a minimum intensity value; and wherein the corresponding edge of the mask is spaced apart from the image by that distance.
Claim 4
Dependent Claim
52 words
The method of claim 2 wherein the step of determining the distance by which the edge of the mask is spaced apart from the image includes the step of: determining a smallest distance from the image at which a placement of a filter produces an intersection volume of zero with the image.
Claim 5
Dependent Claim
26 words
The method of claim 3 wherein the filter is circular and symmetrical in shape and the smallest distance is equal to a radius of the filter.
Claim 6
Dependent Claim
23 words
The method of claim 1 wherein the image includes a line, and the edge of the mask is placed parallel to the line.
Claim 7
Dependent Claim
23 words
The method of claim 1 wherein the image includes a line, and the edge of the mask is placed perpendicular to the line.
Claim 8
Dependent Claim
32 words
The method of claim 1 , further comprising the step of: developing an intensity function that characterizes a relationship between intensity values and distances of pixels from the edge of the mask.
Claim 9
Dependent Claim
64 words
The method of claim 7 , further comprising the step of: implementing the intensity function as a table that maps distances of pixels from the edge of the mask to intensity values, the table including entries, each entry storing one of the intensity values, the table using distances of pixels form the edge of the mask as a index to the stored intensity values.
Claim 10
Dependent Claim
22 words
The method of claim 7 , further comprising the step of: implementing a piece-wise linear approximation of the intensity function using hardware.
Claim 11
Dependent Claim
37 words
The method of claim 1 , further comprising the steps of: representing the edge by an edge function; and evaluating the edge function for the pixel to compute the distance value of the pixel from the edge.
Claim 12
Dependent Claim
66 words
The method of claim 1 , further comprising the steps of: representing the edge of the mask by an edge function; multiplying the edge function by a scale factor to produce a distance function that represents the edge of the mask; and evaluating the distance function for the pixel to determine the distance of the pixel from the edge of the mask in units of pixels.
Claim 13
Dependent Claim
25 words
The method of claim 11 , wherein the image includes a line, and the scale factor is the reciprocal of the length of the line.
Claim 14
Dependent Claim
44 words
The method of claim 11 , further comprising the steps of: normalizing the distance determined by the distance function so that a normalized distance of 1 represents a Euclidean distance over which intensity values given to pixels range from 0 to a maximum value.
Claim 15
Dependent Claim
24 words
The method of claim 13 , wherein the normalized distance is based upon a width of the line and a width of a filter.
Claim 16
Dependent Claim
114 words
A computerized method for rendering an image defined by pixels, comprising the steps of: placing a mask near a line of the image, the mask including a plurality of edges defined by distance functions, the edges together defining boundaries that surround the image; selecting a pixel within the mask; determining for each edge of the mask, a distance value representing a distance of the selected pixel from a corresponding edge of the mask; and determining an intensity value for the selected pixel based upon the determined distance values, the determined intensity value improving the perceived quality of the image by reducing aliasing artifacts when the selected pixel is intensified according to that intensity value.
Claim 17
Dependent Claim
114 words
A computerized method for rendering an image defined by pixels, comprising the steps of: placing a mask near a line of the image, the mask including a plurality of edges defined by distance functions, the edges together defining boundaries that surround the image; selecting a pixel within the mask; determining for each edge of the mask, a distance value representing a distance of the selected pixel from a corresponding edge of the mask; and determining an intensity value for the selected pixel based upon the determined distance values, the determined intensity value improving the perceived quality of the image by reducing aliasing artifacts when the selected pixel is intensified according to that intensity value.
Claim 18
Dependent Claim
36 words
The method of claim 15 , further comprising the steps of: determining an overall distance value from the determined distance values; and using the overall distance value to determine the intensity value for the selected pixel.
Claim 19
Dependent Claim
27 words
The method of claim 16 wherein the step of computing the overall distance value includes equating the overall distance value to a minimum of the distance values.
Claim 20
Dependent Claim
27 words
The method of claim 16 wherein the step of computing the overall distance value includes equating the overall distance value to a product of the distance values.
Claim 21
Dependent Claim
84 words
The method of claim 16 , wherein the image is a line, two of the edges of the mask are perpendicular to the line and two of the edges of the mask are parallel to the line, and the step of computing the overall distance value includes calculating the overall distance value to a product of a minimum of the distance values for the perpendicular edges of the mask multiplied by a minimum of the distance values for the parallel edges of the mask.
Claim 22
Dependent Claim
36 words
The method of claim 15 , further comprising the steps of: determining an intensity value for each distance value; and combining the intensity values for the distance values to produce the intensity value for the pixel.
Claim 23
Dependent Claim
24 words
The method of claim 20 wherein the intensity value for the pixel is a product of the intensity values determined for the distance values.
Claim 24
Dependent Claim
99 words
The method of claim 15 , wherein the image is a line, two of the edges of the mask are perpendicular to the line and two of the edges of the mask are parallel to the line, and further comprising the steps of: determining a minimum of the distance values for the perpendicular edges of the mask; determining a minimum of the distance values for the parallel edges of the line; determining an intensity value for each minimum distance value; and multiplying the intensity values determined for the minimum distance values to compute the intensity value for the pixel.
Claim 25
Dependent Claim
24 words
The method of claim 15 wherein the distance values are used to index a multidimensional table to produce the intensity value for the pixel.
Claim 26
Dependent Claim
85 words
The method of claim 15 wherein the image is a line and two of the edges of the mask are perpendicular to the line and two of the edges of the mask are parallel to the line, and further comprising the steps of: determining a minimum of the distance values of the parallel edges; determining a minimum of the distance values of the perpendicular edges; and using the determined minimum distance values to index a two-dimensional table to determine the intensity value for the pixel.
Claim 27
Dependent Claim
64 words
The method of claim 15 wherein the image is a line with an end and a beginning, and the step of selecting selects the pixel from near the end of the line, and further comprising the step of: selecting subsequent pixels for processing such that the line is traversed in a direction that generally proceeds from the end of the line to the beginning.
Claim 28
Dependent Claim
120 words
A computer system for rendering an image defined by pixels, comprising: means for placing a mask a distance outside of the line of the image, the mask including a plurality of edges defined by distance evaluators, the edges together defining boundaries that surround the image; means for selecting a pixel within the mask; means for determining, for each edge of the mask, a distance value representing a distance of the pixel from that corresponding edge of the mask; and means for determining an intensity value for the pixel based upon the determined distance values, the determined intensity value improving the perceived quality of the image by reducing aliasing artifacts when the pixel is intensified according to the determined intensity value.
Claim 29
Dependent Claim
120 words
A computer system for rendering an image defined by pixels, comprising: means for placing a mask a distance outside of the line of the image, the mask including a plurality of edges defined by distance evaluators, the edges together defining boundaries that surround the image; means for selecting a pixel within the mask; means for determining, for each edge of the mask, a distance value representing a distance of the pixel from that corresponding edge of the mask; and means for determining an intensity value for the pixel based upon the determined distance values, the determined intensity value improving the perceived quality of the image by reducing aliasing artifacts when the pixel is intensified according to the determined intensity value.
Claim 30
Dependent Claim
32 words
The system of claim 26 , further comprising: means for determining an overall distance value from the determined distance values; and means for determining the intensity value from the overall distance value.
Claim 31
Dependent Claim
37 words
The system of claim 26 , further comprising: means for determining an intensity value for each distance value; and means for combining the intensity values for each distance value to produce the intensity value for the pixel.
Claim 32
Dependent Claim
104 words
The system of claim 26 , wherein the image is a line, two of the edges of the mask are perpendicular to the line and two of the edges of the mask are parallel to the line, and further comprising: means for determining a minimum of the distance values for the perpendicular edges of the mask; means for determining a minimum of the distance values for the parallel edges of the mask; means for determining an intensity value for each minimum distance value; and means for multiplying the intensity values determined for the minimum distance values to computer the intensity value for the pixel.
Claim 33
Dependent Claim
35 words
The system of claim 26 , further comprising: a multidimensional table for storing intensity values; and wherein the distance values are used to index the multidimensional table to produce the intensity value for the pixel.
Claim 34
Dependent Claim
102 words
The system of claim 26 wherein the image is a line and two of the edges of the mask are perpendicular to the line and two of the edges of the mask are parallel to the line, and further comprising: a two-dimensional table for storing intensity values for pixels; means for determining a minimum of the distance values of the parallel edge of the mask; and means for determining a minimum of the distance values of the perpendicular edges of the mask, the determined minimum distance values being used to index the two-dimensional table to determine the intensity value for the pixel.
Claim 35
Dependent Claim
132 words
A computerized method for rendering an image defined by pixels, comprising: placing a mask a predetermined distance outside of a line of the image, the mask including a plurality of edges defining a distance evaluator which bound the line; initializing the distance evaluators such that each distance evaluator computes the minimum distance between a corresponding edge of the mask and a pixel about the line; selecting a pixel within the mask; determining the value of the distance evaluators at the selected pixel; and determining an intensity value for the selected pixel based upon the determined distances between the edge of the mask and the pixel, the determined intensity value improving the perceived quality of the image by reducing aliasing artifacts when the selected pixel is intensified according to the corresponding intensity value.
Claim 36
Dependent Claim
132 words
A computerized method for rendering an image defined by pixels, comprising: placing a mask a predetermined distance outside of a line of the image, the mask including a plurality of edges defining a distance evaluator which bound the line; initializing the distance evaluators such that each distance evaluator computes the minimum distance between a corresponding edge of the mask and a pixel about the line; selecting a pixel within the mask; determining the value of the distance evaluators at the selected pixel; and determining an intensity value for the selected pixel based upon the determined distances between the edge of the mask and the pixel, the determined intensity value improving the perceived quality of the image by reducing aliasing artifacts when the selected pixel is intensified according to the corresponding intensity value.
Claim 37
Dependent Claim
27 words
The method of claim 32 , further including the step of combining one or more of the determined distances before the step of determining the intensity value.
Claim 38
Dependent Claim
41 words
The method of claim 33 , wherein combining the determined distances results in a determination of an overall distance value, and the method includes the step of using the overall distance value to determine the intensity value for the selected pixel.
Claim 39
Dependent Claim
25 words
The method of claim 34 wherein computing the overall distance value includes equating the overall distance value to a minimum of the determined distance values.
Claim 40
Dependent Claim
25 words
The method of claim 34 wherein computing the overall distance value includes equating the overall distance value to a product of the determined distance values.
Claim 41
Dependent Claim
87 words
The method of claim 33 , wherein the image is a line, two of the edges or the mask that bound the line are perpendicular to the line and the remaining two edges are parallel to the line, and the step of computing the overall distance value includes calculating the overall distance value to a product of a minimum of the determined distance values for the perpendicular edges of the mask multiplied by a minimum of the determined distance values for the parallel edges of the mask.
Claim 42
Dependent Claim
33 words
The method of claim 33 , further comprising determining an intensity value for each distance value; and combining the intensity values for the distance values to produce the intensity value for the pixel.
Claim 43
Dependent Claim
26 words
The method of claim 33 , wherein the distance values are used to index a multi-dimensional table to produce the intensity value for each selected pixel.
Claim 44
Dependent Claim
91 words
The method of claim 33 , wherein the image is a line, two of the edges of the mask are perpendicular to the line and the remaining edges of the mask are parallel to the line, and further comprising: determining a minimum of the distance values for the perpendicular edges of the mask; determining a minimum of the distance values for the parallel edges of the mask; determining an intensity value for each minimum distance value; and multiplying the determined intensity values to compute the intensity value for the selected pixel.
References Cited (Backward Citations)
US4808984A
Cited
US4873515A
Cited
US5253335A
Cited
US5206628A
Cited
US5243695A
Cited
US5559529A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-12-10 | 2005-06-11 | 2005-12-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-12-10 | 2009-06-11 | 2009-12-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-12-10 | 2013-06-11 | 2013-12-11 | $7700.00 | Window Closed / Lapsed |