Vertex reordering in 3D graphics

The present invention relates generally to processing graphics primitives and more particularly to maintaining the ordering of vertices of those primitives during processing.

In a 3D graphics application, redrawing a graphics primitive should always achieve the same result in appearance, despite how the primitive is drawn. However, because of the finite precision of floating point calculations used in 3D applications, if primitive is drawn a second time in a slightly different way, differences in appearance may show up. One difference that may show up involves the depth values of the primitive. To avoid the differences that may show up when a graphics primitive is drawn in slightly different way is desirable.

The present invention is directed towards an apparatus and method that avoids differences in drawing a graphics primitive, regardless of the order in which its vertices are presented.

A method of reordering vertices of a graphics primitive, in accordance with the present invention includes (i) receiving a plurality of vertices of a graphics primitive, where the vertices having a circular ordering, an unknown position in the circular ordering and include coordinates with respect to a predefined origin, (ii) determining which of the vertices of the primitive is closest to the origin, the closest vertex being designated the minimum vertex, (iii) moving the minimum vertex to a first predefined position in the circular ordering, and (iv) for each next vertex in the circular ordering, moving the next vertex to a next predefined position in the circular ordering so that the vertices of the primitive have a prescribed ordering regardless of the order received.

An apparatus for reordering vertices of a graphics primitive in accordance with the present invention includes a graphics primitive storage block, a comparison logic block, a plurality of multiplexers, and a control logic block. The graphics primitive storage block is configured to store a plurality of vertices of a graphics primitive, the vertices in the storage block having a circular ordering, each vertex having an unknown position in the circular ordering and including coordinates with respect to a predefined origin. The comparison logic block is connected to receive the vertices stored in the graphics primitive storage block and configured to determine which of the vertices of the primitive is closest to the origin, the closest vertex being designated the minimum vertex, and to generate a swap_order bit field that contains instructions for reordering the vertices to prescribed positions in the circular ordering based on the determined minimum vertex. Each of the plurality of multiplexers is connected to receive the plurality of vertices stored in the storage block, where each multiplexer is operative to select one of the plurality of vertices based on the swap_order bit field, such that the plurality of multiplexers provides on its output the reordered vertices of the primitive. The control logic block is connected to the comparison logic block and configured to receive the swap_order bit field, where a header signal indicates when the coordinates of the vertices are available from the storage block, and to distribute the swap_order bit field to the plurality of multiplexers to control the selection by the multiplexers.

These and other features, aspects and advantages of the present invention will become better understood with regard to the following description, appended claims, and accompanying drawings where:

FIG. 1 shows the various reorderings of vertices in accordance with the present invention;

FIG. 2 sets forth an example of a triangle in which (x 1 , y 1 ) is the minimum vertex;

FIG. 3 shows the eight positions possible for each vertex;

FIG. 4A shows a block diagram of an apparatus in accordance with the present invention;

FIG. 4B shows a block diagram of the control logic block in one version of the invention; and

FIGS. 5A–D show a flow chart of an embodiment of a method of the present invention.

When a graphics primitive is received for processing, the order of its vertices may be arbitrary. To avoid differences in rendering the primitive, the vertices must be reordered so that the order matches a pre-established convention. The convention, for a triangle as the primitive, is that vertex 0 v 0 is the vertex closest to an origin, vertex 1 v 1 is the next counter-clockwise vertex and vertex 2 v 2 is the next counter-clockwise vertex. Thus, if a triangle is received with a vertex ordering of (v 2 , v 1 , v 0 ) and v 2 is the minimum vertex as shown in FIG. 1 , case A 10 , then the vertices must be reordered by the following assignments, v 0 ′=v 2 , v 1 ′=v 0 , v 2 ′=v 1 , using primes for the new ordering. If a triangle is received with a vertex ordering of (v 2 , v 1 , v 0 ) and v 1 is the minimum vertex case B 12 , the vertices must be reordered by the following assignments, v 0 ′=v 1 , v 1 ′=v 2 , v 2 ′=v 0 . Finally, if the vertices have the order of (v 2 , v 1 , v 0 ) and v 0 is the minimum vertex, case C 14 , no reordering is needed, i.e., v 0 ′=v 0 , v 1 ′=v 1 , v 2 ′=v 2 .

