Patent Description:
Tessellation is a technique used in computer graphics to divide up a set of surfaces representing objects in a scene into a number of smaller and simpler pieces, (referred to as primitives), typically triangles, which are more amenable to rendering. The resulting tessellated surface is generally an approximation to the original surface, but the accuracy of this approximation can be improved by increasing the number of generated primitives, which in turn usually results in the primitives being smaller. The amount of tessellation/sub-division is usually determined by a level of detail (LOD). An increased number of primitives is therefore typically used where a higher level of detail is required, e.g. because an object is closer to the viewer and/or the object has a more intricate shape. However, use of larger numbers of triangles increases the processing effort required to render the scene.

The sub-division into triangle primitives is typically performed on patches which are square or triangular in shape (i.e. a quad or a triangle) and which may be curved to fit to the surface of the object they represent (and hence may be referred to as 'surface patches') and/or have displacement mapping applied. The sub-division, however, is not performed on curved patches but is instead performed in the domain of the patch (e.g. as if the patch is planar rather than being defined by, for example, a polynomial equation) which may be defined in terms of (u,v) parameters and referred to as 'parametric space'. This means that the tessellation process is independent of any curvature present in the final surface.

Tessellation may be performed ahead of time (e.g. to compute a number of different views of a scene at different levels of detail and/or from different viewpoints) or may be performed on the fly (e.g. to provide continuous or view-dependent levels of detail). With some existing tessellation methods, a user can experience undesirable visual artefacts where, although the requested level of detail is changed smoothly, the resulting tessellation changes in a discontinuous fashion. <CIT> discloses systems and methods for tessellation, in which a domain is divided by a tessellation unit into a plurality of portions. <CIT> discloses a tessellation method which uses both vertex tessellation factors and displacement factors defined for each vertex of a patch which may be a quad, a triangle or an isoline.

The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known methods and apparatus for performing blending as part of (or following on from) tessellation.

Described herein are a number of different implementations of blender hardware. The blender hardware performs both domain shading and blending (which is a post-process to the domain shading) and whilst some vertices may not require blending, all vertices require domain shading. The blender hardware described herein may comprise a cache and/or a content addressable memory and these data structures are used to reduce duplicate domain shading operations.

A first aspect provides a GPU pipeline according to independent claim <NUM>.

A second aspect provides a method of performing post-tessellation blending according to independent claim <NUM>.

The method may further comprise: generating the UV coordinates of the neighbour vertices from the domain space vertex.

The method may further comprise: determining if the blend weight of an input vertex is equal to one; and in response to determining that the blend weight of an input vertex is equal to one, bypassing the blend unit and generating, in a domain shader, a world space coordinate for the input vertex from the UV coordinate of the input vertex. The method may further comprise: in response to determining that the blend weight of an input vertex is equal to one, bypassing the cache.

The method may further comprise: receiving, at the cache, world space vertices generated by the domain shader for input vertices and their neighbours. The method may further comprise: in response to receiving a world space vertex from the domain shader when all entries in the cache are full, evicting a data pair from a selected entry in the cache and storing the received world space vertex in the selected entry. The method may further comprise: selecting a cache entry for eviction based on an age of the cache entry; or selecting a cache entry for eviction based on a distance, in UV space, of the UV coordinate in the data entry and the UV coordinate corresponding to the received world space vertex.

The GPU pipeline may further comprise one or more input buffers.

The method may further comprise, in the blend unit: receiving the blend weight of the input vertex, world space vertices for the input vertex and its neighbour vertices generated in a single task by a domain shader, and generating a single world space vertex for the input vertex. Generating a single world space vertex for the input vertex may comprise: generating a linear average of all input neighbour world space vertices using fixed weights; and performing a linear interpolation of the world space vertex for the input vertex itself and the world space vertex output by the linear averaging hardware logic block using the blend weight to generate a single world space vertex for the input vertex.

Packing, by a task manager, UV coordinates for the input vertex and neighbour vertices of the input vertex into jobs within the same task may comprise: placing UV coordinates for input vertices into jobs at a front end of a task; placing UV coordinates for neighbour vertices into jobs at a back end of a task; and in response to placing a UV coordinate for an input vertex into a job at the front end of a task, where the UV coordinate matches an already placed UV coordinate for a neighbour vertex, removing the job for the neighbour vertex.

The method may further comprise: generating the UV coordinates of the neighbour vertices from the domain space vertex and output the UV coordinates to the content addressable memory.

The method may further comprise: converting coordinates of the vertex from fixed-point to floating-point form prior to input to the task manager.

The method may further comprise: remapping data output by the content addressable memory data and destined for the output index buffer by using indices stored in the input index buffer to reference the indices generated by the content addressable memory.

The GPU pipeline or blender hardware may be embodied in hardware on an integrated circuit. There may be provided a method of manufacturing, at an integrated circuit manufacturing system, a GPU pipeline or blender hardware. There may be provided an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the system to manufacture a GPU pipeline or blender hardware. There may be provided a non-transitory computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed, causes a layout processing system to generate a circuit layout description used in an integrated circuit manufacturing system to manufacture a GPU pipeline or blender hardware.

There may be provided an integrated circuit manufacturing system comprising: a non-transitory computer readable storage medium having stored thereon a computer readable integrated circuit description that describes the GPU pipeline or blender hardware; a layout processing system configured to process the integrated circuit description so as to generate a circuit layout description of an integrated circuit embodying the GPU pipeline or blender hardware; and an integrated circuit generation system configured to manufacture the GPU pipeline or blender hardware according to the circuit layout description.

