Hierarchical tiling in a graphics processing system using chain sorting of primitives

Abstract

Tiling engines and methods for hierarchically tiling a plurality of primitives. A chain of sorting units includes a top level sorting unit followed by lower level sorting units, the top level sorting unit determining which of a plurality of regions of a render space each of the plurality of primitives at least partially falls within. For each such region an identifier of that primitive is stored in a queue. Each of the lower level sorting units selects queues of a preceding sorting unit in the chain to process, and determines which of a plurality of sub-regions of the region associated with that queue each of the primitives at least partially falls within. For each such sub-region an identifier of that primitive is stored in a queue of the lower level sorting unit that is associated with that sub-region. An output unit outputs the primitives identified in the queues of the last lower level sorting unit in the chain on a queue by queue basis.

What is claimed is: 
     
         1 . A tiling engine for use in a graphics processing system, the tiling engine comprising:
 a chain of at least two sorting units configured to sort a plurality of primitives into successively smaller regions of a render space using a set of queues, wherein each sorting unit in the chain of sorting units is configured to sort the plurality of primitives into a plurality of regions by storing information identifying each primitive of the plurality of primitives that fall at least partially within a region of the plurality of regions in a queue, of the set of queues, associated with that region.   
     
     
         2 . The tiling engine of  claim 1 , wherein each sorting unit in the chain of sorting units, other than a first sorting unit in the chain of sorting units, is configured to sort the primitives identified in the queues used by a preceding sorting unit in the chain of sorting units on a queue by queue basis. 
     
     
         3 . The tiling engine of  claim 2 , wherein:
 each sorting unit of the chain of sorting units comprises a plurality of queues of the set of queues;   the plurality of queues of a particular sorting unit of the chain of sorting units are sub-divided into a plurality of banks; and   a next sorting unit in the chain of sorting units, relative to the particular sorting unit, is configured to sort the primitives identified in the queues in each bank of the particular sorting unit using a different subset of the plurality of queues of the next sorting unit.   
     
     
         4 . The tiling engine of  claim 1 , further comprising an output unit configured to output the primitives identified in the queues of a last sorting unit in the chain of sorting units on a queue by queue basis. 
     
     
         5 . The tiling engine of  claim 4 , wherein:
 the graphics processing system comprises a plurality of rasterization processing units;   a last sorting unit of the chain of sorting units comprises a plurality of queues of the set of queues and the plurality of queues are sub-divided into a plurality of banks; and   the output unit is configured to output the primitives identified in the queues of each bank of the last sorting unit to a different subset of the plurality of rasterization processing units.   
     
     
         6 . The tiling engine of  claim 1 , wherein a first sorting unit of the chain of sorting units is configured to determine whether a primitive falls at least partially within a region using a first tiling method and another sorting unit of the chain of sorting units is configured to determine whether a primitive falls at least partially within a region using a second, different, tiling method. 
     
     
         7 . The tiling engine of  claim 1 , wherein the chain of sorting units comprising a top level sorting unit followed by one or more lower level sorting units, and:
 the top level sorting unit is configured to:
 determine which of the plurality of regions of the render space each of the plurality of primitives falls at least partially within, and 
 for each region a primitive falls at least partially within, store an identifier of that primitive in a queue of the top level sorting unit that is associated with that region; and 
   each of the one or more lower level sorting units is configured to:
 select one or more queues of a preceding sorting unit in the chain of sorting units to process, 
 for each of the selected queues, determine which of a plurality of sub-regions of the region associated with the selected queue each of the primitives identified in the selected queue fall at least partially within, and 
 for each sub-region a primitive falls at least partially within, store an identifier of that primitive in a queue of the lower level sorting unit that is associated with that sub-region. 
   
     
     
         8 . The tiling engine of  claim 7 , wherein at least one of the one or more lower level sorting units is configured to select the queue of the preceding sorting unit to process next by selecting one of: a longest queue of the preceding sorting unit, a newest queue of the preceding sorting unit, a queue of the preceding sorting unit that is associated with a region closest to the region of the most recently processed queue of the preceding sorting unit, and an oldest queue of the preceding sorting unit. 
     
     
         9 . The tiling engine of  claim 7 , wherein the one or more lower level sorting units comprises at least two lower level sorting units and one of the lower level sorting units is configured to select one or more queues of the preceding sorting unit to process using a first method, and another of the lower level sorting units is configured to select one or more queues of the preceding sorting unit to process using a second, different, method. 
     
     
         10 . The tiling engine of  claim 7 , wherein at least one of the one or more lower level sorting units is further configured to:
 in response to determining that a primitive falls at least partially within a sub-region, determine whether a queue of that lower level sorting unit is associated with that sub-region;   in response to determining that a queue of the lower level sorting unit is associated with that sub-region, add an identifier of that primitive to the queue associated with that sub-region;   in response to determining that a queue of that lower level sorting unit is not associated with that sub-region, determine if a queue of the lower level sorting unit is free; and   in response to determining that a queue of the lower level sorting unit is free, associate the free queue of the lower level sorting unit with the sub-region and add an identifier of the primitive to that queue.   
     
     
         11 . The tiling engine of  claim 10 , wherein each of the one or more lower level sorting units is configured to, for each selected queue of the preceding sorting unit in the chain, remove the identifiers of the primitives from the selected queue; and the at least one lower level sorting unit is configured to determine that a queue of that lower level sorting unit is free when that queue does not comprise any identifiers. 
     
     
         12 . The tiling engine of  claim 1 , wherein geometry data for each primitive of the plurality of primitives is stored in a buffer and the identifier of a primitive comprises information indicating a location of the geometry data for that primitive in the buffer. 
     
     
         13 . The tiling engine of  claim 12 , wherein the geometry data for the plurality of primitives are stored in the buffer in primitive blocks wherein each primitive block comprises the geometry data for one or more primitives, and the identifier of a primitive comprises information identifying the primitive block that comprises the geometry data for that primitive. 
     
     
         14 . The tiling engine of  claim 1 , wherein a size of the plurality of regions of at least one sorting unit of the chain of sorting units, and/or a number of sorting units in the chain of sorting units is configurable. 
     
     
         15 . The tiling engine of  claim 1 , wherein at least one region of the plurality of regions of at least one sorting unit of the chain of sorting units is a non-contiguous region of the render space. 
     
     
         16 . The tiling engine of  claim 1 , wherein at least one sorting unit of the chain of sorting units is configured to dynamically associate queues of the set of queues with the plurality of regions of that sorting unit. 
     
     
         17 . A method of sorting a plurality of primitives based on regions of a render space, the method comprising:
 executing a chain of sorting phases to sort primitives into successively smaller regions of the render space using a set of queues, wherein each sorting phase of the chain of sorting phases comprises sorting primitives into a plurality of regions by storing information identifying each primitive of the plurality of primitives that fall at least partially within a region of the plurality of regions in a queue, of the set of queues, associated with that region.   
     
     
         18 . A graphics processing system comprising the tiling engine as set forth in  claim 1 . 
     
     
         19 . 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 17 . 
     
     
         20 . A non-transitory computer readable storage medium having stored thereon a computer readable dataset description of the tiling engine as set forth in  claim 1  that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture an integrated circuit embodying the tiling engine.