Ordering of patch selection in tessellation operations

Patent metadata

Field	Value
Publication number	US-10909742-B2
Application number	US-201916376779-A
Country	US
Kind code	B2
Filing date	Apr 5, 2019
Priority date	Apr 5, 2018
Publication date	Feb 2, 2021
Grant date	Feb 2, 2021

Abstract

A method of controlling the order in which primitives generated during tessellation are output by the tessellation unit involves sub-dividing a patch, selecting one of the two sub-patches which are formed by the sub-division and tessellating that sub-patch until no further sub-division is possible before tessellating the other (non-selected) sub-patch. The method is recursively applied at each level of sub-division. Patches are output as primitives at the point in the method where they do not require any further sub-division. The selection of a sub-patch is made based on the values of one or more flags and any suitable tessellation method may be used to determine whether to sub-divide a patch. Methods of controlling the order in which vertices are output by the tessellation unit are also described and these may be used in combination with, or independently of, the method of controlling the primitive order.

First claim

What is claimed is:

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

Assignees

• Imagination Tech Ltd

Inventors

• Lacey Peter Malcolm

Classifications

• G06T17/20 Primary

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title

• G06T15/005 Primary

  General purpose rendering architectures · CPC title

• G06T17/205

  Re-meshing · CPC title

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title