Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-08-20
2004-03-30
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000, C345S614000, C345S622000
Reexamination Certificate
active
06714196
ABSTRACT:
BACKGROUND OF THE INVENTION
Fragment Containment
A three-dimensional (3D) graphic processing device uses a description of an object such as a polygon, line, or triangle to generate the object's constituent fragments. A fragment is defined as all information required to render a single pixel that is within the boundaries of the object, for example, the x and y coordinates of the pixel, the red, green and blue color values used to modify the pixel, alpha transparency and Z depth values, texture coordinates, and the like. The graphics device must determine which fragments are contained within the object. Most prior art fragment generation methods fall into two categories: scanline and half-plane edge functions.
Scanline Generator
A scanline-based fragment generator renders trapezoids on a graphics rendering surface of an output device, such as a printer page or a display terminal screen. Without loss of generality, here a scanline is considered to be a (horizontal) row of pixels, and the top and bottom edges of the trapezoid are horizontal. Note that some fragment generators consider a scanline to be a (vertical) column of pixels and the right and left edges of the trapezoid are vertical.
The scanline fragment generator determines the inverse of the slope of the left and right edges of the trapezoid in order to determine how many pixels the left and right edges move horizontally when moving from one scanline to the next. At each scanline, the generator uses the inverse slope information to determine a starting pixel address and either a length or ending pixel address. This information is used to generate corresponding fragment information for each pixel position on the scanline within the object.
To render a non-trapezoidal object, such as an arbitrary triangle, the generator, in effect, renders two trapezoids while sharing some computation between the two. The generator first determines the inverse of the slope of all three edges of the triangle. The generator then vertically partitions the triangle into a top portion and a bottom portion, the point for partitioning being they coordinate of the vertex that is between the top and bottom of the triangle.
The two portions are degenerate trapezoids. The top portion has a top edge with a length of zero; the bottom portion has a bottom edge with a length of zero. The fragments for the top trapezoid can then be generated, and one of the inverse slopes used to generate the top portion can later be used to generate fragments for the bottom trapezoid portion.
Half-plane Edge Fragment Generator
A half-plane edge function fragment generator uses planar (affine) edge functions of the x and y screen coordinates. The values of these edge functions at a given pixel determine directly if the pixel is inside or outside an object. As an advantage, the generator does not need to determine the inverse slopes of the edges of the objects. However, traversal of the object is less intuitive than with a scanline generator. Given the value of the edge functions at various points surrounding the current position, the generator decides where to go next.
An introduction to half-plane edge functions is given by J. Pineda in “A Parallel Algorithm for Polygon Rasterization,” ACM Computer Graphics, Volume 22, Number 4, August 1988 (SIGGRAPH 1988 issue), which is hereby incorporated by reference as background information, though the basic traversals methods described by Pineda are less than optimal.
As a very brief summary, each directed edge of an object, such as a triangle with three edges or a line with four edges, is represented as function that partitions the 2D (x, y) rendering plane into two portions: at points to the left of the parting edge with respect to its direction, the function is negative, and at points on the parting edge or to the right of the parting edge the function is nonnegative, that is, zero, or positive.
By combining information from all edge functions at a given point, it can be determined whether the point is inside or outside the object. For example, if the three directed edges of a triangle connect in a clockwise fashion, then a point is inside the triangle if all three edge functions are nonnegative. If the three edges connect in a counterclockwise fashion, then a point is inside the triangle if all three edge functions are negative. Note that points along an edge or vertex that is shared between two or more objects should be assigned to exactly one object. The edge equations can be adjusted during setup to accomplish this.
FIG. 2
shows a triangle
200
that can be described by three clockwise directed edges
201
-
203
, which are shown as bold arrows. The half-plane where each corresponding edge function is nonnegative is shown by the several thin “shadow” lines
210
. The shadow lines
210
have the same slope as the corresponding edge. The shaded portion of
FIG. 2
shows the area where all edge functions are nonnegative, i.e., points within the triangle object
200
.
Fragment Stamp
One advantage of using half-plane edge functions is that parallel fragment generation is possible. For example, one can define a “fragment stamp” as a 2
m
pixel wide by 2
n
pixel high rectangle, and simultaneously determine all fragments that are within both the fragment stamp and the object.
Most known half-plane based fragment generators first move the stamp horizontally left, and then horizontally right across a row “stampline” before stepping up or down somewhere into the next stampline. A stampline is similar to a scanline, except that a row stampline has a height equal to the height (i.e., the vertical extent of the stamp, as measured in units of pixels) of the fragment stamp. Alternatively, the stamp can be moved vertically up and down in a column stampline, followed by stepping horizontally into the next column stampline. In this alternative, the column stampline has a width equal to the width of the fragment stamp.
Although Pineda does not describe stamp movement in any great detail, his most efficient implementation implies a method that starts at a vertex that lies on one of the four edges of a minimal horizontally and vertically aligned rectangular bounding box that encloses the object.
Stamp Contexts
The best Pineda traversal method requires at least two stamp contexts. A stamp context is all the information needed to place the stamp at a given position within the object. The context information includes the x and y position of the stamp, the value of all four half-plane edge evaluators, as well as the value of all channel data being interpolated from values provided at the object's vertices. The channel data includes, for example, color, transparency, Z depth, and texture coordinates.
Unfortunately, the Pineda implementation frequently allows the stamp to move outside of the object. This means that the stamp has to somehow find its way back into the object. This increases the amount of time taken to traverse the object completely.
One way to fix this straying problem is to start at a vertex of the triangle that is at one corner of the minimal bounding box. However, usually no vertex of a wide line or an antialiased line will be in the corner of the bounding box, so this solution is of limited usefulness. A more general solution, which works for “four-sided lines” as well as three-sided triangles, adds a third stamp context. If no restrictions are placed upon the starting vertex, then four stamp contexts are required.
Typically, it takes approximately 600 bits or more to store a stamp context. With so many bits, the amount of chip “real estate” required to store stamp contexts becomes significant. Furthermore, as more contexts are used, the decision logic to compute and multiplex the next stamp position becomes more complex and slower. Because stamp movement computations cannot be pipelined, this decision and multiplexing logic may determine the minimum cycle time of the fragment generation logic. Thus, it is desirable that movement methods be implemented with a minimum number of such stamp contexts.
Prior Art Traversal Orde
Dutton Todd Aldridge
McCormack Joel James
McNamara Robert Stephen
Mendyke Laura Edwards
Bella Matthew C.
Hewlett-Packard Development Company L.P
Monestime Mackly
LandOfFree
Method and apparatus for tiled polygon traversal 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 tiled polygon traversal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for tiled polygon traversal will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3271940