As described above, tessellation involves the selective sub-division of patches, which are typically square or triangular in shape, into smaller triangular patches. The determination as to whether a patch should be sub-divided or not is often made based on one or more tessellation factors (TFs), e.g. by comparing one or more TFs to each other and/or to a threshold value. In some examples edge tessellation factors are used, with each edge of a patch having an edge tessellation factor, and the edge tessellation factor defining how many times the particular edge (and hence the patch which it is part of) should be sub-divided. In other examples (such as in the methods described in <CIT> and <CIT> vertex tessellation factors are used, with each vertex (or corner) of a patch having a vertex tessellation factor.

The term 'surface patch' is used herein to refer to a, usually finite, N-dimensional surface (or in the case of an isoline, an N-dimensional curve segment) which is the result of applying a parametric mapping function to a bounded 2D domain, which is either a quadrilateral, a triangle or any polygon, (or in the case of an isoline, a 1D line segment). The resulting surface or isoline can be considered N-dimensional as it may include not only <NUM> (or <NUM>) dimensions for Cartesian (or homogeneous) spatial positioning, but also other parameters such as texture coordinates. As described above, surface patches may be curved to fit to the surface of the object they represent and/or have displacement mapping applied. Tessellation (i.e. the sub-division of patches), however, is not performed in 'world space' (i.e. it is not performed on curved surface patches) but is instead performed in domain space (which may also be referred to as parametric space or parameter space or UV space) in which any position in the domain can be described by two coordinates (u,v) known as the domain space coordinates, which means that the tessellation process is independent of any curvature present in the final surface.

The term 'patch' is used herein to refer to an ordered set of two, three, four or more vertices (for an isoline, triangle, quad or polygon respectively) which bound a domain. The term 'domain' therefore refers to the two-dimensional space bounded by the vertices of a patch. The term 'input patch' is used to refer to a patch which is input to a tessellation unit. In examples where the tessellation unit performs a pre-processing stage which sub-divides the input patch before repeatedly applying a tessellation algorithm to patches formed by the pre-processing stage, the patches formed in the pre-processing stage are referred to herein as 'initial patches'. Patches which are formed by the sub-division of initial patches are referred to herein as 'sub-patches'. The term 'primitive' is used herein to refer to a patch (e.g. an initial patch or sub-patch) that is output by the tessellation unit because it requires no further sub-division. Whilst input, initial patches and sub-patches are often triangles and the examples below show triangles, in other examples, the input, initial patches and/or sub-patches may be isolines, quadrilaterals or any form of polygon.

The term 'vertex' is used generally to describe a location plus other attributes, where these attributes differ depending upon the context. For example, input control points and output vertices from a domain shader comprise a 3D position plus other parameters such as the normal, tangent, texture, etc. (referred to as a world space vertex), whereas the vertices within the tessellator comprise a domain space coordinate and a vertex tessellation factor (referred to as Tessellator vertices). These vertices within the tessellator are therefore not the same as the input control points or the resulting N-dimensional vertices that form the final triangles. The term 'domain vertex' is used herein to refer to the output structure of each vertex from the Tessellator, describing its state in the domain and this is the structure output to the output vertex buffer. In many examples, the domain vertex is a UV coordinate and in other examples it may additionally comprise a blend weight (BW) and optionally the UV coordinates of one or more neighbouring vertices. In particular this blend weight (BW) may be a displacement factor (DF) and these neighbouring vertices may be two or three parent vertices as described in <CIT> and <CIT>. The displacement factor (DF) of a vertex may then be used as a weight in blending hardware which reduces the visibility of artefacts across frames in continuous levels of detail of Tessellation. Any reference to a DF in the following description is by way of example only and in other examples, the DF may be replaced by any other form of BW (e.g. a per vertex blend weight that may be applied to attributes other than the displacement of the vertex, such as normal, texture UV, colour, etc.).

In the following description, primitives, patches and sub-patches are all described as being triangular in shape, in other examples, they may be isolines or comprise more than three sides (e.g. quads or polygons with more than four sides).

Described herein are a number of different implementations of blender hardware. Blending is a post-process to any geometry subdivision of the geometry pipeline, including the Tessellator Stages or the Geometry Shader. Blending operates by mixing the attributes of a generated vertex with those of its neighbours or vertices given in its adjacency list. Blending may be used to achieve desirable visual effects such as reducing the visibility of temporal artefacts in continuous level of detail.

In most of the examples described below, the blender hardware performs both domain shading and blending and whilst some vertices may not require blending, all vertices require domain shading. It will be appreciated, however, that as blending is independent from domain shading, the domain shader may alternatively be separate from (e.g. outside of) the blender hardware. The blender hardware described herein seeks to reduce power consumption and increase throughput by reducing duplicate domain shading operations, i.e. it reduces instances in which domain shading is performed on the same vertex more than once. The blender hardware described herein may comprise a cache and/or a content addressable memory (CAM).

Whilst the methods and hardware are described herein with reference to post-tessellation domain shading, they are also applicable in other situations where there is a dependency relation (e.g. a parent-child relation as described below or other adjacency relation) between vertices that are being processed by the domain shader. For example, in other situations where sub-division occurs followed by a shading operation (e.g. where there is sub-division in a geometry shader or compute shader and blending is also applied). The methods and hardware described herein may be used where processing of vertices is performed independently except for a final cross-processing (or cross-shading) operation that involves multiple vertices as defined by the dependency relation. References to a parent-child relation below are by way of example only and may alternatively relate to any dependency (or adjacency) relation. The hardware described herein may also be used where the sub-division is performed in world space (rather than in UV space as described herein); however, in such instances, the CAM implementation described herein may not be omitted.

The blender hardware described herein may be part of a graphics processing unit (GPU) pipeline and more specifically may be part of a tessellation pipeline within a GPU pipeline.

<FIG> shows a schematic diagram of an example GPU pipeline <NUM> which may be implemented in hardware within a GPU. As shown in <FIG>, the pipeline <NUM> comprises a vertex shader <NUM>, a tessellation unit <NUM> and blender hardware <NUM>. Between the vertex shader <NUM> and the tessellation unit (or tessellator) <NUM> there may be one or more optional hull shaders, not shown in <FIG> and the GPU pipeline may comprise other elements such as a memory, tiling units and/or other elements not shown in <FIG>.

The vertex shader <NUM> is responsible for performing per-vertex calculations. It has no knowledge of the mesh topology that is being processed and performs per-vertex operations so that it only has information of the current vertex that is being processed.

Unlike the vertex shader, the tessellation unit <NUM> (and any optional hull shaders) operates per-patch and not per-vertex. The tessellation unit <NUM> outputs primitives and in systems which use vertex indexing, an output primitive takes the form of three vertex indices and a buffer of vertex data (e.g. for each vertex, a UV coordinate and in various examples, other parameters such as a displacement factor or blend weight and optionally parent or neighbour UV coordinates). Where indexing is not used, an output primitive takes the form of three domain vertices, where a domain vertex may comprise only a UV coordinate or may comprise a UV coordinate plus other parameters (e.g. a displacement factor or blend weight and optionally, parent or neighbour UV coordinates). The data output by the tessellation unit <NUM> may be stored in memory (not shown in <FIG>).

As described above, tessellation, which is performed by the tessellation unit <NUM>, involves the selective sub-division of patches, which are typically square or triangular in shape, into smaller triangular sub-patches which themselves may be further sub-divided. As described above, the patches or sub-patches output by the tessellation unit <NUM> are referred to as primitives. Sub-division of a patch or sub-patch typically involves sub-dividing edges of the patch or sub-patch by adding a new vertex to the edge (i.e. such that the edge is sub-divided into two shorter edges); although there may be some steps (e.g. pre-processing steps) in which a newly added vertex does not sub-divide the edge but is instead placed within the patch or sub-patch being sub-divided (e.g. at the centre of the patch). Where sub-division involves adding a new vertex to sub-divide an edge, the newly added vertex is referred to as a 'child' vertex with two 'parent' vertices which are the vertices that are connected by the edge that is being sub-divided. Where sub-division involves adding a new vertex within a patch or sub-patch, the newly added vertex is referred to as a 'child' vertex and the 'parent' vertices are the vertices of the patch or sub-patch that is being sub-divided. For example, where a triangle patch or sub-patch is being sub-divided by placing a new vertex at the centre of the patch or sub-patch, the newly added child vertex has three parent vertices. This is one way to generate suitable blend weights and neighbour relationships as input to blending. The tessellation unit <NUM> may implement a tessellation algorithm (or method) that ensures that parent vertices are output before their children. An example of such a tessellation method is described below with reference to <FIG>.

The blender hardware <NUM> shown in <FIG> comprises one or more domain shaders <NUM> and a blend unit <NUM> and processes each output vertex generated by the tessellation unit <NUM>. As described above, the blender hardware may alternatively not comprise the domain shaders and may instead work in conjunction with one or more separate domain shaders that are external to the blender hardware. The domain shader(s) <NUM> act as a second vertex shader for vertices produced by the tessellation unit <NUM>. The domain shader is supplied with a domain space location (u,v) and is given patch information and outputs a full vertex structure. The domain shader uses the patch control points (from the patch information) and the domain space coordinates (UV coordinates) to build the new vertices and applies any displacement mapping (e.g. by sampling a height map encoded in a texture). The domain shading (in the domain shader <NUM>) is left as late as possible in the GPU pipeline <NUM> because it greatly enlarges vertex sizes (i.e. it increases the size of memory required to store each vertex).

The blend unit <NUM> takes as inputs the vertex data output from the domain shader(s) <NUM> for all child vertices or alternatively for each child vertex <NUM> that does not have a BW (e.g. DF) equal to one. For each child vertex <NUM> that is input and has a blend weight that is not equal to one, the blend unit <NUM> also takes as input the vertex data output from the domain shader(s) <NUM> for the neighbour (e.g. parent) vertices, N1 <NUM> and N2 <NUM>, along with the BW (e.g. DF) <NUM> for the child vertex and blends the child and neighbour vertex attributes (with each attribute being blended separately) to generate a single output vertex <NUM> corresponding to each input child vertex <NUM>. As each neighbour vertex may also be a child vertex of its neighbour vertices and two child vertices may share a common neighbour vertex, without the optimizations described herein, the same vertex may be processed by the domain shader(s) <NUM> more than once. Such duplication reduces the throughput of the blender hardware <NUM> and increases its power consumption.

An example implementation of the blend unit <NUM> is also shown in <FIG> and in this implementation the blend unit <NUM> comprises a linear averaging hardware logic block <NUM> and a hardware interpolation unit <NUM>. Both of these blocks <NUM>, <NUM> perform linear interpolation; however the linear averaging block may take more than two inputs and has a fixed, equal weight for all inputs. The linear averaging hardware logic block <NUM> performs an averaging operation on all input vertices where this may, for example, comprise generating a linear average of all input vertices, irrespective of how many there are. In other examples and where the vertex's neighbours are the corners of a domain, the linear averaging hardware logic block <NUM> may perform an averaging (or interpolation) operation that is weighted by the barycentric coordinates of the vertex inside the domain. In the example shown in <FIG>, there are two input vertices, the neighbour vertices <NUM>, <NUM> and the linear averaging hardware logic block <NUM> creates a linear average of these two neighbour vertices. There may be some vertices which are special cases and have neighbour information hard coded in the system and these may be supplied as input to the blending operation (and in particular to the linear averaging hardware logic block <NUM>) when those particular vertices are processed. The hardware linear interpolation unit <NUM> interpolates the output from the linear averaging hardware logic block <NUM> and the child vertex <NUM> with a weight which is the BW (e.g. DF) <NUM> for the child vertex, output by the Tessellator.

In examples where all child vertices are input to the blend unit <NUM>, those child vertices with a BW of one bypass both the averaging block <NUM> and the interpolation stage <NUM> within the blend unit <NUM> (as indicated by the dotted arrow).

Although not shown in <FIG>, the BW (e.g. DF) that is input to the blend unit <NUM> may be converted from fixed-point format to floating-point format prior to being used as a weight in the interpolation unit <NUM>.

Although the blend unit <NUM> in <FIG> is shown as comprising a linear averaging hardware logic block <NUM> and a hardware linear interpolation unit <NUM>, in other examples, the interpolation may not be a fixed function but may instead be performed using a shader (e.g. such that there is a further shader in the blend unit <NUM> or such that the blend unit <NUM> is part of the domain shader <NUM>). For example, the blend operation may be performed as a final step of the domain shade of a vertex, whereby the neighbour information (e.g. the parent vertices) are derived from the vertex and shaded as sub-processes of the shader. Additionally if the Tessellation is performed after projection then rather than a linear interpolation, projective correct interpolation may be used instead.

In examples where the GPU pipeline <NUM> uses a tile-based rendering approach, the GPU pipeline <NUM> may additionally comprise a tiling unit (not shown in <FIG>) that is logically positioned after the blender hardware <NUM>. In such examples the domain shader <NUM> within the blender hardware <NUM> may be modified so that it outputs a positional attribute only and omits (or bypasses) operations to generate other parameters such as texture coordinates, normal, etc. The tiling unit reads the data generated by the tessellation unit <NUM> (which, as described above, may be stored in memory) and generates per-tile display lists. Each per-tile display list identifies, for a particular tile, those primitives which are at least partially located within that tile. These display lists may be generated by the tiling unit using a tiling algorithm and may be written to memory and read by subsequent elements in the GPU pipeline <NUM>. This enables the subsequent elements to perform rendering operations (or other operations) on a tile by tile basis and this may, for example, improve efficiency.

<FIG> shows a schematic diagram of a first example blender hardware <NUM> in more detail that may be implemented as the blender hardware <NUM> in the GPU pipeline <NUM> shown in <FIG>. <FIG> is a flow diagram showing the operation of the blender hardware <NUM>. As shown in <FIG>, the blender hardware <NUM> receives as an input a domain space vertex generated by the tessellation unit <NUM> and information on the surface patch (e.g. control points of the patch comprising n vertices output from the vertex shader, as well as the value of n) which bypasses the tessellation unit <NUM> and hence may be received from the vertex shader <NUM>. The control points of the surface patch describe the behaviour of the surface that the tessellated vertices are attempting to approximate. A domain space vertex comprises the UV coordinates of the vertex itself, the UV coordinates of its neighbour (e.g. parent) vertices and the vertex's BW (e.g. the vertex's DF). The domain space vertex output by the Tessellator may not comprise the UV coordinates of its neighbour vertices and instead these may be inherent from the UV coordinate of the vertex itself. In this case a vertex decompression stage may be included as part of the blending unit in order to generate the extra coordinates. Additionally, where the number of neighbour vertices is not fixed (e.g. at two), the domain space vertex may also specify the number of neighbour vertices.

