Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-03-30
2001-02-06
Powell, Mark R. (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06184887
ABSTRACT:
This invention pertains to computer graphics, and more particularly to a system for preventing overflow and underflow of image variables by limiting the minimum dimensions of polygons.
BACKGROUND
It is well known how to generate three-dimensional computer graphics images by modeling three-dimensional objects as a composite of two dimensional polygons, such as triangles. Texture mapping is then typically used to create more detail and realism in an image without geometrically modeling and rendering every three-dimensional surface.
Texture maps are sampled to determine the color of the display pixels of each polygon that is visible. The appearance of a pixel of an object is typically dependent on several functions such as: RGB components of color, alpha translucency, image depth (Z), and texture coordinates. The function values of an image pixel are determined by interpolation using function gradients in the x and y directions. Functions that are interpolated over triangular areas are of the form:
f
(
x
,
y
)
=
f
(
0
,
0
)
+
∂
f
∂
x
*
x
+
∂
f
∂
y
*
y
where:
f(x,y) is the function at a reference point on the image;
∂
f
∂
x
is the function gradient in the x-direction; and
∂
f
∂
y
is the function gradient in the y-direction.
On images where triangular polygons are used, for narrow triangles the interpolation function gradients can exceed the dynamic range of the system. In graphics systems each variable is typically allocated a predetermined number of bits. The number of bits that can be allocated for each variable is limited by the available hardware resources. For example, if a value is represented by an 8-bit integer variable its dynamic range is from 0 to 255. If a large gradient causes the value to exceed 255, then the value can wrap around, causing the wrong value to be stored. For example, if a color value wraps around then the pixel may appear white instead of black.
In a conventional graphics system the color of a polygon is defined by a plane equation consisting of a reference value, a horizontal gradient, and a vertical gradient. The color of each pixel is computed as the color at the center of the pixel. For each pixel, the sampling point is at the pixel center. In general, polygon edges cover only part of a pixel. In a quantized approach, the polygon is displayed in a pixel whenever the center of that pixel is inside of the polygon. In an antialiased approach, the polygon contributes only partially to the pixel color, even when the center of the pixel is outside of the polygon. For these pixels the extrapolated color components could overflow or underflow (i.e. wraparound). The maximum distance error of the sampling point occurs when the polygon edge is near a pixel corner. In this case the distance error is 0.5*sqrt(2) which is 0.7 pixel.
In conventional graphics systems gradient underflow and overflow often causes images to be displayed with artifacts. Such artifacts may include a pixel being displayed in the wrong color, or a pixel that is rendered at the wrong depth (Z), or a pixel with incorrectly sampled texture coordinates. Such artifacts may also cause images to appear to have jagged edges, and generally detract from the quality of the image display. In many graphics systems this poor image quality is accepted as being necessary to achieve desired performance levels.
One prior approach to limiting gradients is illustrated in FIG.
1
. The method identifies triangles that are narrower than a defined threshold width and increases the width of those triangles to the minimum width. The width of the triangle in the x-direction is defined by the equation:
dx
—
min
=(
slope
1
−slope
2)*&Dgr;
y
where:
dx_min is the width of the triangle in the x-direction;
slope 1 is the slope of one side of the triangle;
slope 2 is the slope of a second side of the triangle; and
&Dgr;y is the height of the triangle.
When the difference between slope 1 and slope 2 is small this indicates a narrow triangle. When the product of the difference of the slopes and the triangle width is less than the minimum width, then the width of the triangle is temporarily increased to at least equal the minimum width, for the purpose of gradient computations.
SUMMARY
The present invention provides a system for avoiding overflow and underflow of image variables by clamping image gradients. The method is described with respect to a triangular polygon to be rendered and a function for that polygon such as color. First the delta x and delta y values between each of the vertices of the triangle are computed. In one embodiment, using the delta x and delta y values, the area of the triangle is computed from the cross product of the vectors that define the triangle. The sign of the triangle area is used to determine whether the triangle is visible. If the triangle is visible then the method determines whether the width of the triangle in the x-direction, dx_min, is at least equal to a minimum threshold. To make this determination, first the vector with the largest delta y is selected. Using the largest delta y value, dx_min is computed by the equation dx_min=area/(largest delta y). If dx_min is less than the threshold value, then a correction value is computed. This test uses intermediate values of the gradient computations and thereby minimizes the extra time that the gradient clamping test requires. The position of the vertex that is not part of the vector with the largest delta y is then corrected using the correction value. Making dx_min greater than or equal to the minimum threshold ensures that the dfx function gradients do not exceed the dynamic range of the system variables. A similar method is performed to correct the height of the triangle, dy_min, if it is less than the minimum threshold. If any vertex has been moved during the dx_min or dy_min test, the triangle area needs to be recomputed.
After the required vertex position corrections have been made, the area of the new triangle is computed. Next, the delta x and delta y values are divided by the triangle area to yield scaled dx and dy values. The function gradients are then computed using the equations dfx=df12*scaled_dy23−df23*scaled_dy12, and dfy=scaled dx12*df13−scaled dx23*df12. Lastly, the function gradients are used to compute the function value at a reference point. Additional function values are then obtained by interpolating from the reference point.
REFERENCES:
patent: 5101442 (1992-03-01), Amir
patent: 5224208 (1993-06-01), Miller, Jr. et al.
Caserza Steven F.
Flehr Hohbach Test Albritton & Herbert LLP
Harrison Chante' E.
Oak Technology, Inc.
Powell Mark R.
LandOfFree
Method and apparatus for clamping image gradients 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 clamping image gradients, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for clamping image gradients will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2558134