Clip-less rasterization using line equation-based traversal

Details Clip-less rasterization using line equation-based traversal Clip-less rasterization using line equation-based traversal

1999-12-06

2004-07-20

Brier, Jeffery (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Shape generating

Reexamination Certificate

active

06765575

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to rasterizers and, more particularly, to the conversion of primitives defined by vertexes to equivalent images composed of pixel patterns without clipping the primitives.
BACKGROUND OF THE INVENTION
In a traditional computer graphics pipeline, drawn primitives such as lines or polygons sometimes extend from on-screen to off-screen, and a “clip stage” in the pipeline alters the shape of the primitives to clip them to include only the on-screen portion. The rasterizer stage then generates the pixels corresponding to the on-screen portion of the primitive. This “clip stage,” however, often reduces the performance of the graphics pipeline because the computations involved are complex and highly variable.
There are several ways in which vertex coordinates of a primitive may extend beyond the portion that should be drawn. The most obvious way is extending beyond the top, bottom, left, and/or right edges of the screen, or window.
FIG. 1
shows a triangle
100
clipped by the screen edges thus rendering a seven-sided polygon
102
. It should be noted that in some prior art systems, a “guard band” is defined about an outer perimeter of the screen. By employing the guard band as the “cut-off,” some primitives that extend beyond the screen, but not beyond the guard band may avoid clipping. By employing a guard band, clipping is thus reduced, but not completely avoided.
Yet another type of clipping involves the third “Z” dimension or, in other words, the dimension extending “into” or “out of” the screen. Most graphics systems clip primitives against “near” and “far” limits, or planes. This is primarily done to control the range of the Z coordinate, so it can be expressed with adequate precision. This, however, also can add two more imposed edges on a polygon.
Another consequence of not clipping is more obscure. Before drawing a 3-D triangle, it is projected on to a 2-D image plane. Commonly, the mathematical projection involves perspective, making nearby objects appear large and far objects appear smaller. In a 3-D Cartesian coordinate system with X, Y, and Z axes that has the viewer looking down the +Z axis, this perspective is often accomplished by dividing the 3-D X and Y coordinates by the Z coordinate. Thus objects twice as far away, or twice the distance along the Z axis, have only half the screen-space X and Y extent.
A problem arises when an object spans both the +Z and −Z half-spaces. Division by a negative Z can produce reasonable on-screen X and Y values. As a result, points with a negative Z may project upside down and backwards on to the screen similar to positive Z points. An example of this phenomenon is shown in FIG.
1
A. As shown, an end
110
of a long triangle
112
is in front of the hypothetical “camera” or viewpoint
114
, with +Z coordinates, while the another end
116
is behind the camera with a −Z coordinate.
FIG. 1B
shows that after projection, all three vertexes
118
,
120
and
122
are on-screen when only two of them (
118
and
120
) are legitimate and the other one (
122
) is a projection from behind the camera.
Ordinarily, conventional clipping procedures would have eliminated the part of the triangle behind the camera, cutting off the −Z portion at the bottom of the screen. One example of avoiding the foregoing conventional clipping procedures may be found with reference to “
Triangle Scan Conversion using
2
D Homogeneous Coordinates
” authored by Marc Olano and Trey Greer, published in the 1997 Siggraph/Eurographics Workshop, and which is incorporated herein by reference in its entirety. Such technique, however, fails to deliver a sizable increase in performance.
There is therefore a need for a rasterization system that can handle primitives with any post-transform vertex coordinates that extend beyond the edges of the screen for the purpose of avoiding standard clipping operations while increasing processing performance.
DISCLOSURE OF THE INVENTION
A method, apparatus and article of manufacture are provided for clip-less rasterization. First, a primitive, i.e. line, triangle, etc., is received that is defined by a plurality of vertices. Each of such vertices includes a W-value. Thereafter, an area is identified based on the W-values of the vertices. Such area is representative of a portion of a display to be drawn corresponding to the primitive. As will become apparent, the area enclosed by the primitive is not always the area to be rasterized.
The instant process employs a variable, W, that is commonly used for projection, i.e., for viewing objects in perspective. The variable W is a number that the other coordinates, X, Y and Z, are divided by in order to make nearby things larger and far things smaller. The variable W is representative of a distance between a “center of projection” and the corresponding vertex.
In one embodiment where the primitive is a triangle, if none of the vertices have a negative W-value, the sides of the triangle enclose the area. On the other hand, if only one of the vertices has a negative W-value, the area is positioned outside an edge of the primitive opposite the vertex having the negative W-value. In particular, the area to be drawn is bounded by two lines that are co-linear with the two triangle sides sharing the −W vertex, and further bounded by a side of the triangle that shares the two +W vertexes. Still yet, if only two of the vertices have negative W-values, the area is positioned outside the primitive opposite both of the vertices having the negative W-values. In other words, the area to be drawn is bounded by two lines that are co-linear with the two triangle sides sharing the +W vertex, and further contiguous to the +W vertex.
The present invention is thus capable of handling all three of the foregoing cases. If the vertices are off-screen, it draws only the on-screen portion. If part of the triangle is beyond the near and/or far plane, it draws only the portion within those planes. If the triangle has one or two negative Z vertexes, only the correct +Z portion is drawn. By limiting the traversal using line equations and Z testing, little time is wasted exploring “bad” pixels that fail an edge or Z test. This is possible because all clipping, by screen edge or near or far plane, results in a convex region on-screen which can be “explored” easily because of its convex nature.
In one aspect of the present invention, positioning a plurality of points on or near the area, and moving the points about in the area identifies the space in the area. The points may define an enclosed polygonal region. As an option, the points may be initially positioned on top of the display if a top vertex of the area is positioned outside boundaries of the display.
These and other advantages of the present invention will become apparent upon reading the following detailed description and studying the various figures of the drawings.


REFERENCES:
patent: 5694143 (1997-12-01), Fielder et al.
patent: 5838337 (1998-11-01), Kimura et al.
patent: 5977997 (1999-11-01), Vainsencher
patent: 6000027 (1999-12-01), Pawate et al.
patent: 6057855 (2000-05-01), Barkans
patent: 6198488 (2001-03-01), Lindholm et al.
patent: 6417858 (2002-07-01), Bosch et al.
patent: 6518974 (2003-02-01), Taylor et al.
patent: 0690430 (1996-01-01), None
patent: WO 98/28695 (1998-07-01), None
patent: WO 99/52040 (1999-10-01), None
Olano et al., Triangle Scan Conversion using 2D homogeneous Coordinates, 1997 SIGGRAPH, Eurographics Workshop on Graphics Hardware,.*
Niizeke et al., Projectively Invariant intersection Detections for Solid Modeling, 1994, ACM Press, pp. 277-299.*
Blinn et al., Clipping using Homogeneous Coordinates, 1978, ACM Press, pp. 245-251.*
Ivan E. Sutherland and Gary W. Hodgman,Rreentrant Polygon Clipping, Jan. 1974, Communications of the ACM, vol. 17 No. 1 pp. 32-42.*
Marc Olano and Trey Greer; “Triangle Scan Coversion using 2D Homogeneous Coordinates”; 1997; SIGGRAPH/Eurographics Workshop.

Affiliated with

Also associated with

Rating

Clip-less rasterization using line equation-based 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 Clip-less rasterization using line equation-based traversal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clip-less rasterization using line equation-based traversal will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3205898