Ordering of patch selection in tessellation operations

1. A method of performing tessellation in a computer graphics system, the method comprising:

analysing an initial patch to determine whether to sub-divide the patch;

in response to determining that the initial patch is to be sub-divided, dividing the initial patch into two or more sub-patches; and

selecting and tessellating each sub-patch until there is no further sub-division of that sub-patch, wherein sub-patches are selected for tessellation in an order encoded by one or more stored values;

wherein the method is applied recursively at each level of sub-division; and

wherein selecting and tessellating each sub-patch until there is no further sub-division in an order encoded by one or more stored values comprises:

selecting one of the sub-patches formed by sub-division of the initial patch based on one or more stored values;

tessellating the selected sub-patch until there is no further sub-division; and

repeating the selecting and tessellating until all the sub-patches formed by sub-division of the initial patch have been tessellated until there is no further sub-division of those sub-patches.

2. The method according to claim 1 , wherein the one or more stored values comprise values of one or more flags.

3. The method according to claim 1 , further comprising, prior to analysing the initial patch:

receiving an input patch and sub-dividing the input patch into a plurality of initial patches.

4. The method according to claim 1 , wherein the initial patch is sub-divided into a left sub-patch and a right sub-patch,

selecting one of the sub-patches formed by sub-division of the initial patch based on one or more stored values comprises: selecting one of the left and right sub-patches formed by sub-division of the initial patch based on one or more stored values; and

repeating the selecting and tessellating until all the sub-patches formed by sub-division of the initial patch have been tessellated until there is no further sub-division of those sub-patches comprises: subsequently tessellating the other of the left and right sub-patches formed by sub-division of the initial patch until there is no further sub-division.

5. The method according to claim 4 , wherein tessellating the selected sub-patch until there is no further sub-division comprises:

analysing the selected sub-patch to determine whether to sub-divide the selected sub-patch;

in response to determining that the selected sub-patch is to be sub-divided, dividing the selected sub-patch into a left sub-patch and a right sub-patch;

selecting one of the left and right sub-patches formed by sub-division of the selected sub-patch based on one or more stored values;

first, tessellating the selected sub-patch until there is no further sub-division; and

then, tessellating the non-selected sub-patch until there is no further sub-division;

and wherein tessellating the non-selected sub-patch until there is no further sub-division comprises:

analysing the non-selected sub-patch to determine whether to sub-divide the non-selected sub-patch;

in response to determining that the non-selected sub-patch is to be sub-divided, dividing the non-selected sub-patch into a left sub-patch and a right sub-patch;

selecting one of the left and right sub-patches formed by sub-division of the non-selected sub-patch based on one or more stored values;

first, tessellating the selected sub-patch until there is no further sub-division; and

then, tessellating the non-selected sub-patch until there is no further sub-division.

6. The method according to claim 1 , wherein the one or more stored values comprise one or more flags, wherein the initial patch has one or more ordering flags and selecting one of the patches formed by sub-division of the initial patch based on one or more stored values comprises:

selecting one of the patches formed by sub-division of the initial patch based on values of the one or more ordering flags of the initial patch.

7. The method according to claim 6 , wherein dividing the initial patch into two or more sub-patches comprises:

dividing the initial patch into two or more sub-patches; and

setting one or more ordering flags for each of the sub-patches formed from the initial patch, wherein the one or more ordering flags for each of the sub-patches formed from the initial patch are derived from the one or more ordering flags of the initial patch.

8. The method according to claim 7 , wherein each initial patch and each sub-patch has a single ordering flag and the ordering flag for each sub-patch formed from the initial patch has an opposite value to the ordering flag of the initial patch.

9. The method according to claim 1 , wherein the one or more stored values comprise one or more flags, wherein selecting one of the patches formed by sub-division of the initial patch based on one or more stored values comprises:

selecting one of the sub-patches formed by sub-division of the initial patch based on a value of an ordering flag.

10. The method according to claim 9 , further comprising:

inverting the value of the ordering flag once for each increase or decrease in a level of sub-division.

