Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2001-05-14
2004-12-07
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S587000, C345S589000, C345S611000, C345S544000, C345S545000, C345S694000, C382S269000, C382S272000
Reexamination Certificate
active
06828983
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to 3D graphics and sampling/antialiasing techniques and more particularly to a system and method for efficiently sampling 3D primitives while minimizing the aliasing artifacts that are caused by sampling.
2. Description of Related Art
The problem of aliasing typically occurs when a continuous signal is represented in a discrete form (commonly referred to as sampling). In the context of 3D graphics, a continuous object (such as a polygon) is represented by a collection of discrete points (pixels) on a display screen. If the sampling is not carefully performed, aliasing artifacts may significantly corrupt the rendered scene. Aliasing artifacts include “jaggies” or “staircasing” that normally appear on the edges of the primitives. The staircase effect becomes more prominent in animations, since the staircase effect tends to creep in the animation images.
The process of eliminating aliasing artifacts is broadly referred to as anti-aliasing. One common anti-aliasing mechanism is referred to as A-buffer (anti-aliased, area-averaged, accumulation buffer) in which polygon edge fragments are sampled, and the information about the fragments are stored as linked lists and blended for antialiasing. However, a disadvantage of the A-buffer algorithm is that this algorithm assumes use of an unbounded memory for storing data such as edge fragment information for complex 3D scenes (scenes with high complexity and/or with a large number of primitives). To simplify the memory requirements in the A-buffer algorithm, heuristics may be used. However, the use of heuristics degrades the quality of the output image. A further disadvantage of the A-buffer algorithm is that it does not detect “Z-edges”, thus resulting in color bleeding problems due to improper Z interpolation.
Another method of anti-aliasing involves an architecture which divides each image layer into pixel regions or “chunks”, and the geometry is presorted into bins based upon the particular chunk (or chunks) in which the geometry will be rendered. Each chuck is dealt with independently for anti-aliasing. However, the antialasing algorithm used in this architecture is based upon the A-buffer algorithm, and therefore, suffers from the same disadvantages and drawbacks mentioned previously.
A further anti-aliasing method is known as Z
3
, which maintains a sorted list of edge fragments and blends the fragments in the same manner as the A-buffer algorithm. Although the Z
3
algorithm can detect “Z-edges”, it disadvantageously relies on unbounded memory, use of linked lists which require complex logic, and blending of polygon edge fragments to reduce memory usage which degrades the quality of the output image for a complex 3D scene.
Therefore, there is a need for an improved system and method for efficiently sampling 3D primitives while preventing the aliasing artifacts introduced by the sampling process.
SUMMARY OF THE INVENTION
The present system and method prevents the occurrence of aliasing at the edges of polygons in 3D graphics scenes. Advantageously, the anti-aliasing of edges may occur in real time, and the system may also detect both polygon “geometry edges” and “Z edges” that occur due to the interaction of multiple polygons. Relevant edge information may be stored in a limited (or bounded) memory space during anti-aliasing operations, irrespective of the complexity of the 3D scene. Further, the present system and method may permit significant reduction in memory traffic, leading to a reduced latency and increased rendering speed, since super-sampling need be performed only at the edges of primitives. In an embodiment of the present system and method, selective super-sampling of a pixel is deferred until more than one primitive edge is detected to fall in the pixel. The system and method may also prevent the occurrence of aliasing artifacts and permit high quality images to be generated. In another embodiment, the present system and method prevents aliasing at an edge of a primitive by detecting “geometry edges” of a current primitive, detecting “Z edges” formed by the intersection of the current primitive and a previously rendered primitive, and super-sampling the detected edges.
A super-sampling system for preventing aliasing in 3D data is provided in accordance with various embodiments. In one embodiment, the super-sampling system includes an edge anti-aliasing module configured to selectively super-sample edge portions of a primitive. The super-sampling system also includes two different memory configurations (i.e., a coarse memory and a fine memory). The coarse memory is configured to store information of pixels that are not super-sampled, while the fine memory is configured to store information of pixels that are super-sampled by the edge anti-aliasing module.
The present system and method selectively super-samples the edges generated by individual primitives as well as by the interaction of primitives. Such a selective approach reduces the memory storage requirements and traffic.
REFERENCES:
patent: 4343037 (1982-08-01), Bolton
patent: 5347618 (1994-09-01), Akeley
patent: 5471568 (1995-11-01), Webb et al.
patent: 5511153 (1996-04-01), Azarbayejani et al.
patent: 5734386 (1998-03-01), Cosman
patent: 5740343 (1998-04-01), Tarolli et al.
patent: 5831624 (1998-11-01), Tarolli et al.
patent: 6005582 (1999-12-01), Gabriel et al.
patent: 6016152 (2000-01-01), Dickie
patent: 6064393 (2000-05-01), Lengyel et al.
patent: 6128000 (2000-10-01), Jouppi et al.
patent: 6281903 (2001-08-01), Martin et al.
patent: 6292193 (2001-09-01), Perry et al.
patent: 6304286 (2001-10-01), Shirai et al.
patent: 6317525 (2001-11-01), Aleksic et al.
patent: 6359619 (2002-03-01), Waters et al.
patent: 6377273 (2002-04-01), Lee et al.
patent: 6400370 (2002-06-01), Lee et al.
patent: 6466206 (2002-10-01), Deering
patent: 6489966 (2002-12-01), Kanzaki et al.
patent: 6509897 (2003-01-01), Lewis
patent: 6570579 (2003-05-01), MacInnis et al.
Andreas Shilling, “A New Simple and Efficient Antialiasing with Subpixel Masks”, Jul. 1991, pp. 133-141.
Norman P. Jouppi, Chun-Fa Chang, “Z3: An Economical Hardware Technique for High-Quality Antialiasing and Transparency”, 1999, pp. 85-93, Eurographics Los Angeles California.
Jay Torborg, James T. Kajiya, “Talisman: Commodity Realtime 3D Graphics for the PC”, Microsoft Corporation.
Loren Carpenter, “The A-buffer, an Antialiased Hidden Surface Method”, Computer Graphics, Jul. 1984, pp. 13-18, vol. 18, No. 3, Association for Computing Machinery, Inc.
U.S. patent application Ser. No. 09/855,322, filed May 14, 2001, Vijayakumar, Matched Texture Filter Design for Rendering Multi-Rated Data Samples.
McCormack et al., “Feline: Fast Elliptical Lines for Anisotropic Texture Mapping,” Compaq Computer Corporation Corporation's Western Research Laboratory and Mitsubishi Electrinc Research Laboratory, Computer Graphics Proceedings, Annual Conference 1999, pp. 243-249.
Programming Assignment No. 5; Beier-Neely Morphing; http://www.cs.rochester.edu/u/www/u/kyros/Courses/CS290B/Assigns/assign5.html; Nov. 22, 2002.
Mueller, Carl, “Mipmapping,” http://www.ping.be/powervr/anisotropic2.htm (Date Unknown).
Author Unknown, “Anisotropic Filtering Explained,” http://www.ping.be/powervr/anisotropic.htm (Date Unknown).
Iourcha Konstantine I.
Vijayakumar Baskaran
Bella Matthew C.
Carr & Ferrell LLP
S3 Graphics Co., Ltd.
Sajous Wesner
LandOfFree
Selective super-sampling/adaptive anti-aliasing of complex... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Selective super-sampling/adaptive anti-aliasing of complex..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selective super-sampling/adaptive anti-aliasing of complex... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3283749