In order to carry out this process, some information is needed to determine which vertex is the minimum vertex. One way to determine this is to calculate the distance of each vertex to the origin and compare the results. However, this calculation is relatively complex and time consuming and an alternative is desired. The alternative instead computes the following function:

Min{max(|x 0 |,|y 0 )|,max(|x 1 |,|y 1 )|,max(|x 2 |,|y 2 )|}.

In this function, the absolute values of each coordinate of each vertex is taken, the largest coordinate of the pair is selected, and the smallest of those is then selected. The result is a determination of which vertex is closest to the origin 28 . FIG. 2 sets forth an example of a triangle 20 in which |x 0 |>|y 0 |, |y 1 |>|x 1 |, and |x 2 |>|y 2 | for the three vertices 22 , 24 , 26 shown. This means that x 0 , y 1 and x 2 are chosen in the max step. Then, the smallest among these is chosen which is clearly y 1 . Therefore, the vertex closest to the origin is the v 1 (x 1 , y 1 ) vertex. However, because of the use of absolute values and no distinction about of which coordinate is the largest in the max function, the determination is not unique. There are eight cases for each vertex from which one must be determined. Four cases 40 , 42 , 44 , 46 arise because of the absolute value and four more cases 48 , 50 , 52 , 54 arise because the max function does not distinguish an x-coordinate from a y-coordinate. FIG. 3 shows the eight cases 40 – 54 for each vertex. To find out which of the eight cases for each vertex is the correct case, three more bits are needed for each vertex.

To derive these three bits, the sign of the each coordinate (there are six) must be known. Second, the truth or falsity of each comparison (there are three) performed in the max function must be known. Third, the truth or falsity each comparison (there are three) performed in the min function must be known. This information can be assembled into three bits and used to determine the unique solution to the above function.

The Booleans for the signs are:

sgn_x 0 sgn_y 0 (2 bits) sgn_x 1 sgn_y 1 (2 bits) sgn_x 2 sgn_y 2 (2 bits)

The Booleans for the comparisons in the max function are:

x 0 — lt — y 0 =(| x 0 |<| y 0 |)(1 bit)

x 1 — lt — y 1 =(| x 1 |<| y 1 |)(1 bit)

x 2 — lt — y 2 =(| x 2 |<| y 2 |)(1 bit)

The selection functions used in the max function are:

v 0 — max =(| x 0 |<| y 0 |)?| y 0 |:| x 0 |

v 1 — max =(| x 1 |<| y 1 |)?| y 1 |:| x 1 |

v 2 — max =(| x 2 |<| y 2 |)?| y 2 |:| x 2 |

The above information is assembled into the following concatenations, which gives the selected coordinate for each vertex and the three bits to make it unique.

v 0 — max — p =( v 0 — max, x 0 — lt — y 0 , sgn — x 0 , sgn — y 0 )

v 1 — max — p =( v 1 — max, x 1 — lt — y 1 , sgn — x 1 , sgn — y 1 )

v 2 — max — p =( v 2 — max, x 2 — lt — y 2 , sgn — x 2 , sgn — y 2 )

This enables the comparisons needed for the min function to be performed.

v 0 — lt — v 1 =( v 0 — max — p<v 1 — max — p )

v 1 — lt — v 2 =( v 1 — max — p<v 2 — max — p )

v 2 — lt — v 0 =( v 2 — max — p<v 0 — max — p )

The following algorithm assumes that the vertices are received in the order (v 2 , v 1 , v 0 ) and performs any reordering necessary to place the vertices in the proper order.

if (˜v 1 _lt_v 2 & v 2 _lt_v 0 )// vertex 2 (v 2 ) is the minimum vertex

reorder_vertices (v 2 ′=v 1 , v 1 ′=v 0 , v 0 ′=v 2 ,);

else if (˜v 0 _lt_v 1 & v 1 _lt_v 2 )// vertex 1 (v 1 ) is the minimum vertex

reorder_vertices (v 2 ′=v 0 , v 1 ′=v 2 , v 0 ′=v 1 );

else // vertex 0 (v 0 ) is the minimum vertex

reorder_vertices (v 2 ′=v 2 , v 1 ′=v 1 , v 0 ′=v 0 );

In the above algorithm, the function reorder_vertices ( ) performs the assignments or swaps needed to change the vertex order.

