Image analysis – Applications – 3-d or stereo imaging analysis
Reexamination Certificate
1999-07-23
2003-06-03
Patel, Jayanti K. (Department: 2625)
Image analysis
Applications
3-d or stereo imaging analysis
C382S282000, C382S285000, C382S291000, C345S419000, C345S653000
Reexamination Certificate
active
06574360
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of computer image processing, and more specifically, selectively rendering objects in a scene in image processing systems.
2. Background Description
State of the art computer aided design (CAD) uses very complex models of objects, wherein each model may include a large number of polygons, that represent physical structures. Interactive visualization of these large polygonal models, places an enormous burden upon the current graphics hardware and makes image rendering very complex and time consuming. This complexity makes it impossible to render at interactive rates with state of the art hardware, especially when interactively rendering large 3D models and is a well known problem in the art. Consequently, numerous methods have been proposed to reduce, or cull, the number of polygons that are rendered for a particular viewpoint and scene model.
for example, one such approach, view frustum culling, does not render any polygons lying completely outside of the viewer's field of view. Similarly, for rendering solid objects, those polygons that are facing away from the viewpoint (i.e., the back-facing polygons) may be omitted for rendering. Accordingly, a potentially greater reduction in the number of polygons that must be processed might be realized by culling away those geometric portions of the scene or shapes therein that are occluded from view by other objects in the forefront of the scene.
Another approach to this problem is discussed by S. Teller & C. Sequin in “Visibility Preprocessing for Interactive Walkthroughs,”
SIGGRAPH
1991
Conference Proceedings
, ACM Press, 1991, pp. 61-69. Teller & Sequin's approach has been to break the input model down into “cells” and “portals”. Cells have boundaries coinciding with opaque surfaces, while portals represent non-opaque surfaces between the cells. An adjacency graph is constructed to connect the cells via portals. Then, the adjacency graph is utilized to determine the cell-to-cell visibility and the potentially visible set (PVS) of polygons for each cell. Unfortunately, the Teller & Sequin approach has been presented, typically, within a framework of architectural models wherein cells (e.g., floors, rooms, hallways) and portals (e.g., doors, windows) are easily defined. Teller & Sequin do not address more complicated scenarios, such as rendering general, large 3D models at interactive rates.
yet another approach is discussed by S. Coorg & S. Teller in “Temporally Coherent Conservative Visibility,”
Proceedings
, 12
th Annual ACM Symposium of Computer Geometry
, 1996, 78-87. Coorg & Teller also precompute a superset of the visible polygons when the viewpoint is within a particular region of space. As the viewpoint moves, the Coorg & Teller method tracks only those events that cause changes in the polygons visible from the current viewpoint, termed “visual events” by Coorg & Teller. Unfortunately, the Coorg & Teller method considers only a single polygon as an occluder. Coorg & Teller rely on the model to include large occluders. However, the Coorg & Teller method does not handle scenes with an absence of large occluders or objects being occluded by multiple smaller objects well.
N. Greene, M. Kass and G. Miller in “Hierachical Z-Buffer Visibility,”
SIGGRAPH
93
Conference Proceedings
, ACM Press, 1993, pp. 273-278, teach a Hierarchical Z-buffer (HZB) that extends the traditional Z-buffer by maintaining what is termed an “image Z pyramid” to quickly reject hidden geometry. A second data structure, an octree, is built upon the geometry in object-space. At run-time, the octree is traversed with each node of the tree being queried against the current HZB. If a current node is determined to be behind previously visible geometry, then the current octree node can be skipped, together with all children of the skipped node and the geometry associated with children. Otherwise, as the image geometry is rendered, new z values are propagated for the current node through the HZB, as well as for the children of the current node. Unfortunately, to achieve interactive rendering rates, the HZB approach requires special graphics hardware to make the necessary queries and updates against the HZB.
Yet another approach, similar to the HZB approach, is the Hierarchical Occlusion Maps (HOM) of H. Zhang, D. Manocha, T. Hudson and K. E. Hoff III, “Visibility Culling using Hierarchical Occlusion Maps,”
SIGGRAPH
97
Conference Proceedings
, ACM Press, 1997, pp. 77-88. The HOM approach is similar to the HZB in using both object and image space hierarchies. Initially, the HOM image spaces are built by rendering shapes with a high potential for occluding, i.e., shapes that are very close to the current viewpoint. To determine visibility of the remaining shapes, the object space hierarchy is traversed while checking each node against a hierarchical occlusion map, using, if necessary, a conservative depth test to determine occlusion. However, the HOM approach requires initially selecting occluders to be rendered at each viewpoint. Further, to accelerate HOM shape construction, the HOM approach requires special graphics hardware to support bilinear interpolation of texture maps.
Thus, there is a need for efficiently selecting portions of geometry to be rendered in an image processing system that does not require special graphics hardware.
SUMMARY OF THE INVENTION
It is a purpose of the invention to improve image rendering in image processing systems;
It is another purpose of the invention to improve efficiency in selecting image portions rendered in an image processing system;
It is yet another purpose of the invention to improve selecting scene portions that are rendered and identifying occluded scene portions that are not rendered, thereby improving system efficiency;
It is yet another purpose of the invention to minimize scene geometry rendered while producing an image that is visually indistinguishable with the image resulting from rendering all of the scene geometry.
The present invention is a technique of occlusion culling and system therefor. The culling method of the present invention first determines which polygons are hidden, or occluded, by other objects. These hidden or occluded polygons will not contribute to the final scene and, therefore, need not be rendered. The present invention includes two major steps. In the first major step, the input models are preprocessed to build a hierarchical data structure which is used as an approximation to the input models. In this first step, simple polygonal occluders are determined for substitution in place of the complex image geometry in successive visibility queries. Once the first preprocessing step is complete, the second step may be executed at run-time, while a user is inspecting, or visualizing, the input. In the second step, the occluders, determined in the first step, are used to forego rendering shapes or shape portions that are unseen from the current viewpoint.
REFERENCES:
patent: 4865423 (1989-09-01), Doi
patent: 5579455 (1996-11-01), Greene et al.
patent: 5600763 (1997-02-01), Geene et al.
patent: 5999187 (1999-12-01), Dehmlow et al.
patent: 6075538 (2000-06-01), Shu et al.
patent: 6088035 (2000-06-01), Sudarsky et al.
patent: 6414680 (2002-06-01), Klosowski et al.
Berdardini Fausto
El-Sana Jihad
Klosowski James T.
Luebke David
Menon Jai
International Business Machines Corp.
Kassa Yosef
Patel Jayanti K.
Percello Louis J.
Peterson, Jr. Charles W.
LandOfFree
Accelerated occlusion culling using directional discretized... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accelerated occlusion culling using directional discretized..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accelerated occlusion culling using directional discretized... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3099206