Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-10-13
2002-05-07
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06384822
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to 3-D computer graphics and more particular to rendering shadows cast by objects in a 3-D scene.
2. Description of the Relevant Art
Realistic 3-D rendering of a scene requires rendering shadows cast by objects in the scene. The importance of shadow in locating an object relative to a plane is depicted in
FIGS. 1A and 1B
. Note that in
FIG. 1A
it is not clear whether the sphere is touching the plane while in FIG. B the rendering of the shadow makes the relationship clear.
For static scenes shadows can be rendered using a ray casting procedure. However, for animation, such as utilized in 3-D computer games, shadows must be rendered in real time. Shadows create dramatic effects in games, for example making monsters look more sinister. Additionally, if a game is played by multiple players, shadows enhance the game quality because opponents may be able to see a shadow before the actual game character appears on the screen.
One real-time prior art shadow rendering technique utilizes a stencil buffer. As is well-known in the art, when rendering a scene each object in the scene is drawn. A depth value, called the z value, is calculated to indicate the distance to the last polygon drawn for each pixel on the screen. The z-values for all the pixels on the screen are referred to as the z buffer. Before the scene is rendered, the z buffer is initialized to a maximum distance. As each polygon is drawn there may be hits to a given pixel from more than one polygon. A standard z-test is performed where the z value of the present polygon is compared to the z value stored in the z buffer. The new polygon passes the z-test only if its z value is less than the z value stored in the z buffer, indicating the present polygon surface is in front of the previous polygon surface stored in the pixel. Accordingly, after all the polygons are drawn each pixel is left with the value of the front-most surface of the front-most object. Therefore, the z buffer stores the depth information for each pixel.
A stencil buffer is an additional buffer of per-pixel information, much like a z-buffer. Common stencil/z-buffer formats are 15-bit z and 1-bit stencil, or 24-bit z and 8-bit stencil. It is possible to perform simple arithmetic operations on the contents of the stencil buffer on a per-pixel basis as polygons are rendered. For example, the stencil buffer can be incremented or decremented, or the pixel can be rejected if the stencil value fails a simple comparison test. This is useful for effects that involve marking out a region of the frame buffer, and then performing rendering only on the marked (or unmarked) region. Good examples are volumetric effects like shadow volumes.
Thus, for example, the stencil buffer could be set only for pixels in an area in shadow and then the area in the shadow is filled with a transparent gray rectangle or the light for each pixel could be reduced to create a shadow effect.
The standard prior art technique first calculates a shadow volume which is defined by transparent polygons (Crow, F. C., “Shadow Algorithms for Computer Graphics,” SIGGRAPH 77,242-247). A shadow volume for a first scene object is the region of space in which a first object will cast a shadow on any other object appearing in that region. Like any other volume in computer graphics, it is usually represented as a polygon mesh. The art provides a variety of techniques for constructing shadow volumes. In “Computer Graphics, Principals and Practice,” second edition, Folly, Van Dam, Feiner, Hughes, on page 749, chapter 16.4.3 describes this technique and also includes bibliographic references.
A technique for using the stencil buffer to render shadows based on a shadow volume
10
is depicted in
FIG. 2. A
scene with a shadow volume is rendered in three stages. First, the scene without the shadow is rendered as usual to a bitmap
11
, configured as a rectangular grid of pixels, using the z-buffer. Thus, the z buffer holds the instances from a viewpoint
12
to all the polygons rendered in the scene.
Next, the shadow is marked out in the stencil buffer as follows. The faces of the shadow volume
10
are drawn using invisible polygons
14
and
16
. A polygon is front facing if the dot product of its outward normal with the vector from the viewpoint to the scene is negative. (For opaque solids, the front-facing polygons are the ones that the can be seen from the view point.) A polygon is back facing if the dot product of its outward normal with the vector from the viewpoint to the scene is positive. (For opaque solids, the back-facing polygons are the ones that cannot be seen from the viewpoint.)
In this example, only one back-facing polygon
14
, having a normal vector
14
n
pointing away from the viewer
12
, and one front facing polygon
16
, having a normal vector
16
n
pointing toward the view
12
, are depicted. The z-testing procedure is enabled so that the depth of the shadow volume pixels will be compared with the depth of the scene pixels but z-writes are disabled so that the z-buffer will not be changed by the test.
The invisible front facing polygon
16
is rendered first. For each pixel the z-test is conducted and the stencil buffer entry for that pixel is incremented only if the z-value of the front facing pixel passes the standard z-test. The invisible back facing polygon
14
is rendered second. For each pixel the z-test is conducted and the stencil buffer entry for that pixel is decremented only if the z-value of the back facing pixel passes the standard z-test.
The results of this technique are depicted in FIG.
2
. For pixels p
1
representing a first scene polygon
20
located behind the shadow volume
10
the stencil buffer entry is decremented when the back-facing polygon
14
is drawn and incremented when the front facing polygon
16
is drawn so that the stencil buffer entry remains zero, i.e., the first scene polygon is not in the shadow.
For pixels p
2
representing a second scene polygon
22
located within the shadow volume
10
the pixel fails the z-test when the back facing polygon
14
is drawn, so the stencil entry is not decremented, but passes the z-test when the front facing polygon
16
is drawn so the stencil buffer is incremented for a net increment of the stencil buffer entry, i.e., the second scene polygon
22
is in the shadow.
For pixels p
3
representing a third scene polygon
24
located in front of the shadow volume
10
, the stencil buffer entry is neither decremented when the back-facing polygon
13
is drawn nor incremented when the front facing polygon
16
is drawn because the pixel fails the z-test for each shadow volume polygon. Therefore, the stencil buffer entry remains zero, i.e., the third scene object is not in the shadow.
A problem with the prior art technique occurs when the viewpoint is within the shadow volume, or, more generally, when the shadow volume intersects the near clipping plane of the viewing frustum, as depicted in FIG.
3
. All the shadow volume polygons are back facing. However, for a fourth scene object
30
located within the shadow volume
10
, the z-test fails for the back facing polygons so that the stencil buffer entries remain zero. Thus, the fourth scene object is not in a shadow, which is incorrect.
A solution to the problem is to set the stencil buffer to I for all polygons within the intersection of the shadow volume and the viewing frustum. However, doing so requires the determination of the shape of this intersection, which can be complex.
Accordingly, improved techniques are required for rendering shadows in real-time to add realism and drama to 3-D video applications.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, an improved method for creating shadows in 3-D graphics relies solely on z-testing to set the stencil buffer bits for the shadows, regardless of whether the viewpoint is within the shadow volume.
According to another aspect of the invention, a new z-test inverts the standard z-test so that only pixels
Bilodeau William
Songy Michael
Creative Technology Ltd.
Nguyen Phu K.
Townsend and Townsend / and Crew LLP
LandOfFree
Method for rendering shadows using a shadow volume and a... 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 rendering shadows using a shadow volume and a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for rendering shadows using a shadow volume and a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2868339