Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1997-09-12
2001-12-11
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C708S654000
Reexamination Certificate
active
06330000
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to texturing and shading of 3-D images for display on a screen.
BACKGROUND OF THE INVENTION
The method most commonly used by commercial systems to generate textured and shaded real-time 3-D images uses a Z-buffer system. This is one of simplest visible-surface algorithms to implement in either software or hardware and is used by such companies as Silicon Graphics, Evens & Sutherland, and Hewlett Packard.
It requires that we have available not only a frame buffer in which colour values are stored, but also a Z-buffer, with the same number of entries, in which a z-value is stored for each pixel. Polygons, normally triangles, are rendered into the frame buffer in arbitrary order. During scan-conversion, if the polygon point is not further from the viewer than the point already in the buffer, then the new point's textured and shaded colour is evaluated and the z-value replaces the old value. No pre-sorting is necessary and no object-object comparisons are required.
The term “Texture Mapping” refers to the process of transforming a 2D array of pixels onto another 2D array of pixels. The transformation can be completely arbitrary, but in this document we will consider perspective mapping. Perspective mapping effectively takes a 2D array of pixels, rotates and translates them into 3D and then projects them onto a z=n plane for display.
Texture mapping is used in computer graphics to try to mimic the surface detail of real objects. Using perspective mapping, it is possible to place a picture (e.g. the surface of wood onto a 3D object (e.g. a table). The result being that the table has the appearance of wood.
The equation for perspective mapping is given below.
u
=
ax
+
by
+
c
px
+
qy
+
r
v
=
dx
+
ey
+
f
px
+
qy
+
r
‘u’ and ‘v’ are the 2D coordinates in texture space.
‘x’ and ‘y’ are the 2D coordinates in screen space.
‘a’, ‘b’, ‘c’, ‘d’,‘e’, and ‘f’ are the coefficients used in the mapping process.
Sampling a signal that has frequencies above half the sample rate causes aliasing. Texture mapping is a re-sampling process which can easily cause aliasing. To produce a texture mapped image that does not alias, one has to low pass filter the image in texture space to half the sample rate of the mapping. A complication to the situation is that the sample rate may vary depending on the position in screen space.
To correctly filter the image, one requires a large amount of processing. There are many ways to approximate the correct filtering with mathematically simpler operations. The simplest method is MIP Mapping where MIP stands for MULTIM IMPARVO.
MIP Mapping requires a pre-processing stage where a texture map stored in memory is filtered and decimated to half the resolution. This is repeated until the resulting image is 1 pixel in size (this does assume that the texture is square and a power of 2).
FIG. 1
shows an example of a brick texture at 128×128 resolution with the associated lower MIP Map levels.
A MIP Map can be thought of as a pyramid of images. The MIP Map is accessed through 3 variables ‘u’, ‘v’ and ‘D’. The variables ‘u’ and ‘v’ are the coordinates of the pixel in texture space that is required to be anti-aliased. The variable ‘D’ is a measure of how filtered that pixel is required, i.e. how high up the pyramid. The value D=1 means that the full resolution image is used. The value D=2 means the half resolution image is used, and so on. When values of ‘D’ are not powers of 2, a blend of the two nearest mip-map levels are calculated using linear interpolation in a well know manner.
Ideally, ‘D’ is the square root of the area that the screen pixel covers when it is transformed into texture space. Unfortunately, this is extremely expensive to calculate on a pixel by pixel basis.
P. S. Heckbert (Comm ACM 18(6) June 1975) suggested using the following approximation for ‘D’:
D
2
=
MAX
ⅆ
u
2
ⅆ
x
+
ⅆ
v
2
ⅆ
y
,
ⅆ
u
2
ⅆ
y
+
ⅆ
v
2
ⅆ
y
Although this method is far simpler than the ideal, it still requires a square root, and two additional mappings per pixel.
Shading is a term used in computer graphics which refers to part of the process of evaluating the colour of a surface at a particular screen position. When a surface is shaded, the position, orientation, and characteristics of the surface are used in the modelling of how a light source interacts with that surface.
The realism of computer generated images depends considerably on the quality of this illumination model. Unfortunately an accurate lighting model is too expensive to use in a real time rendering system. It is therefore necessary to compromise and use approximations in the lighting calculations.
The most common form of approximation is diffuse or lambert shading, which simulates the light reflected from matte components of materials. This is illustrated in FIG.
2
and the following equation:
I
(
L
,
S
,
θ
)
=
LS
(
cos
θ
)
if
(
cos
θ
)
≤
0
0
if
(
cos
θ
)
<
0
FIG. 2
illustrates a light ray emanating from the eye or camera, (which passes through a particular screen pixel) and strikes a surface at a given point, P. It also shows the vector, the normal, which is perpendicular to the surface at P, and a ray from a light to P.
The equation states that the intensity (or colour), I, of the diffuse illumination at P is the product of the light's intensity, L, the diffuse reflectivity of the surface, S, and the cosine of the angle between the light ray and the normal &thgr;.
This calculation can either be assumed constant for an entire surface, which is known as flat shading, or can be interpolated in various ways across polygonal facets to stimulate curved surfaces. Gouraud shading (Comm ACM 18(60) pp. 311-17, 1971) for example, is the linear interpolation of the diffuse colours across the polygonal facets.
An alternate manner of interpolation is to linearly interpolate the surface normals, in the above equation. This method was proposed by Bui Thuong Phong (Comm ACM 18(6) June 1975). Unfortunately, this computation is relatively expensive. An effective approximation has been proposed by Bishop and Weimer (Computer Graphics 20(4) pp. 103-6, 1975) which uses 2 dimensional Taylor series approximations. These approximations can be evaluated efficiently using differences equations. Apart from a small precalculation overhead, the cos &thgr;, can be approximated at the cost of only 2 addition per pixel.
The next most common lighting feature that is simulated is glossy or specular highlights. These are the reflections of the lights in a scene. Specular highlights give surfaces a reflective appearance, and greatly improve the realism of images. They are most commonly approximated by a method again described by Bui Tuong Phong, which is illustrated in FIG.
3
and in the following equation.
I
(
L
,
S
,
θ
,
n
)
=
LS
(
cos
θ
)
n
if
(
cos
θ
)
≥
0
0
if
(
cos
θ
)
<
0
FIG. 3
, illustrates a ‘ray’ emanating from the eye or camera, which passes through a particular pixel, and strikes a surface at a given point, P. It is then reflected in the shown direction using the usual mirror angles. Note that because surfaces are not perfectly smooth, the reflected ray is assumed to spread out to some degree, governed by the roughness of the surface. Finally,
FIG. 3
also shows a ray coming from a light which will appear as a highlight. The closer the reflected direction is to the light, the brighter the highlight will appear.
The equation describes the intensity of the highlight, I, as a function of the intensity of the Light, L, the reflectivity of the surface, S, the angle between the reflected direction and the light, &thgr;, and the smoothness of the surface, n. This function means that as the reflected direction approaches the light direction, (i.e. &thgr; gets small), the
Dunn Mark Edward
Fenney Simon James
Leaback Peter David
Overliese Ian James
Yassaie Hossein
Flynn ,Thiel, Boutell & Tanis, P.C.
Imagination Technologies Limited
Padmanabhan Mano
Zimmerman Mark
LandOfFree
Method and apparatus for performing arithmetic division with... 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 and apparatus for performing arithmetic division with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing arithmetic division with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2571368