The Hardware Rasterizer
You met
rasterization as an
algorithm: evaluate three edge functions at a pixel centre, light the pixel if the signs agree.
Now meet it as a circuit — arguably the most elegant fixed-function block on the whole
die. The question silicon asks is different from the question software asks. Software asks
"is this pixel inside?" Hardware asks "how do I answer that for hundreds of pixels at
once, every clock cycle, forever, using almost no energy?" The answer is that the edge
function
E(x, y) = a\,x + b\,y + c
is not merely correct — it is hardware gold, for two properties no other
inside-test has.
Why edge functions are hardware gold
-
It evaluates anywhere, independently. E at any point
is two multiplies and two adds — no history, no neighbours, no divisions. So the hardware can
drop a grid of evaluators onto a block of pixels and test them all in the same
clock cycle. Parallelism is free because the maths has no dependencies.
-
It steps incrementally. Because E is linear,
E(x+1, y) = E(x, y) + a, \qquad E(x, y+1) = E(x, y) + b.
Marching one pixel right costs one addition. Marching a whole block over costs one
addition per evaluator. The multipliers run once per triangle (in setup, which handed us
a, b, c precomputed); from then on the rasterizer is essentially a
box of adders — and adders are the cheapest, coolest-running arithmetic silicon there is.
Compare the alternatives: point-in-polygon by angle summation needs trigonometry; ray-crossing
needs branches. The edge function needs adders. That is why every GPU rasterizer for thirty years
has been built on it.
The hierarchical march: coarse, then fine
Testing every pixel on a 4K screen against every triangle would waste almost all its work — most
triangles touch a tiny fraction of the screen. So real rasterizers march hierarchically:
- Coarse raster: the screen is carved into tiles (say
8\times 8 pixels). Because E is linear,
testing a tile's corners settles the whole tile: all four corners outside one edge
→ the tile can't touch the triangle, skip 64 pixels with 4 evaluations. Only tiles the triangle
might touch go on.
- Fine raster: inside a surviving tile, a bank of parallel evaluators — one
per pixel position, fed by those incremental adds — stamps out the exact coverage mask for a
block of pixels per clock.
The output is not individual pixels but quads: 2\times 2
blocks of fragments, the pipeline's currency from here on. Why quads? Because a fragment shader
needs derivatives — how fast a texture coordinate changes between neighbouring pixels —
to choose mipmap levels, and the cheapest derivative estimate is a difference between quad
neighbours. The price: a quad with only one covered pixel still runs all four
fragment invocations; the three uncovered ones are helper lanes, computing only so their
neighbour can difference against them.
The march, drawn
Step through the hierarchy on a toy screen (tiles here are 4\times 4
pixels so everything fits): edges, then touched tiles, then covered pixels, then the quads that
actually ship to the shaders.
Interpolation — and the divide that ended wobbly textures
The same edge values do double duty: scaled by the triangle's area they are the barycentric
weights, and setup's attribute gradients let the rasterizer produce every
interpolated value (depth, UVs, colour) with the same one-add-per-pixel trick. But there is a
famous subtlety: interpolating an attribute linearly in screen space is wrong under
perspective — a floor tile's far half covers fewer pixels than its near half, so its texture must
compress non-linearly. The fix, hardwired into every modern rasterizer, is
perspective-correct interpolation: interpolate \tfrac{u}{w}
and \tfrac{1}{w} linearly (those are linear in screen space),
then recover
u = \frac{u/w}{1/w}
with one divide per fragment. The original PlayStation's rasterizer lacked that divide — which is
exactly why PS1 textures famously swim and warp as the camera moves. One small divider circuit
separates that era from ours.
- inside test: signs of three linear edge functions E = ax + by + c,
coefficients precomputed by setup;
- linearity buys parallel evaluation (a grid of evaluators per clock) and
incremental stepping (one add per pixel step);
- the march is hierarchical: coarse tiles first, fine pixels within survivors;
- output is 2×2 quads (for derivatives), with helper lanes in partially
covered quads;
- attributes interpolate perspective-correctly via u/w and
1/w.
Build the rasterizer yourself
Here is the whole fine-raster idea in thirty lines: three edge functions, one pass over a
character-cell "screen", and a printed framebuffer. The counters underneath tally what the
hierarchy would have saved and what the quads cost.
// A mini hardware rasterizer: 40×20 framebuffer, one triangle.
const W = 40, H = 20;
const A = [3, 17], B = [36, 12], C = [14, 2]; // screen-space vertices
// Edge function through P→Q, evaluated at (x, y): E = a·x + b·y + c
function edgeCoeffs(P: number[], Q: number[]): [number, number, number] {
const a = Q[1] - P[1];
const b = P[0] - Q[0];
const c = -(a * P[0] + b * P[1]);
return [a, b, c];
}
const edges = [edgeCoeffs(A, B), edgeCoeffs(B, C), edgeCoeffs(C, A)];
const E = (e: number[], x: number, y: number) => e[0] * x + e[1] * y + e[2];
// Fine raster: test every pixel CENTRE (x+0.5, y+0.5).
const fb: string[][] = [];
let covered = 0;
for (let y = 0; y < H; y++) {
fb.push([]);
for (let x = 0; x < W; x++) {
const inside = edges.every((e) => E(e, x + 0.5, y + 0.5) >= 0);
fb[y].push(inside ? "█" : "·");
if (inside) covered++;
}
}
// Print top row last so y points up, like the maths.
for (let y = H - 1; y >= 0; y--) console.log(fb[y].join(""));
// Coarse raster: which 8×8 tiles hold any covered pixel?
let tiles = 0;
for (let ty = 0; ty < H; ty += 8)
for (let tx = 0; tx < W; tx += 8) {
let hit = false;
for (let y = ty; y < Math.min(ty + 8, H) && !hit; y++)
for (let x = tx; x < Math.min(tx + 8, W); x++)
if (fb[y][x] === "█") { hit = true; break; }
if (hit) tiles++;
}
// Quad generation: 2×2 blocks containing at least one covered pixel.
let quads = 0;
for (let qy = 0; qy < H; qy += 2)
for (let qx = 0; qx < W; qx += 2) {
const any =
fb[qy][qx] === "█" || fb[qy][qx + 1] === "█" ||
fb[qy + 1][qx] === "█" || fb[qy + 1][qx + 1] === "█";
if (any) quads++;
}
console.log(`\ncovered pixels: ${covered}`);
console.log(`8×8 tiles touched: ${tiles} of ${(W / 8) * Math.ceil(H / 8)}`);
console.log(`2×2 quads emitted: ${quads} → ${quads * 4} fragment lanes (${quads * 4 - covered} helpers)`);
Change the vertices and re-run. Notice the helper count: a long thin triangle wastes far more
lanes than a fat one — the quad tax in action, and one reason slivers are expensive.
Fill rate: the rasterizer's speed limit
A rasterizer's throughput is quoted as fill rate: pixels stamped per clock,
times the clock. A block that emits 16 pixels per clock at 2 GHz supplies
32 Gpixels/s — and a GPU carries several such blocks. Divide your
screen's pixel count into that and you get the hard ceiling on overdraw at 60 fps: fill rate is
why "how many times do I touch each pixel?" is a performance question with a silicon answer.
Two classic misreadings of the inside test, both fixed by convention:
- A pixel is covered when its CENTRE is inside — not when the triangle overlaps it.
A triangle can overlap half a pixel's area and light nothing (centre outside), or clip a corner
of the sample point and claim the whole pixel. Coverage is point sampling, with all the aliasing
that implies.
- Shared edges need a tie-break. Where two triangles share an edge, a pixel
centre exactly on it satisfies E = 0 for both. Award it to
both and it is shaded twice (visible seams under blending); to neither and a one-pixel
crack of background shows through. Every hardware rasterizer implements the
top-left rule: an E = 0 pixel counts as inside only
for a triangle whose top or left edge it sits on — so exactly one owner wins,
always. It is the rule every rasterizer implements and every beginner's software rasterizer
forgets.
Do the arithmetic for one mid-range GPU: 4 raster engines × 16 pixels per clock × 2.5 GHz is
160 billion coverage tests a second — each one three sign checks fed by three adds. At a
few femtojoules per add, the entire inside/outside decision machinery for a AAA game frame costs
less energy than lighting one LED for the same duration. This is the specialisation argument of
this module's first lesson made concrete: the same tests as shader code would burn instruction
fetch, scheduling and 32-bit datapaths on what a purpose-built array of narrow adders does almost
for free. When an operation is this regular, silicon specialisation is not a 20% win — it is
orders of magnitude, and that is why the rasterizer will likely be the last fixed-function block
ever to die.