Half-Space Coverage and the Edge Function Test

A rasterizer receives triangles in normalized device coordinates and must produce fragments for a rectangular grid of pixels. The grid is not a mathematical plane; it is a set of discrete sample points, conventionally at pixel centers, so a pixel with integer coordinates $(x, y)$ is sampled at $(x + 0.5, y + 0.5)$. Coverage is therefore a point-in-polygon question asked once per sample. Everything else in the rasterizer, including the antialiasing schemes in multisample coverage and analytic coverage, is a refinement of this single decision.

Turning three vertices into three line equations

For a triangle with vertices $p_0, p_1, p_2$ in screen space, each edge defines an oriented line. The edge from $p_0$ to $p_1$ has the implicit equation

$$E_{01}(x, y) = (x - x_0)(y_1 - y_0) - (y - y_0)(x_1 - x_0)$$

This is twice the signed area of the triangle $(p_0, p_1, (x,y))$, and its sign says which side of the directed line the point falls on. With counter-clockwise winding in a coordinate system where $y$ grows downward, the interior of the triangle is the region where all three edge functions agree in sign. The rasterizer computes the sign of the doubled area of the whole triangle once and uses it to know which agreement counts as inside.

The reason this form is preferred over slope-intercept lines is that it evaluates with multiplies and adds only, has no division, and degrades gracefully: the value is proportional to distance from the edge, so a near-zero value means the sample is near the boundary regardless of triangle size. A rasterizer can compare against zero without normalizing.

Evaluated as written, each sample costs two multiplies and several adds per edge. Real hardware does not evaluate it per sample. Because the function is linear in $x$ and $y$, a whole row of samples advances by a constant increment in $x$, and a whole column advances by a constant in $y$. Setup computes those two increments per edge, so traversal becomes three additions per sample:

/* Coverage test for one sample, using edge functions computed in fixed point.
   Half-open convention: inside when all three values are >= 0 for positive area. */
typedef struct { long long a, b, c; } edge_t;   /* E(x,y) = a*x + b*y + c */

static inline long long eval(const edge_t *e, int x, int y) {
    return e->a * (long long)x + e->b * (long long)y + e->c;
}

static inline int covered(const edge_t e[3], int x, int y) {
    return eval(&e[0], x, y) >= 0 &&
           eval(&e[1], x, y) >= 0 &&
           eval(&e[2], x, y) >= 0;
}

/* Row stepping: the x increment is e->a per pixel, so a triangle scan is
   one add per edge per pixel after the first sample of the row. */

Sign agreement is a complete test only for triangles whose projection is a proper triangle. When a vertex has $w \le 0$ behind the eye, the projected coordinates are meaningless, which is why the pipeline clips before this stage; the coverage machinery assumes a convex, non-degenerate, front-facing region in screen space. A rasterizer that receives an inverted winding, from a mirrored transform or a negative-determinant matrix on a mesh with flipped culling state, sees the sign flip and rejects everything, producing the familiar symptom of geometry that disappears when a negative scale is applied.

The arrangement of the three tests also allows early rejection. If any edge function is negative at the bounding box corner, the triangle cannot cover any part of the box, and setup discards it before traversal; that is the first line of defence described in triangle setup.

Why the arithmetic is integer

If the edge functions were evaluated in floating point, two triangles sharing an edge would not agree on which side a sample lies, because the shared edge would be computed from different vertex orderings and different rounding. The result is worse than a one-pixel crack: with alpha blending or depth writes, a sample covered by both triangles is shaded twice, and a sample covered by neither is left as background. Both are visible as seams.

The standard fix is to quantize vertex positions onto a fixed-point grid before setup, and to evaluate the edge functions in integers exactly. Direct3D 10 and later specify 8 bits of subpixel precision, meaning vertex coordinates land on a grid of $1/256$ of a pixel. With 8 subpixel bits, the difference terms in the edge function fit in about 24 bits for coordinates up to a few thousand pixels, and the products fit in 48, so a 64-bit accumulator is sufficient with margin. The quantization is not free: a vertex that should sit exactly on a pixel boundary may snap to either side, and a triangle thinner than one subpixel unit collapses.

Fixed-point evaluation makes the sign test exact, but it does not by itself decide boundary cases. A sample lying exactly on a shared edge satisfies $E = 0$ for both triangles, so a naive ”$\geq 0$ counts as inside” test shades it twice, and a ”$> 0$” test leaves a gap. Neither is acceptable.

The top-left rule and what it costs

The resolution is a tie-break that assigns every boundary sample to exactly one of the two triangles sharing the edge. The convention, named explicitly in the Direct3D rasterization rules, is to include samples on an edge only when that edge is a top edge or a left edge of the triangle, and to exclude them otherwise. An edge counts as top if it is exactly horizontal and runs in the direction that puts the triangle’s interior below it; it counts as left if it runs downward on the left side of the triangle. The precise conditions depend on the winding convention, but the effect does not: for any shared edge, exactly one of the two triangles sees it as top-left.

Implementing it adds one predicate per edge, evaluated once at setup rather than per sample. Each edge carries a flag, and the inside test for a sample with $E = 0$ consults that flag instead of accepting the sample unconditionally. The per-sample cost is therefore one extra conditional on the rare exact-zero case, which in practice is predicted correctly almost always.

The rule also has a consequence for degenerate geometry. A triangle whose three vertices are collinear has zero doubled area, and all three edge functions are proportional to each other; the sign test then either passes everywhere along a line or nowhere, and the top-left rule can produce no fragments at all. Hardware and APIs generally handle this by treating zero-area triangles as producing nothing, which is the mathematically consistent answer but surprises code that relies on degenerate triangles to draw thick lines.

Where point sampling fails

Point sampling is exact for the coverage question it asks, and wrong for every question about partial coverage. A triangle edge crossing a pixel covers some fraction of that pixel’s area, but the sample either lands inside or outside, so the fragment is either fully shaded or absent. The visible result on a long, near-horizontal edge is a staircase whose step width is one pixel, and the staircase crawls along the edge as the geometry moves. This is the aliasing that the entire rest of the cluster exists to address.

There is a second, subtler failure. Because the sample is a single point, geometry thinner than the sample spacing can vanish entirely: a sliver triangle can pass the bounding-box test and produce zero fragments even though its area is nonzero. The complement of this problem, geometry that must be guaranteed to produce at least one fragment, is what conservative rasterization adds on top of the same edge functions.

Both failures come from the same root: a binary decision at one point stands in for a continuous area. The cheapest improvement is to ask the question at more than one point per pixel and average the answers, which is what multisampling does; the most accurate is to compute the covered area analytically, which requires a different data structure entirely.

Numerical limits worth knowing

The edge function’s magnitude grows with the product of the triangle’s extent and the distance from the sample to the line. For a triangle spanning 4096 subpixel units in each direction, the products stay inside 32 bits, but a triangle whose vertices span the full range of a large render target, combined with a 64-bit accumulator, leaves little room for error if the increments drift. Rasterizers avoid drift by rebuilding the edge value from scratch at the start of each scanline rather than accumulating across an entire span, so error is bounded per row instead of per triangle.

The other limit is the fixed-point range itself. Coordinates outside the representable subpixel grid, which happens when a vertex is clipped but not clamped, must be handled by clipping and the guard band before setup, because the quantizer cannot represent them and silently wraps. A rasterizer that skips clipping and relies on a large fixed-point range is choosing a bound on triangle size; a rasterizer that clips first has a bound on vertex count instead.