The blender hardware <NUM> shown in <FIG> comprises one or more domain shaders <NUM> and a blend unit <NUM>, as described above with reference to <FIG>. Although two domain shaders <NUM> are shown in <FIG>, this is by way of example only and there may, in other examples, be one domain shader or one block of domain shaders or alternatively the domain shaders may be external to the blender hardware <NUM>. The blender hardware <NUM> further comprises an optional blend weight assessment logic block <NUM>, a vertex decompression logic block <NUM> and a cache for world space vertices <NUM> (i.e. vertices output by the domain shaders <NUM>). In other examples, the BW assessment logic block <NUM> may be omitted and all vertices may be processed in the same way irrespective of their BW value. The blender hardware <NUM> may additionally comprise other elements not shown in <FIG>, such as elements that convert coordinates (e.g. U and V coordinates) from a fixed-point integer (e.g. a value between <NUM> and <NUM> or <NUM>) to a floating point value (e.g. in the range [<NUM>,<NUM>]) in examples where the tessellation unit <NUM> outputs a fixed point value, in order that the domain shaders <NUM> receive inputs in floating point format.

As described above, the domain space vertex that is received as an input comprises the UV coordinates of the vertex itself, the vertex's BW (e.g. the vertex's DF) and, unless the UV coordinates are inherent from the UV coordinates of the vertex itself, the UV coordinates of its neighbour (e.g. parent) vertices. The vertex decompression logic block <NUM> comprises hardware logic arranged to convert the domain space vertex (which is output from the tessellation unit <NUM>) into multiple domain space coordinates, for the child vertex and its neighbours.

The cache for world space vertices <NUM> is arranged to store a number of (UV coordinate, world space vertex) pairs, with the UV coordinate being used to address the cache entries. In various examples, the cache <NUM> may be arranged to store <NUM> data pairs or more than <NUM> data pairs (e.g. <NUM> data pairs). For known tessellation schemes even a small cache (e.g. <NUM> data pairs) yields a large reduction in the number of duplicate domain shader calls and if the cache is arranged to store <NUM> or more data pairs, the amount of excess domain shader processing may be reduced by over <NUM>% in the worst case and on average by <NUM>% for spatially coherent geometry, such that there are <NUM>-<NUM> domain shader calls per vertex instead of one plus the average number of neighbouring vertices, typically no less than <NUM> in total (where the cache is omitted). By increasing the size of the cache the chance of a cache miss (which may result in a duplicate domain shader call) is reduced; however, as the size of the cache increases, the time taken to perform a cache look-up is also increased and the improvement that is achieved, in terms of a reduction in duplicate domain shader calls, does not increase linearly. In various examples, the entries in the cache may be sorted by the UV coordinates to increase the speed of cache look-ups.

The cache <NUM> may operate a replacement policy of FIFO (first-in-first-out) such that once the cache is full, the oldest entry in the cache is ejected when there is a new world space vertex that needs to be stored (in block <NUM>). In other examples, the cache may instead select a data pair for ejection based on the UV coordinates of the new vertex to be added to the cache. For example, the data pair that is selected for ejection may be the data pair with a UV coordinate which is furthest away in UV space from the UV coordinate in the new data pair that is to be stored in its place. By using a replacement policy that ejects the data pair for a vertex that is furthest away in UV space, the number of domain shader calls (which are a consequence of a cache miss) can be significantly reduced (e.g. halved). This can be further reduced if the tessellation unit <NUM> implements a tessellation algorithm (or method) that produces primitives more coherently in UV space, such as alternating subdivision of left and right sub-patches in a known binary subdivision tessellation scheme. An example of such an improved tessellation method is described below with reference to <FIG>. This further reduction in the number of domain shader calls is achieved because this triangle ordering reduces the distance (in UV space) between adjacent triangle patches and hence vertices that are input to the blender hardware <NUM> are nearer to their neighbouring vertices in the output order.

Within the blender hardware <NUM> shown in <FIG>, the blend weight is assessed (block <NUM>) in the optional BW assessment logic block <NUM>. This logic block <NUM> comprises hardware logic arranged to check whether the vertex's blend weight is equal to one. A blend weight that is equal to one indicates that the vertex is in its final state and is not affected by its neighbours, and hence blending (in the blend unit <NUM>) is redundant and so not required. As many vertices that are input to the blender hardware <NUM> (e.g. approximately one half of displacement factors in certain tessellation schemes) will have a blend weight equal to one, by filtering these out early and bypassing the blend unit <NUM> for these vertices, the overall amount of processing that is performed by the blender hardware <NUM> is significantly reduced and so the power consumption is similarly significantly reduced.

If a vertex has a blend weight equal to one ('Yes' in block <NUM>), a check is performed to determine whether the world space vertex is stored in the cache <NUM> (block <NUM>). If the world space vertex is not in the cache ('No' in block <NUM>), the UV coordinates of the vertex (denoted UVC in <FIG>) are input to the domain shader <NUM> (block <NUM>) and the domain shader <NUM> generates a world space vertex from the input UV coordinates and the surface patch information. If the world space vertex is in the cache ('Yes' in block <NUM>), the domain shader <NUM> is bypassed. The world space vertex, which is either generated by the domain shader or accessed from the cache, is then output from the blender hardware <NUM> (block <NUM>) and if the world space vertex wasn't already stored in the cache for world space vertices <NUM>, it is added into the cache (block <NUM>).

