Computer graphics processing and selective visual display system – Display peripheral interface input device – Light pen for fluid matrix display panel
Reexamination Certificate
1998-03-10
2001-12-11
Luu, Matthew (Department: 2779)
Computer graphics processing and selective visual display system
Display peripheral interface input device
Light pen for fluid matrix display panel
C345S443000, C345S440000
Reexamination Certificate
active
06329977
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer graphics, and more particularly to a method and apparatus for reducing aliasing artifacts in images defined by pixels.
BACKGROUND
Pixel-based graphics systems define images on a display device by a two-dimensional, rectangular array of pixels. The discrete nature and finite number of such pixels can lead to visual artifacts such as jagged or staircase edges. These aliasing effects worsen for animated images where the jagged edges turn into crawling artifacts. Aliasing artifacts can occur when an entire pixel is given an intensity or color based upon an insufficient sample of points within that pixel, such as, for example, when a pixel is given either full intensity or no intensity, depending upon whether the image covers the center of the pixel.
To lessen or eliminate such jagged or crawling artifacts, the intensity of a pixel should not depend entirely upon whether the image covers a single point in the pixel. Accordingly, a variety of antialiasing techniques base the intensity of a pixel on more than that pixel's center. One such technique uses filters. Filters determine the intensity of each pixel by averaging data from a small area around that pixel. The width of the filter determines the area around the pixel that is included within the averaging, and a filter function is a weighting function applied to the averaging. For example, a box filter gives equal weight to the entire area covered by the filter. More sophisticated filter functions, such as a conical function, for example, give more weight to the area near the center of a pixel than to the area farther away. In practice, such sophisticated filters have better high-frequency rejection than box filters and consequently produce better antialiased images.
A problem, however, is that determining the pixel area covered by a sophisticated filter function and performing the weighted averaging can be computationally expensive. This is especially true if this filtering must be performed using multiple sample points within or near a pixel each time the pixel is written. One pre-filtering technique, described by Satish Gupta and Robert F. Sproull in “Filtering Edges for Gray-Scale Displays”,
Proceedings of SIGGRAPH
81, pp. 1-5, 1981, attempts to mitigate the problem by using a table to store pre-computed intensity values. The technique uses the table to map distances of pixels from the center of the line to be antialiased into pixel intensities.
Properly antialiasing the endpoints of a line, however, has traditionally been a problem for such pre-filtering techniques. In order to determine intensities for pixels at the endpoints, the technique described by Gupta et al., for example, must compute the slope of the line to produce an index into a table that maps slopes into pixel intensities. As a result, special operations are required at the start and end of each line. Moreover, the table works only for lines with endpoints that have integer coordinates, and the size of the table would become impracticable for line endpoints that are specified with multiple bits of sub-pixel precision. Thus, some filtering implementations simply ignore the endpoints—but then the endpoints become sharply cut off and remain aliased.
As a result, there remains a need for a method and computer system that can effectively antialias lines, including the endpoints, without being computationally expensive.
SUMMARY OF THE INVENTION
In accordance to the present invention, one objective is to minimize aliasing artifacts in images using improved pre-filtering techniques. More specifically, an objective is to provide pre-filtering techniques that can effectively minimize aliasing artifacts for lines, including their endpoints, by using distance functions to produce intensity values for pixels near the lines and at their endpoints. Other objectives are for these distance functions to be independent of the slopes of the lines to be antialiased and to be useful for a range of line width to filter radius ratios. Yet another objective is to map the distance values produced by distance functions into intensity value approximations that demonstrate high-frequency filtering.
The present invention relates to a method and a computer system for reducing aliasing artifacts when rendering an image on a pixel-based display device. In terms of the method, a plurality of edges are placed near the image, a pixel in the image is selected, and the distance of the pixel from each edge is determined. Based on these distances, an intensity value is determined for the pixel.
In one aspect of the method, each edge is represented by a distance function. An edge function is multiplied by a scale factor to produce a distance function. The scale factor is the reciprocal of the Euclidean length of the line times a factor that is dependent upon the width of the line and the filter radius. The distance function is evaluated to determine the distance of the pixel from each edge. Pixels on or beyond the edges are given a minimum intensity value; pixels inside all the edges are given intensity values corresponding to their distances from the edges. In another aspect of the method, an intensity function is developed to characterize a relationship between pixel distances from the edges and their corresponding intensity values. The intensity function can be implemented in a look-up table or approximated with hardware.
In terms of the computer system, an embodiment of the invention includes means for placing edges near the image. The edges together define boundaries that surround the image. The embodiment has means for selecting a pixel in the image, means for determining, for each edge, a distance value representing a distance of the pixel from that edge, and means for determining an intensity value for the pixel based upon the determined distance values. The determined intensity value improves the perceived quality of the image by reducing aliasing artifacts when the pixel is intensified according to that intensity value.
In one aspect of the computer system, the embodiment includes means for determining an overall distance value from the distance values, and means for determining the intensity value from the overall distance value. In another aspect, the system includes 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.
In still another aspect of the embodiment, the image is a line. Two of the edges surrounding the image are perpendicular to the line and two of the edges are parallel to the line. The system includes means for determining a minimum of the distance values for the perpendicular edges, means for determining a minimum of the distance values for the parallel edges, 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 compute the intensity value for the pixel.
REFERENCES:
patent: 4808984 (1989-02-01), Trueblood et al.
patent: 4873515 (1989-10-01), Dickson et al.
patent: 5206628 (1993-04-01), Kelleher
patent: 5243695 (1993-09-01), Russell et al.
patent: 5253335 (1993-10-01), Yoshiyuki et al.
patent: 5559529 (1996-09-01), Maher
Feibush et al., “Synthetic Texturing Using Digital Filters”, Cornell University, 1980.*
Pineda, Juan, “A Parallel Algorithm for Polygon Rasterization,” Apollo Computer Inc., 1988, ACM #0-89791-275-6/88/008/0017.
Gupta et al., “Filtering Edges for Gray-Scale Displays,” Carnegie-Mellon University, 1981, ACM #0-8971-045-1/81-0800-0001.
Claffey James T.
Jouppi Norman P.
Knittel James M.
McCormack Joel J.
McNamara Robert S.
Compaq Computer Corporation
Harrison Chante′
Luu Matthew
McRoss Loren H.
Oppenheimer Wolff & Donnelly
LandOfFree
Pre-filtered antialiased lines using distance functions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pre-filtered antialiased lines using distance functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pre-filtered antialiased lines using distance functions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2583782