Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-04-21
2002-07-02
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06414680
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to image processing systems and, more particularly, to image processing systems capable of finding visible points or fragments that are connected by a line segment to the eyepoint that meets the closure of no other primitive within the same scene.
2. Background Description
In a given scene,
, finding visible points or fragments that are connected to the eyepoint by a line segment that meets the closure of no other primitive within the same scene is a well known image processing problem. This visibility problem is discussed by D. Dobkin and S. Teller “Computer Graphics,” Handbook of Discrete and Computational Geometry, chapter 42, pages 779-96. CRC Press, Boca Raton, Fla., 1997 (hereinafter Dobkin).
As described in Dobkin, the scene,
, is composed of modeling primitives (e.g., triangles, or spheres), and a viewing frustum defining an eye position, a view direction, and a field of view. For any scene with n primitives, the complexity of the set of visible fragments might be quadratic as a function of n. One well known approach to solving this visibility problem is the Z-buffer algorithm of E. Catmull as described in “A Subdivision Algorithm for Computer Display of Curved Surfaces”, PhD thesis, Dept. of Computer Science, University of Utah, December 1974.
The Z-buffer algorithm exploits the discrete nature of the screen to solve the visibility problem in time proportional to n, because it only touches each primitive once. The Z-buffer algorithm solves the visibility problem by maintaining a depth value for each pixel and, only updating the pixels when rendering geometry closer to the eyepoint. For high-depth complexity scenes, the Z-buffer algorithm might result in overdrawing each pixel a considerable number of times. However, despite this potential inefficiency, the Z-buffer is a popular algorithm and widely implemented in hardware.
Given the wide availability of the Z-buffer approach but with exact visibility computations potentially being too costly in terms of computer time and associated hardware costs, alternative approaches are being sought. One approach is to use the Z-buffer as a filter and design algorithms that compute an approximation of the visible set to reduce the amount of overdraw. More precisely, the visible set
(a subset of
) is defined to be a set of modeling primitives that contribute at least one pixel to the screen. In computer graphics, visibility-culling research has focused, mainly, on algorithms for computing estimations of
, then, obtaining correct images using the Z-buffer.
The simplest examples of visibility-culling algorithms are the “backface” and “view-frustum” algorithms, as described by Foley et al. “Computer Graphics, Principles and Practice, Second Edition,” Addison-Wesley, Reading, Mass., 1990. Backface-culling algorithms avoid rendering geometric primitives that face away from the viewer; while viewing-frustum culling algorithms avoid rendering geometric primitives that are outside of the viewing frustum.
Still another approach is using hierarchical occlusion maps as described by Zhang et al. in “Visibility Culling Using Hierarchical Occlusion Maps,” SIGGRAPH 97 Conference Proceedings, pages 77-88, 1997. The hierarchical occlusion map approach solves the visibility problem by using two hierarchies, an object-space bounding volume hierarchy and another hierarchy of image space occlusion maps. A set of objects (occluders) are selected for each frame from a pre-computed database. The occluders are used to cull unseen geometric primitives. Closely related to this technique is the hierarchical Z-buffer described in U.S. Pat. No. 5,579,455 entitled “Rendering of
3
d
Scenes on a Display Using Hierarchical Z-buffer Visibility” to Greene et al., which is incorporated herein by reference.
Yet another approach is object-space visibility culling. One such object-space visibility culling technique, described by Teller and Sequin in “Visibility Preprocessing for Interactive Walkthroughs,” Computer Graphics, pages 61-69, July 1991 (hereinafter Teller). Teller teaches dividing space into cells and, then, preprocessing the cells for potential visibility. The Teller technique works particularly well for architectural models. These state of the art visibility-culling techniques mostly exploit the presence of large occluders, and keep track of spatial extents over time.
In yet another approach, Funkhouser and Sequin in “Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments,” Computer Graphics, pp. 247-54, 1993, describe a constant-frame rendering system.
However, all of the above state of the art techniques for occlusion-culling have several drawbacks. First of all, the simple backface and viewing-frustum culling algorithms of Foley et al. are unable to cull “overdraw” geometry. For this type of culling, more complex techniques that lead to substantial improvements in rendering time are needed. Unfortunately, these techniques for tighter estimation of the visible set do not come easily. Most currently proposed techniques are quite involved and complex, typically requiring computation of complex object hierarchies in both 3- and 2- space.
In addition to the above problems, typically, a significant portion of the geometric primitives that are not visible are not culled by the prior art occlusion culling methods. Further, these prior art methods do not allow a user-defined budget to be used for culling, e.g., specifying a limit on the number of primitives to render, and therefore, these prior art methods are not time-critical.
Thus, there is a need for more efficient rendering techniques for optimizing the rendering of high-depth complexity scenes.
SUMMARY OF THE INVENTION
It is therefore a purpose of the present invention to efficiently select geometric primitives to be rendered in an image;
It is another purpose of the present invention to efficiently select geometric primitives to be rendered within an image processing system's budget constraints;
It is yet another purpose of the present invention to efficiently select geometric primitives to be rendered within an image processing system's time constraints.
The present invention is a Prioritized-Layered Projection (PLP) technique and system for optimizing the rendering of high-depth complexity scenes. Objects in each frame are prioritized with an estimation of the visible set within the rendered frame. Visible sets are not explicitly computed, but, instead, a priority order is computed “on demand” to maximize the likelihood of rendering visible primitives before rendering occluded ones. For a fixed budget, e.g., time or number of triangles, the rendering technique of the present invention constrains that geometry rendering to the budgeted priority.
The preferred embodiment of the present invention includes two main steps: (1) an occupancy-based tessellation of space; and (2) a solidity-based traversal algorithm. By first computing an occupancy-based tessellation of space, more cells result where there are more geometric primitives. In this spatial tessellation, each cell is assigned a “solidity” value directly proportional to its likelihood of occluding other cells. In its simplest form, a cell's solidity value is directly proportional to the number of primitives contained within the cell. Cells are marked for projection, and the geometric primitives contained within the marked cells are rendered. The present invention uses the cells solidity and other view-dependent information to determine the ordering in which to project cells.
REFERENCES:
patent: 5751291 (1998-05-01), Olsen et al.
patent: 5825369 (1998-10-01), Rossignac et al.
Klosowski James T.
Silva Claudio T.
Fitch Even Tabin & Flannery
International Business Machines Corp.
Peercello Louis J.
Vo Cliff N.
LandOfFree
System, program product and method of rendering a three... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, program product and method of rendering a three..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, program product and method of rendering a three... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826901