The rasterization pipeline

Lesson 05 gave us surfaces — explicit triangle meshes and implicit fields, with marching cubes bridging them. But a representation is inert until you can turn it into an image, and every lesson so far has quietly assumed a renderer to close the loop. This lesson builds the classical one the entire real-time field runs on: rasterization. It is lesson 01's forward operator R made concrete for a mesh — the map from 3D triangles to 2D pixels that a GPU executes billions of times a second. We build it end to end: the transform chain that projects triangles through the camera, the coverage test that decides which pixels each triangle owns, and the z-buffer that resolves who is in front.

1 · Rasterization vs ray tracing — two directions through the same question

Rendering answers one question: for each pixel, what piece of scene geometry is visible there, and what color should it be? There are exactly two ways to loop over that question, and they differ only in which index is on the outside.

Ray tracing is image-centric. Loop over pixels. For each pixel, construct the ray from the camera through that pixel and ask the scene "what do you hit first?" — an intersection query against every primitive (accelerated by a spatial data structure like a BVH). The loop is \text{for each pixel: for each object, intersect}. It is the natural formulation for global effects — a hit point can spawn secondary rays for shadows, reflections, and refractions — which is exactly why it is the physically-based, offline-render workhorse.

Rasterization is geometry-centric. Loop over triangles. For each triangle, project its three vertices to the screen and ask "which pixels does this cover?" — then write those pixels. The loop is \text{for each triangle: for each covered pixel, shade}. Nothing about triangle A's processing depends on triangle B, so the loop is a stream: triangles flow through a fixed sequence of stages, embarrassingly parallel, needing no global scene data structure held in memory.

Rasterization dominates real time for a structural reason, not an accidental one. Its inner loop touches one triangle's worth of data at a time and emits pixels independently, so it maps directly onto the GPU's model of thousands of threads running the same program over different data. There is no scene-wide acceleration structure to build or chase pointers through; the pipeline is fixed and feed-forward. That is why every mesh you have ever seen move at 60 fps — every game, every CAD viewer, every AR overlay, and (lesson 10) every Gaussian-splat renderer — went through a rasterizer.

In lesson 01's terms, this lesson computes the forward operator R for the mesh representation of lesson 05: \hat I = R(\text{mesh}, \text{camera}). Hold onto one word: forward. Everything here runs the loop's step ② in the easy direction, image out of geometry. The reason lessons 09–10 exist is that the inverse — geometry out of image, by backpropagating through R — is broken for this R, because (as §4 makes precise, and lesson 07 §5 develops) the coverage test is not differentiable. Build the forward pipeline first; feel exactly where it becomes non-invertible.

2 · The geometry pipeline — the transform chain

A triangle starts life as three vertices in the coordinate frame the artist modeled it in, and must end as three points in pixel coordinates. It gets there by a fixed chain of coordinate changes, each a matrix multiply, most of them the rigid-body and camera transforms of lessons 02 and 04:

