Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-01-06
2002-08-20
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S427000, C345S582000, C345S589000
Reexamination Certificate
active
06437782
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer graphics systems, and, more particularly, to rendering shadows generated by computer graphics systems.
BACKGROUND OF THE INVENTION
The entertainment and advertising industries have made computer-generated animations common place today in movie special effects and in commercials, respectively. In addition, games and visual simulations have also created consumer interest in realistic images and animations. Typically, in order to create realistic images and animations, a computer must generate a three-dimensional (3D) scene with various objects and then capture the effects of light interacting between each of the various objects. The computer then generates a new, slightly different two-dimensional (2D) view of the scene many times per second, thereby simulating movement and interaction of the various objects. The computer generation of new, slightly different views is commonly referred to as real time 3D graphics.
Typically, the computer generating multiple 2D graphic views in sequence includes specialized hardware usually referred to as a graphics display processor. The combination of an integrated computer with a display processor is commonly known as a graphics workstation. A graphics workstation runs a 3D graphics application that provides various techniques for simulating the movement and interaction of various objects. Simulating shadows caused by the interaction of the various objects is very desirable because shadows convey a large amount of information necessary for conveying the 3D nature of rendered objects and for adding realism to the computer generated sequence of 2D views. Therefore, a 3D graphics workstation typically provides a technique for generating shadows of 3D objects and rendering these objects along with their shadows onto a 2D view.
Various methods of rendering shadows have been proposed. Many of these methods are described in the publication “Computer Graphics Principles and Practice, Second Edition in C”, Foley et al., Addison-Wesley Publishing Company, Inc., pp. 745-753. Examples of some computationally intense methods of rendering shadows are the two-pass z-buffer shadow method described in an article entitled “Casting Curved Shadows on Curved Surfaces,” Williams, L., Proceedings of SIGGRAPH '78, pp. 270-274 which is also described on pp. 751-753 of the above mentioned publication and the shadow volume method described in an article entitled “Shadow Algorithms for Computer Graphics,” Crow, F. C., Proceedings of SIGGRAPH '77, pp. 442-448 which is also described on pp. 749 of above mentioned publication.
In general, the two-pass z-buffer method involves generating a z-buffer (a shadow map) for an image from a viewpoint of a light (a light coordinate system) with values in the z-buffer representing distances from the light to the object (i.e. closer objects will have a value indicating a higher intensity than farther away objects). A second pass generates a z-buffer for the image from the viewpoint of an observer (an observer coordinate system) using a well known z-buffer algorithm along with a modification that transforms a pixel's observer coordinates into light coordinates whenever that pixel is determined to be visible. Therefore, computations for shadow calculations must be performed for each pixel even if the pixel is ultimately painted over by closer objects. In addition, computations for transforming an object coordinate to light coordinate for every pixel must be performed.
The shadow volume method involves the generation of a shadow volume determined by a volume that is blocked from a light source by an object. A point (or pixel) is then determined to be in shadow by assigning each front-facing shadow polygon a value of +1 and each back-facing shadow polygon a value of −1, and using a counter to increment or decrement accordingly to determine whether the point is in shadow. Because the shadow volume does not require any translation of coordinate systems, the method is fairly efficient to implement if the object is simple. However, if the object is a complex shape, the computation required to calculate the shadow volume becomes very complicated.
Because both the two-pass z-buffer and the shadow volume methods are computationally intense when employed to generate the shadows of complex shaped objects, neither method is desirable for real-time applications. As a result, other, less computationally intense, techniques have been developed. Unfortunately, these other techniques result in poorer quality views because of the introduction of undesirable artifacts. One such other technique is the shadow projection method described in the publication “OpenGL Programming Guide, Second edition,” Woo et al., Addison-Wesley Developers Press, pp. 519-521. In general, the shadow projection method uses a shadow projection matrix to find the shadow of an object on an arbitrary plane using an arbitrary light source. This method avoids the computations necessary to translate the coordinates of an object from one coordinate system to another coordinate system.
FIG. 1
illustrates a view generated using the shadow projection method. A teapot model
10
is shown creating a shadow
12
on a shadow plane
14
as a result of the teapot model
10
blocking simulated rays (not shown) from a light source
16
. The computer represents the shape of the teapot model
10
by using several polygons (i.e. triangles) that approximate the surface of the teapot model
10
, such as a spout polygon
20
, a teapot body polygon
22
(and a teapot handle polygon, not viewable in FIG.
1
). This modeling of an object is well known in the art and is referred to as polygon mesh or polygonal modeling.
To create the shadow
12
, the shadow projection method first multiplies the world coordinates of each polygon representing the teapot model
10
with the shadow projection matrix shown below:
[
b
*
dy
+
c
*
dz
-
a
*
dy
-
a
*
dz
0
-
b
*
dx
a
*
dx
+
c
*
dz
-
b
*
dz
0
-
c
*
dx
-
c
*
dy
a
*
dx
+
b
*
dy
0
-
d
*
dx
-
d
*
dy
-
d
*
dz
a
*
dx
+
b
*
dy
*
c
*
dz
]
(
1
)
where a, b, c, and d are variable obtained from the equation of the shadow plane
14
, ax+by+c+d=0, and dx, dy, and dz represent the distance from a point to the shadow plane
14
. Multiplication by this matrix projects each polygon onto the shadow plane
14
, thus projecting the teapot model
10
onto the shadow plane
14
.
After projecting the teapot model
10
onto the shadow plane
14
, the shadow projection method adjusts colors and textures of each polygon of the teapot model in relation to the objects that were shadowed. In the example shown, only the relation between the polygons of the teapot model itself is shown without showing any interaction of the tea pot model with other objects. This simplification more easily illustrates a disadvantage of using the shadow projection method for generating realistic images, as will be described below.
The adjustment of colors and textures for the teapot model
10
is accomplished by blending each polygon into- the scene. In general, blending is the linear combination of the color for two object's pixels that overlap. Each object has associated alpha values that represent the color for each individual pixel of the object along with the degree of transparency. When two objects are blended, for each pixel that overlaps, one object is considered a top object and the other object is considered a bottom object. Blending results in any pixel whose top object pixel alpha value is non-transparent, taking on the top object's pixel color. Blending results in a linear combination of both the top and bottom objects' pixel color when the top object pixel alpha value has any degree of transparency. Typically, a polygon covers several pixels selected so that each pixel's alpha value representing the color and transparency are the same. Therefore, the alpha value of each polygon represents the alpha value for each individual pixel in the associat
Lacey Stephen J.
Pieragostini Ian B.
Christensen O'Connor Johnson & Kindness PLLC
Microsoft Corporation
Nguyen Kimbinh T.
Zimmerman Mark
LandOfFree
Method for rendering shadows with blended transparency... 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 with blended transparency..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for rendering shadows with blended transparency... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2927995