August, 2026

Rasterization

How to create a Direct3D and Vulkan specification conformant rasterization algorithm.

This article assumes familiarity with rendering concepts such as texels, samples, coverage, and shading. It was informed by my work functionally modelling AMD's rasterization stage.

Rasterization is the algorithm responsible for converting a 2D triangle into a set of texel or sample coordinates for shading. The Direct3D and Vulkan graphics APIs both specify formal requirements for rasterization to ensure shaded texels are consistent between vendors. This article explains the requirements in the specifications, and builds a conformant scanline rasterizer for triangles.

The Specification

Assume framebuffer coordinates have their origin at the upper-left corner of the upper-left texel, with increasing downwards. Texel occupies . A texel contains one or more samples, whose positions are defined by the API.

Point Sampling

Vulkan defines coverage by point sampling:

Fragments are produced for any fragment area groups of pixels for which any sample points lie inside of this polygon. Coverage bits that correspond to sample points that satisfy the point sampling criteria are 1, other coverage bits are 0.

Coverage is a predicate on sample positions, not a measure of area. The dashed texel is substantially overlapped but produces nothing.

A primitive overlapping most of a texel produces nothing if no sample lies inside it, and a sub-texel sliver produces a fragment if one does.

The Fill Rule

A sample lying exactly on an edge is a boundary case. It occurs suprisingly often, whenver an edge is axis-aligned on the sample grid.

The Vulkan specification is typically generic, stating

if two polygons lie on either side of a common edge (with identical endpoints) on which a sample point lies, then exactly one of the polygons must result in a covered sample for that fragment during rasterization.

Direct3D 11.3 is more specific, explicitly requiring the top-left rule:

If an edge is exactly horizontal, and it is above the other edges of the triangle in pixel space, then it is a "top" edge. If an edge is not exactly horizontal, and it is on the left side of the triangle in pixel space, then it is a "left" edge. [...] If a sample location falls exactly on the edge of a triangle, the sample is inside the triangle if the edge is a "top" edge or a "left" edge.

A triangle positioned so that samples fall exactly on all three edges. Circled samples are those the rule decides.

A quad triangulated along a diagonal passing through samples. (a) every edge inclusive, and the diagonal is drawn twice. (b) every edge exclusive, and it is dropped. (c) the top-left rule, covering each sample once. The rule also decides the quad's outer boundary: its top and left edges are covered, its bottom and right are not.

Fixed Point Coordinates

Section §3.4.1 of the D3D11.3 specification requires that after clipping and the perspective divide, vertex and are converted to fixed point. Vulkan exposes the same quantity as subPixelPrecisionBits, at least .

Section §3.2.4 provides a formal definition of fixed point representations and conversions. As a refresh, fixed point represents a decimal value as an integer with an implicit decimal point at a fixed location, written for integer bits and fractional bits.

Conversion to fixed point, drawn with rather than the specified . Dashed is the input, solid is its fixed point representation.

After conversion to fixed point, the rasterizer's stages should ensure no rounding occurs. The fixed point triangle defines the exact coverage.

Edge case: a primitive of zero area is supposed to produce no fragments. Area is evaluated after conversion, so a primitive with small nonzero area which collapses in must produce nothing rather than a sliver.

Operations on Fixed Point Values

The format of a fixed point value propagates as

In plain language: addition and subtraction don't require more bits in fixed point but multiplication needs double the bits.

Viewport Size, Clipping and Guard Bands

Clipping ensure a primitive does not extend outside a certain boundary. Conceptually, this is usually thought of as the edges of the screen. However, because clipping is an expensive operation which amplifies the number of primitives, clipping actually occurs against a guard band which can extend well beyond the screen coordinates. A primitive that leaves the viewport but is inside the guard band has out of bounds pixels discarded (or not rasterized at all). Only a primitive leaving the guard band is clipped geometrically.

(a) inside the viewport. (b) outside the viewport but inside the guard band, rasterized whole with the walker clamped. (c) outside the guard band, and the only case that is clipped.

An Algorithm

Checking Coverage with Barycentrics

Barycentric coordinates are already needed to interpolate attributes across a triangle. They can also be used to test whether a sample point is covered by a triangle.

Define the edge function

which is twice the signed area of (can been seen from cross product). For a triangle with vertices , define

(a) a sample inside the triangle, where no weight is negative. (b) a sample outside it: the sub-triangle opposite the crossed edge reverses orientation, so changes sign.

These quantities are proportional to the barycentric coordinates of . In particular,

Thus, if the triangle is counterclockwise,

are its barycentric coordinates. A point is inside the triangle (including edges) when

For a clockwise triangle, all signs are reversed, so the equivalent test is .

The Top-Left Rule

