Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1996-09-03
2001-09-04
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06285376
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a computer graphics system, and more particularly, to a triangle traversing method and a rasterizer adopting the same, in which Phong shading can be efficiently performed.
In computer graphics, the methods for coloring objects can be divided into two types: one where the color value of a pixel at a curved surface of the object is directly calculated (for example, by ray tracing or radiosity) and another where the object is modeled as a polyhedron having constant color values throughout each face. In other words, a smooth surface is approximated as a polyhedron in order to simplify hidden-surface elimination, and shading calculations are employed to restore the surface's smooth appearance.
Shading algorithms such as Gouraud shading and Phong shading have been suggested. In shading, normals are computed at the vertices of each face and approximate the normal to the true surface at the vertex. Each vertex normal is then used to compute a vertex color value. Then, in Gouraud shading, the color values inside the face are linearly interpolated from the vertex color values. Thus, Gouraud shading, although very simple, has deficiencies, for example, Mach band effects. For remedying such deficiencies, Phong shading has been proposed, in which vertex normals instead of vertex shades are linearly interpolated and then the shade at each pixel is determined based on the shading equation. However, Phong shading entails a complex calculation, which leads to difficulty in its hardware implementation. In addition, the software implementation of Phong shading requires an immense amount of processing time. For instance, for a diffused reflection model, the calculation of the color value at any pixel based on its normal according to the following equation (1) requires seven addition operations, six multiplication operations, one division operation, and one square root calculation.
F
=
I
diffuse
=
I
d
K
d
LN
&LeftBracketingBar;
L
&RightBracketingBar;
&LeftBracketingBar;
N
&RightBracketingBar;
(
1
)
Here, F denotes a color value; I
d
denotes the intensity of a point light source; K
d
denotes a coefficient of scattering refection; L denotes a unit normal vector with respect to the surface; and N denotes a unit vector of the surface.
To reduce the amount of the above computation which is required for performing Phong shading, a new algorithm typically called “fast Phong shading” has been proposed by Gary Bishop and David M. Weimer, in which the shading equation is approximated into two terms of a Taylor series. Consequently, by fast Phong shading, the linear interpolation of normals is converted into a quadratic interpolation of shades.
Meanwhile, as the polygon constituting the faces of the polyhedron, a triangle is commonly used in order to obtain high efficiency by reducing needless overhead since, if span data for a polygon (not a triangle) is generated from a geometric processor and applied to a rasterizer, the workload of the geometric processor is so much greater than that of the rasterizer, so that the rasterizer is often idle, which diminishes the system's overall efficiency. Accordingly, it follows that the polygon span data should be converted into triangle span data using the geometric processor for attaining the load distribution.
The amount of rasterizer calculation depends on how the triangle is to be traversed. Therefore, a more efficient traversing method is required, for increasing the speed of the graphics system. To do this, the Pineda algorithm has been proposed to traverse a triangle efficiently. However, this algorithm has a disadvantage in that its control logic is so complex that its hardware implementation is difficult. In addition, this algorithm performs needless calculations which relate to pixels outside the triangle.
SUMMARY OF THE INVENTION
Accordingly, an object of the present invention is to provide a highly efficient traversing method for use in the rasterizer of a computer graphics system.
Another object of the present invention is to provide a rasterizer adopting the above traversing method.
To attain the above first object of the present invention, there is provided a method for traversing a triangle defined by three vertices, comprising:
a first step for determining two of the three vertices as a starting point and a final point, respectively, based on a predetermined primary traversing direction;
a second step for assigning said starting point to a reference point, a edge point;
a third step for updating the reference point such that, if a pixel shifting from the reference point in the primary traversing direction passes over an edge of the triangle, the updated reference point has an address shifted by one pixel in the primary traversing direction from one edge point selected between the first and second edge points based on the slope of the passed edge, and otherwise, the updated reference point has an address shifted by one pixel in the primary traversing direction from the previous reference point;
a fourth step for performing both outward traversing from the updated reference point, until the points of the line within the triangle are all traversed and storing the two outermost points traversed in the outward traversings as the first and second edge points, respectively; and
repeatedly performing said third and fourth steps, until said final point is traversed.
Here, in a preferred embodiment, the third step includes the steps of:
shifting the reference point by one pixel in the primary traversing direction;
producing three edge function values of the shifted reference point in order to check whether the shifted reference point is located within the triangle;
producing image values of the shifted reference point, provided that the three edge function values are all located-in values; and
selecting one between the first edge point and second edge point, provided that any one of the three edge function values is a located-out value, wherein the selection is made based on the slope of an edge having a located-out value, and assigning the point shifted by one pixel in the primary traversing direction from the selected edge point as the reference point then producing image values of the reference point.
In addition, the image values are produced using a quadratic interpolation according to fast Phong shading.
The primary traversing direction is deemed the −Y direction and the outward traversings are deemed the ±X directions.
To attain the other object of the present invention, there is provided a rasterizer comprising:
a traversing control unit for producing an address of a traversing point by performing the triangle traversing described above;
a boundary checking unit for checking whether the traversing point is located within the triangle;
a function processing unit for producing the image values of the traversing point determined to be located within the triangle; and
an output processing unit for performing a hidden-surface elimination for the point whose image values have been produced, and then updating a frame buffer.
REFERENCES:
patent: 5369739 (1994-11-01), Akeley
patent: 5598517 (1997-01-01), Watkins
Foley et al. “Computer Graphics Principles And Practice” pp 9-15, 96-104, 165-175, 1990.*
English translation of Korean Patent Application No. 93-22956.
Choi Sang-gil
Wee Young-cheul
Jankus Almis R.
Rothwell Figg Ernst & Manbeck
Samsung Electronics Co,. Ltd.
LandOfFree
Triangle traversing method and a rasterizer adopting the same does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Triangle traversing method and a rasterizer adopting the same, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Triangle traversing method and a rasterizer adopting the same will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476361