2.4 Bucket sorting
2.4.2 Exact bucket sorting overlap
When small triangles such asT2orT3in figure 2.12 stay within a tile or straddle the boundary between two tiles, then exact bucket sorting and bounding box bucket sorting will have the same overlap factor. But as soon as a triangle bounding box straddles both horizontalandvertical tile boundaries, the differences appear. T1in figure 2.12 overlaps 3 tiles when exactly bucket sorted and 4 tiles when sorted by the bounding box method. Figure 2.13 shows how the hash table of the buckets is represented by the algorithm. As the triangle size increases relative to the tile size, this effect is increased. Figure 2.14 shows what happens when a long and narrow triangle spans across the entire screen. The bounding box method would place it in all buckets, but exact bucket sorting only places it in the buckets actually affected by for the shaded tiles. The overhead of placing a triangle into buckets it does not actually cover causes each tile renderer affected to waste time that could be used
T3
T2 T1
Tile
0,0 Tile
1,0
Tile
0,1 Tile
1,1
Tile 2,0
Tile 2,1
X axis
Y axis
Figure 2.12: Examples of overlap in a tile-based renderer. Triangle T2 is completely inside one tile. T3overlaps two tiles.T1overlaps 4 tiles if bounding box bucket sorting is used, but will only overlap 3 tiles if exact bucket sorting is used.
0,0 Tile x,y
Hash table with a bucket for each tile
1,0 2,0
0,1 1,1 2,1
T1
T1 T3
T3
T1 T1 T2
*)
Figure 2.13: Hash table for the bucket sorted triangles in figure 2.12. Each bucket maintains a list of triangles overlapping its tile. *) This triangle entry is created when using bounding box bucket sorting, but not if exact bucket sorting is used.
Figure 2.14: Bounding box bucket sorting will place this long and narrow triangle inallbuckets, resulting in an overlap ofO=256. Exact bucket sorting will only place the triangle in the buckets for the shaded tiles, in this case resulting in a lower overlapO=40.
rendering other triangles. The communication network for distributing triangles into buckets is also burdened by this overhead.
A method for exact bucket sorting is discussed in [169]. It relies on testing triangle edges against region edges using the following algorithm which determines that a triangle intersects a region if:
1. a triangle vertex is inside the region, or 2. a region corner is inside the triangle, or 3. a region edge intersects a triangle edge.
The algorithm requires these tests to be made for every region overlapped by the triangle’s bounding box.
Alternatively each tile can be treated as a large pixel. By scan converting the tri-angle into these large pixels, the exact coverage can be determined. Unfortunately this duplicates the work done by the tile renderers to some degree, and requires tri-angle set-up in the sorting stage. Performing tritri-angle set-up before bucket sorting has some side-benefits, though. TheHybrisrenderer performs triangle set-up in the bucket sorting stage as an optimization to allow reuse of rasterization parameters across all tiles covered by the triangle. Knowing the triangle set-up parameters,
exact bucket sorting can be performed using the same rasterization algorithm and rasterization rounding rules that is used in the tile renderers. Further, these raster-ization rounding rules can be used to cull triangles prior to bucket sorting. While exact bucket sorting adds a scan conversion overhead it may improve the overlap factor, in particular for large triangles such as the one in figure 2.14.
Returning to equation 2.1 which in [156] was derived from this integral:
O= Z H
0
Z W
0 p(x,y)r(x,y)dxdy (2.5)
where p(x,y) is the probability for the triangle bounding box center to be placed at(x,y)andr(x,y)is the number of regions affected by this placement. Assuming even distribution over square tiles we get:
O=
Revisiting the geometric construction in figure 2.11 and assuming a square triangle bounding box and square tiles, then, for triangles with a bounding box size smaller than the tile size, the following can be stated: If the triangle bounding box is completely within a tile or overlaps two tiles either horizontally or vertically, exact and bounding box bucket sorting has the same overlap. Only in the case when the triangle bounding box overlaps four tiles, the triangle itself overlaps either three or four tiles. Based on the triangle bounding box area to triangle area ratioρ we can derive an expression for the overlap factor of exact bucket sorting for small triangles. In the corner four tile overlap case, the estimated overlap with exact bucket sorting becomes
Ocorner=3+1
ρ (2.7)
allowing the following derivation, whereAcorners,AedgesandAcenterare the areas of the corner, edge and center regions in figure 2.11,sis the side length of the square triangle bounding box andSis the side length of the square tile.
Acorners = s2
by substitutingOcornerfrom (2.7) we get O=1+2s
S + s2
ρS2 (2.8)
This derivation results in the following nice expression (2.10) for the estimated overlap factor of exact bucket sorting when the triangle areaais known, by substi-tutings=√ρain (2.8)
O=1+2√ρa S + a
S2 (2.9)
substituting again to get rid ofρgives O=1+2s
S + a
S2 (2.10)
where the area ratioρ can be approximated toρ=3 when triangles are used, as previously stated in the discussion for (2.4). Note thatρ=3 is an average estimate, a rare case such as the long and narrow triangle in figure 2.14 has a much higher bounding box area to triangle area ratio. Subtracting equation (2.9) from (2.4) yields the difference
∆O=OBBox−OExact=a(ρ−1)
S2 (2.11)
which is low for relatively small triangles.
Figure 2.15 lists some estimated overlap factors calculated for bounding box and exact bucket sorting, where it is clear that the overlap factor is high for large triangles and that exact bucket sorting significantly reduces the overlap in this case.
However for small triangles the difference between exact and bounding box sorting is negligible, as shown in equation 2.11.
The tile size for the renderer should be chosen to be small enough to allow good load balancing and efficient caching while at the same time be large enough to allow good coherence within the tile as well as a low bucket sorting overlap fac-tor. A practical tile size satisfying these criteria, as well as being small enough to be practically implemented in caches and on-chip RAM, seems to be 32x32 pix-els. Note that 2nx2ntile sizes are preferred in order to match hardware resources.
Figure 2.16 plots a comparison between exact and bounding box overlap for 32x32 tiles. This suggests that an adaptive bucket sorting algorithm which dynamically chooses between using bounding box bucket sorting for small triangles and exact bucket sorting for large triangles can be useful.
1 4 16 64 256 1024 Tile side length:
8 1.480 2.054 3.482 7.464 19.928 62.856 16 1.228 1.480 2.054 3.482 7.464 19.928 32 1.111 1.228 1.480 2.054 3.482 7.464 64 1.055 1.111 1.228 1.480 2.054 3.482 128 1.027 1.055 1.111 1.228 1.480 2.054 256 1.014 1.027 1.055 1.111 1.228 1.480
1 4 16 64 256 1024
Tile side length:
8 1.449 1.929 2.982 5.464 11.928 30.856 16 1.220 1.449 1.929 2.982 5.464 11.928 32 1.109 1.220 1.449 1.929 2.982 5.464 64 1.054 1.109 1.220 1.449 1.929 2.982 128 1.027 1.054 1.109 1.220 1.449 1.929 256 1.014 1.027 1.054 1.109 1.220 1.449
Bounding box overlap:
Triangle area:
Exact overlap:
Triangle area:
Figure 2.15: Example bounding box and exact overlap for some interesting tile and triangle sizes.
0 1 2 3 4 5 6 7 8
1 4 16 64 256 1024
Triangle area
Overlap
Bounding Box Exact
Figure 2.16:Overlap for 32x32 pixel tile.