If it is determined (in the blend weight assessment logic block <NUM>) that the vertex's blend weight is not equal to one ('No' in block <NUM>), a check is performed to determine whether the world space vertex is stored in the cache <NUM> (block <NUM>). If the world space vertex is not in the cache ('No' in block <NUM>), the UV coordinates of the vertex, UVC, are input to the domain shader <NUM> (block <NUM>) and as described above, the domain shader <NUM> generates a world space vertex. If the world space vertex is in the cache ('Yes' in block <NUM>), the domain shader <NUM> is bypassed. Even once the world space vertex has been obtained (e.g. generated in the domain shader <NUM> or accessed from the cache <NUM>) blending cannot occur until the world space vertices for the neighbour vertices are also available ('Yes' in block <NUM>). As well as outputting the UV coordinates of the vertex, UVC, the blend weight assessment logic block <NUM> also outputs input domain space vertex to the vertex decompression block <NUM> which generates the UV coordinates of the neighbour vertices, denoted UVN1 and UVN2 in <FIG> (block <NUM>). As described above, these UV coordinates are used to address the cache <NUM> and hence to determine whether either or both of the world space vertices for the neighbour vertices are stored in the cache (block <NUM>). If both world space vertices for the neighbour vertices are in the cache ('Yes' in block <NUM>), then these values, denoted N1 and N2 in <FIG>, along with the world space vertex for the vertex and the vertex's blend weight are input to the blend unit <NUM> (block <NUM>). If, however, either or both of the world space vertices for the neighbour vertices are not in the cache ('No' in block <NUM>, i.e. resulting in at least one cache miss), then the UV coordinates of the missing vertices are input to the domain shader <NUM> (block <NUM>). As described above, the domain shader <NUM> generates a world space vertex from the input UV coordinates (e.g. UVN1 or UVN2) and the surface patch information. The generated world space vertices for the missing neighbours are stored in the cache <NUM> (block <NUM>).

Once the world space vertices for the input (child) vertex and the neighbour vertices are available ('Yes' in block <NUM>), then these world space vertices are input to the blend unit <NUM> (block <NUM>). The operation and structure of the blend unit <NUM> may be as described above with reference to <FIG>. The output from the blend unit <NUM>, which is a blended world space vertex, is then output from the blender hardware <NUM> (block <NUM>).

Where both neighbour UV coordinates along with the corresponding world space vertices are already stored in the cache <NUM> ('Yes' in block <NUM>), the latency is minimised because blending (in blend unit <NUM>) can occur as soon as the domain shader has processed the input vertex's UV coordinates to generate the corresponding world space vertex. Where neither neighbour UV coordinate is found in the cache <NUM>, the latency can be reduced by running three domain shaders in parallel (one for each neighbour and one for the vertex itself); however the latency may be increased (e.g. to the maximum time taken to process any of the three vertices) and additional power is required compared to where a cache is used. Hence the use of a cache, as described above, reduces both latency and power consumption.

As described above, where world space vertices are generated (in the domain shader <NUM>) for neighbour vertices (in block <NUM>) or an input vertex with a blend weight equal to one (in block <NUM>), then the world space vertices are stored in the cache <NUM> (block <NUM>). However, the world space vertex for an input vertex with a blend weight that is not equal to one (and hence is less than one as the blend weight is between <NUM> and <NUM> inclusive) need not be stored in the cache because such vertices cannot be parents as they are not yet in their final position.

