Facsimile and static presentation processing – Static presentation processing
Reexamination Certificate
1999-07-30
2004-03-02
Williams, Kimberly (Department: 2626)
Facsimile and static presentation processing
Static presentation processing
C382S269000, C382S279000, C358S003260, C358S003270, C345S611000
Reexamination Certificate
active
06700672
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to image processing, and more particularly to removing aliasing effects that occur when sampling a continuous image.
BACKGROUND OF THE INVENTION
There are a wide variety of computer applications which generate images. These applications include games, graphic design, animation, simulation, visualization, modeling, and the like. In these applications, the generated images should be as realistic as possible.
In computer graphics, a generated image is represented as a regular array of discrete samples of a continuous image. This “discrete image” is a result of sampling the continuous image at some fixed and finite rate. The individual sample points are referred to as pixels. It is critical to remember that a pixel is a sampling point, not a rectangular area in the discrete image.
Because the sampling rate is finite, high frequencies present in the continuous image can “alias” as incorrect low frequencies. Some common features in continuous images, such as edges, contain infinitely high frequencies, so any finite sampling rate will invariably lead to aliasing. In computer-generated images, the aliasing appears as stair-stepped contours of image objects, i.e., so called “jaggies.” Other aliasing effects can cause moire patterns and the break-up of fine details.
Anti-aliasing is used to improve the appearance of discrete images. Anti-aliasing is accomplished by computing and sampling a convolution of the continuous image with some frequency-limiting filter. The pixels are samples of the filtered version of the continuous image. There are two common methods used to compute the samples of this convolution in the prior art: area sampling and point sampling.
Area Sampling Anti-aliasing
Area sampling anti-aliasing uses a processed but still continuous form of the continuous image to exactly compute the convolution of an anti-aliasing filter function and this continuous image. This convolution is sampled to produce a value to be used while determining a pixel in the discrete image. Typically, the filter function is a Gaussian filter having a radius R. The radius defines the “footprint” or “support” of the filter.
The processed form of the continuous image used by area sampling is usually a set of polygons visible in the filter footprint around each pixel. Unfortunately, in many cases the continuous image is defined by a three-dimensional scene description including geometric objects which can occlude or intersect one another. These occlusions and intersections make it difficult to efficiently process the continuous image into a form suitable for area sampling because complicated shapes can result from the interaction of even simple objects.
Point Sampling Anti-aliasing
Point sampling anti-aliasing uses multiple point sample locations in the vicinity of a pixel. The continuous image is evaluated at points corresponding to the pixel locations, and the resulting values are combined according to some weighting function in an attempt to approximate the convolution of the filter with the continuous image. Point sampling is the most common method used for anti-aliasing because of its simplicity and ease of implementation. Point sampling simplifies the occlusion problem present in area sampling of three-dimensional scenes, but suffers from slow convergence to the correct solution.
In general, N point samples are required to compute the value of a pixel with an accuracy of 1/N. Because the point sample locations are separated from each other and not connected, fine details can be missed entirely in the sampling. Consequently, the missed details fail to contribute to the discrete image.
Combined Point and Area Sampling
Area and point sampling methods are often combined in rendering systems. Area sampling can be applied efficiently to two-dimensional sampled images, such as texture maps, while point sampling is generally used to anti-alias the edges and intersections of polygons. Point sampling is used to generate weighted coverage values (WCVs) for polygons that lie within the filter footprint of some pixel, which are then associated with that pixel. A WCV is the result of the convolution of the visible portion of a polygon with the anti-aliasing filter at a pixel that weights the color contribution of that polygon to the color of that pixel. An area sampling method is used to produce colors for the polygons, which are also associated with that pixel. The WCVs and colors associated with that pixel are then combined to produce the final color for the pixel in the discrete image.
Other Anti-aliasing Method
Max, in “Anti-aliasing Scan-Line Data,” IEEE Computer Graphics & Applications, 10(1): 18-30, January 1990, describes a hybrid method. His hybrid method provides continuous anti-aliasing in one direction, by approximating area sampling, while using supersampling to anti-alias the other direction. Edges that run substantially parallel to the continuous direction are anti-aliased less effectively than edges that are substantially perpendicular to the continuous direction.
Accordingly, there are numerous drawbacks and disadvantages of prior art area and point sampling anti-aliasing methods. Therefore, there is a need to provide an improved anti-aliasing method without a large increase in memory or a decrease in drawing speed while generating discrete images.
SUMMARY OF THE INVENTION
The invention provides a method that uses a filter function to generate an anti-aliased discrete image sampled from a continuous image including an edge. The method defines a line sample. A progressive convolution is derived from the filter function and the line sample. A pixel at a predetermined location in the discrete image is selected, and the line sample is oriented with respect to the selected pixel.
A distance is measured from a point in the continuous image corresponding to the selected pixel to the edge along the oriented line sample. The progressive convolution is evaluated at the measured distance to produce a weighted coverage value, and the weighted coverage value is associated with the pixel to anti-alias the pixel in the discrete image.
In one aspect of the invention, only visible edges are anti-aliased, and only pixels within a predetermined distance from the edge are considered, for example, the distance is less than or equal to a length of the line sample.
In another aspect of the invention, the line sample is straight, centered on the pixel, and substantially perpendicular to the edge.
In yet another aspect of the invention, the filter function is a Gaussian function, and the progressive convolution is a cumulative integral of the filter function for various distances. The progressive convolution can be defined by a continuous function, or alternatively, the values of the progressive convolution are stored in a table for a finite number of distances.
In yet another aspect of the invention, multiple line samples are defined for each pixel and the weighted coverage values of the line samples are combined to produce a combined weighted coverage value which is associated with the pixel.
REFERENCES:
patent: 5617459 (1997-04-01), Makram-Ebeid et al.
patent: 5999659 (1999-12-01), McCarthy et al.
patent: 6038031 (2000-03-01), Murphy
patent: 6133901 (2000-10-01), Law
patent: 6329977 (2001-12-01), McNamara et al.
patent: 6424343 (2002-07-01), Deering et al.
patent: 2003/0210251 (2003-11-01), Brown
Max et al.; “Antialiasing Scan-Line Data”; InIEEE Computer Graphics and Applications; Jan '90, pp. 18-30.
Edwin Catmull; “A Hidden-Surface Algorithm with Anti-Aliasing”; InProceedings from SIGGRAPH '78; pp. 6-11.
Feibush et al.; “Synthetic Texturing Using Digital Filters”; InProceedings from SIGGRAPH '80; pp. 294-301.
Kenneth Turkowski; “Anti-Aliasing through the Use of Coordinate Transformations”; In ACM Transactions on Graphics, vol. 1, No. 3, Jul., 1982; pp. 215-234.
Abram et al.; “Efficient Alias-Free Rendering Using Bit-Masks and Look-up Tables”; InProceedings from SIGGRAPH '85; vol. 19, No. 3, Jul., 1985; pp. 53-59.
Tom Duff; “Poly
Jones Thouis R.
Kotredes Robert M.
Perry Ronald N.
Brinkman Dirk
Curtin Andrew
Mitsubishi Electric Research Labs Inc.
Vida Melanie
Williams Kimberly
LandOfFree
Anti-aliasing with line samples does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Anti-aliasing with line samples, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Anti-aliasing with line samples will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3282709