Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2002-04-16
2003-04-15
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06549203
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention relates to computer graphics and, more particularly, to improved methods and arrangements for use in rendering lighting and shadows in computer graphic simulations, such as, for example, interactive computer graphics simulations of multi-dimensional objects.
BACKGROUND OF THE INVENTION
Computer generated graphics are becoming more popular in everyday computing especially given recent advances in affordable computer hardware and software. This trend is expected to continue in the foreseeable future. By way of example, interactive computer generated graphical images are becoming increasingly detailed and more realistic due to increased processing capabilities in personal computers (PCs). No where is this more evident than in the computer gaming arena, wherein virtual three-dimensional (3D) worlds are created in software and interactively explored by the computer's user.
As with the real World, these virtual 3D worlds consist of a plurality of 3D objects. These 3D objects are typically modeled by one or more polygons. In the computer, depending upon the orientation of the scene being viewed, some of these polygons correspond to individual pixels that are displayed on the computer's display screen. Within the computer, these pixels are represented by data that can be manipulated and stored in at least one data base. For example, once the arrangement of these 3D objects with respect to one another has been determined for a particular viewpoint, the rendered scene of the 3D world is projected onto a two-dimensional (2D) frame that can be displayed to the user. The frame is typically a data base that contains pixel color information with regard to the display screen.
A sense of motion within this virtual 3D world is provided by incrementally altering the arrangement of these 3D objects and quickly re-displaying the transformed frame. Typically, a frame rate of at least about twenty-five (25) frames-per-second (fps) is desired to convey a sense of motion.
Rendering such interactive 3D worlds, however, typically requires that millions of calculations be conducted between frames (i.e., in “real time”). Since there is a limit to the amount of processing that a computer can provide between frames, simplifications or other compromises often need to be made in modeling a 3D world. Additionally, advanced algorithms are implemented in either hardware and/or software to further streamline the processing of the resulting 3D scene and 2D images. Regardless of how the rendering computations are completed, the goal remains the same, namely, to provide a realistic, interactive virtual 3D world to the user.
One of the unfortunate compromises made in the past, has been in the area of lighting and, more particularly, in the area of rendering shadows cast by lighted 3D objects. Many shadow rendering processes have been considered to be too compute intensive for most lower-end computer applications, and as such shadow rendering is often ignored or otherwise greatly simplified. Several advanced and simplified shadow rendering algorithms and other graphical algorithms and techniques are described by James D. Foley, et al. in
Computer Graphics: Principles and Practice
, second edition, 1997 (ISBN 0-201-84840-6), published by Addison-Wesley Publishing Company, Inc. This text is expressly incorporated herein, by reference, in its entirety and for all purposes.
By way of a particular example, Foley et al. describe a promising two-pass object-precision shadow algorithm in Section 16.4.2 of the text. This two-pass shadow algorithm, developed by Atherton, Weiler and Greenberg, essentially determines which portions on a 3D object's surfaces are visible from the perspective of a light source (i.e., from the light source's view point). This requires converting the data for the 3D object, as represented in a data base, from a modeled world coordinate to a light source coordinate and then determining which portions of the various polygons are visible surfaces with respect to the light source, for example, using a hidden-surface removal algorithm. Since these visible portions are illuminated (i.e., lit) by the light source, the remaining portions (i.e., the hidden-surfaces) are darkened as being shaded from the light. The resulting data is then transformed back to modeling world coordinates and merged with the original object data base. This creates a viewpoint-independent merged data base that can be used to determine the shadows on the various 3D objects from any other viewpoint. This is the first step of the two-step shadow algorithm.
In the second step of the two-pass shadow algorithm, the data in the merged data base is then converted from the modeled world space to a corresponding screen (or camera) viewpoint. Then, a hidden-surface algorithm is used to determine which portions of the various polygons are visible surfaces with respect to the camera. These visible portions are identified as being visible to the camera and as being either not-darkened (i.e., lit) or darkened (i.e., in a shadow). A polygon scan-conversion algorithm is then used to render the resulting 2D image.
One of the drawbacks to this type of shadow algorithm is that unrealistic shadowing can occur in scenes having multiple light sources. Foley et al. for example, one page 747 of their text, teach that multiple light sources are handled by re-processing the merged data base for each new light source. Thus, for example, assume that a portion of a polygon which is visible from the camera viewpoint has been darkened because it is shaded from a first light source. This is information is recorded in the merged data base. Then, this merged data base is used as the starting point for a similar process for the second light source's viewpoint determination. As part of this second light source's viewpoint determination, additional darkening can occur to portions of the scene that are also shaded from the second light source. As a result, there is a potential for a portion of the scene to be darkened twice. In scenes having multiple light sources, including ambient light, this additive darkening of portions, and in particular, pixels, tends to reduce the realism of the shadowing effects and can lead to awkward shadowing cross-talk, wherein a shadow is made overly dark and has unrealistic transitions. This is especially true for applications using a “stencil buffer” technique for shadowing.
Additionally, when there are several light sources, for example, four or more, the transformation process associated with converting between the camera, world, and light viewpoints in support of this type of two pass algorithm can prove to be too burdensome, thereby inhibiting or otherwise diminishing the effectiveness of the resulting interactive real-time graphics.
Consequently, there is need for improved shadow rendering methods and arrangements. Preferably, the improved shadow rendering methods and arrangements support real time interactive graphics on conventional PCs and the like, and allow for multiple light sources to be modeled in a more efficient and realistic manner.
SUMMARY OF THE INVENTION
The present invention overcomes the foregoing and other problems with a shadow rendering system and method for use in a graphics device wherein observer data is provided of a simulated multidimensional scene as is lighting data associated with at least one simulated light source to illuminate said scene. For the at least one light source, a comparison of at least portion of the observer data is made with at least a portion of the lighting data to determine if a model point within the scene is illuminated by the light source. If so, a portion of the light image data associated with a said model point is stored in a portion of a frame buffer of the system. Light accumulation data stored within the frame buffer is combined with the observer data to create a rendered image and the resulting image data is output to a computer screen.
REFERENCES:
patent: 5704024 (1997-12-01), Voorhies et a
Jenkens & Gilchrist P.C.
Terminal Reality, Inc.
Vo Cliff N.
LandOfFree
Lighting and shadowing methods and arrangements for use in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lighting and shadowing methods and arrangements for use in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lighting and shadowing methods and arrangements for use in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3085436