Ordering of patch selection in tessellation operations

Patent metadata

Field	Value
Publication number	US-12469202-B2
Application number	US-202418601817-A
Country	US
Kind code	B2
Filing date	Mar 11, 2024
Priority date	Apr 5, 2018
Publication date	Nov 11, 2025
Grant date	Nov 11, 2025

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:
dividing an initial patch into two or more sub-patches; and selecting and tessellating each sub-patch in an order encoded by one or more stored values.

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 , wherein dividing an initial patch into two or more sub-patches is in response to determining that an initial patch is to be sub divided, and wherein selecting and tessellating each sub-patch comprises selecting and tessellating each sub-patch until there is no further sub-division of that sub-patch in an order encoded by one or more stored values and selecting and tessellating each sub-patch further 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.

4 . The method according to claim 3 , 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 , 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; 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.

12 . The method according to claim 11 , further comprising, 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.

13 . The method according to claim 12 , 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.

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:
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.

15 . The method according to claim 11 , 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.

16 . A method of performing tessellation in a computer graphics system, comprising:
dividing an initial patch into two or more sub-patches; and selecting and tessellating each sub-patch in an order encoded by one or more stored values, and wherein the order for selection is alternated for each increase or decrease in level of sub-division.

17 . A non-transitory computer readable storage medium having stored

Assignees

• Imagination Tech Ltd

Inventors

• Lacey Peter Malcolm

Classifications

• G06T17/20 Primary

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

• G06T17/205

  Re-meshing · CPC title

• G06T15/005 Primary

  General purpose rendering architectures · CPC title

• G06T1/20

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