Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-11-29
2002-06-04
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S428000
Reexamination Certificate
active
06400372
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATION
This Application is related to the following Application, which is filed of even date herewith:
“Methods and Apparatuses for Performing Z-Buffer Granularity Depth Calibration in Graphics Displays of Three-Dimensional Scenes,” by Richard Carl Gossweiler III and Bernardo A. Huberman, U.S. application Ser. No. 09/450,237, filed Nov. 29, 1999.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to the field of graphic rendering. Specifically, the present invention is related to the problem of selecting levels of detail for objects having multi-resolution models in complex scenes in order to reduce the graphics rendering load.
2. Discussion of the Related Art
Creating more and more detailed models, consisting of a greater number of polygons, is one way to add visual interest to a scene. However, adding polygons necessitates paying the price of having to manipulate more geometry. 3D systems have what is known as a ‘polygon budget,’ an approximate number of polygons that can be manipulated without unacceptable performance degradation. In general, fewer polygons yield higher frame rates.
When a rendering engine is incapable of drawing the entire scene within the allotted time frame, either the rendering engine must slow down or it must reduce the graphics complexity. Even after culling all of the objects that are not visible, the rendering engine may still not be able to draw everything within the required time frame. A fundamental technique is to reduce the graphics complexity of individual objects in the scene. If the objects have multiple resolutions, then a lower resolution object can be rendered (e.g. a lamp might be represented as a point, or a cube, or a cube with a cone or eventually as a multi-faceted polygonal model).
One aspect of this technique is determining when to transition between one level of detail (LOD) and the next. A common algorithm is to assign a distance range to each level. As the object moves further away from the viewpoint, the resolution changes. But this simple approach ignores important factors such as the cost of performing the transition, or that external parameters (such as lighting conditions, or where the object is in the view) may influence what LOD to present. A fundamental technique for reducing the graphics rendering load when displaying complex scenes is to use multi-resolution models. A common, but simplistic technique for determining when to transition from one level of detail to the next is based on the distance the object is from the viewpoint. This conventional approach frequently leads to undesirable flickering of objects and unstable frame rates.
If there are too many objects and all objects are drawn at the highest level of detail, then there may be too many objects to draw in real time, resulting in a drop in the frame rate below the desired frame rate required for smooth interactivity. For example, the desired frame rate for smooth interactivity could be fifteen frames per second. If the frame rate for a given frame falls below the desired minimum frame rate for interactivity, then the graphics renderer during the next frame may decide to draw some of the objects at lower levels of detail in an attempt to speed up the frame rate in the next frame.
Some approaches to determining levels of detail are task specific. For example, in a scene in which a pilot is attempting to land a plane on a virtual runway, then it is important to always draw the virtual runway at the highest level of detail. Some other approaches to determining levels of detail are task independent. For example, the object in the middle of the scene can always be drawn at the highest levels of detail. Flickering is the sporadic change in the rendering of an object between various levels of detail in successive frames. Flickering of an object in the periphery of a scene may draw the users attention to the flickering object and cause the user to turn the virtual camera toward the flickering object, thereby moving the flickering object into the center of the screen so that it is drawn at the higher levels of detail. Then objects previously in the center of the screen will possibly be in the periphery of the scene and may flicker, causing the user to move the camera back toward the original object. This flickering induced movement of the camera by the user in generally undesirable. Even if the flickering of objects does not alter the user's interactive behavior with the scene, it is nonetheless visually displeasing and therefore undesirable. The flickering may additionally cause unevenness or instability in the frame rate, called hitching, which results in a staccato movement in the scene as the frame rates oscillates.
A conventional algorithm for determining the levels of detail for objects is a greedy algorithm based upon the distance from the observation point or camera. In the greedy approach, the levels of detail for the objects are determined in order of increasing distance from the observation point or camera. In other words, the closest object is drawn at the highest level of detail possible with the remaining graphics resources, and after the closest object is drawn, then the remaining graphics resources are available for the next closest object, and so on until all the graphics resources have been claimed. Other greedy approaches are based upon other measures of the relative importances of the objects instead of distances from the observation point. Greedy approaches suffer from the above-described flickering problems which may indesirably influence the visual appearance and the user's behavior in the interactive scene. A greedy algorithm approach may still result in flickering, as the importance levels change from one object to another. To prevent this, developers are then forced to additionally include dampening functions (for example, weighting functions that retard an object from changing once it has changed).
A conventional approach for solving the above-described flickering and interactivity problems is to maintain the level of detail for an object during consecutive frames that an object is in the scene. However, this approach undesirably results in the consequence that the most important object in the scene (for example, the object in the center and/or closest to the user) is drawn at a lower level of detail if it first entered the scene at a lower level of detail.
As is apparent from the above discussion, a method is needed for determining multi-resolution model transitions in a more powerful and more general manner which can eliminate unnecessary flickering of objects and instability in the frame rate.
SUMMARY OF THE INVENTION
A fundamental technique for reducing the graphics rendering load when displaying complex scenes is to use multi-resolution models. A common, but simplistic technique for determining when to transition from one level of detail to the next is based on the distance the object is from the viewpoint. This conventional approach frequently leads to undesirable flickering of objects and unstable frame rates. According to the present invention, the portfolio method is used to provide a more powerful and more general method for determining multi-resolution model transitions which can eliminate unnecessary flickering of objects and instability in the frame rate.
According to the present invention, the level of detail selected for each object in a scene 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 having levels of detail 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
Gossweiler III Richard Carl
Huberman Bernardo A.
Fliesler Dubb Meyer & Lovejoy LLP
Vo Cliff N.
Xerox Corporation
LandOfFree
Methods and apparatuses for selecting levels of detail for... 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 selecting levels of detail for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatuses for selecting levels of detail for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2948696