11. The method according to claim 1 , further comprising:

in response to determining that the initial patch or a sub-patch is not to be sub-divided, outputting the initial patch or sub-patch as a primitive.

12. The method according to claim 1 , wherein dividing the initial patch or a sub-patch into two or more sub-patches comprises:

adding a new vertex;

and the method further comprising, in response to determining that the initial patch or a sub-patch is to be sub-divided:

pushing the new vertex onto a data structure operating a first in, last out scheme; and

in response to determining that the initial patch or sub-patch is not to be sub-divided, popping a vertex from the data structure and outputting the vertex if it has not previously been output.

13. A method of performing tessellation in a computer graphics system, the method comprising:

analysing an initial patch to determine whether to sub-divide the patch;

in response to determining that the initial patch is to be sub-divided, dividing the initial patch into two or more sub-patches; and

selecting and tessellating each sub-patch until there is no further sub-division of that sub-patch, wherein sub-patches are selected for tessellation in an order encoded by one or more stored values;

wherein dividing the initial patch or a sub-patch into two or more sub-patches comprises:

adding a new vertex;

the method further comprising, in response to determining that the initial patch or a sub-patch is to be sub-divided:

pushing the new vertex onto a data structure operating a first in, last out scheme;

in response to determining that the initial patch or sub-patch is not to be sub-divided, popping a vertex from the data structure and outputting the vertex if it has not previously been output; and

in response to determining that the initial patch or sub-patch is not to be sub-divided, delaying output of the initial patch or sub-patch, as a primitive, until all vertices of the initial patch or sub-patch have been output.

14. The method according to claim 13 , wherein delaying output of the initial patch or sub-patch until all vertices of the initial patch or sub-patch have been output comprises:

adding the initial patch or sub-patch to a queue;

determining whether all vertices of the initial patch or sub-patch have been output; and

in response to determining that all the vertices of the initial patch or sub-patch have been output, outputting the initial patch or sub-patch as a primitive.

15. The method according to claim 14 , wherein delaying output of the initial patch or sub-patch until all vertices of the initial patch or sub-patch have been output comprises:

determining whether all vertices of the initial patch or sub-patch have been output; and

in response to determining that all the vertices of the initial patch or sub-patch have not been output, adding the initial patch or sub-patch to a queue.

16. The method according to claim 12 , further comprising, prior to adding a first new vertex to the data structure:

outputting the middle vertex of a polygonal domain and a first corner vertex of the polygonal domain; and

initializing the data structure by pushing vertices corresponding to the other corners of the polygonal domain in either a clockwise or counter-clockwise order into the stack.

17. The method according to claim 1 , wherein dividing the initial patch or a sub-patch into two or more sub-patches comprises:

adding a new vertex;

and the method further comprising, in response to determining that the initial patch or sub-patch is to be sub-divided:

popping a top vertex from a data structure operating a first in, last out scheme;

pushing the new vertex into the data structure, followed by the popped vertex and a copy of the new vertex; and

in response to determining that the initial patch or sub-patch is not to be sub-divided, popping two vertices from the data structure and outputting any of the popped vertices that have not previously been output.

18. A tessellation unit configured to perform tessellation in a graphics processing pipeline, wherein the tessellation unit comprises hardware logic arranged to:

analyse an initial patch to determine whether to sub-divide the patch;

in response to determining that the initial patch is to be sub-divided, divide the input patch into two or more sub-patches; and

select and tessellate each sub-patch until there is no further sub-division of that sub-patch, wherein sub-patches are selected for tessellation in an order encoded by one or more stored values;

wherein the hardware logic operates recursively at each level of sub-division, and

wherein the hardware logic is arranged to select and tessellate each sub-patch until there is no further sub-division of that sub-patch in an order encoded by one or more stored values by:

selecting one of the sub-patches formed by sub-division of the initial patch based on one or more stored values;

tessellating the selected sub-patch until there is no further sub-division; and

repeating the selecting and tessellating until all the sub-patches formed by sub-division of the initial patch have been tessellated until there is no further sub-division of those sub-patches.