skip to content

How does a GPU rasterizer decide which pixels a triangle covers, and why does it need a fill rule for edges shared by two triangles?

level: middleimportance: should knowfreq 45%

answer

  1. three signed edge tests
  2. sample at the pixel centre
  3. a shared edge needs one owner
  4. top-left rule, fixed-point snapping

basics

~20 s

The rasterizer evaluates three edge functions at each sample position, usually the pixel centre, and covers the sample when all agree it is inside. A top-left fill rule gives samples lying exactly on a shared edge to one triangle only.

solid answer

~50 s

After the viewport transform, vertex positions are snapped to a fixed-point sub-pixel grid. For each edge `a -> b`, the edge function `E(p) = (b.x - a.x)(p.y - a.y) - (b.y - a.y)(p.x - a.x)` is twice a signed area: zero on the edge, positive on one side. A sample, by default at the pixel centre, is covered when all three edge functions have the interior's sign. A sample exactly on an edge shared by two triangles would otherwise be claimed by both (blended twice) or by neither (a crack), depending on the test. The **top-left rule** gives it to the triangle for which the edge is a top edge (horizontal, interior below) or a left edge; the two triangles traverse the edge in opposite directions, so exactly one owns it. Snapping makes `E` exact, which is what lets the rule work. Because `E` is linear, hardware steps it incrementally and accepts or rejects whole tiles at once.

code

pseudocode · 19 lines
pseudocode
// Convention: screen y grows downward; positions already snapped to fixed point;
// triangles wound so the interior gives E >= 0 (clockwise as seen on screen).
function edge(a, b, p):
    return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)

function isTopLeft(a, b):
    isTop  = (a.y == b.y) and (b.x > a.x)   // horizontal, interior below it
    isLeft = (b.y < a.y)                    // runs up the screen: interior to its right
    return isTop or isLeft

function covers(v0, v1, v2, px, py):
    p = (px + 0.5, py + 0.5)                // sample at the pixel centre
    for (a, b) in [(v0, v1), (v1, v2), (v2, v0)]:
        e = edge(a, b, p)
        if e < 0:
            return false
        if e == 0 and not isTopLeft(a, b):
            return false
    return true

go deeper

for a junior

Recall that rasterization turns a triangle into fragments by testing which pixel centres lie inside it.

for a middle

Write the edge function, explain sample-at-centre coverage, and show why shared edges need the top-left rule and fixed-point snapping.

for a senior

Diagnose seams, double-blended edges and crawling thin geometry, and explain what tile traversal and tiny triangles mean for rasterizer throughput.

for a principal

Weigh when a software or compute rasterizer for very small triangles is worth building beside the hardware path, and what correctness rules it must reproduce.

## From vertices to coverage After the viewport transform each triangle is three points in pixel coordinates, each with a depth. **Rasterization** decides which pixels the triangle covers and creates a **fragment** for each. Modern GPUs generally do not fill horizontal spans between edges the way early software renderers did; they test sample positions, by default one per pixel at the pixel's centre `(x + 0.5, y + 0.5)`. ## Edge functions For an edge from `a` to `b`, the **edge function** `E(p) = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)` is twice the signed area of the triangle `a, b, p`. It is zero on the line through `a` and `b`, positive on one side and negative on the other. A sample is inside the triangle when all three edge functions have the sign that the triangle's winding gives its interior. Useful properties: - **Linearity**: `E` changes by a constant per pixel step, `-(b.y - a.y)` per step in x and `(b.x - a.x)` per step in y, so hardware evaluates it incrementally with additions. - **Tile tests**: evaluating `E` at the corners of a block of pixels shows whether the block is fully inside, fully outside or straddling an edge, so whole blocks are accepted or skipped at once. - **Barycentrics for free**: the three values divided by their sum add up to 1 and are the weights used to interpolate depth across the triangle, and vertex outputs after a perspective correction. - **Facing**: the sign of the triangle's total area shows which way it is wound on screen, which is what face culling uses. ## Why a fill rule is needed Meshes are made of triangles that share edges. A sample lying exactly on a shared edge gives `E = 0` for both triangles: - Count it as inside for both, and it is shaded and blended twice: a bright seam in an additive effect, a visible line in an alpha-blended one, a double increment in a stencil count. - Count it as outside for both, and a one-pixel crack appears. The rule must give each such sample to exactly one triangle. The usual choice is the **top-left rule**: a sample on an edge belongs to the triangle only if that edge is a **top edge**, exactly horizontal with the triangle's interior below it, or a **left edge**, on the triangle's left side. Two triangles that share an edge traverse it in opposite directions, so it is a left edge for exactly one of them, and a shared horizontal edge is the top of one triangle and the bottom of the other. ## Fixed-point snapping The rule works only if both triangles compute exactly the same `E` along the shared edge. Floating-point evaluation in a different order for each triangle can give a tiny positive value for one and a tiny negative value for the other, which brings the cracks and double hits back. GPUs therefore snap post-viewport positions to a **fixed-point sub-pixel grid**, with a number of fractional bits set by the hardware and API (commonly between 4 and 8), and evaluate edge functions in exact integer arithmetic. ## Edge cases interviewers probe 1. **Thin triangles**: a triangle narrower than a pixel covers only the samples whose centres fall inside it, so a thin wire becomes a dotted line. Multisampling tests more positions per pixel; **conservative rasterization**, available on some hardware, covers every pixel the triangle touches at all. 2. **Tiny triangles** waste throughput: setup costs the same per triangle however few pixels it covers, and shading works on small pixel blocks, which is a question of fragment cost. 3. **Degenerate triangles** with zero area cover nothing and are dropped at setup. 4. **Multisampling** evaluates the same edge functions at several sample positions per pixel, applying the fill rule at each, and records which samples are covered. ## Hardware versus a simple software rasterizer | Concern | Typical GPU | Simple software rasterizer | |---|---|---| | Positions | fixed-point sub-pixel | often float, cracks unless snapped | | Traversal | tiles with corner tests | bounding box, one test per pixel | | Shared edges | top-left rule built in | must be coded by hand | | Throughput | many samples per clock | one sample per loop step |

  • What happens to a long triangle that is thinner than a pixel, such as a distant cable?
    It covers only pixels whose sample point falls inside it, so it breaks into a dotted, crawling line as it moves. More samples per pixel, from multisampling or supersampling, catch more of it; conservative rasterization marks every pixel it touches. Content often widens such geometry or fades it with distance.
  • How does hardware avoid evaluating three edge functions from scratch at every pixel?
    Edge functions are linear, so moving one pixel in x adds a constant and moving one row adds another; the rasterizer steps them with additions. It also evaluates them at the corners of tiles, accepting tiles fully inside without per-pixel tests and skipping tiles fully outside, and only tests individual samples in tiles the edge crosses.

  • A pixel is covered whenever any part of the triangle touches it.
  • Pixels on a shared edge are drawn twice, which is harmless.
  • Floating-point edge tests are exact enough without snapping positions.
  • The rasterizer tests every pixel on the screen for every triangle.
  • The fill rule exists to smooth jagged edges, like anti-aliasing.