Polygon rendering method and system with dedicated setup engine

Claim 2

In a graphics system, a method of rendering a polygon having a plurality of edges and plurality of vertices, each edge being defined by two vertices, and wherein the method is performed in a manner that eliminates having to do a separate division for calculating a slope for each edge, comprising the steps for: a) selecting a polygon edge; and prior to rendering the polygon, performing steps for; b) initializing a set of coordinates at a selected one of the two vertices defining the selected edge; c) defining a plurality of starting points for successive spans along the selected edge, each span comprising at least one pixel, by iteratively incrementing the set of coordinates; and d) for each successive span, rendering each pixel in the span by iteratively incrementing the set of coordinates along the span, and thereafter, rendering the polygon by performing only two divisions, one for a single edge of the polygon and one for the inverse area of the polygon.

Claim 3

The method of claim 1, wherein the polygon has an area, further comprising: b.1) initializing a first characteristic function value as equal to the polygon area; b.2) initializing a second characteristic function value as equal to zero; and wherein c) comprises: c.1) incrementing each coordinate in the set of coordinates; c.2) incrementing each of the first and second characteristic function values; c.3) responsive to the sum of the first and second characteristic functions being greater than the polygon area: c.3.1) adjusting a first coordinate in the set of coordinates; and c.3.2) adjusting each of the first and second characteristic function values; c.4) defining a span starting point as the set of coordinates; and c.5) responsive to the first characteristic function value being greater than zero, repeating c.1) through c.5).

Claim 4

The method of claim 2, wherein the coordinates comprise an x-coordinate and a y-coordinate, the method further comprising: a.1) determining a slope of the selected edge; a.2) determining a first y-difference value and a second y-difference value; and a.3) determining a first characteristic function increment and a second characteristic function increment; and wherein: c.1) comprises adding the slope to the x-coordinate and adding 1 to the y-coordinate; c.2) comprises adding the first characteristic function increment to the first characteristic function value and adding the second characteristic function increment to the second characteristic function value; c.3.1) comprises adding 1 to the x-coordinate; and c.3.2) comprises subtracting the first y-difference value from the first characteristic function value and subtracting the second y difference value from the second characteristic function value.

Claim 5

The method of claim 3, wherein the polygon is a triangle having vertices (x1,y1), (x2,y2), and (x3,y3): a.1) comprises determining the slope as xstep=(x3-x1)/(y3-y1); a.2) comprises determining the first y-difference value as dy1=y2-y3 and the second y-difference value as dy0=y1-y2; and a.3) comprises determining the first characteristic function increment as dxy1=dy1*xstep-(x2-x3) and determining the second characteristic function increment as dxy0=dy0*xtep-(x1-x2).

Claim 6

The method of claim 4, further comprising the step of a.1.1) adjusting the determined slope to equal an integer value.

Claim 7

The method of claim 1, wherein d) comprises: d.1) initializing pixel coordinates as equal to the span starting point; d.2) initializing a span characteristic function value; d.3) rendering a pixel located at the pixel coordinates; d.4) incrementing the pixel coordinates; d.5) incrementing the span characteristic function value; and d.6) responsive to the span characteristic function value being greater than zero, repeating d.3) through d.6).

Claim 8

The method of claim 6, wherein the coordinates comprise an x-coordinate and a y-coordinate, and wherein the span starting point has a position, the method further comprising: a.1) determining a first y-difference value and a second y-difference value; and wherein: d.2) comprises: d.2.1) selecting a vertex of the polygon; d.2.2) defining a first vector representing the position of the span starting point with respect to the selected vertex; d.2.3) defining a second vector representing a polygon edge adjacent to the selected vertex; and d.2.4) initializing the span characteristic function value as equal to a cross-product between the first and second vectors; d.4) comprises adding 1 to the x-coordinate; and d.5) comprises adding one of the first and second y-difference values to the span characteristic function value.

Claim 9

The method of claim 1, wherein: a) further comprises determining at least one material value at each vertex of the polygon; c) further comprises for each successive span, determining at least one material value for the span starting point by iteratively incrementing the determined material value at the selected vertex; and d) further comprises for each successive span, determining at least one material value for each pixel in the span by iteratively incrementing the material value for the span starting point.

Claim 10

The method of claim 8, wherein the at least one material value represents color.

Claim 11

The method of claim 8, wherein: a) further comprises determining a first material value gradient along the selected edge for each material value, and determining a second material value gradient along a span for each material value; b) comprises iteratively incrementing the material value by adding the first material value gradient; and c) comprises iteratively incrementing the material value by adding the second material value gradient.

Claim 12

A computer program product for implementing in a graphics system, a computerized method of rendering a polygon having a plurality of edges and a plurality of vertices, each edge being defined by two vertices, and wherein the method is performed in a manner that eliminates having to do a separate division for calculating a slope for each edge, the computer program product comprising a computer readable medium for carrying computer readable instructions for implementing the method, and wherein the computer readable instructions are comprised of computer program code means for performing the steps of: a) selecting a polygon edge; and prior to rendering the polygon, performing steps for; b) initializing a set of coordinates at a selected one of the two vertices defining the selected edge; c) defining a plurality of starting points for successive spans along the selected edge, each span comprising at least one pixel, by iteratively incrementing the set of coordinates; and d) for each successive span, rendering each pixel in the span by iteratively incrementing the set of coordinates along the span, and thereafter, rendering the polygon by performing only two divisions, one for a single edge of the polygon and one for the inverse area of the polygon.

