Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-03-09
2003-10-21
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06636215
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention, generally, relates to computer graphics and, more particularly, to a new and improved method and apparatus for rendering images of three-dimensional scenes using z-buffering.
2. References
The following documents are all incorporated herein by reference.
J. Airey, “Increasing Update Rates in the Building Walkthrough System with Automatic Model-Space Subdivision and Potentially Visible Set Calculations,” PhD Thesis, Technical Report TR90-027, Computer Science Dept., UNC Chapel Hill, 1990.
L. Carpenter, “The A-Buffer, an Antialiased Hidden Surface Method,”
Proc. of SIGGRAPH
'84, July 1984, 103-108.
J. H. Clark, “Hierarchical Geometric Models for Visible Surface Algorithms,”
Communications of the ACM
19(10), October 1976, 547-554.
S. Coorg and S. Teller, “Temporally Coherent Conservative Visibility,”
Proc. Of
12
th
ACM Symposium on Computational Geometry
, 1996.
M. Deering, S. Schlapp, and M. Lavelle, “FBRAM: A new Form of Memory Optimized for 3D Graphics,”
Proc. of SIGGRAPH
'94, July 1994, 167-174.
Jay Duluk, personal communication, 1999.
H. Fuchs, J. Goldfeather, J. Hulquist, S. Spach, J. Austin, F. Brooks, Jr., J. Eyles, and J. Poulton, “Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes,”
Proc. of SIGGRAPH
'85, July 1985, 111-120.
T. Funkhouserand C. Sequin, “Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments,”
Proc. of SIGGRAPH
'93, August 1993, 247-254.
B. Garlick, D. Baum, and J. Winget, “Interactive Viewing of Large Geometric Databases Using Multiprocessor Graphics Workstations,”
Siggraph
'90
Course Notes: Parallel Algorithms and Architectures for
3
D Image Generation
, 1990.
N. Greene, M. Kass, and G. Miller, “Hierarchical Z-Buffer Visibility,”
Proc. of SIGGRAPH
'93, July 1993, 231-238.
N. Greene, “Hierarchical Rendering of Complex Environments,” PhD Thesis, Univ. of California at Santa Cruz, Report UCSC CRL-95-27, June 1995.
N. Greene, “Hierarchical Polygon Tiling with Coverage Masks,”
Proc. of SIGGRAPH
'96, August 1996.
H. Hoppe, “Progressive Meshes,”
Proc. of SGGRAPH
'96, August 1996, 99-108.
T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang, “Accelerated Occlusion Culling Using Shadow Frusta,”
Proc. Of ACM Symposium on Computational Geometry
, 1997.
Adam Levinthal, personal communication, 1999.
D. Luebke and C. Georges, “Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible Sets,”
ACM Interactive
3
D Graphics Conference
, 1995.
D. Meagher, “The Octree Encoding Method for Efficient Solid Modeling,” PhD Thesis, Electrical Engineering Dept., Rensselaer Polytechnic Institute, Troy, N.Y., August 1982.
B. Naylor, “Partitioning Tree Image Representation and Generation from 3D Geometric Models,”
Proc. of Graphics Interface
, 1992.
N. Scott, D. Olsen, and E. Gannett, “An Overview of the VISUALIZE fx Graphics Accelerator Hardware,”
The Hewlett
-
Packard Journal
, 49(2), May 1998, 28-34.
O. Sudarsky and C. Gotsman, “Dynamic Scene Occlusion Culling,”
IEEE Transactions on Visualization and Computer Graphics
, 5(1), January 1999.
Gary Tarolli, personal communication, 1999.
S. Teller, “Visibility Computations in Densely Occluded Polyhedral Environments,” PhD Thesis, Univ. of California at Berkeley, Report UCB/CSD 92/708, October 1992.
“Denali Technical Overview,” Kubota Pacific Computer, January 1993.
J. Warnock, “A Hidden Surface Algorithm for Computer Generated Halftone Pictures,” PhD Thesis, TR 4-15, Computer Science Dept., Univ. of Utah, June 1969.
F. Xie and M. Shantz, “Adaptive Hierarchical Visibility in a Tiled Architecture,”
Proc. Eurographics/Siggraph Workshop on Graphics Hardware
, August 1999, 75-84.
H. Zhang, D. Manocha, T. Hudson, and K. Hoff, “Visibility Culling Using Hierarchical Occlusion Maps,”
Proc. of SIGGRAPH
'97, August 1997, 77-88.
H. Zhang, “Effective Occlusion Culling for the Interactive Display of Arbitrary Models,” PhD Thesis, Computer Science Dept., UNC Chapel Hill, 1998.
3. Description of Related Art
Rendering is the process of making a perspective image of a scene from a stored geometric model. The rendered image is a two-dimensional array of pixels, suitable for display.
The model is a description of the objects to be rendered in the scene stored as graphics primitives, most typically as mathematical descriptions of polygons in three-dimensional space, together with other information related to the properties of the polygons. Part of the rendering process is the determination of occlusion, whereby the objects and portions of objects which are occluded from view by other objects in the scene are eliminated.
As the performance of polygon-rendering systems advances, the range of practical applications grows, fueling demand for ever more powerful systems capable of rendering ever more complex scenes. There is a compelling need for low-cost high-performance systems capable of handling scenes with high depth complexity, i.e., “densely occluded” scenes (for example, a scene in which ten polygons overlap on the screen at each pixel, on average).
In a typical z-buffer system for rendering polygons, each polygon in the scene is rasterized using a z-buffer to determine visibility at image samples. In many systems a host processor takes advantage of hardware assistance by sending each polygon in the scene on a bus to graphics hardware that rasterizes the polygon and maintains the z-buffer. Other z-buffer systems employ hierarchical z-buffering, which uses a “z-pyramid” instead of a conventional single-level z-buffer, as described in N. Greene, M. Kass, and G. Miller, “Hierarchical Z-Buffer Visibility,” Proceedings of SIGGRAPH '93, July 1993, pages 231-238, incorporated by reference herein. Hierarchical z-buffering can be very expensive to implement in its full form in hardware, so implementations of this algorithm in the past have maintained the z-pyramid and performed z-buffer visibility checking entirely in software.
As an alternative to hardware implementation of a full z-pyramid, some systems use only a two-level z-pyramid which includes just the two finest-resolution levels of a full z-pyramid. For example, some flight simulators use a two-level z-pyramid in which the coarser level contains “zfar” values for rectangular regions of the screen. The rectangular screen regions are called “spans.” Having spans enables “skip over” of regions where a primitive is occluded over an entire span.
Another alternative to conventional hierarchical z-buffering is to separate culling from rendering in a hardware graphics pipeline by employing a culling stage that culls occluded geometry and passes visible geometry on to be rendered by a conventional z-buffer rendering stage. See N. Greene,
Occlusion Culling with Optimized Hierarchical Z
-
Buffering
, Siggraph Technical Sketch, Siggraph '99 Conference Abstracts and Applications, August 1999; and N. Greene,
Optimized Hierarchical Occlusion Culling for Z
-
Buffer Systems
, Siggraph '99 Conference Abstracts and Applications CD-ROM, August 1999, both incorporated by reference herein. This method is also described in the above-incorporated CIP parent patent application.
There is presently an obstacle to achieving high performance in processing densely occluded scenes. Typically, all “on-screen” polygons in the scene are processed one-by-one by the host and sent on a bus to graphics hardware, which also processes polygons one by one. This is particularly inefficient for densely occluded scenes, because most polygons are occluded, and even the occluded polygons need to be sent on the bus, transformed to image space, and processed in other ways.
In the prior art, this problem has been addressed by organizing the model in three-dimensional bounding boxes and having the host processor cull occluded bounding boxes. With this approach, which will be called “box culling,” only the polygons in visible bounding boxes need to be sent through the hardware renderi
Nguyen Phu K.
NVIDIA Corporation
Silicon Valley IP Group PC
Zilka Kevin J.
LandOfFree
Hardware-assisted z-pyramid creation for host-based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hardware-assisted z-pyramid creation for host-based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware-assisted z-pyramid creation for host-based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3153110