Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-03-20
2001-07-10
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000
Reexamination Certificate
active
06259452
ABSTRACT:
BACKGROUND OF THE INVENTION
Computer modeling of a 3-dimensional space usually begins by defining a collection of “objects” existing within the space and maintaining this collection within a data base. The “definition” of an object includes enough information to allow a computer to draw, or render, the object from any perspective. Each object's location in “object space” coordinates is specified as well.
These objects are usually described in terms of vertices which define polygons in 3-dimensional object space. These polygons are then projected into a 2-dimensional image space, and drawn into a frame buffer which is used to display the polygons on a computer display.
Typically, a z-buffer is used to hide more distant objects behind objects nearer to the point of view. The z-buffer has an entry corresponding to each pixel in a frame buffer. While the frame buffer contains pixel color/intensity information, the z-buffer maintains a relative depth of each pixel. Before a pixel is overwritten in either buffer, a new pixel's depth is compared with the old (z-buffer) pixel's depth value. If the new pixel is closer, the frame buffer and z-buffer pixels are overwritten. Otherwise, the new pixel is discarded. In this manner, closer objects are displayed while objects obscured from view are not. While the actual z-buffer algorithm is usually implemented in hardware, all objects must first be processed, e.g. projected into 2-dimensional space and colored/textured, in order to be passed to the z-buffer, even though many of these objects are ultimately hidden. This is a very time-consuming and wasteful task.
Greene (U.S. Pat. No. 5,600,763), among others, attempts to improve on this by culling objects in image space. Greene does so by progressively subdividing the object space into smaller and smaller cubic spaces until either a size limit is reached or a cube is found to be the smallest cube that fully encloses a particular object. Greene tests for visibility of the cubes in image space, starting with the largest cube, and if that cube is visible, testing the sub-cubes therein, and so forth. Cubes that are not visible are culled before their associated objects are rendered. This would require significant modification to existing current graphics workstations.
Previous work by one of the present inventors, “Visibility Preprocessing For Interactive Walkthroughs”, Teller and Séquin, Computer Graphics, Vol. 25, No. 4, July 1991, pp. 61-69, incorporated herein by reference, describes a process in which the “world” is divided early in the process into cells which have viewing portals into other cells. At start-up, it is determined for each cell which other cells are visible from the given cell. This information is maintained statically and allows culling of all cells (and objects therein) which are not visible from the cell holding the current viewpoint. As a refinement, a “view cone” is calculated to further dynamically cull cells that are not actually visible from the viewpoint as the viewpoint moves around. While this algorithm works well for architectural walk-throughs, it is not efficient for models with less apparent cell/portal structures such as outdoor city models.
SUMMARY OF THE INVENTION
Identifying visible polygons or eliminating hidden polygons is an important component of efficient scene rendering algorithms. Despite the availability of high performance z-buffer hardware, a significant fraction of graphics machines have lesser or no hardware z-buffering capabilities. Software z-buffering (e.g., on personal computers) can be a rendering bottleneck. Moreover, on many computer architectures, the z-test occurs after other graphics processing (e.g., shading, texture mapping), wasting computation on invisible portions of the model.
One way to address this problem is to develop occlusion culling algorithms that efficiently identify, then render, only the visible portions of the model or a tightly-bounded superset thereof. The present invention exploits the presence of large occluders in typical architectural or urban models to design a real-time occlusion culling algorithm.
In accordance with the present invention, an image constructed, relative to a viewpoint and a field of view, from a three-dimensional object data base is drawn. Individual occluders within the field of view are dynamically identified in object space. Any objects in the object data base which are within the field of view, but which are fully occluded from sight of the viewpoint by the identified occluders, are culled from the list of objects to be drawn. Objects which have not been culled from the object data base are drawn.
In a preferred embodiment, the object space is partitioned into octree nodes, or cells, and objects are culled by determining whether cells which contain the objects are fully occluded from sight.
Furthermore, information about viewing regions of object space from which objects are occluded may be dynamically determined. This information may be retained for reuse by subsequent culling operations.
In the preferred embodiment, a viewing region of object space, from which the object is occluded from sight, is defined. When the point of view is within the defined region, the object is culled. Such a region is defined by supporting planes which are tangential to an occluder and an object set. The object set may be, for example, a cell partitioned from the object space, or alternatively, the object set may be a single object.
Significant occluders are large objects which are near the viewpoint, thus potentially occluding a large volume of space relative to the viewpoint, or which are near other objects and therefore have the potential to occlude the other objects relative to the viewpoint.
In the preferred embodiment, significant occluders are identified by statically identifying potential occluders based on the apparent size of the objects and dynamically selecting significant occluders based on a current viewing direction. Such a determination of apparent size may be based on an estimate of the solid angle subtended by the potential occluder relative to the viewpoint, or alternatively, relative to the center of the object set.
Once the significant occluders are selected for a given viewpoint, it is determined which objects are completely occluded by the significant occluders, and these occluded objects are culled from the list of objects so as not to be rendered. Information pertaining to regions of object space from which each object is occluded is retained for reuse by subsequent culling operations. The set of regions thus identified due to large occluders near the viewpoint is dynamically maintained as the viewpoint moves around in object space.
The preferred embodiment uses a simple and fast visibility test that determines whether some region of the model is completely or partially occluded by a set of occluders. Second, a preprocessing step identifies nearby large occluders for all viewpoints. Finally, a hierarchical visibility algorithm repeatedly applies the visibility test to determine the status of octree nodes in a spatial hierarchy.
Culling occurs very early, in object space, before any other graphics transformations or operations are performed. It is therefore a very efficient process in that, once an object is culled from the list of objects, no further graphics processing or rendering need be done on that object.
The above and other features of the invention including various novel details of construction and combinations of parts, and other advantages, will now be more particularly described with reference to the accompanying drawings and pointed out in the claims. It will be understood that the particular method and device embodying the invention are shown by way of illustration and not as a limitation of the invention. The principles and features of this invention may be employed in various and numerous embodiments without departing from the scope of the invention.
REFERENCES:
patent: 3602702 (1971-08-01), Warnock
patent: 4594673 (1986-06-01), Holly
patent: 4694404 (
Coorg Satyan R.
Teller Seth J.
Hamilton Brook Smith & Reynolds P.C.
Massachusetts Institute of Technology
Vo Cliff N.
LandOfFree
Image drawing system and method with real-time occlusion... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image drawing system and method with real-time occlusion..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image drawing system and method with real-time occlusion... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2536769