The first two matrices are review. M places the object in the world (lesson 02's rigid transforms, optionally with scale). V re-expresses the world in the camera's own frame: if the camera's pose in the world is T_wc ∈ SE(3), then V = T_wc⁻¹, because moving the world into camera coordinates is the inverse of placing the camera in the world. Composed, V·M takes a model-space vertex straight into view space, where the camera sits at the origin looking down its own axis — exactly the setup CV lesson 04's pinhole assumed.

Deriving the perspective projection

Now the one genuinely new matrix. From CV lesson 04, the pinhole camera projects a view-space point (X, Y, Z) onto the image plane by dividing by depth:

That divide is the entire source of perspective — distant things (large Z) shrink. The problem: a matrix multiply is linear, and dividing by a coordinate is not a linear operation. You cannot write "divide by Z" as a 4×4 matrix acting on (X, Y, Z, 1). So the pipeline splits the job in two, and this is the key idea of the whole section: the matrix does not do the division — it sets up the division. The projection matrix's real job is to copy (a function of) view-space Z into the fourth, homogeneous coordinate w. Then a separate, fixed hardware step — the perspective divide — divides everything by that w, and the 1/Z foreshortening falls out for free.

Concretely, a projection matrix maps the view-space homogeneous point to a clip-space 4-vector whose w component is Z (up to sign/scale):

The perspective divide then produces NDC coordinates (x_c/w_c,\ y_c/w_c,\ z_c/w_c) = (x_c/Z,\ y_c/Z,\ z_c/Z). If the matrix set x_c = f·X, the divide yields f·X/Z — exactly the pinhole. The matrix stayed linear; the nonlinearity lives entirely in the one shared divide. That factorization — linear matrices, then a single divide by w — is precisely why homogeneous coordinates are the language of graphics.

Frustum → cube: the near and far planes

The projection matrix also handles depth. The camera sees a truncated pyramid — the view frustum, bounded by a near plane at distance n and a far plane at f (everything nearer than n or farther than f is discarded). Projection warps this frustum into the axis-aligned NDC cube [−1,1]³: the x,y extents map to [−1,1], and the depth range [n, f] maps monotonically to z_ndc ∈ [−1, 1] so that hidden-surface tests can compare a single number per pixel. The standard depth mapping is

which one checks sends Z=n → z_ndc=-1 and Z=f → z_ndc=+1. Notice its shape: it is affine in 1/Z, not in Z. That is the whole subtlety of the next callout.

A worked number

Pick a near plane n = 1 and a far plane f = 100 (a 100:1 range, typical), and push a view-space point at depth Z = 5 through the chain. Suppose its view-space lateral coordinates and focal-like term give clip x_c = 3.0, and w_c = Z = 5. The perspective divide gives

For depth, plug into the mapping:

Read what just happened. Linearly, Z=5 sits only (5-1)/(100-1) ≈ 4\% of the way from the near plane to the far plane. Yet its NDC depth 0.616 is already (0.616-(-1))/2 ≈ 81\% of the way across the [-1,1] depth range. The first 4\% of physical depth consumed 81\% of the depth-buffer's range. Depth precision is lavished near the camera and starved far away.

3 · Triangle setup, clipping, and culling

Between "projected vertices" and "filled pixels" the pipeline does two cheap rejections that save enormous downstream work.

Clipping. Triangles are trimmed to the view frustum before the perspective divide, and the near plane is not optional — it is a correctness requirement. The divide is (x_c, y_c, z_c)/w_c with w_c = Z. For a point behind the camera, Z ≤ 0, so w_c ≤ 0 and the divide is meaningless — dividing by zero, or by a negative that flips the point through the origin to a phantom position on screen. So a triangle straddling the camera plane must be clipped against the near plane first: the portion with Z < n is cut off, and the polygon is re-triangulated from the safe part (a triangle clipped by one plane can become a quad → two triangles). Only then is it safe to divide. Clipping against the other five frustum planes is an optimization (it avoids rasterizing off-screen pixels); near-plane clipping is a must.

Back-face culling. A closed (watertight) mesh shows you only its outward-facing triangles; the ones facing away are always occluded by the front of the object, so drawing them is wasted work. You detect them after projection from the winding order: compute the signed area of the projected triangle in screen space (the same signed area §4 is built on). A consistently-wound mesh (lesson 05's manifoldness) has front faces of one sign and back faces of the other; the pipeline discards, say, all clockwise-projected triangles. For a convex closed shape exactly half the triangles face away, so back-face culling roughly halves the fill work essentially for free — a single sign test per triangle, done before touching any pixel.

4 · The coverage test — edge functions and barycentric coordinates

Now the heart of rasterization. A triangle's three vertices are in screen (pixel) coordinates V₀, V₁, V₂. For a candidate pixel with sample point P (its center), the question is binary: is P inside the triangle? The classical answer is the edge function. For the directed edge from V₀ to V₁, define

the 2D cross product (a scalar). Geometrically it is twice the signed area of the triangle (V₀, V₁, P): its sign tells you which side of the directed line V₀→V₁ the point P lies on. Compute all three edge functions E₀₁, E₁₂, E₂₀. Then

The picture: each edge, oriented consistently around the triangle, splits the plane into a "left" and "right" half; the triangle's interior is the one intersection where you are on the interior side of all three edges at once. All-same-sign is exactly that intersection.

The same numbers are the barycentric coordinates

Here is the fact that makes this the elegant center of the pipeline. Divide each edge function by the full triangle's signed area A = \tfrac12 E₀₁₂ (itself an edge function on all three vertices). The three normalized quantities

are the barycentric coordinates of P, and they satisfy

(The three sub-triangle areas tile the whole triangle, so their fractions sum to one.) "All three edge functions same sign" is identically "all three barycentrics ≥ 0" — the coverage test is the sign of the barycentrics. So a single computation does double duty: the signs of (\alpha, \beta, \gamma) answer coverage, and their values are the interpolation weights. Any per-vertex attribute — depth, color, normal, texture coordinate — is carried to P by the very same weights, a(P) = \alpha\,a₀ + \beta\,a₁ + \gamma\,a₂. That is the interpolation machinery lesson 07 builds shading on, and it is why §5 can interpolate depth for the z-buffer without any extra math. It is also why triangles are the primitive (lesson 05 §2): only a triangle has this unique, linear barycentric interpolation.

Two properties make this ideal for hardware. It is local — each pixel's test needs only the triangle's three vertices, nothing global. And it is parallel — every pixel in the triangle's screen-space bounding box can be tested independently, at the same time, by the same tiny program. A GPU rasterizer evaluates edge functions incrementally over a whole tile of pixels at once. This is the streaming loop of §1 realized down at the pixel level.

5 · The z-buffer — hidden-surface removal

Coverage tells you which triangles touch a pixel, but many can touch the same one — a near wall and the far wall behind it both cover it. Which color survives? The winner is the nearest fragment, and the z-buffer (depth buffer) finds it with almost no bookkeeping.

Alongside the color framebuffer, keep a second buffer of the same size holding, per pixel, the nearest depth seen so far, initialized to +∞ (the far plane). As each triangle is rasterized, for every covered pixel produce a fragment and:

1. Interpolate its depth with the barycentric weights from §4: z_frag = \alpha z₀ + \beta z₁ + \gamma z₂ (in NDC/buffer depth). No extra geometry — the same weights that decided coverage.
2. Depth test. If z_frag is nearer than the stored depth, the fragment wins: write its color to the framebuffer and overwrite the stored depth with z_frag. Otherwise it is occluded — discard it.

That is the whole algorithm. Its virtues are exactly what a streaming pipeline needs:

• O(1) per fragment — one interpolation, one compare, one conditional write. No sorting.
• Order-independent — the final image is the same no matter what order the triangles arrive in, because each pixel independently keeps the running minimum. This is what lets rasterization stay a stream: you never need all the geometry at once.

Contrast the painter's algorithm — sort triangles back-to-front and paint over. It needs a global sort (breaking the stream), and worse, it is simply wrong for interpenetrating triangles (which is in front depends on the pixel, not the triangle) and for cyclic overlaps (A over B over C over A, where no single ordering exists). The z-buffer resolves all of these per pixel, because it compares depths at the sample point rather than committing to one order for a whole triangle.

The widget puts §4 and §5 together at pixel scale: two triangles fighting over an overlap region, resolved by edge-function coverage per pixel and a per-pixel z-buffer. Slide one triangle's depth below the other's and watch it seize the contested pixels.

// signed area of triangle (a,b,c) = 2× area; sign encodes winding / which side.
function area(a, b, c){
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// Rasterize one triangle into the pixel grid + z-buffer.
// tri.v = [v0,v1,v2] in canvas coords; tri.z = constant depth (per-vertex works the same).
function rasterize(tri, color, zbuf, colbuf, W, H, cols, rows){
  var v0 = tri.v[0], v1 = tri.v[1], v2 = tri.v[2];
  var Atot = area(v0, v1, v2);            // full-triangle signed area (2×)
  if (Atot === 0) return 0;               // degenerate
  var cw = W / cols, ch = H / rows;       // pixel size
  var covered = 0;
  for (var iy = 0; iy < rows; iy++){
    for (var ix = 0; ix < cols; ix++){
      var P = { x: (ix + 0.5) * cw, y: (iy + 0.5) * ch };   // pixel centre
      // three edge functions == three sub-triangle signed areas
      var w0 = area(v1, v2, P);           // opposite v0  -> weight of v0
      var w1 = area(v2, v0, P);           // opposite v1  -> weight of v1
      var w2 = area(v0, v1, P);           // opposite v2  -> weight of v2
      // inside iff all edge functions share the sign of the total area
      var inside = (Atot > 0) ? (w0 >= 0 && w1 >= 0 && w2 >= 0)
                              : (w0 <= 0 && w1 <= 0 && w2 <= 0);
      if (!inside) continue;
      covered++;
      // barycentric weights = sub-area / total area  (sum to 1)
      var b0 = w0 / Atot, b1 = w1 / Atot, b2 = w2 / Atot;
      // interpolate fragment depth (here z is constant, but this is the general form)
      var zf = b0 * tri.z + b1 * tri.z + b2 * tri.z;
      var idx = iy * cols + ix;
      if (zf < zbuf[idx]){                 // DEPTH TEST: keep the nearer fragment
        zbuf[idx] = zf;
        colbuf[idx] = color;
      }
    }
  }
  return covered;
}

Where this points next

We can now turn a mesh into an image: transform triangles through model → world → view → clip → NDC → screen, cut them at the near plane and cull the back faces, decide coverage with edge functions that double as barycentric weights, and resolve occlusion with an order-independent z-buffer. That is the complete forward operator R for a mesh — geometry in, pixels out, in real time. But the pixels we produced are flat: we interpolated depth, yet said nothing about their color, and even the interpolation hides a subtlety. Lesson 07 finishes the picture. It interpolates per-vertex attributes correctly — and shows why naive screen-space interpolation is wrong under perspective, so you must interpolate in 1/Z (the same inverse-depth structure from §2 and lesson 03) — then maps textures (and confronts their aliasing, fixed by mipmapping) and applies shading. It closes on the formal argument this lesson previewed in §4's red callout: the coverage step is a discontinuous function of geometry with no useful gradient, so the whole rasterizer is non-differentiable. That single fact is the hinge of the track: it is precisely why lesson 09 abandons hard surfaces for a soft, semi-transparent radiance field rendered by an integral you can backpropagate — turning the un-invertible forward map of this lesson into the differentiable one that inverse rendering needs.

Interview prompts

• Contrast rasterization and ray tracing, and explain why rasterization dominates real-time rendering. (§1 — rasterization loops over triangles (geometry-centric), ray tracing over pixels (image-centric); rasterization is a stateless parallel stream needing no global structure, so it maps onto GPU hardware, while ray tracing's per-ray traversal is natural for global effects but memory-bound.)
• Walk through the transform chain from model space to pixel coordinates, and derive how the perspective projection produces 1/Z foreshortening. (§2 — model→world (M)→view (V = camera-pose⁻¹ ∈ SE(3))→clip (P)→NDC (÷w)→screen; P stays linear by copying view-space Z into the clip w, and the single perspective divide by w yields x = fX/Z.)
• Why is depth stored nonlinearly in the buffer, and what problem does that cause? (§2/§5 — z_ndc is affine in 1/Z, so precision bunches near the camera and starves far away; distant coplanar surfaces round to equal depths and z-fight. Same inverse-depth structure as stereo disparity, lesson 03. Fix: shrink f/n, reversed/log-Z.)
• Why must triangles be clipped against the near plane, and how does back-face culling work? (§3 — points with Z ≤ 0 give w ≤ 0, so the perspective divide is invalid/flips them; near-clip is a correctness must. Back-face culling drops triangles by the sign of their projected signed area (winding), roughly halving fill work on closed meshes.)
• Explain edge functions and their connection to barycentric coordinates. (§4 — an edge function is the 2D cross product / twice the signed area of (edge, P); P is inside iff all three share a sign. Normalized by the total area they ARE the barycentrics (\alpha,\beta,\gamma), summing to 1 — one computation gives both the coverage test and the interpolation weights.)
• How does a z-buffer resolve visibility, and why is it better than the painter's algorithm? (§5 — per fragment, interpolate depth barycentrically and keep it iff nearer than the stored value; O(1), order-independent, no sort. The painter's algorithm needs a global sort and fails on interpenetrating and cyclically-overlapping triangles, which the per-pixel depth test handles.)