Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-03-17
2001-10-09
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06300956
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to the art of computer graphics and computer generated animation. More particularly, the invention relates to the use of, and means for smoothly transitioning between, different representations of objects depending on the object's visibility and importance in the rendered scene.
In computer rendering (digital image synthesis) objects in the synthesized image must be mathematically represented in three dimensional object space. This is achieved by modeling the object's bounding surfaces as a collection of geometric primitives. Typically, the primitives are simple polygons or more complicated surface elements defined by non-linear paramatized curves (e.g. NURBS (Nonuniform Rational B-Splines)).
The realism obtainable in the resulting image depends to a large degree on the number and complexity of the primitives used to represent the objects. The flip side is that more., and more complex primitives require more computations, i.e., more time and memory. A given object, depending on its position in a scene and distance from the viewer, need not always be represented with the same level of detail. Thus, it is possible to use multiple representations of a given object with varying levels and types of primitives. One can use only a few simple primitives to describe an object when it is far away in a scene and a more complex description when it is viewed up close.
The technique of matching the complexity of the object description to the object's visibility and the limits of resolution is known generally as level-of-detail (LOD) computation. LOD schemes eliminate geometric primitives that are too small to make a significant individual color contribution to the final image, in some cases by replacing large collections of such primitives by a smaller collection of larger primitives that will generate approximately the same aggregate color contribution to the final image. A particular object representation may have a finely detailed version for close-ups, a simple version for distant shots, and perhaps several levels in between.
This has two obvious benefits to the rendering system: it reduces the total number of geometric primitives to process and it replaces tiny subpixel primitives with larger primitives that are easier to antialias because the renderer's sampling rate is less likely to be below their Nyquist limit. An early description of the usefulness of having multiple representations of a single object is found in Clark, J. H., “Hierarchical Geometric Models for Visible Surface Algorithms”,
Comm. ACM,
19(10):547-554 (October 1976). Flight simulators have used multiple levels of detail for many years to reduce scene generator workload. These simulators select among several object representations on-the-fly based on the objects actual or foveal (centrality in the pilots field of view) distance from the viewer. Similarly, Funkhouser and Sequin used multiple levels of detail to maintain a constant frame rate for interactive walkthroughs, using a cost/benefit analysis of perceived scene quality verses frame rate to select among detail levels. Funkhouser, Thomas A. and Sequin, Carlo H., “Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments”,
Computer Graphics Annual Conference Series
1993, pp. 247-254.
In both the flight simulators and Funkhouser and Sequin walkhrough, the transition between object representations is instantaneous and discrete resulting in “popping”, a visual artifact that is unacceptable for high quality computer animation. Attempts to smooth these transitions have focused on interpolating between the geometric representations. See, e.g., Certain A., J. Popovic, T. DeRose, T. Duchamp, D. Salesin, W. Stuetzle, “Interactive Multiresolution Surface Viewing”,
Computer Graphics
Annual Conference Series 1996, pp. 91-98; Hoppe, Hugues, “Progressive Meshes”,
Computer Graphics
Annual Conference Series 1996, pp. 99-108, 1996; Turk, Greg, “Re-tiling Polygonal Surfaces”,
Computer Graphics
26(2):55-64, July 1992; Hoppe, Hugues, T. DeRose, T. Duchamp, J. McDonald, W. Stuetile, “Mesh Optimization”,
Computer Graphics
Annual Conference Series 1993, pp. 19-26. All of these methods depend, however, on particular geometric representations which must be used to represent the models at all detail levels. The object representations must also retain the identical topology, so that they can be related to each other by smooth interpolations. None of the prior methods allows one to create smooth transitions between representations with arbitrary modeling primitives, topologies, and shading paradigms, including smooth transitions between arbitrary three dimensional geometric representations and approximations of them using displacement or texture maps.
Another technique to obtain smooth transitions between different object representations requires rendering the images using both representations and cross-dissolving between the images at the pixel level. This technique is inefficient, requiring multiple renderings of each object, and results in poorer image quality because the visibility computation is only approximate at the whole pixel level and does not fully account for antialiasing, reconstruction filters, or motion blur already applied to these pixels. Moreover, cross dissolving between rendered scenes at the pixel level requires that all objects in the scene transition in the same manner, or else one must render a multitude of scenes with various combinations of different object representations and somehow cut and paste between them to form the desired cross dissolve.
SUMMARY OF THE INVENTION
The present invention solves the “popping problem” efficiently with results suitable for high quality animation. It allows the rendering of smooth transitions between different object representations of arbitrary type and topology without visual artifacts or discontinuities and without the need for pixel level post processing. The present invention is an extension of the elegant and powerful stochastic sampling techniques used in many high quality renders to perform spatial antialiasing, and produce motion blur, depth of field and soft shadows. These methods are described in U.S. Pat. Nos. 4,897,806; 5,025,400 and 5,239,624 entitled “Pseudo-Random Point Sampling Techniques in Computer Graphics” which are assigned to Pixar, and are incorporated herein by reference.
The conceptual underpinning of the present invention is the treatment of the level of detail (or other range over which one characterizes differing object representations) as an additional “dimension” like screen position, lens position or time, over which one approximates integration by stochastic sampling. In the disclosed embodiment, this is done by associating with each screen space sample of the object scene an additional random variable, the representation dimension deviate m. In a transition region in which more than one object representation may contribute, the object representation sampled depends on the random variable m and the weighting of the object representations within the ensemble depends on an image based selection criteria, e.g., the screen size of the object.
By combining the techniques of the present invention with those of Cook et al. one can, in a unified way without post processing or pixel level manipulations, produce smooth efficient animation incorporating multiple levels of detail, antialiasing, motion blur, depth of field and soft shadows in which visibility is correctly determined at each sub-pixel sample location.
Because in the present method individual samples are evaluated against a single LOD representation for each object, and visibility is computed correctly for each subpixel sample, it is more efficient and produces better images than can be obtained by cross-dissolving at the pixel level images separately rendered from different object representations. In addition, because the present invention does not depend on, or constrain, the details of the geometric rep
Apodaca Anthony A.
Gritz Larry I.
Vande Wettering Mark T.
Arent Fox Kintner & Plotkin & Kahn, PLLC
Pixar Animation
Vo Cliff N.
LandOfFree
Stochastic level of detail in computer animation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Stochastic level of detail in computer animation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stochastic level of detail in computer animation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2573591