Tiling a primitive in a graphics processing system by testing subsets of tiles in a rendering space

Abstract

In tile-based graphics processing systems, a tiling unit determines which tiles of a rendering space a primitive is in, such that the primitives in a tile can be rendered. Rather than performing tiling calculations for each tile in a bounding box for a primitive, tiling tests can be performed for a subset of the tiles. Then the results of the tiling tests for the subset of tiles can be used to determine whether the primitive is in other tiles which are located within a region bounded by two or more of the tiles of the subset. In this way the tiling process can be implemented without performing tiling calculations for all of the tiles in the bounding box for a primitive. Reducing the number of tiling calculations can help to improve the efficiency of the graphics processing system (in terms of speed and power consumption) for rendering a primitive.

What is claimed is: 
     
         1 . A method of processing a primitive in a graphics processing system, the method comprising tiling the primitive to determine which of a plurality of tiles of a rendering space the primitive is in by:
 determining a bounding box for the primitive;   for each of at least one tile boundary between lines of tiles in the bounding box, determining initial intersection points of the tile boundary with edge lines defining edges of the primitive;   identifying which of the initial intersection points lie on an edge of the primitive; and   using the identified initial intersection points to determine which of the tiles in the bounding box the primitive is in.   
     
     
         2 . The method of  claim 1 , wherein the step of using the identified initial intersection points to determine which of the tiles in the bounding box the primitive is in comprises, for a line of tiles:
 determining a start tile in the line of tiles by finding the first tile in the line which includes an identified initial intersection point on its boundary or includes a vertex of the primitive;   determining an end tile in the line of tiles by finding the last tile in the line which includes an identified initial intersection point on its boundary or includes a vertex of the primitive; and   determining that the primitive is in the tiles in the line between, and including, the start tile and the end tile.   
     
     
         3 . The method of  claim 1 , wherein the lines of tiles are rows or columns of tiles. 
     
     
         4 . The method of  claim 1 , further comprising:
 determining that the lines of tiles are rows of tiles if there are fewer rows of tiles than columns of tiles in the bounding box; and   determining that the lines of tiles are columns of tiles if there are fewer columns of tiles than rows of tiles in the bounding box.   
     
     
         5 . The method of  claim 1 , wherein the primitive is determined to not be in tiles which do not at least partially overlap with the bounding box. 
     
     
         6 . The method of  claim 1 , wherein the bounding box is clipped so that it does not extend beyond the edges of the rendering space. 
     
     
         7 . The method of  claim 1 , further comprising:
 including a primitive identifier of the primitive in a display list for a particular tile if it is determined that the primitive is in the particular tile; and   for each of the tiles of the rendering space, rendering the primitives in the tile in accordance with the display list for the tile.   
     
     
         8 . The method of  claim 1 , further comprising rendering the primitive in dependence on the determining which of the tiles in the bounding box the primitive is in. 
     
     
         9 . The method of  claim 1 , wherein the determining of the initial intersection points of the tile boundary with edge lines defining edges of the primitive comprises:
 for each edge of the primitive, unless it is parallel to the tile boundary, determining an initial intersection point of the tile boundary with an edge line defining the edge of the primitive.   
     
     
         10 . The method of  claim 1 , wherein said identifying which of those initial intersection points lie on the edge of the primitive comprises, for each of the initial intersection points:
 progressing along the tile boundary and determining whether points either side of the initial intersection point are inside or outside of the primitive.   
     
     
         11 . The method of  claim 10 , wherein if the determination of whether points either side of the initial intersection point are inside or outside of the primitive is different for the two points either side of the initial intersection point then the initial intersection point is an intersection point on the edge of the primitive, whereas if the determination is the same for the two points either side of the initial intersection point then the initial intersection point is not an intersection point on the edge of the primitive. 
     
     
         12 . A graphics processing system comprising a tiling unit for tiling a primitive to determine which of a plurality of tiles of a rendering space the primitive is in, wherein the tiling unit is configured to:
 determine a bounding box for the primitive;   for each of at least one tile boundary between lines of tiles in the bounding box, determine initial intersection points of the tile boundary with edge lines defining edges of the primitive;   identify which of the initial intersection points lie on an edge of the primitive; and   use the identified initial intersection points to determine which of the tiles in the bounding box the primitive is in.   
     
     
         13 . The graphics processing system of  claim 12 , wherein the tiling unit is configured to use at least some of the identified initial intersection points to determine which of the tiles in the bounding box the primitive is in by, for a line of tiles:
 determining a start tile in the line of tiles by finding the first tile in the line which includes an identified initial intersection point on its boundary or includes a vertex of the primitive;   determining an end tile in the line of tiles by finding the last tile in the line which includes an identified initial intersection point on its boundary or includes a vertex of the primitive; and   determining that the primitive is in the tiles in the line between, and including, the start tile and the end tile.   
     
     
         14 . The graphics processing system of  claim 12 , wherein the tiling unit is configured to identify which of the initial intersection points lie on the edge of the primitive by, for each of the initial intersection points:
 progressing along the tile boundary and determining whether points either side of the initial intersection point are inside or outside of the primitive.   
     
     
         15 . The graphics processing system of  claim 14 , wherein if the determination of whether points either side of the initial intersection point are inside or outside of the primitive is different for the two points either side of the initial intersection point then the initial intersection point is an intersection point on the edge of the primitive, whereas if the determination is the same for the two points either side of the initial intersection point then the initial intersection point is not an intersection point on the edge of the primitive. 
     
     
         16 . The graphics processing system of  claim 12 , wherein the tiling unit is configured to determine that the primitive is not in tiles which do not at least partially overlap with the bounding box. 
     
     
         17 . The graphics processing system of  claim 12 , wherein the tiling unit is configured to clip the bounding box so that it does not extend beyond the edges of the rendering space. 
     
     
         18 . The graphics processing system of  claim 12 , wherein the tiling unit is further configured to include a primitive identifier of the primitive in a display list for a particular tile if it is determined that the primitive is in the particular tile, and wherein the graphics processing system comprises a rendering unit configured to render, for each of the tiles of the rendering space, the primitives in the tile in accordance with the display list for the tile. 
     
     
         19 . The graphics processing system of  claim 12 , wherein the graphics processing system comprises a rendering unit configured to render the primitive in dependence on the determining which of the tiles in the bounding box the primitive is in. 
     
     
         20 . A non-transitory computer readable storage medium having stored thereon a computer readable dataset description that when processed by an integrated circuit manufacturing system causes the integrated circuit manufacturing system to manufacture a graphics processing system having a tiling unit for tiling a primitive to determine which of a plurality of tiles of a rendering space the primitive is in, the tiling unit being configured to:
 determine a bounding box for the primitive;   for each of at least one tile boundary between lines of tiles in the bounding box, determine initial intersection points of the tile boundary with edge lines defining edges of the primitive;   identify which of the initial intersection points lie on an edge of the primitive; and   use the identified initial intersection points to determine which of the tiles in the bounding box the primitive is in.