Claim 13

A computer program product for implementing in a graphics system, a computerized method of rendering a polygon having a plurality of edges and a plurality of vertices, each edge being defined by two vertices, and wherein the method is performed in a manner that eliminates having to do a separate division for calculating a slope for each edge, the computer program product comprising a computer readable medium for carrying computer readable instructions for implementing the method, and wherein the computer readable instructions are comprised of computer program code means for performing the steps of: a) selecting a polygon edge; and prior to rendering the polygon, performing steps for; b) initializing a set of coordinates at a selected one of the two vertices defining the selected edge; c) defining a plurality of starting points for successive spans along the selected edge, each span comprising at least one pixel, by iteratively incrementing the set of coordinates; and d) for each successive span, rendering each pixel in the span by iteratively incrementing the set of coordinates along the span, and thereafter, rendering the polygon by performing only two divisions, one for a single edge of the polygon and one for the inverse area of the polygon.

Claim 14

The computer program product of claim 11, wherein the polygon has an area, and wherein the implemented method further comprises: b.1) initializing a first characteristic function value as equal to the polygon area; b.2) initializing a second characteristic function value as equal to zero; and wherein c) comprises: c.1) incrementing each coordinate in the set of coordinates; c.2) incrementing each of the first and second characteristic function values; c.3) responsive to the sum of the first and second characteristic functions being greater than the polygon area: c.3.1) adjusting a first coordinate in the set of coordinates; and c.3.2) adjusting each of the first and second characteristic function values; c.4) defining a span starting point as the set of coordinates; and c.5) responsive to the first characteristic function value being greater than zero, repeating c.1) through c.5).

Claim 15

The computer program product of claim 12, wherein the coordinates comprise an x-coordinate and a y-coordinate, and wherein the method further comprises: a.1) determining a slope of the selected edge; a.2) determining a first y-difference value and a second y-difference value; and a.3) determining a first characteristic function increment and a second characteristic function increment; and wherein: c.1) comprises adding the slope to the x-coordinate and adding 1 to the y-coordinate; c.2) comprises adding the first characteristic function increment to the first characteristic function value and adding the second characteristic function increment to the second characteristic function value; c.3.1) comprises adding 1 to the x-coordinate; and c.3.2) comprises subtracting the first y-difference value from the first characteristic function value and subtracting the second y difference value from the second characteristic function value.

Claim 16

The computer program product of claim 13, wherein the polygon is a triangle having vertices (x1, y1), (x2,y2), and (x3,y3) and wherein step a) comprises: a.1) determining the slope as xstep=(x3-x1)/(y3-y1); a.2) determining the first y-difference value as dy1=y2-y3 and the second y-difference value as dy0, y1-y2; and a.3) determining the first characteristic function increment as dxy1=dy1*xstep-(x2-x3) and determining the second characteristic function increment as dxy0=dy0*xstep-(x1-x2).

Claim 17

The computer program product of claim 14, wherein the implemented method further comprises the step of a.1.1) adjusting the determined slope to equal an integer value.

Claim 18

The computer program product of claim 11, wherein step d) of the implemented method comprises: d.1) initializing pixel coordinates as equal to the span starting point; d.2) initializing a span characteristic function value; d.3) rendering a pixel located at the pixel coordinates; d.4) incrementing the pixel coordinates; d.5) incrementing the span characteristic function value; and d.6) responsive to the span characteristic function value being greater than zero, repeating d.3) through d.6).

Claim 19

The computer program product of claim 16, wherein the coordinate comprise an x-coordinate and a y-coordinate, and wherein the span starting point has a position, the implemented method further comprising: for step a): a.1) determining a first y-difference value and a second y-difference value; and for step d.2): d.2.1) selecting a vertex of the polygon; d.2.2) defining a first vector representing the position of the span starting point with respect to the selected vertex; d.2.3) defining a second vector representing a polygon edge adjacent to the selected vertex; and d.2.4) initializing the span characteristic function value as equal to a cross-product between the first and second vectors; d.4) comprises adding 1 to the x-coordinate; and d.5) comprises adding one of the first and second y-difference values to the span characteristic function value.

Claim 20

The computer program product of claim 11, wherein: step a) further comprises determining at least one material value at each vertex of the polygon; step c) further comprises for each successive span, determining at least one material value for the span starting point by iteratively incrementing the determined material value at the selected vertex; and step d) further comprises for each successive span, determining at least one material value for each pixel in the span by iteratively incrementing the material value for the span starting point.

Claim 21

The computer program product of claim 18, wherein the at least one material value represents color.

Claim 22

The computer program product of claim 18, wherein: step a) further comprises determining a first material value gradient along the selected edge for each material value, and determining a second material value gradient along a span for each material value; step b) comprises iteratively incrementing the material value by adding the first material value gradient; and step c) comprises iteratively incrementing the material value by adding the second material value gradient.