Screen-Space Binning in Tiled Rasterizers

An immediate-mode rasterizer shades each fragment as it arrives, in the order the application issued the draws. A fragment belonging to a distant wall may be shaded, tested, and rejected, then a fragment from a nearby object shaded and written, and the two accesses to the depth buffer may be thousands of pixels apart in time and in address. The depth and colour traffic that results is the dominant cost of a mobile or integrated design, and the fix is to change the traversal order: shade the screen in tiles, and keep each tile’s working set resident while every triangle that touches it is processed.

The binning pass and its output

The pipeline splits into two passes. The first consumes the geometry, transforms vertices, clips and projects as described in the clipping stage, and for each surviving triangle computes its screen-space bounding box. It then writes a reference to the triangle into the bin of every tile the box overlaps. The output is a per-tile list of primitive indices plus, usually, the transformed vertex data in a compact form that the second pass can consume without re-running vertex work.

The bin lists are variable-length. A tile in an empty part of the screen holds nothing; a tile in the middle of a dense mesh holds every triangle of the mesh. The memory for the lists is therefore proportional to the sum over tiles of the number of overlapping primitives, which for a triangle covering the whole screen is the tile count, and for a mesh of unit triangles is close to the number of triangles times a constant near one. Neither bound is tight, and the total is not knowable until the geometry has been processed, which is why hardware implementations allocate from a fixed pool and fall back when it overflows.

The bounding box is used again here, and for the same reason as in triangle setup: it is conservative, cheap, and prevents a triangle from being omitted from any tile it might touch. A bin that under-includes a triangle produces a hole in the image that no later stage can repair, so the box calculation is not allowed to be approximate.

/* Assign a primitive to every tile its bounding box overlaps.
   tile_shift converts pixels to tile coordinates; lists are fixed-capacity. */
void bin_primitive(binner_t *b, uint32_t prim, int minx, int miny, int maxx, int maxy)
{
    int tx0 = minx >> TILE_SHIFT, tx1 = (maxx + TILE_SIZE - 1) >> TILE_SHIFT;
    int ty0 = miny >> TILE_SHIFT, ty1 = (maxy + TILE_SIZE - 1) >> TILE_SHIFT;
    for (int ty = ty0; ty < ty1; ty++) {
        for (int tx = tx0; tx < tx1; tx++) {
            tile_t *t = &b->tiles[ty * b->tiles_x + tx];
            if (t->count == t->capacity) {           /* overflow: grow or defer */
                grow_tile(b, t);
            }
            t->list[t->count++] = prim;
        }
    }
}

Tiles are typically a small power of two such as 16×16 or 32×32 pixels, a choice that follows from cache geometry: a 16×16 tile of 32-bit colour is 1 KB, which fits in a cache line set without conflict, and a 32×32 tile of depth plus colour is 8 KB, which fits comfortably in a small on-chip memory but may exceed the associativity of a shared cache. The tile size also sets the granularity of the bin lists: smaller tiles mean more lists and more per-tile overhead, larger tiles mean more wasted work for triangles that only graze a tile.

What the reordering buys

The first benefit is depth and colour locality. While a tile is resident, every depth test and every colour write addresses the same small region, so the reads hit an on-chip buffer rather than external memory. On a design with a small tile memory, the colour and depth of a tile never leave the chip until the tile is finished, at which point the resolved tile is written once. An immediate-mode design writes and reads the same bytes many times over the course of a frame, which is why the bandwidth difference is large enough to change a product’s power budget.

The second benefit is that per-tile ordering makes deferred shading straightforward. All fragments that land in a tile are visible together, so the pipeline can first run the depth test for every fragment in the tile without shading, build a compact list of surviving fragments, and shade only those. This is the classic tile-based deferred approach: the shading cost becomes proportional to pixels times the average number of visible layers, rather than to the total fragment count. The list must be bounded, since a tile can contain many layers, and the standard fallback records the extra fragments and shades them by re-running the geometry for that tile.

The third benefit is that per-tile state is naturally serialized. Depth writes from earlier triangles in a tile are visible to later triangles in the same tile without any global synchronization, and the early depth test’s ordering constraints are satisfied trivially because the whole tile is processed by one unit in one pass. Ordering across tiles is irrelevant, since no fragment in one tile can affect another, which is exactly the property that makes parallel execution safe.

