Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-06-29
2004-12-14
Wong, Don (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S428000
Reexamination Certificate
active
06831636
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of computer image processing. More specifically, the invention relates to the field of level-of-detail selection for rendering.
BACKGROUND OF THE INVENTION
A large portion of the computer graphics literature deals with the rendering problem. For a scene S, composed of modeling primitives (e.g., triangles, spheres, cars), rendering consists of computing a visual representation of the primitives given an eye position, a view direction, and a field of view. Foley et al., “Computer Graphics, Principles and Practice”, Second Edition, Addison-Wesley, Reading, Mass., 1990, which is here incorporated by reference in its entirety, contains further details about rendering.
There are several factors that contribute to the complexity of rendering a scene S. Two important ones are the total number of modeling primitives, and the complexity of each primitive, which can be measured in several ways, for instance, as the number of triangles that define the given primitive.
Resource limitations led inventors to propose several techniques for optimizing the rendering process. One such technique is proposed in U.S. patent application “SYSTEM, PROGRAM PRODUCT AND METHOD OF RENDERING A THREE DIMENSION IMAGE ON A DISPLAY”, Ser. No. 09/296,077, filed Apr. 29, 1999, by J. Klosowski and C. Silva, which is here incorporated by reference in its entirety, where a technique for visibility estimation is proposed.
Another popular technique, originally proposed by J. Clark, “Hierarchical geometric models for visible surface algorithms”, Communications of the ACM, 19(10):547-554, October 1976, for rendering optimization consists of generating several ‘level-of-detail’ representations for each modeling primitive. Originally, a modeling primitive is specified in full detail, also known as full-resolution. Prior art simplification algorithms, which are surveyed in “Survey of polygonal surface simplification algorithms”, in Multiresolution Surface Modeling Course Notes, ACM SIGGRAPH, 1997, by Paul S. Heckbert and Michael Garland, (this survey is here incorporated by reference in its entirety), can be applied to the full-resolution model to reduce the rendering complexity, while still providing reasonable visual fidelity to the original full-resolution model. Using the simplification methods, several level-of-detail representations can be generated for a model, ranging from the full-resolution model, with the greatest rendering complexity, to a very simplified model, with the least rendering complexity. At render time, a single level-of-detail representation is selected for each modeling primitive in an attempt to lower the total rendering cost of the scene, while keeping the visual quality of the final image high. A simple example of this idea is to have different representations for a car, and when the user is looking at it from far away using a simpler representation, since the user will not be able to distinguish fine details of the car anyway, than when the car is nearby, and more details of the car will be visible to the user.
PROBLEMS WITH THE PRIOR ART
The prior art lacks a technique for level-of-detail selection that is based upon visibility information. Rather, prior art techniques base their level-of-detail selection on simple geometric facts, such as screen-space coverage. This coupling of visibility information and level-of-detail representation would provide improved image quality over the prior art at the same rendering cost.
OBJECTS OF THE INVENTION
An object of this invention is an improved system and method for selecting portions of geometry, and their level-of-detail representation to be rendered in an image processing system.
An object of this invention is an improved system and method for selecting portions of geometry and their level-of-detail representation to be rendered within budget constraints.
SUMMARY OF THE INVENTION
The present invention is a technique and system for selecting level-of-detail representations of geometric models to be rendered within an image processing system.
For each modeling primitive, ‘fractional’ visibility estimations are computed, thereby ranking how likely it is that a modeling primitive is visible, given the current viewing position, view direction, and field of view. Using these rankings, an appropriate level-of-detail for each modeling primitive is selected to optimize the rendering process by reducing the overall rendering complexity of the scene S, e.g., by reducing the total number of triangles that need to be rendered, while preserving the quality of the final image produced and displayed upon the screen.
The present invention includes two main steps: (1;) a visibility estimation process; and (2) a level-of-detail selection process.
The visibility estimation process provides estimates, e.g., probabilities, as to how likely it is that each of the modeling primitives in a given scene are visible for the current viewing parameters. In the preferred embodiment, this process is the Prioritized-Layered Projection (PLP) technique discussed in U.S. patent application Ser. No. 09/296,077 incorporated above. The PLP method can provide visibility estimations on a per model basis or upon a per cell basis, where, as described in the aforementioned patent application, the union of all cells provide a subdivision of the space occupied by the models in the scene.
The level-of-detail selection process determines which representations of the models will be rendered to produce the displayed image. Level-of-detail is utilized when the capabilities of the imaging system are not sufficient to render the full-resolution models within a specific budget B, e.g., a specified amount of time. Visibility estimates v
1
, v
2
, . . . , vN, are provided for N modeling primitives m
1
, m
2
, . . ., mN. In the preferred embodiment, the visibility estimates are fractions between 0.0 and 1.0, and will sum to 1.0, although alternative visibility estimates could also be used and then scaled appropriately. Level-of-detail selection can be accomplished on a per model basis by choosing the best representation of the model i that is constrained to the budget of (B times vi). In other words, each modeling primitive is assigned a fraction of the budget B that is directly proportional to its likelihood of being visible. The budget can be either a time constraint or a number of triangles. Since each model will obey its allocated budget, the global budget B for the imaging system will also be met.
REFERENCES:
patent: 5844571 (1998-12-01), Narayanaswami
patent: 5872572 (1999-02-01), Rosignac
patent: 5926183 (1999-07-01), Menon et al.
patent: 6111582 (2000-08-01), Jenkins
patent: 6288730 (2001-09-01), Duluk, Jr. et al.
John Edward Warnock, A Hidden Surface Algorithm For Computer Generated Halftone Picture, Jun. 1969, University of Utah.*
Paul S. Heckbert, et al., “Survey of Polygonal Surface Simplification Algorithms,” School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, May 1, 1997, pp. 1-29.
James H. Clark, “Hierarchical Geometric Models for Visible Surface Algorithms,” Graphics and Image Processing, University of California at Santa Cruz, Communications of the ACM, Oct. 1976, vol. 19, No. 10, pp. 547-554.
Klosowski James T.
Silva Claudio T.
Cao Huedung X.
Percello, Esq. Louis J.
Wong Don
LandOfFree
System and process for level of detail selection based on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and process for level of detail selection based on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and process for level of detail selection based on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3314603