Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-12-06
2003-11-18
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S422000, C345S428000, C345S581000, C345S586000, C345S552000, C345S561000
Reexamination Certificate
active
06650325
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to rasterizers and, more particularly, to optimizing results during 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 picture elements or “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.
Triangles are created by the union of three edges, or more particularly three half-planes, each of which is specified by edge functions. 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 tie-breaker 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 generating the pixels in a unidirectional manner. Such traditional unidirectional solution includes generating the pixels row-by-row in a constant direction. This requires that the sequence shift across the primitive to a starting location on a first side of the primitive upon finishing at a location on an opposite side of the primitive. Each time this shift is executed, pixels or texture values are stored which were not positioned adjacent to pixels or texture values processed immediately beforehand. Therefore, such distant pixels or texture values have a greater chance of belonging to different memory access blocks, making such access inefficient.
This problem is exacerbated with primitives of a large size. For example, if a sequence generates pixels along a very long row or column, the probability is reduced that contiguous pixels or texture values from an adjacent row or column, respectively, will still be in memory. This probability is further reduced with memory of a limited size.
As yet another example, a haphazard generation sequence includes jumping around randomly within the primitive. Using this method, pixels or texture values that are accessed are rarely adjacent to those that were accessed recently enough to still be in a limited size memory.
There is therefore a need for a rasterization system that processes pixels or texture values that are frequently adjacent to pixels or texture values that have been previously processed immediately beforehand and are still stored in memory.
DISCLOSURE OF THE INVENTION
A method, apparatus and article of manufacture are provided for performing rasterization using alternating sense point traversal. Upon receipt of a primitive, i.e. a triangle, a plurality of points is positioned on or near the primitive. Such points define an enclosed convex region and are located at corners of the convex region. In operation, the points and thus the convex region are moved in an alternating manner for the purpose of identifying an area in the primitive for rendering pixels therein. In particular, the points are moved in a boustrophedonic manner.
This boustrophedonic rasterization constrains the sequence to obey certain rules that offer better performance for hardware. Boustrophedonic refers to a serpentine pattern that folds back and forth. A horizontal boustrophedonic sequence, for example, may generate all the pixels within a primitive triangle that are on one row from left to right, and then generate the next row right to left, and so on. Such a folded path ensures that an average distance from a generated pixel to recently previously generated pixels is relatively small.
Generating pixels that are near recently generated pixels is important when recent groups of pixels and/or their corresponding texture values are kept in memories of a l
Foskett Nicholas J.
Voorhies Douglas A.
Bella Matthew C.
NVIDIA Corporation
Sajous Wesner
Silicon Valley IP Group
Zilka Kevin J.
LandOfFree
Method, apparatus and article of manufacture for... 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..., 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... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136574