Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
1998-06-18
2001-04-24
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
C703S001000, C345S440000
Reexamination Certificate
active
06222555
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to computer graphics rendering systems for the creation and display of arbitrarily complex scenes, and in particular to methods for improving the apparent performance of such systems under the constraints imposed by operation in real-time.
2. Background Description
Computer systems designed to generate images often are comprised of various stages that can be implemented in combinations of hardware and software. Although there are a great variety of implementations, in general all systems are similar in function. At the coarsest level, computer graphics systems consist of two major components: a database to describe the geometric entities which need to be created, and the rendering pipeline, which transforms this database into a displayed image.
The performance limitations of a computer graphics system are most poignant in real-time situations, where scene complexity is limited by the specific amount of time available to generate the image. For example, real-time image generators (another name for computer graphics rendering systems) commonly must complete and display a new frame every thirtieth of a second. How an image generator implements the various intermediate stages and characterizes its inevitable bottlenecks bounds its performance.
The two most common gauges of performance of a graphics system are its ability to generate geometric primitives, such as polygons, and screen space primitives, such as pixels. (For the sake of clarity, the remainder of this document will discuss polygons and pixels, although the methods described herein would apply equally well to many other methods of image generation, such as parametric surfaces with control points, and non-raster displays.)
Polygon and pixel processing are also the source of two of the major bottlenecks in rendering pipelines. Polygon processing usually dominates the front-end of the pipeline, and is often the limiting factor for the transition between database loading and rendering. Pixels are generated within the rendering pipeline, prior to image display.
One of the challenges of designing computer graphics systems is that simply changing the viewing position of a static database can drastically alter the polygonal or pixel requirements. It is therefore important that methods to extend the apparent capability of computer graphics systems behave in a manner which performs consistently. For real-time situations, solutions which vary widely in effectiveness depending on viewing position are of questionable value, since the worst case is always the constraint limiting performance.
Much of the work aimed at optimizing these systems focuses on the fact that computer imagery is usually generated with a perspective view, as is common in stereo viewing in real life. The representation of a polygon and its pixel coverage changes depending on its position and the viewing position in a perspective scene. The farther away from the viewpoint an object is, the smaller its screen representation. The problem this creates is that perspective scenes of a relatively balanced distribution of objects concentrate object density in the distance. This is directly in opposition to the usual desire to have more detail close to the viewer. This problem is demonstrated in
FIG. 1
, using equal area quadrilaterals. Many methods to improve apparent performance, including the present invention, key on this observation. Note that these methods focus on the front-end of the graphics pipeline
Current Solutions and Their Deficiencies
Far plane clipping
By far the simplest method of reducing distance-based complexity in a scene is to limit the viewing far plane, or the effective distance viewed. This uses the capability of most computer graphics systems to define a clipping plane perpendicular to the line of sight at some distance. Moving this plane closer to the viewpoint reduces the number of objects seen at a distance, and often increases the geometric precision of objects remaining in view.
However, most applications cannot limit the viewing distance arbitrarily, as this method obviously limits the depth of view. Some degree of this solution is usually used in concert with other methods, particularly to handle worst-case situations dynamically.
Narrow field of view
Similar to the far clipping plane are the four (top, left, bottom, right) walls of the viewing volume, or frustum, which represent the edges of the screen extended into the perspective world. Unlike human sight, the field of view, or width and height of the corresponding image, does not have to map precisely to the viewing angle subtended by the viewer's eyes and the physical screen dimensions. One effect of modifying this viewing angle is much like the zoom function of binoculars, where, a narrower field of view (in height or width or both) can reduce overall scene complexity while concentrating on a limited area. When one axis of the field of view is modified without relation to the other, the field of view's aspect ratio is changed.
There are two problems with this solution. One, it breaks the tie between normal human perspective experience and the artificial scene. Forcing a false perspective is disconcerting and may have negative human factors considerations. Secondly, limiting the field of view can severely hamper immersion in a scene. The general goal is to increase the display size and field of view, not reduce it.
Line of sight minimization
A series of techniques designed to reduce the processing required for image generation involves rejecting occluded objects in a scene. If you are in a room of a mansion looking at a solid wall, there is no need to process all the rooms beyond that wall. These methods have the added benefit of reducing depth complexity and corresponding pixel loads, and were developed primarily for interior room viewing situations, such as visual building ‘walk throughs’.
Although useful, these methods have several serious drawbacks for real-time situations. First and foremost, they mitigate scene complexity only in certain situations, and are subject to complete breakdown for many scenes, which is unacceptable for real-time environments. Secondly, many of the algorithms require occlusion preprocessing, which is both computationally and representationally demanding for large databases. Finally, hybrid solutions require a two-stage rendering process with buffer and object processing feedback, an unrealistic demand on current generations of graphics hardware. By itself, this method is unsuitable for arbitrary scene reduction.
Level of Detail (LOD) transitions
By far the most generally useful method for scene complexity reduction is employing Levels of Detail (LOD's). A database created with multiple LOD's allows the geometric density of the database to vary depending on viewing distance. For instance, a building seen from a distance might be represented by a cube, but when viewed close up it may have much greater geometric detail. (Note: geometric detail is not to be confused with detailed surface textures. They are independent concepts.)
The LOD method allows dynamic optimization of the apparent detail in a scene by concentrating the greatest effort of the image generator on the objects viewed at a close range. In situations where the eyepoint or the objects viewed are moving, LOD's allow different representations on the fly. This introduces one of the chief drawbacks of LOD implementations, transition anomalies. These effects and various partial solutions are described below. The second major drawback of the LOD approach is the need for additional database resources, where each level of detail requires independent object descriptions, increasing the size and complexity of the geometric database.
LOD Transition Anomalies
The most common and simplistic LOD implementation is to have multiple geometric descriptions of the object to be displayed and to simply choose which representation is to be sent to the image generator based on a criteria, usuall
Christofferson Carl L.
Christofferson Frank C.
Christofferson Clyde R.
Christofferson Enterprises, LLC
Padmahabnan Mano
Zimmerman Mark
LandOfFree
Method for automatically smoothing object level of detail... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for automatically smoothing object level of detail..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for automatically smoothing object level of detail... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2448037