Bandwidth arithmetic, and where it stops paying

A fragment scattered across a large target costs a read-modify-write of colour plus a read-modify-write of depth for every blending or depth-updating draw, and each of those is a full memory transaction at cache-line granularity. If four fragments hit the same pixel, that is eight transactions for one pixel’s worth of data, and the transactions are to external memory if the working set exceeds the cache. Tiled execution reduces the same work to one load of the tile at the start and one store at the end, with everything in between served from on-chip storage.

The savings shrink as the tile’s working set grows. A tile with many depth layers, or with blending that requires reading the destination repeatedly, still needs the same on-chip traffic, and if the tile memory is small the pipeline spills. The pathological case is heavy overdraw with alpha blending, where every layer must be read, blended, and written; tiling does not reduce the number of layers, only the distance to memory, and once the tile memory is exhausted the advantage over immediate mode narrows.

The second limit is the binning pass itself. It must transform every vertex and write every bin entry before any shading begins, so the latency from a draw call to visible pixels includes a full geometry pass. An application that issues a small draw and reads back the result immediately pays that latency in full, and an application that queries occlusion after a draw cannot get the answer without finishing the binning. Both are reasons tiled designs are described as batch-oriented, and both are why very small draws are expensive in a way that immediate-mode designs do not exhibit.

Sorting, not just binning

Binning changes locality but not the order in which triangles within a tile are processed, which is still the application’s order. Sorting the bin lists front to back before rasterizing improves the depth test’s rejection rate, because a near triangle writes depth first and the later fragments fail. The sort costs a comparison pass per tile and is worthwhile only when the depth complexity is high, so implementations typically sort coarsely by a cheap key such as the triangle’s nearest depth, or by draw call, rather than exactly.

Exact per-tile sorting is what makes the A-buffer’s front-to-back compositing affordable, and it is the mechanism behind hardware that supports order-independent transparency. The bin lists become the sort’s input, the sort’s output is a depth-ordered fragment stream, and the compositing is a fold over that stream. The cost moves to the sort, which is where the engineering effort goes.

Bin lists also serve culling. A tile whose bin is empty costs nothing, and a coarse visibility test that rejects whole tiles before rasterizing them is cheap because the tile is the unit of memory and of work. The hierarchical depth structure described in early rejection is a tile-level test by construction, and it composes naturally with a binning pass: a tile whose depth summary already covers everything behind it discards its entire list.

Failure modes specific to binned designs

The bin overflow is the characteristic one. A scene with a very large triangle covering the whole target writes a reference into every tile, so a single primitive can exhaust the pool; worse, geometry with a bounding box that spans the target but covers almost none of it (a long diagonal sliver, or a triangle whose vertices are far outside the viewport) writes into every tile it merely crosses. The memory per tile is proportional to the box, not the area, which is the same box-versus-area ratio that makes bounding-box traversal wasteful, applied at the tile level with a much larger box.

Very long, thin triangles therefore have a disproportionate binning cost, and the usual mitigation is to clip or split them so that their boxes are bounded. Geometry processed at the guard band’s edge is exactly this case: a triangle spanning from one side of the band to the other has a bounding box covering the whole target, and every tile must record it even though only a strip is covered. Tighter clipping at the viewport boundary reduces this, at the cost of the clipping work the guard band was introduced to avoid.

The second failure is the fragment-list depth. A deferred tile records the visible fragments in the tile, and the list capacity is fixed. A tile through which many transparent layers pass exceeds it, and the excess must be handled by a second pass over the same geometry, which doubles the geometry cost for that tile only. The alternative, dropping layers, is visually wrong. The choice between the two is a per-architecture decision that applications cannot see, which means the same content can behave differently in performance across implementations while looking identical.

The third is the interaction with state changes. Because the binning pass and the shading pass are separate, a state change between draws must be recorded so the shading pass can restore it per bin entry, and the cost of that recording scales with the number of state changes rather than with the pixels. An application that switches shaders per object pays in bin entries what an immediate-mode design pays in pipeline flushes; the balance point differs, which is why advice written for one architecture often misleads on the other.