Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2001-08-24
2004-06-08
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S581000
Reexamination Certificate
active
06747663
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the field of digital signal processing and, more particularly, to a system and method for interpolating sample values based on known values at the vertices of a triangle.
2. Description of the Related Art
Prior art graphics systems have typically partitioned objects into a stream of triangles. Each triangle may comprise three vertices with assigned color values. To generate color values for pixels residing inside a triangle, an interpolation may be performed based on the position of each pixel with respect to the triangle vertices. Many prior art techniques for this interpolation have operated under the assumption that the pixel positions lie on a rectangular grid. If the pixels do not lie on a rectangular grid, such prior art techniques may not be as useful or may operate with degraded efficiency. Therefore, a graphics system and method are desired which may provide interpolation of ordinate values (e.g. color values) for pixels (and/or samples) which do not necessarily lie on a rectangular grid.
SUMMARY OF THE INVENTION
A graphics system may, in one embodiment, comprise a rendering unit, a sample buffer, and a sample-to-pixel calculation unit. The rendering unit may comprise one or more processors (e.g. DSP chips), dedicated hardware, or any combination thereof. The rendering unit may be configured to receive graphics data including three vertices defining a triangle. The rendering unit may generate sample positions in a two-dimensional screen space, and may determine which of the samples resides inside the triangle. The samples positions may be generated according to a perturbed regular sample-positioning scheme, a pseudo-random perturbed regular sample-positioning scheme, etc.
In some embodiments, the rendering unit may be configured to compute a first axial rate of change of a first ordinate based on the three vertices, and, for each sample residing inside the triangle, (a) to multiply the first axial rate by an edge-relative sample displacement resulting in a first product, (b) to interpolate a first projection value for a projection point on a first edge of the triangle, and (c) to add the first product to the first projection value resulting in the sample ordinate value. The projection point on the first edge may have the same major axis coordinate as the sample point. The first edge may be the edge of the triangle which has the largest major axis displacement.
The sample buffer may be configured to store the first sample ordinate value for each of the samples inside the triangle. The sample-to-pixel calculation unit may be configured to read one or more of the first sample ordinate values from the sample buffer, to generate a pixel value by filtering (e.g. convolving) the one or more first sample ordinate values, and to supply the pixel value to a display device.
The rendering unit may compute the first axial rate by (1) determining a change in the first ordinate between an opposing vertex not on the first edge and an auxiliary point on the first edge having an identical first axis coordinate as the opposing vertex, (2) determining a coordinate change along a second axis between the opposing vertex and the auxiliary point, and (3) multiplying the first ordinate change by the reciprocal of the second axis coordinate change.
The first ordinate change of (1) above may be determined by interpolating an auxiliary ordinate value for the auxiliary point based on a first vertex and a second vertex terminating the first edge and, and subtracting the auxiliary ordinate value from an opposing ordinate value of the opposing vertex.
The rendering unit may interpolate the first projection value for the projection point by (i) computing a first difference between a first coordinate of the projection point and a first coordinate of a first vertex of the first edge, (ii) multiplying the first difference by a first scaling factor resulting in a second difference, and (iii) adding the second difference to a root ordinate value corresponding to the first vertex. The first scaling factor may be computed by determining an ordinate change between a second vertex of the first edge and the first vertex, determining a second difference between a first coordinate of the second vertex and the first coordinate of the first vertex, and multiplying the ordinate change by the reciprocal of the second difference.
The rendering unit may be configured to determine if each sample resides inside the triangle by computing edge-relative displacements between the sample and the three edges of the triangle. Thus, the first sample displacement mentioned above may be the edge-relative displacement for the first edge.
In one set of embodiments, the rendering unit may be configured to compute a first minor axis ordinate difference along a minor axis of the triangle. The rendering unit may compute a sample ordinate value for each sample inside the triangle by:
(a) computing a minor axis positional fraction corresponding to the first sample;
(b) multiplying the minor axis positional fraction by the first minor axis ordinate difference to generate a first product; and
(c) adding the first product to one or more ordinate adjustment values to generate the first sample ordinate value.
The rendering unit may compute the first minor axis ordinate difference by interpolating an auxiliary ordinate value for an auxiliary point on a first edge of the triangle, and subtracting the auxiliary ordinate value from an ordinate value of an opposing vertex not on the first edge. The auxiliary point may have the same major axis coordinate as the opposing vertex.
The minor axis positional fraction corresponding to the first sample may be computed by subtracting a minor axis coordinate of the auxiliary point from the minor axis coordinate of the opposing vertex to generate a minor axis positional difference; and multiplying a first minor axis sample displacement corresponding to the first sample by a reciprocal of the minor axis positional difference to generate the minor axis positional fraction. The first minor axis sample displacement may equal a minor axis coordinate of said first sample minus a minor axis coordinate of a projection point on the first edge.
The rendering unit may be further configured to compute a first edge ordinate difference for a first edge of the triangle, and to compute the first sample ordinate value for the first sample inside the triangle by: (d) computing a major axis positional fraction corresponding to the first sample; and (e) multiplying the major axis positional fraction by the first edge ordinate difference to generate a first one of said one or more ordinate adjustment values. The ordinate value of a first vertex bounding the first edge may be a second one of said one or more ordinate adjustment values.
The first edge ordinate difference may be computed by subtracting an ordinate value for the first vertex from an ordinate value of a second vertex bounding the first edge. Furthermore, the major axis positional fraction corresponding to the first sample may be computed by: subtracting a major axis coordinate of the first vertex from a major axis coordinate of a second vertex bounding the first edge to generate a first edge major displacement; subtracting a major axis coordinate of the first vertex from a major axis coordinate of the first sample to generate a sample-relative major axis displacement; and multiplying the sample-relative major axis displacement by the reciprocal of the first edge major displacement.
As used herein the term “ordinate” refers to any attribute value such as red, green, blue or alpha which is to be determined at sample (or pixel) positions internal to a polygon based on the corresponding attributes values assigned to the polygon vertices.
REFERENCES:
patent: 5801711 (1998-09-01), Koss et al.
patent: 6535220 (2003-03-01), Deering et al.
patent: 6618054 (2003-09-01), Deering
patent: 2 278 524 (1994-11-01), None
Arcuri Salvatore
Deering Michael F.
Oberoi Ranjit S.
Brightwell Mark K.
Hood Jeffrey C.
Luu Matthew
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
LandOfFree
Interpolating sample values from known triangle vertex values does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interpolating sample values from known triangle vertex values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interpolating sample values from known triangle vertex values will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3333775