FIG. 4A shows a block diagram 100 of an apparatus in accordance with the present invention. The apparatus includes a graphics primitive storage block 102 that supplies the vertex coordinates (header data), which may be homogenous coordinates in some versions, a comparison logic block 104 that implements the above algorithm and supplies a swap_order bit field, control logic 106 and three 3:1 multiplexers 108 a–c , each of which receives all three vertices. The control logic block 106 is operative to control the selection inputs of the three multiplexers 108 a–c to perform the reordering.

Referring to FIG. 4B , the control logic block 106 includes a 2:1 multiplexer 120 , a register 122 and a gate 124 . The selection input of the 2:1 multiplexer 120 receives a signal called is_header, which indicates that coordinate information for the vertices of a graphics primitive is available from the triangle parameters block. When is_header is true, the 2:1 multiplexer 120 passes the swap_order bit field through to the selection inputs of the 3:1 multiplexers. At the same time, the register 122 , via the gate 124 , stores the swap_order bit field, so that when is_header is not true, the reordering information is preserved, allowing other triangle parameter data to pass through the multiplexers according to the same ordering as was established when the header data passed through.

The swap_order bit field is a 6 bit field. Each pair of bits in the bit field is configured to operate a pair of selection inputs of one of the 3:1 multiplexers. Binary value b'00, selects the lowest order input, binary b'01, selects the middle input and binary b'10 selects the highest order input. For convenience, each of the 3:1 multiplexers receives the vertex coordinates on its inputs in the same fashion, i.e., with v 0 at the lowest order position, v 1 in the middle position and v 2 in the highest order position.

Therefore, the function reorder_vertices (v 2 ′=v 1 , v 1 ′=v 0 , v 0 ′=v 2 ) can be implemented by assigning a value (01,00,10) to the swap_order bit field. The lower two bits b'10 cause v 0 ′=v 2 , the middle two bits b'00 cause v 1 ′=v 0 and the upper two bits b'01 cause v 2 ′=v 1 . For reorder_vertices (v 2 ′=v 0 , v 1 ′=v 2 , v 0 ′=v 1 ) the swap_order bit field is (00,10,01) and for reorder_vertices (v 2 ′=v 2 , v 1 ′=v 1 , v 0 ′=v 0 ) the swap_order bit field is (10,01,00), which preserves the current order.

FIGS. 5A–D show a flow chart of an embodiment of a method of the present invention. In step 200 of FIG. 5A , a plurality of vertices of a graphics primitive is received. Next, in step 202 , the minimum vertex, i.e., the one closest to the origin is determined. In step 204 , the minimum vertex is moved to a first predefined position in the circular ordering, and in loop 206 , 208 , 210 each next vertex is moved to a next predefined location in the ordering.

FIG. 5B shows the steps for determining the minimum vertex. For each vertex of the primitive as determine by loop 220 , 232 , the x-coordinate is compared, in step 222 , to the y-coordinate to determine which is the larger coordinate. The result of the comparison is saved in step 224 . Next, in step 226 , the larger of the two coordinates is selected. In step 228 , the sign of the x- and y-coordinates are determined and saved. In step 230 , the selected coordinate, the saved results of the coordinate comparison, and the saved signs of each coordinate are concatenated. In step 234 , with all of the concatenations available, the bit string of each vertex is compared to the bit string of the other vertices to determine the minimum vertex.

FIG. 5C shows the steps for moving the minimum vertex to a first predefined position in the circular ordering. Assuming there are three vertices, if the minimum vertex is in the third position, as determined in step 250 , then the third position is moved, in step 252 , to a new first position in the circular order. If the minimum vertex is in the second position, as determined in step 254 , then the second position is moved to a new first position in step 256 .

FIG. 5D shows the steps for moving each next vertex to a next predefined position in the circular ordering. Assuming there are three vertices, if the minimum vertex is in the third position, as determined in step 260 , the vertex in the second position is moved to a new third position and the vertex in the first position is moved to a new second position, in step 262 . If the minimum vertex is in the second position, as determined in step 264 , then the vertex in the third position is moved to a new second position, and the vertex in the first position is moved to a new third position, in step 266 .

Although the present invention has been described in considerable detail with reference to certain preferred versions thereof, other versions are possible. Therefore, the spirit and scope of the appended claims should not be limited to the description of the preferred versions contained herein.