As shown in <FIG>, a cache look-up is performed (in block <NUM>) prior to domain shading. However, where a tessellation method is used that guarantees to output neighbour vertices before their children (e.g. the method described below with reference to <FIG>, these cache look-ups (i.e. block <NUM> in <FIG>) may be omitted and the UV coordinate of the vertex may be passed directly to a domain shader <NUM>.

<FIG> shows a schematic diagram of a second example blender hardware <NUM> in more detail that may be implemented as the blender hardware <NUM> in the GPU pipeline <NUM> shown in <FIG>. As shown in <FIG>, the blender hardware <NUM> receives as inputs the domain space vertices generated by the tessellation unit <NUM> and information relating to the surface patch which bypasses the tessellation unit <NUM> and hence may be received from the vertex shader <NUM>. The domain space vertex comprises the UV coordinate of the vertex and the vertex's blend weight and may also comprise the UV coordinates of the neighbour vertices (e.g. parent vertices) where these are not inherent from the UV coordinate of the vertex itself and the number of neighbour vertices where this is not a fixed number.

The blender hardware <NUM> shown in <FIG> comprises one or more domain shaders <NUM> and a blend unit <NUM> as described above with reference to <FIG>. As noted above, in variations on this blender hardware <NUM>, the domain shaders <NUM> may be external to the blender hardware <NUM>. <FIG> and <FIG> are flow diagrams showing the operation of the blender hardware <NUM>. The blender hardware <NUM> further comprises a vertex decompression block <NUM>, a content addressable memory (CAM) <NUM> that comprises (or has associated with it) a counter <NUM>, a conversion logic block <NUM>, a task manager <NUM>, an output index buffer <NUM> and an output vertex buffer <NUM>. The blender hardware <NUM> may additionally comprise other elements not shown in <FIG>, e.g. a second smaller CAM or other data structure.

The vertex decompression block <NUM> (like the vertex decompression block <NUM> shown in <FIG>) comprises hardware logic arranged to convert the domain space vertex (which is output from the tessellation unit <NUM>) into multiple domain space coordinates, for the child vertex and its neighbours.

The CAM <NUM> is provided in order to stitch together equivalent vertices (i.e. vertices with the same UV coordinate and same blend weight, although one may be child vertex and the other a neighbour vertex with an implicit blend weight of <NUM>) and is arranged to store a number of (UV coordinate, patch reference, index) tuples (e.g. <NUM>, <NUM> or <NUM> data tuples). The CAM <NUM> may store both parent and neighbour vertices or, where the tessellation method guarantees that neighbour vertices are output before their children, the CAM <NUM> may only store child vertices. The task manager <NUM> assembles vertices into tasks that are then processed by the domain shader <NUM> and blend unit <NUM>. The term 'job' is used herein to refer to a single instruction for execution of a shader and the term 'task' is used herein to refer to a set of jobs (e.g. <NUM>, <NUM>, <NUM>, etc. jobs) to be processed together. Each task therefore comprises a plurality of vertices and all the vertices within a task are processed in parallel so that the world space vertices for all vertices in a task are available for use by the blend unit <NUM> when processing vertices in that task. The task manager <NUM> therefore minimises duplicate work by efficient packing of vertices into tasks, i.e. by ensuring that where a vertex is not found to be stored in the CAM, the vertex and its neighbour vertices are added to the same task (with the vertex job having indices associated with it to indicate which vertices in the task are its neighbours). This means that the domain shader results for the vertex and its neighbours are all available at the same time for input to the blend unit <NUM>. In the blender hardware <NUM>, all geometry after the CAM stage is indexed (e.g. for primitive assembly before rasterization or the geometry shader stage).

As shown in <FIG>, the CAM <NUM> receives as input domain space vertices generated by the tessellation unit <NUM> and a reference to the current patch (e.g. a patch index, which is part of the surface patch information input to the blender hardware <NUM>). Each input domain space vertex is checked against the current CAM entries, which as described above comprise (UV coordinate, patch reference, index) tuples (block <NUM>). The patch reference that is stored in a CAM entry may, for example, be an index to a list of patches and as a memory optimisation, the patch reference stored in the CAM may be a shorter, local patch index which references a look-up table from which the longer patch reference may be obtained. If a match is found for both the UV and the patch reference ('Yes' in block <NUM>), the corresponding entry index is passed out to the output index buffer <NUM> (block <NUM>). If a match is not found ('No' in block <NUM>), an entry in the CAM <NUM> is replaced by the new vertex UV (block <NUM>), the counter <NUM> is incremented (block <NUM>) and the new counter value is assigned to the new CAM entry (block <NUM>) as well as being passed on to the output index buffer <NUM> (block <NUM>). The entry that is replaced (in block <NUM>) may, for example be the oldest entry in the CAM or alternatively a different replacement scheme may be used, e.g. with the entry that is furthest away in UV space being replaced. Additionally, if a match is not found ('No' in block <NUM>), the UVs of the neighbours are generated (block <NUM>). If the domain vertices have fixed point coordinates, the coordinates of the vertex and its neighbours are converted from fixed-point form to floating-point form (block <NUM>, in the converter logic block <NUM>) and then passed to the task manager <NUM> (block <NUM>). This ensures that the coordinate is in floating-point form before being input to the domain shader <NUM>.

The task manager <NUM> is arranged to assign a task job to each received vertex and to each neighbour of the new vertex (block <NUM>). These jobs are then packed into a task (block <NUM>) and in various examples an additional small CAM or other data structure (not shown in <FIG>) may be used to store details of which vertices are already in the task and hence to check whether a vertex (in the form of its UV coordinate) has already been added to the task. This small CAM or data structure may, for example, store (UV, task index) data pairs. When duplicate UVs are added to the task (either as a vertex or one of its neighbours) only one job is processed for the vertex so that duplicate work is not performed. To ensure that only one job is processed for the vertex, the jobs in the task are condensed and this is performed in such a way that the order of vertices output from the blender hardware <NUM> matches the order the vertices are submitted to the task (in block <NUM>). To achieve this, the child vertex jobs occupy contiguous entries from the front of the task, ensuring all indices are correct and neighbour only jobs occupy entries at the end of the task, such that the resultant task comprises jobs organised as follows by the task manager:
[child only or child & neighbour jobs | empty jobs | neighbour only jobs].

This may be achieved (in block <NUM>) by the task manager placing child jobs on the left in turn and all neighbour jobs on the right (when defined logically). If a new child job is entered that matches a neighbour job then the new job is placed at the end of the left group and the neighbour job on the right is removed. In order to use space efficiently, when a neighbour job on the right is removed, all neighbour jobs to its left may be shifted one job to the right to remove the gap or the leftmost neighbour job may be moved into the empty slot instead.

If at any stage the new vertex (including all of its neighbours) cannot fit into the task ('Yes' in block <NUM>), all the jobs are flushed and processed (block <NUM>) and the vertex is added to the next task (block <NUM>). This implies that the task size should be at least n+<NUM> (when the maximum number of neighbours is n) so that every vertex and its neighbours can be processed as jobs in a single task; however larger tasks (e.g. comprising <NUM> or <NUM> jobs) provide greater efficiency. Having processed the task, the output from the blend unit <NUM> is input into the output vertex buffer <NUM> (block <NUM>). An example method of operation of the task manager <NUM> is described in more detail below with reference to the flow diagram in <FIG>.

The operation of the domain shader <NUM> and blend unit <NUM> may be fixed function or may use programmable shader code. Although the domain shader <NUM> and blend unit <NUM> are shown as separate elements in <FIG> (and also in <FIG> and <FIG>), the processing may be done locally or passed to a different unit for execution (such as to a unified shader core, USC, within the GPU).

As shown in <FIG>, in various examples the counter <NUM> is updated (in block <NUM>) when jobs are flushed (in block <NUM>). For example, if the system requires that all vertices processed in the task are output (even if they are not referenced by the Output Index Buffer <NUM>) then the counter <NUM> is increased (in block <NUM>) to the next multiple of the task size each time a task is processed so that the indices are correct. This increase may be communicated to the CAM <NUM> using a Task Flush Signal generated by the task manager <NUM>. In various examples, in order to reduce the maximum size of the counter <NUM> of the CAM <NUM> when processing multiple patches and therefore reduce the size of indices in CAM entries, the counter <NUM> may be reset for each patch and an index offset accumulated - the indices can then be offset by this value before being emitted from the CAM.

<FIG> is a flow diagram showing an example method of operation of the task manager <NUM> in more detail. The operations shown in <FIG> correspond to blocks <NUM>-<NUM> in <FIG>. As shown in <FIG>, the task manager receives a vertex from the CAM <NUM> via the converter hardware <NUM> (block <NUM>) and builds one or more jobs for the vertex and each of its neighbours, consisting of a UV coordinate and a Patch Reference, (block <NUM>). The task manager <NUM> processes each neighbour in turn before processing the vertex (block <NUM>) in order to generate the neighbour task indices first, followed by the vertex itself. Furthermore, as described below, the vertex itself is treated differently to its neighbours. Each job assigned by the task manager <NUM> has one of three states determining how much processing the vertex requires and these are: NO_SHADE, NO_OUTPUT and OUTPUT. The details of these job states are described below.

As shown in <FIG>, neighbour jobs ('Yes' in block <NUM>) are checked against the current Task Entries (block <NUM>), i.e. against all the jobs already added to the current task. If a match is found ('Yes' in block <NUM>) the index of that job is returned (block <NUM>). If not, ('No' in block <NUM>) and the task is not full ('No' in block <NUM>), the job is added to the first available entry from the back end of the Task, is marked NO_SHADE (block <NUM>), and the index of this job is returned (block <NUM>).

The job for the vertex itself is also checked against the current Task Entries (block <NUM>). If a match is found ('Yes' in block <NUM>) the current job entry, which will be a neighbour job (marked NO_OUTPUT, from a previous instance of block <NUM>), is moved to the first available entry from the front of the Task, is changed to OUTPUT (block <NUM>), and all index references to the found entry are replaced by the new entry index (block <NUM>). If, however, no match is found ('No' in block <NUM>), and the task is not full ('No' in block <NUM>), the job is added to the first available entry from the front of the Task and is marked OUTPUT (block <NUM>). It is then assigned its neighbour indices and the jobs referenced by these indices are updated from NO_SHADE to NO_OUTPUT (block <NUM>).

In order to update index references at the point of change (in block <NUM>) the Task Manager <NUM> can either iterate through all the tasks looking for any instance of the old index or, if back references are added (where a back reference is a reference in a neighbour vertex job to the tasks that depend upon them), it can go directly to the outdated entries.

The assumption that a duplicate UV found in the Task must be a neighbour job can be made if and only if the size of the CAM is greater than or equal to the number of job entries, as any sequence of this many vertices submitted to the Task Manager will have any duplicates merged by the CAM. An alternative way for the task manager to operate is for each vertex to be added to the task in turn (without adding neighbour jobs), then once the task is sufficiently full a second pass of the task is made to add indices to each vertex with neighbours corresponding to the jobs of these neighbours. If a neighbour is not found it is simply added to the end of the task and marked as NO_OUTPUT rather than OUTPUT. However in this scheme a sufficient number of job slots must be reserved at the end of the task in order to fit in these extra neighbours.

If at any point the Task is full ('Yes' in block <NUM> or block <NUM>), i.e. all entries are occupied by jobs, the Task is flushed (block <NUM>), thereby freeing up all the entries for subsequent vertices, and the flushed jobs are dispatched to the domain shader <NUM> and blend unit <NUM> (which as described above may be implemented as a shader processor, e.g. a USC, that is configured to perform both domain shading and blending). Once processing has finished the results corresponding to OUTPUT jobs are passed (in their Task entry order) to the Output Vertex Buffer <NUM> or, in systems where feedback is supplied by the task manager <NUM> to the CAM <NUM>, the results of every job are passed to the Output Vertex Buffer <NUM>.

<FIG> shows a schematic diagram of a third example blender hardware <NUM> in more detail that may be implemented as the blender hardware <NUM> in the GPU pipeline <NUM> shown in <FIG>. The third example blender hardware <NUM> is very similar to that shown in <FIG> and described above; however, the blender hardware shown in <FIG> is configured for use when the geometry output by the tessellation unit <NUM> is indexed. Consequently, the blender hardware <NUM> comprises two additional elements: a CAM index buffer <NUM> and a remapping logic block <NUM>.

If the vertices output by the tessellation unit <NUM> are compressed, the blender hardware <NUM> (like the blender hardware <NUM>) may comprise hardware logic elements arranged to decompress vertices <NUM> prior to passing them (in their decompressed form) to the CAM <NUM> (e.g. a vertex decompression block <NUM> as shown in <FIG> and described above). The blender hardware <NUM> (and similarly the blender hardware <NUM>) may also comprise one or more input buffers <NUM>, <NUM>.

The blender hardware <NUM> operates as described above with reference to <FIG> and <FIG> with the addition that the CAM <NUM> outputs indices to the CAM index buffer <NUM> instead of directly to the output index buffer <NUM> and the remapping logic block <NUM> is arranged to assemble the final data that is input to the Output Index Buffer <NUM> by using the indices stored in the Input Index Buffer <NUM> to reference the new indices (as generated by the CAM <NUM> based on values of the counter <NUM>) stored in the CAM Index Buffer <NUM>.

As described above with reference to <FIG> and <FIG>, when the Task is full ('Yes' in any of blocks <NUM>, <NUM> and <NUM>), the contents are processed with fixed function and/or shader programmable code in the domain shader <NUM> (blocks <NUM> and <NUM>). When using tessellation schemes producing vertices with neighbour information, the blend unit <NUM> may be used to mix attributes between domain shader results of the vertex and domain shader results of its neighbours. This may occur in the same shader core as the domain shader as the neighbours are packed into the same task as their children.

The responsibility of the task manager <NUM> (in blender hardware <NUM>, <NUM>) is to ensure all neighbours are assigned jobs in the task and that all references to these task indices are properly generated. Additionally, the Task Manager <NUM> is responsible for setting the correct state for each job as follows:.

<FIG> is a schematic diagram showing stages of processing performed on flushed tasks and these tasks are all labelled with their task state, which may also be referred to as the task type. NO_SHADE jobs, such as job <NUM> in <FIG>, undergo no processing as they do not contribute to the results of any vertex. NO_OUTPUT jobs, such as jobs <NUM> and <NUM>, relate to vertices which are parents of other vertices in the task but are not themselves child vertices, and these are shaded and not blended but their results are used in the blending of other vertices (i.e. the relevant child vertices). OUTPUT jobs, such as <NUM>, <NUM>, <NUM>, <NUM> and <NUM>, are child vertices (and may also be parent vertices for other vertices in the task) and these are shaded, blended and sent to the Output Vertex Buffer <NUM> as now blended world vertices.

The Domain Shade stage (in domain shader <NUM>) occurs in the same way as in any other Tessellation Scheme. A domain space UV and a set of domain Control Points (fetched using the Patch Reference) are used to generate all the world space attributes of the vertex e.g. position, normals and texture coordinates.

The blending operation (in blend unit <NUM>) uses fixed function or programmable code that is executed for each job with permission to access to any of the post domain shader attributes of neighbours in order to modify results of that job, e.g. to interpolate between the current result and the average of the results of two neighbours. When the Blending stage is given as user programmable code, performing modifications on a subset of the world space attributes reduces the total operations. All vertices that are blended are output.

In scenarios where both the Domain Shader <NUM> and Blend Unit <NUM> are given as user programmable shader code, both stages may be performed as a single shader execution in a processor (e.g. the USC) with a barrier between the DS and Blender sections. All accesses to attributes of neighbour results occur after this barrier.

<FIG> shows how much processing is required for jobs of each state, however in various examples, in order to treat all jobs the same those with the NO_SHADE or NO_OUTPUT states can still be processed by the same Domain Shader and Blender code and Output to the Output Vertex Buffer even if the results are never referenced by an index. In this case, as described above, the counter <NUM> is updated to the next multiple of the Task size every time the Task is flushed and this is triggered by the task manager <NUM> sending a flush signal back to the CAM <NUM> (or counter <NUM>).

<FIG> is a schematic diagram that illustrates the task packing operation that is performed by the task manager <NUM> in the blender hardware <NUM>, <NUM>. <FIG> shows an example set of four primitives <NUM>-<NUM> processed by the Task Manager <NUM> and in this example there is adjacency information provided for two vertices only, v<NUM> and v<NUM> (as indicated by the arrows in <FIG>). In this example the Task Size is <NUM>, and the CAM <NUM> has produced no duplication of vertices.

First, vertex v<NUM> is added to the task and it has no parents that need to be added. Similarly, v<NUM> can be added to the task on its own. The next vertex v<NUM> has two parents, v<NUM> and v<NUM>. Vertex v<NUM> is already in the task but v<NUM> is not and so vertex v<NUM> is added to the task as a parent. The next vertex, v<NUM>, from the CAM is already in the task. The next vertex, v<NUM>, from the CAM cannot fit in the task (even without its parent vertices) and so the first task is flushed. In the first task, all jobs are marked OUTPUT as they correspond to corner vertices of a primitive and need to be output.

Vertex v<NUM>, which could not fit into the first task, is added to the second task along with its parents v<NUM> and v<NUM>. The next vertex, v<NUM>, from the CAM is already in the task. There are no more vertices shown in <FIG>; however, if the next vertex from the CAM has two parents, at least one of which is not already in the second task, then the new vertex cannot fit into the one available job slot and so the second task must be flushed and the vertex (and its parents) entered into the next task. In the second task, the only two entries that need to be passed to the Output Vertex Buffer are v<NUM> and v<NUM> and are thus marked OUTPUT. Vertex v<NUM> is in the Task only as a neighbour so is marked NO_OUTPUT and the empty job is marked NO_JOB. As v<NUM> is the parent of two vertices (v<NUM> and v<NUM>) processed in different tasks, it must be included in both tasks and therefore is processed twice.

Although there are two ways in which a Task can fail to output a final vertex for each available job entry in the Task (e.g. because some vertices, such as v<NUM> in the example of <FIG>, are included in more than one task and because not all the tasks are full, such as the second task in the example of <FIG>), these situations occur relatively infrequently, for example at around an average of <NUM> entries per Task for the tessellation scheme shown in <FIG>.

It will be appreciated that while <FIG> shows a task with <NUM> job slots, this is just one example task size. As the number of entries in a task is increased, the task efficiency also increases. For a task size of <NUM>, <NUM> or <NUM> job slots, the efficiency is around <NUM>% or more for the tessellation scheme shown in <FIG>.

<FIG> is a flow diagram showing an example tessellation method that controls the order in which primitives are output by a tessellation unit (e.g. tessellation unit <NUM> in <FIG>) and this method may be described with reference to the example patches shown in <FIG>. As described above, the method alternates the order that new patches are processed for each level of sub-division within the tessellation unit and as a consequence of this, adjacent primitives in the output ordering are guaranteed to be neighbouring primitives in UV space and thus share two vertices.

The method shown in <FIG> takes as an input, an initial patch (which may, in various examples, be an initial triangle patch) and <FIG> shows an example triangle initial patch <NUM>. As described above, a triangle patch is an ordered set of three vertices which bound a domain and in the examples described herein, this ordered set of vertices is written (T, L, R), where T, L and R refer to the top, left and right vertices respectively (as shown in <FIG>).

As shown in <FIG>, an assessment is made to determine whether sub-division of the initial patch <NUM> is required (block <NUM>). This determination may be made using any suitable tessellation method (e.g. any tessellation method that involves binary sub-division) and two examples which use vertex tessellation factors are described in <CIT> and <CIT>.

If it is determined that the initial patch needs to be sub-divided ('Yes' in block <NUM>), then left and right sub-patches are formed (block <NUM>). This sub-division of the initial patch <NUM> may comprise adding a mid-vertex (denoted M) on the edge between the left and right vertices (as shown in <FIG>) and in various examples the mid-vertex may be added at the mid-point between the left and right vertices. Both of these patches <NUM>, 1304R which are formed (in block <NUM>) are triangle patches and comprise an ordered set of three vertices: (M, R, T) and (M, T, L), but in other examples they may be isolines or have more than three sides, and they may be referred to as the right sub-patch 1304R and the left sub-patch <NUM> respectively.

One of the newly formed sub-patches (i.e. the left sub-patch <NUM> or the right sub-patch 1304R formed in block <NUM>) is then selected (in block <NUM>) to be further tessellated ahead of the other of the newly formed sub-patches by inputting the selected sub-patch back into the method of <FIG>. The order of selection of the left or right sub-patch (in block <NUM>) is made based on the values of one or more flags and two different examples of the use of flags are described below. In this way, the method of <FIG> is applied recursively at each level of sub-division of an initial patch with one branch of the sub-division tree being sub-divided fully, before assessing the other branch of the sub-division tree and with the order of selection at each branching point being determined by the one or more flags.

In a first example, there is a flag (e.g. a single bit flag) for each patch (e.g. for each initial patch and for each sub-patch which is subsequently formed by tessellation). This per-patch flag determines whether the left sub-patch or the right sub-patch is selected first and input back into the method of <FIG> (in block <NUM>) when that patch is sub-divided, i.e. when sub-dividing the initial patch (in block <NUM>), it is the flag associated with the initial patch that determines the selection made in the subsequent step (in block <NUM>). In such an example, this makes a triangle patch an ordered set of three vertices and a flag, e.g. (T, L, R, F) or (T, L, R, F) where F and F represent the two different flag values (e.g. off and on, <NUM> and <NUM>).

If the flag of the initial patch <NUM> (which is being sub-divided in block <NUM> as a consequence of the assessment in block <NUM>) has a first value of the flag (e.g. F) then the right sub-patch is selected and processed first (in block <NUM>) and the left sub-patch is input back into the method of <FIG> (i.e. tessellated as needed) only when no further sub-division of the right sub-patch is possible. If, however, the flag of the input patch <NUM> has the other value (e.g. F) then the left sub-patch is selected and processed first (in block <NUM>) and the right sub-patch is input back into the method of <FIG> (i.e. tessellated as needed) only when no further sub-division of the left sub-patch is possible. In such an example, when two sub-patches are generated by sub-division of a parent patch (in block <NUM>, where the parent patch may be the initial patch or a sub-patch formed from the initial patch), the value of the flag for both of the newly formed sub-patches is set to have the opposite value to the parent patch. Consequently, if the initial patch is (T, L, R, F) then the two sub-patches which are formed (in block <NUM>) are (M, T, L, F) and (M, R, T, F). Similarly, if the initial patch is (T, L, R, F) then the two sub-patches which are formed (in block <NUM>) are (M, T, L F) and (M, R, T, F).

In a second example, a single flag may be used in the tessellator which switches state every time the level of recursion decreases or increases by one. In this second example if the single flag has a first value (e.g. F) then the right sub-patch is selected and input back into the method of <FIG> first (in block <NUM>) and the left sub-patch is input back into the method of <FIG> (i.e. tessellated as needed) only when no further sub-division of the right sub-patch is possible. If, however, the single flag has the other value (e.g. F) then the left sub-patch is selected and input back into the method of <FIG> first (in block <NUM>) and the right sub-patch is input back into the method of <FIG> (i.e. tessellated as needed) only when no further sub-division of the left sub-patch is possible. In this example, the swapping of the flag value may, for example, be performed following the decision to sub-divide (e.g. in response to a 'Yes' in block <NUM>) or following the formation of the two sub-patches (in block <NUM>).

As described above, having selected one of the two newly formed sub-patches 1304R, <NUM> (in block <NUM>), the selected sub-patch is input back into the method of <FIG> and tessellated until no further sub-division is possible (in block <NUM>) and this is a recursive process. The selected newly formed sub-patch (e.g. sub-patch 1304R) becomes an input to the method of <FIG> and it is determined whether that patch should be sub-divided (in block <NUM>).

If no sub-division is required ('No' in block <NUM>), the selected newly formed sub-patch is output as a primitive (block <NUM>) and the non-selected newly formed sub-patch (e.g. patch <NUM>) is input to the method of <FIG>.

If, however, sub-division of the selected sub-patch (e.g. 1304R) is required ('Yes' in block <NUM>), left and right sub-patches (<NUM>, 1306R) are formed from the selected sub-patch (in block <NUM>). As the flags at this level of recursion have been swapped (either as a consequence of the flag in sub-patch 1304R being opposite to that in initial patch <NUM> or because the single flag was swapped as part of the method of generating the sub-patches 1304R, <NUM>), instead of selecting the right sub-patch 1306R first (as was the case at the immediately preceding level of recursion which resulted in the selection of sub-patch 1304R), the left sub-patch <NUM> is selected first (in block <NUM>). If this selected sub-patch <NUM> does not require any sub-division, it is output as a primitive (in block <NUM>) and the non-selected sub-patch 1306R is selected and assessed (in block <NUM>). Only when tessellation of both of these sub-patches <NUM>, 1306R is complete, is the non-selected sub-patch <NUM> from the top level of tessellation input back into the method of <FIG> and considered for sub-division (in block <NUM>).

The output primitive (from block <NUM>) takes the form of three indices in systems which use vertex indexing and three domain vertices where indexing is not used and where, as detailed above, a domain vertex may comprise only a UV coordinate or may comprise a UV coordinate plus other parameters (e.g. a weight and optionally the UV coordinates of one or more neighbouring vertices). In particular this weight may be a displacement factor and these neighbouring vertices may be two or three parent vertices as described in <CIT> and <CIT>.

As shown in <FIG>, if the non-selected sub-patch <NUM> requires sub-division ('Yes' in block <NUM>), two new sub-patches are formed, <NUM>, 1308R. The flag used to make the selection (in block <NUM>) has the same value when making a selection between patches <NUM> and 1308R as it did when making a selection between sub-patches <NUM> and 1306R because both sub-divisions occur at the same level of recursion / tessellation and hence the left sub-patch <NUM> is selected first. If this selected sub-patch <NUM> does not require any sub-division, it is output as a triangle primitive (in block <NUM>) and the non-selected sub-patch 1308R is input to the method of <FIG> and assessed (in block <NUM>).

If using the method shown in <FIG>, the initial patch <NUM> is sub-divided into four sub-patches <NUM>, 1306R, <NUM>, 1308R, the sub-patches are generated and their primitives output in the following order: <NUM>, 1306R, <NUM>, 1308R and this ordering (with output primitives labelled <NUM>-<NUM> in order on the tessellated initial patch <NUM>) is shown in <FIG>.

Whilst the method of <FIG> involves use of a tessellation method that performs binary sub-division, the method of <FIG> may also be used where a patch is sub-divided into more than two sub-patches (in block <NUM> e.g. into four sub-patches or X sub-patches, where X may often be a power of <NUM>).

Whilst the methods and hardware are described herein with reference to post-tessellation domain shading, they are also applicable in other situations where there is a dependency relation (e.g. a parent-child relation as described below or other adjacency relation) between vertices that are being processed by the domain shader.

A further example provides blender hardware comprising: an input for receiving a domain space vertex, the domain space vertex comprising UV coordinates of the vertex, a blend weight of the vertex and where the UV coordinates of neighbour vertices are not inherent from the UV coordinates of the vertex itself, the UV coordinates of the neighbour vertices; a cache arranged to store data pairs, each data pair comprising a UV coordinate and a world space vertex generated from the UV coordinate by a domain shader; and a blend unit arranged to receive the blend weight of the input vertex, world space vertices for the input vertex and its neighbour vertices generated by a domain shader or accessed from the cache, and to generate a single world space vertex for the input vertex using the blend weight, wherein the cache is arranged to, in the event of a cache hit at a cache entry for a UV coordinate, output the world space vertex from the cache entry, and in the event of a cache miss for a UV coordinate, output the UV coordinate to a domain shader; and wherein the cache is arranged to receive and store world space vertices generated by the domain shader for input vertices and their neighbours.

A second further example provides a method of performing blending comprising: receiving a domain space vertex, the domain space vertex comprising UV coordinates of the vertex, a blend weight of the vertex and where the UV coordinates of neighbour vertices are not inherent from the UV coordinates of the vertex itself, the UV coordinates of the neighbour vertices; storing, in a cache, data pairs, each data pair comprising a UV coordinate and a world space vertex generated from the UV coordinate by a domain shader; in response to a cache hit at an entry in the cache, outputting the world space vertex from the cache entry; in response to a cache miss at an entry in the cache, outputting the UV coordinate to a domain shader and generating, in the domain shader, a world space vertex from the UV coordinate; and once world space vertices for the vertex and neighbour vertices have been output from the cache or the domain shader, generating, in a blend unit, a single world space vertex for the input vertex using the blend weight.

A third further example provides blender hardware comprising: an input for receiving a domain space vertex, the domain space vertex comprising UV coordinates of the vertex, a blend weight of the vertex and where the UV coordinates of neighbour vertices are not inherent from the UV coordinates of the vertex itself, the UV coordinates of the neighbour vertices; a content addressable memory arranged to store data tuples, each data tuple comprising a UV coordinate, a patch reference and an index; a counter arranged to be incremented when a data tuple is evicted from the content addressable memory; a blend unit arranged to receive the blend weight of the input vertex, world space vertices for the input vertex and its neighbour vertices generated in a single task by a domain shader, and to generate a single world space vertex for the input vertex; a task manager; an output index buffer; and an output vertex buffer, wherein the content addressable memory is arranged to, on receipt of an input vertex, to determine if the UV coordinate of the input vertex is stored in the content addressable memory and in response to the UV coordinate being stored in a data tuple in the content addressable memory, output the index from the data tuple to the output index buffer and in response to the UV coordinate not being stored in the content addressable memory, evict a data tuple from the content addressable memory, add the UV coordinate to a new data tuple with an index having a value equal to a value of the counter and output the index to the output index buffer and output the input vertex to the task manager, and wherein the task manager is arranged to receive input vertices from the content addressable memory, to pack UV coordinates for the input vertex and neighbour vertices of the input vertex into jobs within the same task and in response to determining that a task is full to output all the jobs in the task to the domain shader.

A fourth further example provides a method of performing blending comprising: receiving a domain space vertex, the domain space vertex comprising UV coordinates of the vertex, a blend weight of the vertex and where the UV coordinates of neighbour vertices are not inherent from the UV coordinates of the vertex itself, the UV coordinates of the neighbour vertices; storing data tuples in a content addressable memory, each data tuple comprising a UV coordinate, a patch reference and an index; on receipt of an input vertex, determining if the UV coordinate of the input vertex is stored in the content addressable memory; in response to the UV coordinate being stored in a data tuple in the content addressable memory, outputting the index from the data tuple to an output index buffer; in response to the UV coordinate not being stored in the content addressable memory: evicting a data tuple from the content addressable memory, adding the UV coordinate to a new data tuple with an index having a value equal to a value of the counter, outputting the index to the output index buffer; packing, by a task manager, UV coordinates for the input vertex and neighbour vertices of the input vertex into jobs within the same task; and in response to determining that a task is full, outputting all the jobs in the task to a domain shader and blend unit.

<FIG> shows a computer system in which the GPU pipeline <NUM> described herein may be implemented. The computer system comprises a CPU <NUM>, a GPU <NUM>, a memory <NUM> and other devices <NUM>, such as a display <NUM>, speakers <NUM> and a camera <NUM>. The GPU <NUM> comprises a GPU pipeline <NUM> as described herein. The components of the computer system can communicate with each other via a communications bus <NUM>.

The GPU pipeline <NUM> and blender hardware <NUM>, <NUM>, <NUM> of <FIG>, <FIG>, <FIG> and <FIG> are shown as comprising a number of functional blocks. This is schematic only and is not intended to define a strict division between different logic elements of such entities. Each functional block may be provided in any suitable manner. It is to be understood that intermediate values described herein as being formed by a GPU pipeline or blender hardware need not be physically generated by the GPU pipeline or blender hardware at any point and may merely represent logical values which conveniently describe the processing performed by the GPU pipeline or blender hardware between its input and output.

The GPU pipeline or blender hardware described herein may be embodied in hardware on an integrated circuit. The GPU pipeline or blender hardware described herein may be configured to perform any of the methods described herein. Generally, any of the functions, methods, techniques or components described above can be implemented in software, firmware, hardware (e.g., fixed logic circuitry), or any combination thereof. The terms "module," "functionality," "component", "element", "unit", "block" and "logic" may be used herein to generally represent software, firmware, hardware, or any combination thereof. In the case of a software implementation, the module, functionality, component, element, unit, block or logic represents program code that performs the specified tasks when executed on a processor. The algorithms and methods described herein could be performed by one or more processors executing code that causes the processor(s) to perform the algorithms/methods. Examples of a computer-readable storage medium include a random-access memory (RAM), read-only memory (ROM), an optical disc, flash memory, hard disk memory, and other memory devices that may use magnetic, optical, and other techniques to store instructions or other data and that can be accessed by a machine.

A processor may be any kind of general purpose or dedicated processor, such as a CPU, GPU, System-on-chip, state machine, media processor, an application-specific integrated circuit (ASIC), a programmable logic array, a field-programmable gate array (FPGA), physics processing units (PPUs), radio processing units (RPUs), digital signal processors (DSPs), general purpose processors (e.g. a general purpose GPU), microprocessors, any processing unit which is designed to accelerate tasks outside of a CPU, etc. A computer or computer system may comprise one or more processors. Those skilled in the art will realize that such processing capabilities are incorporated into many different devices and therefore the term 'computer' includes set top boxes, media players, digital radios, PCs, servers, mobile telephones, personal digital assistants and many other devices.

It is also intended to encompass software which defines a configuration of hardware as described herein, such as HDL (hardware description language) software, as is used for designing integrated circuits, or for configuring programmable chips, to carry out desired functions. That is, there may be provided a computer readable storage medium having encoded thereon computer readable program code in the form of an integrated circuit definition dataset that when processed (i.e. run) in an integrated circuit manufacturing system configures the system to manufacture a GPU pipeline or blender hardware configured to perform any of the methods described herein, or to manufacture a GPU pipeline or blender hardware comprising any apparatus described herein. An integrated circuit definition dataset may be, for example, an integrated circuit description.

Therefore, there may be provided a method of manufacturing, at an integrated circuit manufacturing system, a GPU pipeline or blender hardware as described herein. Furthermore, there may be provided an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, causes the method of manufacturing a GPU pipeline or blender hardware to be performed.

An integrated circuit definition dataset may be in the form of computer code, for example as a netlist, code for configuring a programmable chip, as a hardware description language defining an integrated circuit at any level, including as register transfer level (RTL) code, as high-level circuit representations such as Verilog or VHDL, and as low-level circuit representations such as OASIS (RTM) and GDSII. Higher level representations which logically define an integrated circuit (such as RTL) may be processed at a computer system configured for generating a manufacturing definition of an integrated circuit in the context of a software environment comprising definitions of circuit elements and rules for combining those elements in order to generate the manufacturing definition of an integrated circuit so defined by the representation.

An example of processing an integrated circuit definition dataset at an integrated circuit manufacturing system so as to configure the system to manufacture a GPU pipeline or blender hardware will now be described with respect to <FIG>.

<FIG> shows an example of an integrated circuit (IC) manufacturing system <NUM> which is configured to manufacture a GPU pipeline or blender hardware as described in any of the examples herein. In particular, the IC manufacturing system <NUM> comprises a layout processing system <NUM> and an integrated circuit generation system <NUM>. The IC manufacturing system <NUM> is configured to receive an IC definition dataset (e.g. defining a GPU pipeline or blender hardware as described in any of the examples herein), process the IC definition dataset, and generate an IC according to the IC definition dataset (e.g. which embodies a GPU pipeline or blender hardware as described in any of the examples herein). The processing of the IC definition dataset configures the IC manufacturing system <NUM> to manufacture an integrated circuit embodying a GPU pipeline or blender hardware as described in any of the examples herein.

In other examples, processing of the integrated circuit definition dataset at an integrated circuit manufacturing system may configure the system to manufacture a GPU pipeline or blender hardware without the IC definition dataset being processed so as to determine a circuit layout. For instance, an integrated circuit definition dataset may define the configuration of a reconfigurable processor, such as an FPGA, and the processing of that dataset may configure an IC manufacturing system to generate a reconfigurable processor having that defined configuration (e.g. by loading configuration data to the FPGA).

Those skilled in the art will realize that storage devices utilized to store program instructions can be distributed across a network. For example, a remote computer may store an example of the process described as software. A local or terminal computer may access the remote computer and download a part or all of the software to run the program. Those skilled in the art will also realize that by utilizing conventional techniques known to those skilled in the art that all, or a portion of the software instructions may be carried out by a dedicated circuit, such as a DSP, programmable logic array, or the like.

The methods described herein may be performed by a computer configured with software in machine readable form stored on a tangible storage medium e.g. in the form of a computer program comprising computer readable program code for configuring a computer to perform the constituent portions of described methods or in the form of a computer program comprising computer program code means adapted to perform all the steps of any of the methods described herein when the program is run on a computer and where the computer program may be embodied on a computer readable storage medium. Examples of tangible (or non-transitory) storage media include disks, thumb drives, memory cards etc. and do not include propagated signals. The software can be suitable for execution on a parallel processor or a serial processor such that the method steps may be carried out in any suitable order, or simultaneously.

The hardware components described herein may be generated by a non-transitory computer readable storage medium having encoded thereon computer readable program code.

Memories storing machine executable data for use in implementing disclosed aspects can be non-transitory media. Non-transitory media can be volatile or non-volatile. Examples of volatile non-transitory media include semiconductor-based memory, such as SRAM or DRAM. Examples of technologies that can be used to implement non-volatile memory include optical and magnetic memory technologies, flash memory, phase change memory, resistive RAM.

A particular reference to "logic" refers to structure that performs a function or functions. An example of logic includes circuitry that is arranged to perform those function(s). For example, such circuitry may include transistors and/or other hardware elements available in a manufacturing process. Such transistors and/or other elements may be used to form circuitry or structures that implement and/or contain memory, such as registers, flip flops, or latches, logical operators, such as Boolean operations, mathematical operators, such as adders, multipliers, or shifters, and interconnect, by way of example. Such elements may be provided as custom circuits or standard cell libraries, macros, or at other levels of abstraction. Such elements may be interconnected in a specific arrangement. Logic may include circuitry that is fixed function and circuitry can be programmed to perform a function or functions; such programming may be provided from a firmware or software update or control mechanism. Logic identified to perform one function may also include logic that implements a constituent function or sub-process. In an example, hardware logic has circuitry that implements a fixed function operation, or operations, state machine or process.

Any reference to 'an' item refers to one or more of those items. The term 'comprising' is used herein to mean including the method blocks or elements identified, but that such blocks or elements do not comprise an exclusive list and an apparatus may contain additional blocks or elements and a method may contain additional operations or elements. Furthermore, the blocks, elements and operations are themselves not impliedly closed.

Claim 1:
A GPU pipeline comprising a tessellation unit (<NUM>) and post-tessellation blender hardware (<NUM>, <NUM>), wherein the blender hardware comprises:
an input for receiving an input domain space vertex output by the tessellation unit, the input domain space vertex comprising UV coordinates of the vertex, a blend weight of the vertex, and where UV coordinates of neighbour vertices are not inherent from the UV coordinates of the vertex itself, the UV coordinates of the neighbour vertices;
a cache (<NUM>) arranged to store data pairs, each data pair comprising UV coordinates and a world space vertex generated from the UV coordinates by one or more domain shaders; and
a blend unit (<NUM>) arranged to receive the blend weight of the input domain space vertex, world space vertices for the input domain space vertex and its neighbour vertices generated by the one or more domain shaders or accessed from the cache, and to generate a single world space vertex for the input domain space vertex using the received blend weight and world space vertices, wherein the cache is arranged to, in the event of a cache hit at a cache entry for UV coordinates, output the world space vertex from the cache entry, and in the event of a cache miss for UV coordinates, output the UV coordinates to the one or more domain shaders; and wherein the cache is arranged to receive and store world space vertices generated by the one or more domain shaders for input vertices and their neighbours.