Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-11-29
2002-08-27
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06441817
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to the field of three-dimensional graphics rendering. Specifically, the present invention is related to the problem of calibrating the z-buffer granularity or depth based upon the objects in a scene.
2. Discussion of the Related Art
A Z-buffer is an area in graphics memory reserved for storing the Z-axis value of each pixel. Z-buffing is an algorithm used in 3-D graphics to determine which objects, or parts of objects, are visible and which are hidden behind other objects. With Z-buffering, the graphics processor stores the Z-axis value of each pixel in a special area of memory called the Z-buffer. Different objects can have the same x- and y-coordinate values, but with different z-coordinate values. The object with the lowest z-coordinate value is in front of the other objects, and therefore that's the one that's displayed.
3-D graphics is the field of computer graphics concerned with generating and displaying three-dimensional objects in a two-dimensional space (e.g., the display screen). Whereas pixels in a 2-dimensional graphic have the properties of position, color, and brightness, a 3-D pixels adds a depth property that indicates where the point lies on an imaginary Z-axis. When many 3-D pixels are combined, each with its own depth value, the result is a three-dimensional surface, called a texture. In addition to textures, 3-D graphics also supports multiple objects interacting with one another. For example, a solid object may partially hide an object behind it. Finally, sophisticated 3-D graphics use techniques such as ray tracing to apply realistic shadows to an image.
Converting information about 3-D objects into a bit map that can be displayed is known as rendering, and requires considerable memory and processing power. In the past, 3-D graphics was available only on powerful workstations, but now 3-D graphics accelerators are commonly found in personal computers. The graphics accelerator contains memory and a specialized microprocessor to handle many of the 3-D rendering operations.
One of the big challenges of translating 3D environments into rapidly changing 2D frames is fighting out what surfaces are hidden by other objects and should not be visible. Two techniques used to correctly position objects are called Z-sorting and Z-buffering. (The ‘Z’ is the Z-direction of depth.) The Z-sorting algorithm simply arranges polygons in back-to-front order before rendering, and draws the front polygons last. It produces correct results except when objects pass through other objects, in which case they appear as stacked instead of intersecting. Z-sorting is performed by the host CPU and involves considerable overhead which, naturally, translates into lower frame rates.
By contrast, Z-buffering can be effectively implemented in a hardware rendering engine, but at the expense of dedicating more memory to the job. A Z-buffer involves a block of memory equal to the display resolution (e.g. 640×480) multiplied by the number of bits of depth resolution desired (e.g. 16-bits). The Z-buffer algorithm stores a depth value for each pixel in the display. When rendering objects, the engine calculates a Z-value for each pixel and stores that value in the Z-buffer memory location corresponding to the X/Y address of the pixel in the display buffer. The lower the Z-value, the closer the object is to the viewer. When a new pixel is rendered its Z-value is compared with the Z-value of the current pixel and only if the Z-value of the new pixel is less than the one already stored will the new pixel be written to the display buffer.
When rendering 3D objects to the screen, often a z-buffer is used to sort the objects. If the z-buffer is not deep enough, or if it is too finely grained, then two objects will be sorted into the same z-buffer slot. This produces visible anomalies (shimmering) when rendering. To remedy this, developers adjust the z-buffer to be deeper or to be more finely grained based on the situation. However, when the z-buffer is calibrated based upon the objects in a changing scene, the changes in the scene may result in undesirable visual discontinuities as the z-buffer calibration results in different z-buffer depths during each frame, thereby changing the position of each object within the z-buffer from frame to frame.
When rendering 3D objects to the 2D display, a common technique is to sort the objects into a z-buffer. The rendering engine sorts the objects along the z-dimension (into the screen). The z-buffer represents a fixed amount of memory into which the objects are sorted.
Either that memory can represent a large distance (depth) or it can be fine-grained for better resolution when objects are close to one another. For example, when rendering a 3D object representing a book, then the pages are close to one another and the z-buffer must be finely partitioned to keep the objects separate. But when two objects are far apart, such as two spheres representing planets, then the z-buffer must stretch over a large distance.
Programmers can adjust the granularity of the z-buffer based on what is in the scene. When they need high resolution and depth, they must decide what is the best value. For example, they may decide that objects closer to the center of the screen are more valuable to the user, and therefore have more influence on the adjustment of the z-buffer granularity. But if the object is constantly moving in and out of the center of the screen, then this z-buffer adjustment becomes more volatile.
As is apparent from the above discussion, a need exists for determining the weights associated with the objects in a scene for performing the z-buffer calibration before rendering each frame.
SUMMARY OF THE INVENTION
Programmers can adjust the granularity of the z-buffer based on what is in the scene. When they need high resolution and depth, they must decide what is the best value. For example, they may decide that objects closer to the center of the screen are more valuable to the user, and therefore have more influence on the adjustment of the z-buffer granularity. But if the object is constantly moving in and out of the center of the screen, then this z-buffer adjustment becomes more volatile. An object of the present invention is to provide a method for determining the weights associated with the objects in a scene for performing the z-buffer calibration before rendering each frame.
According to the present invention, the weight given to each object in a scene in the computation of the z-buffer granularity is determined based upon a variable risk parameter which may be supplied by the application. In the preferred embodiment, the risk parameter is normalized assuming values between zero and one, inclusive.
The leaf objects in the scene are preferably organized into a binary tree, whose structure may indicate the importance of the leaf objects. Composite parent objects each have two children objects. Children objects are either leaf objects or composite parent objects. Each composite parent object contains both of its children objects and all of the objects contained by both of its children object. The importance ranking of objects is optionally determined by one of a variety of methods. For example, the importance ranking may be predetermined based upon the type of object. Alternatively, the importance ranking is determined by decreasing order of mean hit values determined over a predetermined number of frames. As yet another alternative, the importance ranking of the objects in the scene is determined by the distances of the objects from the observation point. For example, the closest objects may be assigned the highest importance. Some combination of the above described methods for ranking the objects may also be performed in accordance with the present invention.
In a greedy algorithm embodiment, the most important object is a child of the scene object, and each composite parent object has as its two children one leaf object and one composite parent object except th
Gossweiler III Richard Carl
Huberman Bernardo A.
Fliesler Dubb Meyer & Lovejoy LLP
Vo Cliff N.
Xerox Corporation
LandOfFree
Methods and apparatuses for performing Z-buffer granularity... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatuses for performing Z-buffer granularity..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatuses for performing Z-buffer granularity... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2944514