We need to avoid samples which lie exactly on an edge being incorrectly included or excluded. For a directed edge of our primitive,

We can encode this constraint directly into our barycentric test by biasing the weights according to the edge conditions. A weight is a product of coordinate differences, so it carries fractional bits and its smallest representable increment is . Subtracting one such increment turns into , and both cases become a single comparison.

bias(a, b):                              # once per edge
    top  = y_a == y_b and x_b > x_a
    left = y_b < y_a
    return 0 if (top or left) else -ulp  # ulp = 2^-2f

covered(p):                              # once per sample, assumes CCW
    return D(v0, v1, p) + bias(v0, v1) >= 0
       and D(v1, v2, p) + bias(v1, v2) >= 0
       and D(v2, v0, p) + bias(v2, v0) >= 0

Each weight is paired with the bias of the edge it is measured against, and the three biases are fixed once the primitive is set up.

Candidate Texel Walker

Sample positions are the subtexel positions that determine whether a texel is covered.

Vulkan standard sample locations, relative to the upper-left corner of a texel. and have no standard positions.

A walker bounded against sample positions would have to account for these subtexel geometries. Bounding against whole texels is conservative and allows any sampling rate, even variable rates.

Divide the framebuffer into horizontal rows (or scan lines) of texels. Row is covered by . Our walker will emit one pair per band,

Once we have start and end we can test each sample.

for y in rows spanned by the primitive:
    for x in [floor(start[y]), floor(end[y])]:
        for s in sample_positions:
            p = (x + s.x, y + s.y)
            if covered(p): emit(p)

To find start and end we start by reducing the number of cases by sorting the vertices so that . After sorting we have

The long edge spans the full vertical range.
The short edges and consisting of an upper and lower edge with shared vertex .

Note that the edge are defined so they go from top to bottom. Depending on the winding order we can clasify the long edge as either a left or right edge.

If the winding order is clockwise: the long edge is a left edge.
If the winding order is counter-clockwise: the long edge is a right edge.

As a small trick, we can compute the winding order cheaply from the parity of the number of swaps we performed when sorting. We flip the pre-sort winding order if the parity is odd.

One pair per band. Here the long edge is a left edge, so it supplies every , and the short edges supply every . Emitted texels are shaded.

Interpolating an Edge

Take one edge, running from down to , so . Its contribution to each band is bounded by where it meets the horizontal lines enclosing that band, so what is needed is the coordinate at every whole the edge crosses. Call them , top to bottom.

Two of those coordinates are not crossings. The edge may begin or end part way through a band, so and , which are already exact. Only the interior coordinates are interpolated, and consecutive whole lines are exactly one apart, so they are evenly spaced.

We accumulate in the direction we are walking here to avoid a multiplication.

We need to account for the rounding introduced by the division when calculating step. Held to fractional bits beyond the coordinate format, the step is off by at most , and an edge crossing rows accumulates of those. With , and inside the guard band, the total stays under , which is a quarter of the spacing of the coordinate grid. Widening each interpolated coordinate outwards by one absorbs it, so no texel is ever missed.

Reading the Correct End of a Band

Within a band the edge is a straight line, so its extreme lies at one of the band's two horizontal lines and never between them. The coordinates bound rows, band running from down to , and the sign of alone says which of the two to take.

A left edge contributes to and so wants its leftmost point. Given from the sort,

: the edge moves right as it descends, so each band's leftmost point is on its upper line and the walk reads .
: the edge moves left as it descends, so it is on the lower line and the walk reads .

A right edge contributes to and takes the opposite line in each case. Reading the wrong one offsets every span by a band of slope, which silently drops the texels down one side of the primitive.

A left edge with .

The Band Containing the Shared Vertex

The short edges meet at . This band is a special case with three possible extremes

The band holding , with the short edges on the right so the extreme wanted is the rightmost. (a) : both increasing right, so the lower edge's crossing wins. (b) : both decreasing left, so the upper edge's wins. (c) : saddle where wins.

Putting It Together

Here is psuedocode for the walker logic.

# precondition: y_a <= y_b
walk(edge a -> b, side):
    if y_a == y_b:
        contribute min or max of x_a, x_b to its single band
        return

    step = (x_b - x_a) / (y_b - y_a)
    x    = x_a + (ceil(y_a) - y_a) * step

    top = x_a
    for j in bands spanned by the edge:
        bot = x_b if j is the last band else widen(x)

        if edge is left: contribute (step >= 0 ? top : bot) to start
        else:            contribute (step >= 0 ? bot : top) to end

        top = bot
        x  += step

The algorithm presented in this article is one solution consistent with the Vulkan and D3D11 rasterization specifications. While it is a performant serial algorithm it is not how GPU hardware works.