Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1999-12-06
2003-01-07
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06504542
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to rasterizers and, more particularly, to accelerating the conversion of primitives defined by vertexes to equivalent images composed of pixel patterns that can be stored and manipulated as sets of bits.
BACKGROUND OF THE INVENTION
Raster displays are commonly used in computer graphics systems. These displays store graphics images as a matrix of the smallest picture elements that can be displayed on a screen (“pixels”) with data representing each pixel being stored in a display buffer. This data specifies the display attributes for each pixel on the screen such as the intensity and color of the pixel. An entire image is read from the display buffer and displayed on the screen by sequentially scanning out horizontal rows of pixel data or “scan lines.”
Raster display systems commonly use polygons as basic building blocks or “primitives” for drawing more complex images. Triangles are a common basic primitive for polygon drawing systems, since a triangle is the simplest polygon and more complex polygons can always be represented as sets of triangles. The process of drawing triangles and other geometric primitives on the screen is known as “rasterization.”
An important part of rasterization involves determining which pixels fall within a given triangle. Rasterization systems generally step from pixel to pixel in various ways and determine whether or not to “render,” i.e. draw into a frame buffer or pixel map, each pixel as part of the triangle. This, in turn, determines how to set the data in the display buffer representing each pixel. Various traversal algorithms have been developed for moving from pixel to pixel in a way such that all pixels within the triangle are covered.
Rasterization systems sometimes represent a triangle as a set of three edge-functions. An edge function is a line equation representing a straight line, which serves to subdivide a two-dimensional plane. Edge functions classify each point within the plane as falling into one of three regions: the region “inside” of the triangle, the region “outside” of the triangle or the region representing a line itself. The type of edge function that will be discussed has the property that points “inside” of the triangle have a value greater than zero, points “outside” have a value less than zero, and points exactly on the line have a value of zero. This is shown in Prior Art FIG.
1
. Applied to rasterization systems, the two-dimensional plane is represented by the graphics screen, points are represented by individual pixels, and the edge function serves to subdivide the graphics screen.
The union of three edges, or more particularly three half-planes, each of which is specified by edge functions, create triangles. It is possible to define more complex polygons by using Boolean combinations of more than three edges. Since the rasterization of triangles involves determining which pixels to render, a tiebreaker rule is generally applied to pixels that lie exactly on any of the edges to determine whether the pixels are to be considered interior or exterior to the triangle.
As shown in Prior Art
FIG. 1A
, each pixel has associated with it a set of edge variables, (e
0
, e
1
and e
2
), which are proportional to the signed distance between the pixel and the three respective edges. The value of each edge variable is determined for a given triangle by evaluating the three edge functions, f
0
(x,y), f
1
(x,y) and f
2
(x,y) for the pixel location. It is important to note that it can be determined whether or not a pixel falls within a triangle by looking at only the signs of e
0
, e
1
and e
2
.
In determining which pixels to render within a triangle, typical rasterization systems compute the values of the edge variables, (e
0
, e
1
and e
2
), for a given set of three edge functions and a given pixel position, and then use a set of increment values (&Dgr;e
outside
, &Dgr;e
inside
, etc.) to determine the edge variable values for adjacent pixels. The rasterization system traverses the triangle, adding the increment values to the current values as a traversal algorithm steps from pixel to pixel.
With reference again to Prior Art
FIG. 1
, a line is illustrated that is defined by two points: (X,Y) and (X+dX, Y+dY). As noted above, this line can be used to divide the two dimensional space into three regions: all points “outside” of, “inside” of, and exactly on the line.
The edge f(x,y) can be defined as:
f
(
x,y
)=(
x−X
)
dY
−(
y−Y
)
dX.
This function has the useful property that its value is related to the position of the point (x,y) relative to the edge defined by the points (X,Y) and (X+dX, Y+dY):
f
(
x,y
)>0 if (
x,y
) is “inside”;
f
(
x,y
)=0 if (
x,y) is exactly on the line;
and
f
(
x,y
)<0 if (
x,y
) is “outside”.
Existing rasterization systems commonly use this function, since it can be computed incrementally by simple addition:
f
(
x+
1,
y
)=
f
(
x,y
)+
dY
;
and
f
(
x,y+
1)=
f
(
x,y
)−
dX.
A variety of different traversal algorithms are presently used by different rasterization systems in the rendering process. Any algorithm guaranteed to cover all of the pixels within the triangle can be used. For example, some solutions involve following the sides of the triangle while identifying a horizontal or vertical span of pixels therein. Following the sides of the triangle is adequate for the triangle edges, but if the triangle is clipped by a near or far plane, these boundaries are not known explicitly and cannot be followed as easily as the triangle edges.
Other methods search in a recursively narrowing manner. Recursion, however, can require an excessive amount of processing. This is due to the fact that many more points might be tested than there are inside the triangle.
Still other methods test individual pixels one at a time. Individual pixel testing works well, but generates only one pixel at a time. This is inadequate for devices that process multiple pixels simultaneously.
There is therefore a need for a rasterization system that overcomes the problems and deficiencies associated with the prior art methods.
DISCLOSURE OF THE INVENTION
A method, apparatus and article of manufacture are provided for performing area rasterization using sense points. Upon receipt of a primitive, i.e. a triangle, line equation coefficients of line equations are determined for lines that define the primitive. Thereafter, a plurality of points is positioned on or near the primitive. Such points define an enclosed convex region and reside at corners of the convex region. Next, the line equations are evaluated at the points. During operation, the points and convex region are moved based on the evaluation of the line equations for the purpose of identifying an area in the primitive for rendering pixels therein.
In one embodiment, the points may be initially positioned to enclose a vertex of the primitive. The evaluation includes determining if the points reside in the primitive. Such determination as to whether the points reside in the primitive may include determining whether the evaluation of the line equations renders a positive value or a negative value. For example, the evaluation of a line equation at a point that renders a negative value indicates that such point resides outside the primitive.
In another embodiment, the points may be moved along a first row until lateral edges of the primitive are identified after which the points are moved along a second row below the first row. Further, a starting position of the points on subsequent rows may reside adjacent a position on a previous row where the points were at least partially in the primitive. The points may then be moved from the starting position in a first direction until a first lateral edge of the primitive is identified after which the points are moved from the starting position in a second direction to identify a second lateral edge of the primitive.
One aspect of the present invention thus includes outputting multiple pixels
Foskett Nicholas J.
Voorhies Douglas A.
Brier Jeffery
Nvidia Corporation
Silicon Valley IP Group, LLC.
Yang Ryan
Zilka Kevin J.
LandOfFree
Method, apparatus and article of manufacture for area... 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, apparatus and article of manufacture for area..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus and article of manufacture for area... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3061592