Triangle Setup: Subpixel Snapping and the Bounding Box

Between the vertex shader and the first fragment there is a stage that produces no visible output at all. It converts a triangle’s projected vertices into a fixed set of integer constants: three edge equations, a bounding rectangle, and the per-attribute interpolation coefficients. Every fragment the rasterizer ever emits is derived from those constants by addition. The cost of setup is paid once per triangle; the cost of getting setup wrong is paid per pixel, which is why the format chosen for those constants matters more than the arithmetic used to produce them.

Quantization before anything else

The projected vertex arrives as a floating-point pair in normalized device coordinates, mapped to pixel space by a scale and offset derived from the viewport. The first act of setup is to convert each coordinate to fixed point on a subpixel grid. With $n$ fractional bits the representable step is $2^{-n}$ of a pixel, and the vertex is snapped to the nearest grid point.

The choice of $n$ is a compromise with three pressures. More bits reduce the chance that a vertex moves visibly, since the maximum snap error is half a grid step. More bits also reduce the chance that a thin triangle collapses to zero area or that two adjacent triangles develop a crack, because both vertices of a shared edge quantize identically. But more bits widen the integers needed for the edge function products, and those products must fit in the accumulators of the whole traversal unit. Direct3D 10 fixed the value at 8 bits of subpixel precision and the Vulkan specification adopts the same convention, which means a vertex is placed within $1/256$ of a pixel of its exact position.

Snapping is not the same as rounding to nearest in all cases. Some implementations snap consistently toward a fixed direction to guarantee that the snap is monotonic, so that a vertex that moves in $+x$ on the grid never appears to move in $-x$ after quantization. Monotonicity matters when adjacent triangles share vertices and their union must remain watertight: identical input bits must produce identical output bits, and a rounding mode that is a pure function of the input value satisfies that.

What setup must produce

Four things, and nothing else, are needed downstream.

The edge equations as coefficients $a, b, c$ for $E(x,y) = ax + by + c$, in the fixed-point grid units described in the half-space test. Because the vertices are already integers, these coefficients are integers exactly, and the test is exact arithmetic, not an approximation of one.

The bounding box, as integer pixel coordinates. Its lower bound is the floor of the minimum $x$ and $y$ across all three vertices, and its upper bound is the ceiling of the maximums, clamped to the render target. The box is conservative: it can contain pixels the triangle does not touch, but it never excludes one that it does.

The winding sign, as the sign of the total doubled area. This decides which direction of edge-function value means inside, and combined with the top-left flags it decides boundary ownership.

The interpolation coefficients for each vertex attribute. For depth and for any varying, hardware needs the derivative of the attribute with respect to $x$ and $y$ across the triangle plane, plus a base value at a known reference point. These plane equations are computed in the same step and consume the same edge values.

/* Setup for one triangle. v[] are already snapped to a 1/256 pixel grid (int32).
   Returns 0 if the triangle is degenerate or back-facing under the given sign. */
typedef struct {
    int64_t a[3], b[3], c[3];      /* edge functions, fixed point */
    int32_t minx, miny, maxx, maxy; /* inclusive bounding box in pixels */
    int      area_sign;            /* +1 or -1 */
} setup_t;

