Data structures, methods and tiling engines for hierarchically storing tiling information in a graphics processing system

1. A method of tiling primitives in a tile based graphics processing system in which a rendering space is divided into a plurality of tiles, the method comprising:

generating a multi-level hierarchy of tile groups comprising at least two levels, each level of the multi-level hierarchy comprising one or more tile groups comprising one or more of the plurality of tiles, wherein each level of the multi-level hierarchy comprises non-overlapping tile groups and tile groups in higher levels comprise more tiles than tile groups in lower levels;

receiving information identifying each of a plurality of primitive blocks, each primitive block comprising geometry data for one or more primitives;

associating each of the plurality of primitive blocks with one or more of the tile groups up to a maximum number of tile groups such that if at least one primitive of a primitive block falls, at least partially, within the bounds of a tile, the primitive block is associated with at least one tile group that includes that tile, wherein the maximum number of tile groups is less than a total number of tiles forming the plurality of tiles; and

generating a control stream for each tile group based on the associations, wherein each control stream comprises a primitive block entry for each primitive block associated with the corresponding tile group.

2. The method of claim 1 , wherein the maximum number of tile groups is one.

3. The method of claim 1 , wherein associating a primitive block with one or more of the tile groups comprises:

identifying an axis-aligned bounding box in the rendering space that encompasses the one or more primitives of the primitive block; and

associating the primitive block with a smallest tile group whose one or more tiles encompass the bounding box.

4. The method of claim 1 , wherein the maximum number of tile groups is greater than one.

5. The method of claim 1 , wherein associating a primitive block with one or more of the tile groups comprises:

identifying an axis-aligned bounding box in the rendering space that encompasses the one or more primitives of the primitive block; and

associating the primitive block with a smallest set of one or more tile groups whose one or more tiles encompass the bounding box.

6. The method of claim 5 , wherein each tile group in the set of one or more tile groups is at a same level of the hierarchy.

7. The method of claim 5 , wherein the set of one or more tile groups comprises a plurality of tile groups and at least two of the tile groups in the set are at different levels of the hierarchy.

8. The method of claim 1 , wherein each primitive block entry comprises information identifying the corresponding primitive block.

9. The method of claim 1 , wherein each primitive block is associated with an axis-aligned bounding box in the rendering space that encompasses the one or more primitives of the primitive block, and if the bounding box for a primitive block does not encompass an area of the rendering space covered by the tiles in the tile group the primitive block entry for that primitive block comprises information identifying one or more co-ordinates of the bounding box.

10. The method of claim 1 , wherein each primitive block is associated with an axis-aligned bounding box in the rendering space that encompasses the one or more primitives in the set of the primitives, and if a primitive block does not comprise at least one primitive that falls in each tile of the tile group, the primitive block entry for that primitive block comprises a coverage mask which indicates which tiles of the tile group that intersect the bounding box for the primitive block are valid for the primitive block, a tile being valid for a primitive block if at least one primitive in the primitive block falls, at least partially, within the bounds of the tile.

11. The method of claim 10 , wherein each coverage mask comprises information for successively smaller and smaller areas of a block of relevant tiles that indicates whether that area is valid for the primitive block, the block of relevant tiles comprising the tiles of the tile group that intersect the bounding box for the primitive block.

12. The method of claim 10 , further comprising generating the coverage mask for a primitive block entry by:

(a) dividing a block of relevant tiles into quadrants of tiles, the block of relevant tiles comprising the tiles of the tile group that intersect the bounding box for the primitive block;

(b) adding information to the coverage mask indicating whether each of the quadrants is valid for the primitive block; and

(c) if a quadrant is valid for the primitive block and the quadrant comprises more than one tile, dividing that quadrant into sub-quadrants and repeating (b) and (c) for each sub-quadrant.

13. The method of claim 12 , wherein generating the coverage mask for a primitive block entry further comprises, prior to dividing the block of relevant tiles into quadrants of tiles, expanding the block of relevant tiles to a square block with power of two sides.

14. The method of claim 1 , wherein each tile group of level k comprises a h k ×h k block of tiles, wherein h is an integer greater than one, k is an integer between 0 to N−1, and N is a number of levels in the hierarchy.

15. The method of claim 1 , wherein each tile group of level comprises n tile groups of level j−1 wherein n is an integer greater than one, j is an integer between 1 and N−1, and N is a number of levels in the hierarchy.

16. The method of claim 1 , wherein each tile group at a lowest level of the hierarchy comprises only a single tile of the plurality of tiles.

17. A non-transitory computer readable storage medium having stored thereon computer readable instructions that, when executed at a computer system, cause the computer system to perform the method as set forth in claim 1 .

18. A tiling engine for use in a graphics processing system in which a render space is divided into a plurality of tiles, the tiling engine comprising:

tile group selector logic configured to:

obtain information defining a multi-level hierarchy of tile groups comprising at least two levels, wherein each level of the multi-level hierarchy comprises one or more tile groups comprising one or more of the plurality of tiles, wherein each level of the multi-level hierarchy comprises non-overlapping groups of tiles and tile groups in higher levels comprise more tiles than tile groups in lower levels,

receive information identifying each of a plurality of primitive blocks, each primitive block comprising geometry data for one or more primitives, and

associate each of the plurality of primitive blocks with one or more of the tile groups up to a maximum number of tile groups such that if at least one primitive of a primitive block falls, at least partially, within the bounds of a tile, the primitive block is associated with at least one tile group that includes that tile, wherein the maximum number of tile groups is less than a total number of tiles forming the plurality of tiles; and

a control stream generator configured to generate a control stream for each tile group in the multi-level hierarchy based on the associations, wherein each control stream comprises a primitive block entry for each primitive block associated with the corresponding tile group.

19. A control stream decoder for use in a graphics processing system in which a rendering space is subdivided into a plurality of tiles, each tile forming part of at least two different tile groups of different sizes, the control stream decoder comprising:

control stream fetch logic configured to fetch a control stream for each tile group that a current tile forms part of, each control stream comprising none, one or more than one primitive block entries, each primitive block entry comprising (i) information identifying a primitive block comprising geometry data for one or more primitives, and (ii) bounding box information identifying a bounding box that encompasses the one or more primitives; and

a control stream analyser configured to, for each fetched control stream:

if the control stream comprises at least one primitive block entry, for each primitive block entry:

determine from the bounding box information whether the current tile falls within the bounding box, and

in response to determining that the current tile does not fall within the bounding box, determine that the primitive block is not relevant to rendering the current tile.

20. The control stream decoder of claim 19 , wherein the control stream decoder is further configured to:

in response to determining that the current tile falls within the bounding box, determining whether the control stream comprises a coverage mask, the coverage mask indicating which tiles in the tile group that intersect with the bounding box are relevant for the corresponding primitive block, and

in response to determining that the control stream comprises a coverage mask, determining from the coverage mask whether the primitive block is relevant to rendering the current tile.