Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-11-02
2003-02-25
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S422000
Reexamination Certificate
active
06525726
ABSTRACT:
TECHNICAL FIELD
The invention relates to computer graphics and, in particular, to the culling of occluded polygons from a scene being rendered in a tiled, three-dimensional computer graphics architecture.
BACKGROUND
In the field of data processing, there is an ever increasing demand for graphics and full-motion video applications which are faster, more detailed, and generally more lifelike than their predecessors. Many of these applications are useful in commercial, educational, military, and personal data processing systems. In addition, the rapid acceleration of Internet applications is mandating high performance graphics and multimedia features in newly released computer systems.
High speed three-dimensional (3D) graphics processing requires fast, pipelined processing in order to provide realistic detail and to implement special effects, such as texture maps, lighting, alpha blending, and Z-buffering.
Texture maps provide life-like surfaces and shadows within a three-dimensional image. Lighting provides realistic approximations of the effect of light from various sources striking objects. Alpha blending allows two graphics objects to be blended together.
Z-buffering (or hidden surface removal) tracks the depth of objects or pixels to ensure that a minimum of processing is carried out on polygons which are hidden behind others in a scene. Z-buffering has become increasingly important in graphical processing systems, because the size and complexity of graphical databases have been growing for many 3D graphics applications. These 3D graphics models typically have high depth complexity, i.e. a given pixel is rendered many times due to many overlapping polygons, and only the polygon closest to the viewer ends up being visible.
Identifying and culling these occluded polygons represents a significant performance improvement opportunity. In general, low cost graphics accelerators have not yet been able to incorporate effective occlusion culling. Previously proposed occlusion culling algorithms have been too complex for integration into low cost architectures.
Graphics processing architectures must address both the computational load of transformations, texturing, and lighting, as well as the increasingly important bandwidth load of accessing the geometry, texture, and visibility data. To be commercially successful, graphics accelerators for personal computers must address these computation and bandwidth requirements while keeping the hardware cost very low.
High output bandwidth implies high cost memory for Z-buffering and for anti-aliasing (reducing stair-stepping or jagged lines that sometimes occur on a display screen). This cost can be kept down by using a tiled architecture that renders the scene one tile or chunk at a time and reuses the fast expensive memory for each tile.
The Z-buffer provides a basic hidden surface removal mechanism for graphics, accelerators used in personal computers, despite its lack of support for occlusion culling. Major performance improvements can be achieved by identifying and eliminating those polygons that cannot be seen from some regions of space. This saves the cost of rendering such polygons by scan converting, lighting, alpha-blending, shading, and/or texturing them.
Software algorithms are currently known for processing, including culling, polygons, in computer graphics systems. However, these algorithms have either required complex and costly computer hardware to implement, or they have provided unsatisfactory performance.
For the reasons stated above, there is a substantial need in the area of computer graphics processing to provide a graphics processing system which can render high depth complexity scenes while reducing both computational and bandwidth loads.
In addition, there is a substantial need in the area of computer graphics processing to provide computer graphics hardware which can efficiently perform high depth complexity graphics processing and which is relatively inexpensive to manufacture.
SUMMARY
Accordingly, in one embodiment of the invention there is provided a method for use in a processor adapted to be used in a graphical data processing system. The data processing system comprises a frame buffer and a Z-buffer. The method operates to cull occluded polygons from a scene being assembled in the frame buffer. The method comprises rendering the polygons in each tile of the scene in depth order, starting with a closest polygon, and storing their pixel depths in the Z-buffer. As polygons are rendered, an evaluation is made whether a coverage parameter has been satisfied and, if so, a hierarchical Z-buffer is constructed from the Z-buffer. Subsequent polygons are compared to the hierarchical Z-buffer to determine whether they are completely hidden and, if so, they are culled. Additional embodiments are described and claimed.
REFERENCES:
patent: 5579455 (1996-11-01), Greene et al.
patent: 5596686 (1997-01-01), Duluk, Jr.
patent: 6052125 (2000-04-01), Gardiner et al.
patent: 6259452 (2001-07-01), Coorg et al.
patent: 6300965 (2001-10-01), Sowizral et al.
patent: 6348919 (2002-02-01), Murphy
patent: 6362818 (2002-03-01), Gardiner et al.
patent: 6366283 (2002-04-01), Tampieri
Article Titled “Hierarchical Polygon Tiling with Coverage Masks” by Ned Greene, Apple Computer, Proceedings of the 23rd annual conference on Computer Graphics and Interactive Techniques, Aug. 1996.*
Article Titled “Preprocessing Occlusion For Real-Time Selective Refinement” by Fei-Ah Law et al., National University of Singapore, Proceedings of the Symposium in Interactive 3D Graphics, Apr. 1999.*
Article Titled “Visibility Preprocessing for Interactive Walkthroughs” by Seth J. Teller et al., University of California at Berkeley, ACM SIGGRAPH Computer Graphics, Proceedings of the 18th annual conference on Computer Graphics and Interactive Techniques.
Shantz Michael J.
Xie Feng
Intel Corporation
Santiago Enrique L.
Schwegman Lundberg Woessner & Kluth P.A.
Zimmerman Mark
LandOfFree
Method and apparatus for adaptive hierarchical visibility in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for adaptive hierarchical visibility in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for adaptive hierarchical visibility in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3123649