int setup(const int32_t v[3][2], int w, int h, setup_t *s)
{
    int32_t area2 = (v[1][0]-v[0][0])*(v[2][1]-v[0][1])
                  - (v[1][1]-v[0][1])*(v[2][0]-v[0][0]);
    if (area2 == 0) return 0;            /* collinear: nothing to fill */
    s->area_sign = area2 > 0 ? 1 : -1;

    for (int e = 0; e < 3; e++) {
        int32_t x0 = v[e][0], y0 = v[e][1];
        int32_t x1 = v[(e+1)%3][0], y1 = v[(e+1)%3][1];
        s->a[e] = (int64_t)(y1 - y0);
        s->b[e] = (int64_t)(x0 - x1);
        s->c[e] = (int64_t)x1 * y0 - (int64_t)x0 * y1;
    }
    /* Bounding box in pixel units: min floors, max ceils after the shift. */
    int32_t xlo = v[0][0], xhi = v[0][0], ylo = v[0][1], yhi = v[0][1];
    for (int i = 1; i < 3; i++) {
        if (v[i][0] < xlo) xlo = v[i][0];
        if (v[i][0] > xhi) xhi = v[i][0];
        if (v[i][1] < ylo) ylo = v[i][1];
        if (v[i][1] > yhi) yhi = v[i][1];
    }
    s->minx = xlo >> 8;
    s->miny = ylo >> 8;
    s->maxx = (xhi + 255) >> 8;
    s->maxy = (yhi + 255) >> 8;
    if (s->minx < 0) s->minx = 0;
    if (s->miny < 0) s->miny = 0;
    if (s->maxx > w) s->maxx = w;
    if (s->maxy > h) s->maxy = h;
    return (s->minx < s->maxx && s->miny < s->maxy);
}

The coefficients above differ by a sign from the expansion in the previous article; both conventions are valid and the winding sign picks the consistent one. Whichever is chosen, the constants must be checked against the box: computing one edge value at a box corner is cheaper than evaluating a row that covers nothing, and many rasterizers also compute the three edge values at the box origin as the starting accumulator so that traversal begins without re-deriving them.

Why the bounding box pays

A triangle’s area is usually small relative to the render target, but its bounding box can be much larger than its area. The ratio of box area to triangle area is worst for long, thin slivers, where the box can be hundreds of times the covered area. The box still helps, because the alternative is scanning the whole target, and the box reduces the work from the target’s area to the box’s area, a ratio that is usually in the thousands.

The important property is that the box test is free at the fragment level: traversal iterates only within the declared rectangle, so a fragment outside it is never generated, never shaded, and never bandwidth. That makes the box one of the few optimizations in the pipeline that reduces work rather than reordering it. The related optimization, hierarchical coverage by testing larger tiles against the edge equations before descending, is what binned rasterization does structurally rather than opportunistically.

The box has a cost too, in that it is derived from the snapped vertices rather than the original ones. A triangle with a vertex one subpixel unit outside a pixel boundary expands the box by a whole pixel on that side, doubling the scanned area in the worst case of a small triangle. This is why some implementations compute the box from the unsnapped coordinates and then expand by one pixel, trading a little wasted coverage for the guarantee that snapping cannot push geometry outside the box.

Degeneracies that reach setup

Three cases arrive at setup with data that breaks the assumptions above.

Zero-area triangles have $area2 = 0$ and produce no fragments, as described earlier. They are common in meshes with collapsed edges, in geometry generated by tessellation, and in point-sprite tricks that deliberately emit degenerate geometry for the vertex shader to expand. A rasterizer that returns early here saves the whole traversal.

Very large triangles overflow the fixed-point accumulation. A triangle covering the full width of a 16K render target, with 8 subpixel bits, spans $16384 \times 256 = 2^{22}$ grid units per side, so the products in the edge function reach $2^{44}$ before the three-point sum, which fits in a signed 64-bit accumulator with 19 bits to spare. Two of those products can cancel to a near-zero result, and catastrophic cancellation in exact integer arithmetic is not an issue, but the intermediate must not overflow: the accumulator width is chosen from the maximum target size the hardware supports, not from typical sizes.

Vertices far outside the target arise when clipping is partial or when the guard band is used. If the snapped coordinate exceeds the representable integer range, quantization wraps and the triangle appears in the wrong place. The guard band in clipping exists precisely to keep projected coordinates inside a representable margin so that setup never sees such a vertex.

The pipeline position

Setup sits between primitive assembly and traversal, and its output is consumed by the traversal unit that emits fragments. In a hardware pipeline the stage is fixed-function and highly parallel: each triangle is set up independently and needs no state from its neighbours, which is exactly what makes the tiled designs that assign triangles to bins by their bounding box possible in the first place. The box computed here is the same rectangle used for bin assignment higher in the pipeline, and a bounding box that is wrong by one pixel in either direction produces dropped primitives that no later stage can recover.