Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2000-05-31
2003-03-04
Padmanabhan, Mano (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S611000
Reexamination Certificate
active
06529207
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
The present invention relates generally to computer graphics rendering, and more particularly to anti-aliasing of the edges of objects represented in computer generated images.
2. The Prior State of the Art
Graphics rendering systems create images of objects which are combined in a visual scene. An object is a computer readable specification of appearance attributes which, when used to create an image, has the appearance of physical substance. A scene is a collection of objects distributed around an area to be represented in an image. In a two dimensional graphics rendering system an image is constructed based on the location and orientation of two dimensional objects in a scene. For a three dimensional graphics rendering system, three dimensional objects are placed in a three dimensional scene with a three dimensional coordinate system. A camera is defined by at least a location and a direction of view relative to a scene. Rendering is the process of creating an image based on the objects which would be visible to a camera viewing a scene if it were real, and placing this image in memory, typically a frame buffer. The image is composed of an array of picture elements, or pixels, which each exhibit a color. In real-time rendering systems, the image is displayed, typically on a computer monitor, while a later image is being constructed. The part of the rendering system which interprets object data to determine what the scene looks like is referred to as the rendering pipeline.
High speed rendering systems typically rely on combinations of simple polygons, referred to as primitives, to build more complex objects. The rendering pipeline of such a system is generally optimized to render primitives into the frame buffer quickly. Triangles are commonly used as primitives, since objects of arbitrary complexity may be composed of triangles. This is illustrated in FIG.
1
.
The discrete pixels of an image in a frame buffer are comparable to samples of a continuous image. A well known phenomenon associated with discrete sampling of continuous values is aliasing. In the field of computer graphics rendering, aliasing is most often encountered in the form of straight lines which have a jagged or stair-stepped appearance, as illustrated in FIG.
2
. The edges of primitives (such as triangles) rendered to an image may exhibit this pattern, which is especially noticeable where there is high contrast between the color of a foreground primitive and the color of the background. This aliasing of primitive edges is generally undesirable, and steps are taken to reduce the effect of it.
If nothing is done to reduce the effects of aliasing, a pixel which represents an area of a scene containing an edge of high color contrast in a computer generated image will generally be colored according to whichever color happens to coincide with the centroid of the pixel. This is illustrated in
FIG. 3
, where a pixel is shown representing an area which is partly red and partly blue. The pixel is given the color red, because the centroid of the pixel falls on the red primitive. A more realistic image, and one without noticeable aliasing effects, would be obtained if the pixel were colored with both red and blue, in the proportion each is present in the area represented by the pixel. This blending of colors is at the heart of most schemes to reduce the effects of aliasing. Efforts to reduce aliasing in the field of computer graphics are referred to as anti-aliasing.
One method of performing anti-aliasing, known in the art as sub-sampling, is to determine colors for a number of samples within the area represented by each pixel. Each of these sub-samples is at a slightly different location, and the sub-samples are averaged together to determine a final color for the pixel. This method reduces aliasing considerably, but at the expense of increasing the amount of calculation, and time, required for rendering each pixel. The time expense is so large that this solution is not generally used for real-time rendering systems.
A solution which is feasible for real-time rendering is to blend the color of each pixel in an image with the colors of surrounding pixels. This is, in effect, a low-pass filter applied to the initial image determined by the rendering pipeline. The added amount of calculation is much less than for the sub-sampling solution, but the results are poor. The entire image is blurred, and appears to be out of focus.
Another solution to the problem of anti-aliasing real-time computer generated images is to only apply anti-aliasing techniques to areas of an image which correspond to object silhouette edges. A silhouette edge is the visible perimeter of an object. Sharp contrasts (and therefore areas of noticeable aliasing) are generally most likely to occur at silhouette edges. Finding the portions of an image which correspond to object silhouette edges is not trivial. One method of finding these edges is to use a buffer which holds one bit per pixel of the finished image. The buffer is set to all zeros, then as each object is rendered the state of the bits in the buffer corresponding to the drawn pixels are changed. When all objects have been rendered, the bits of this buffer will have gradients from one to zero or from zero to one in areas corresponding to the silhouette edges of many of the objects. The corresponding areas in the image are then subjected to low-pass filtering. This method, however, uses a lot of memory for the buffer, does not always catch all of the object silhouette edges and generates a lot of false edges.
What is needed is a system and method for performing anti-aliasing on those parts of a rendered image which should be anti-aliased, without disturbing those portions of the image which should not be anti-aliased. To do this a system should accurately determine object silhouette edges without requiring intensive additional computing or large amounts of additional memory.
SUMMARY OF THE INVENTION
The present invention is a computer apparatus and method for anti-aliasing the silhouette edges of objects rendered by a rendering pipeline. The objects are composed of primitives, such as triangles, each of which has edges which may be a silhouette edge of the object under particular circumstances. When the object is constructed, information concerning which edges may be silhouette edges in particular circumstances is encoded with the object. While the rendering pipeline renders an image in a first pass, information is collected concerning how many times some of the potential silhouette edges are drawn. After the rendering pipeline is finished with the first pass, a second pass begins. In this pass, the rendering pipeline uses the information about the edges which was encoded with each object, in conjunction with the information about the number of times particular edges were drawn, to determine which edges in the image lie at the silhouette edge of an object. If a particular edge has a primitive drawn on one side, but none on the other side, that edge is a silhouette edge. These silhouette edges are anti-aliased, providing a clear image without significant aliasing effects, through the use of a method which does not require much additional time or memory.
REFERENCES:
patent: 3889107 (1975-06-01), Sutherland
patent: 5287436 (1994-02-01), Fischer et al.
patent: 5303339 (1994-04-01), Ikuma
patent: 5357600 (1994-10-01), Shirman et al.
patent: 5359704 (1994-10-01), Rossignac et al.
patent: 5574835 (1996-11-01), Duluk, Jr. et al.
patent: 5579456 (1996-11-01), Cosman
patent: 5729672 (1998-03-01), Ashton
patent: 5742277 (1998-04-01), Gossett et al.
patent: 6111582 (2000-08-01), Jenkins
Angel (“Interactive Computer Graphics”:1997; ISBN:0-201-85571-2): Fig.2.19.
Laker Robert
Landau Edouard
Liu Mei-Chi
Malamy Adam
Sabella Paolo
Padmanabhan Mano
WEBTV Networks, Inc.
Workman & Nydegger & Seeley
LandOfFree
Identifying silhouette edges of objects to apply anti-aliasing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Identifying silhouette edges of objects to apply anti-aliasing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Identifying silhouette edges of objects to apply anti-aliasing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3033987