Tile-Based Rasterization

Topic Overview

Why Process the Whole Screen Per Triangle?

A modern GPU rasterizes millions of triangles per frame. Most triangles are small and touch only a tiny screen fraction. Testing every pixel on the full framebuffer for every triangle wastes work and destroys cache locality.

Tile-based rasterization divides the screen into rectangles (typically 8x8, 16x16, or 32x32 pixels). The rasterizer first finds which tiles a triangle overlaps, then runs fine per-pixel tests only inside those tiles.

The Assignment Algorithm

1. Compute the triangle's axis-aligned bounding box
2. Find tiles intersecting the bounding box
3. Coarse test: does the triangle actually overlap each candidate tile?
4. Fine rasterize: per-pixel barycentric tests inside passing tiles

cCopy
Loading…

For example, on a 32x32 screen with 8x8 tiles, a small triangle in the top-left corner might touch only tile (0,0) instead of all 16 tiles. Mobile GPUs (ARM Mali, PowerVR, Apple) extend this with tile-based deferred rendering, keeping intermediate results in on-chip memory to cut VRAM bandwidth.

• Desktop GPUs: hybrid tiled binning (NVIDIA, AMD)
• Mobile GPUs: full TBDR with on-chip G-buffer
• Tradeoff: setup overhead vs massive bandwidth savings

For This Exercise

You will implement tile assignment for three triangles on a 32x32 screen divided into 4x4 tiles of 8x8 pixels. This task asks you to print which tiles each triangle touches. The cache-friendly chunking you model here is why phones render complex 3D scenes without draining the battery on constant memory traffic.

Your Task

Tile-based GPUs (and parallel software rasterizers) first bin triangles: the screen is cut into T×T tiles, and each triangle is added to the list of every tile it might touch, so tiles can later be rasterized independently. Compare two binning tests, then check the bins against real pixel coverage:

• the cheap bounding-box test;
• an exact triangle/rectangle overlap test based on the separating axis theorem.

Input

# starts a comment line.

cCopy
Loading…

The tile grid is ceil(W/T) × ceil(H/T), at most 16 × 8.

Rules

• Tiles: tile (tx, ty) is the open rectangle (tx·T, (tx+1)·T) × (ty·T, (ty+1)·T). Merely touching its boundary does not count.
• Winding: a triangle with negative area has vertices 1 and 2 swapped, and zero area prints NAME: degenerate, not binned.
• Bounding box: the tile is binned unless maxx ≤ x0, minx ≥ x1, maxy ≤ y0 or miny ≥ y1.
• Exact: a bounding-box candidate is kept unless some triangle edge a→b has E(a→b, corner) = (bx-ax)(cy-ay) - (by-ay)(cx-ax) ≤ 0 at all four tile corners, which means that edge separates them.
• Pixels: for each exact bin, count the tile's pixel centres the triangle covers, using the rasterizer rules: centres (px+½, py+½) inside the screen, a doubled grid, and zero edge values allowed only on top (ay == by && bx > ax) or left (by < ay) edges. A bin with no covered centre is marked *.

Output

cCopy
Loading…

• Triangle lines: the exact bins are listed in row-major order, or (off screen) when there are none. Plurals: tile(s), pixel(s), bin(s).
• Grids: one digit per tile, or + above 9.
• Errors:
  • screen: W (1-128) H (1-64), tile: 4, 8, 16 or 32
  • tri: NAME X0 Y0 X1 Y1 X2 Y2, tri: coordinates within +-1000, at most 16 triangles
  • bin: at most 16 x 8 tiles (use larger tiles)
  • unknown command X

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Test the edges against the tile corners with integer edge functions. For a convex triangle and an axis-aligned box, the box axes plus the three edge normals are all the separating axes there are, so the test is exact.
2. Count pixel coverage with the same fill rules as the rasterizer. A bin can overlap a triangle and still own no pixel centre, which is wasted binning work.

Hidden tests cover two triangles tiling a screen exactly, degenerate and off-screen triangles, a sliver whose only pixel centre lies on its diagonal, a single large tile, and argument errors.