Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-05-06
2002-09-24
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S629000, C345S630000, C345S592000
Reexamination Certificate
active
06456285
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of computer generated graphics. More particularly, the present invention relates to a method and apparatus for efficiently rendering transparent objects in a complex transparent scene.
BACKGROUND OF THE INVENTION
Computer graphics is used in a wide variety of applications, such as in business, science, animation, simulation, computer-aided design, process control, electronic publishing, gaming, medical diagnosis, etc. In an effort to portray a more realistic real-world representation, three dimensional objects are transformed into models having the illusion of depth for display onto a two-dimensional computer screen. This is accomplished by using a number of polygons to represent a three-dimensional object. Next, a scan conversion process is used to determine which pixels of a computer display fall within each of the specified polygons. Thereupon, texture is selectively applied to those pixels residing within specified polygons. Finally, lighting, shading, shadowing, translucency, and blending effects are applied.
For a high resolution display (1280×1024) having over a million pixels, for which values must be generated for each and every pixel, displaying a three-dimensional scene on a computer system is a rather complicated task. Processes like lighting, shading, shadowing, texture mapping, blending, etc., are particularly computation intensive, requiring a tremendous amount of processing power. Indeed, even more processing power is necessary for displaying interactive computer graphics, where 3-D images change in response to a user input (e.g. flight simulation). Naturally, the more complex the scene, the more processing power will be required to render that scene.
Although throughput of computer graphics systems has increased considerably in recent years, the size and complexity of three-dimension scenes have been growing even faster. Scenes composed of millions of polygons are no longer uncommon. In light of the enormous processing power necessary to generate highly-complex scenes and the limitations in the speed of currently available hardware, there have been efforts to develop more efficient methods to simplify the task of rendering three-dimensional images. One such method is known as visibility culling or occlusion culling. Simply put, visibility culling limits the number of polygons rendered in each frame by removing hidden or obscured surfaces from the graphics pipeline. When these hidden surfaces are culled away, highly complex scenes can be rendered at a very high rate.
Visibility culling for opaque surfaces is typically performed with a method known as Z-buffer visibility culling. Essentially, Z-buffer visibility culling involves utilizing a Z-buffer for storing the Z-values for a small number of potentially occluding polygons of a scene, and comparing Z-values of a potentially occluded polygon of the scene with the Z-values stored in the Z-buffer before the potentially occluded polygon is drawn. If it is determined that the Z-values of the potentially occluded polygon represents a closer distance to the view point than that represented by the Z-values in the Z-buffer, then the potentially occluded polygon is drawn. Otherwise, the potentially occluded polygon is rejected from the graphics pipeline. In this way, processing bandwidth is not wasted on occluded objects, effectively increasing rendering efficiency.
Z-buffers, however, do not handle transparent or partially transparent polygons well. For instance, imagine a scene having a partially transparent polygon and an opaque one. If the Z-buffer stores the Z-values of the partially transparent polygon, then the opaque polygon may not be drawn if it is positioned behind the partially transparent polygon. On the other hand, if the Z-buffer does not store the Z-values of the partially transparent polygon, there will not be sufficient information to determine the polygons' relative order. Then, the partially transparent polygon will not be culled away even if it is positioned behind the opaque polygon. Hence, partially transparent or translucent polygons cannot contribute to an accurate, conventional Z-buffer or occlusion test. This yields inefficiencies in scenes containing such polygons and surfaces.
Thus, what is needed is a method and apparatus for accelerating the rendering of complex transparent scenes. What is further needed is a method and apparatus for performing visibility culling that is capable of handling transparent and partially transparent polygons.
SUMMARY OF THE PRESENT DISCLOSURE
The present invention is a method of and apparatus for efficiently rendering a complex transparent scene. In furtherance of one embodiment of the present invention, the method comprises steps of determining Z-values for a pre-determined number of potential occluders selected from the transparent scene, storing the Z-values in a Z-stack, comparing Z-values of a potential occludee with the Z-values in the Z-stack, and removing the potential occludee from further processing provided that the Z-values of the potential occludee do not represent a closer distance from a view point than that represented by the Z-values in the Z-stack. Objectives of the present invention are achieved as processing efficiency is increased when substantially occluded objects are not further processed. Such an approach is validated by the observation that although a single partially transparent polygon is not an occluder, it is an attenuator of light. Hence, a plurality of such polygons positioned in succession along a viewing direction may be considered as occluders.
In accordance with one embodiment of the present invention, a Z-stack comprises a three-dimensional array for storing Z-values of the potential occluders. Particularly, each Z-stack includes a plurality of Z-maps corresponding to different depth levels of the transparent scene. Each pixel is associated with an entry in each of the Z-maps, and each entry includes a Z-value corresponding to a distance from the view point to the point on one of the overlapping objects. In one embodiment, the Z-maps are ranked in a descending order with the highest ranked Z-map associating with the frontmost surface of the frontmost objects in the scene, and the lowest ranked Z-map associating with the backmost surface of the backmost objects visible in the scene. In another embodiment, a plurality of pixels are mapped to each entry of the Z-maps for increased processing efficiency.
In one embodiment of the present invention, the Z-values of the potential occluders are computed by the CPU(s) of a computer system. In that embodiment, a bounded volume comprising simple geometrical primitives is first determined for each of the potential occluders. Because Z-values for simple geometrical primitives can be quickly calculated by the CPU, the Z-values for the potential occluders can be easily calculated. The computed Z-values are then stored in the Z-stack according to their respective depth levels in the scene. In one embodiment of the present invention, Z-values that represent a closer distance from the view point are stored in a higher-ranked Z-map, and Z-values that represent a farther distance from the view point are stored in a lower-ranked Z-map. In one embodiment, new Z-value replaces the Z-value stored in one of the Z-maps if the new Z-value represents a closer distance to the view point than that of the stored Z-value. The replaced Z-value is then stored in a lower-ranked Z-map. The use of a bounded volume generates a conservative but efficient representation of the occluder's extent. In another embodiment, the exact occluder's extent may be generated by direct calculation.
In yet another embodiment of the present invention, the Z-values of the potential occluders may be determined by graphics hardware. In that embodiment, potential occluders are sent to the graphics hardware to be drawn, and the Z-values associated with the potential occluders are returned from the graphics hardware (e.g. by reading the h
Brier Jeffery
Good-Johnson Motilewa
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
Occlusion culling for complex transparent scenes in computer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Occlusion culling for complex transparent scenes in computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Occlusion culling for complex transparent scenes in computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2901652