Mapping time-sorted to direction-sorted triangle vertices

Details Mapping time-sorted to direction-sorted triangle vertices Mapping time-sorted to direction-sorted triangle vertices

2001-05-18

2004-08-31

Razavi, Michael (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Attributes

C345S419000, C345S418000, C345S589000, C345S601000, C345S602000, C345S606000

Reexamination Certificate

active

06784894

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the field of computer graphics and, more particularly, to high performance graphics systems for rendering graphical objects based on a decomposition of the graphical objects into triangles.
2. Description of the Related Art
A graphics system may be configured to receive a stream of vertices from a host application executing on a host computer. The vertices specify triangles in a 3D coordinate space. The triangles represent a collection of 3D objects in the 3D world coordinate space. The graphics system may operate on the triangles to generate a video stream which represents the view of a virtual camera (or virtual observer) in the 3D world coordinate space. In particular, the graphics system may compute color values for each pixel that resides within each triangle (i.e. the two-dimensional footprint of the triangle in screen space). This process of assigning color values to pixels (or samples) internal to triangles is referred to herein as triangle rasterization.
Each triangle is defined by three vertices. Each vertex comprises a coordinate pair (X,Y), a color vector and texture coordinates. One prior art method for rasterizing a triangle operates by walking along horizontal scan lines from a left edge to a right edge of the triangle. Within a scan line, color values for successive pixels may be generated by repeated addition of pixel increment values (one pixel increment value per color). Successive scan lines may be processed in the order of increasing Y coordinate (i.e. the vertical screen space coordinate) until the entire triangle is covered. Thus, it is important to identify the vertex with the smallest Y coordinate and the vertex with the largest Y coordinate.
It is noted that the identity of the left edge or the right edge may change through the rasterization process. For example, given a triangle with vertices V
A
=(0,0), V
B
=(10,10) and V
C
=(0,20), it is observed that edge V
A
V
B
will be the right edge for scan lines having Y coordinate less than 10, and edge VBVC will be the right edge for scan lines having Y coordinate greater than 10. Thus, for a generic triangle, it is important to identify the vertices having minimum, maximum and intermediate Y coordinates values. The minimum and maximum Y coordinates define the first and last scan lines, and the intermediate Y coordinate defines where an edge boundary change will occur.
The portion of a scan line that intersects the triangle is referred to as a span. Each span is bounded by a left boundary point on a left edge and a right boundary point on a right edge of the triangle. The X coordinates of the left (right) boundary points for successive spans may be computed by repeatedly adding a left (right) edge increment starting with the X coordinate of the vertex V
A
. The left (right) edge increment may equal the slope (&Dgr;X/&Dgr;Y) of the left (right) edge. Thus, the slopes of the left and right edges are computed before the spans are processed.
Observe that an edge slope may attain a large magnitude if its Y displacement &Dgr;Y is small relative to its X displacement &Dgr;X. Thus, it may be necessary to assign a large number of bits to the slope variables.
One drawback of the above triangle rasterization method is that tall skinny triangles may not be handled efficiently. A tall skinny triangle intercepts a large number of scan lines, but each scan line may have only a few pixels. Thus, a significant portion of the rasterization time may be consumed in the overhead of generating successive scan lines.
The manufacturers of 3D graphics systems are constantly under pressure from consumers to provide increased rendering performance. Thus, there exists a need for a system and method which could rasterize triangles with higher throughput rates.
SUMMARY OF THE INVENTION
A graphics system may be configured to operate on a collection of vertices to determine mappings from an initial ordering to secondary and tertiary ordering. The initial order corresponds to the ordering of the vertices in an input buffer. The secondary (tertiary) ordering corresponds to the ordering of the vertices along a triangle major (minor) axis. The graphics system may compute horizontal and vertical displacements along edges of the triangle in the initial ordering, and use the signs of the horizontal displacements and vertical displacements to access one or more mapping tables which determine the mappings. The mappings may be used to rasterize the triangle in terms of pixels (or samples).
In one set of embodiments, the graphics system comprises a buffer memory, a presetup unit and a setup unit. The presetup unit may be configured to compute a horizontal edge displacement and a vertical edge displacement for each edge of a triangle in response to receiving the three vertices defining the triangle. The presetup unit may identify a major displacement as the larger of the horizontal edge displacement and vertical edge displacement for each edge, identify a controlling edge as that edge of the triangle which has the largest major displacement, and identify a major axis coordinate as the coordinate (i.e. horizontal or vertical coordinate) corresponding to the major displacement of the controlling edge. In other words, the major axis coordinate is the horizontal (vertical) coordinate if the horizontal edge displacement of the controlling edge is larger (smaller) than the vertical displacement of the controlling edge.
The presetup unit determines a first ordering code corresponding to the ordering of the vertices with respect to the major axis coordinate in response to the signs of the corresponding edge displacements (i.e. the edge displacements along the major axis coordinate). In addition, the presetup unit may determine a second ordering code corresponding to the ordering of the vertices with respect to a coordinate complementary to the major axis coordinate in response to the signs of the edge displacements along the complementary coordinate. The first and second ordering codes may be determined by table lookup. The presetup unit may store the ordering codes, the vertices and the edge displacements in a buffer memory.
Setup unit accesses the vertices and edge displacements from the buffer memory according to the first ordering and the second ordering using the first and second ordering codes respectively, and computes the rate of change of image attributes (e.g. red, green, blue) with respect to the major axis coordinate and the complementary coordinate. These rates of change are referred to herein as axial ordinate rates, and the image attributes are referred to as ordinates.
The graphics system may further include a sample fill unit, a frame buffer and a pixel computation unit. The sample fill unit may identify a set of sample positions interior to the triangle, compute sample ordinate values (e.g. red, green, blue) for the interior sample positions using the axial ordinate values, and store the sample ordinate values in the frame buffer. The pixel computation unit may then filter the sample ordinate values to determine pixels values which form a displayable image. In one embodiment, the pixel values are stored in the frame buffer for subsequent display. In another embodiment, the pixel values are immediately converted to analog form and transmitted to a video output port (for display on one or more display devices). In some embodiments, pixel values may be provided to a display device in digital form.


REFERENCES:
patent: 5343558 (1994-08-01), Akeley
patent: 5347618 (1994-09-01), Akeley
patent: 5392385 (1995-02-01), Evangelisti et al.
patent: 5446836 (1995-08-01), Lentz et al.
patent: 5671401 (1997-09-01), Harrell
patent: 5852446 (1998-12-01), Hashimoto et al.
patent: 5945997 (1999-08-01), Zhao et al.
patent: 6034699 (2000-03-01), Wong et al.
patent: 6160557 (2000-12-01), Narayanaswami
patent: 6166717 (2000-12-01), Nakayama
patent: 6529196 (2003-03-01), Holt
patent: 6624823 (2003-09-01), Deering
“Triangle Rasterization, Setup” web page

Affiliated with

Also associated with

Rating

Mapping time-sorted to direction-sorted triangle vertices does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mapping time-sorted to direction-sorted triangle vertices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mapping time-sorted to direction-sorted triangle vertices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3340508