Conservative Rasterization for Thin and Subpixel Geometry

The point-sampling coverage rule described in rasterization rules and the top-left fill convention has a failure mode that is not an artifact but a correctness violation for some uses: a triangle can cover no sample point and produce no fragments at all. For a renderer drawing pixels, that is acceptable, because a subpixel triangle is invisible. For a renderer computing something from the set of covered pixels — a voxelization, an occlusion query, a collision or visibility mask, a shadow volume construction — a missing triangle is a hole in a data set, and the data set is wrong.

Conservative rasterization changes the coverage question from “is the sample inside the triangle” to “does the pixel, as a region, intersect the triangle”. Every pixel that any part of the triangle touches produces a fragment.

Why the point test loses geometry

Geometry smaller than a pixel is commonplace. A triangle in a highly tessellated mesh at a distance can project to a speck a few hundredths of a pixel across. A line rendered as a thin quad has the same property. The number of such triangles in a frame is not small: a tessellated surface at distance has a large fraction of its triangles below a pixel, and a distant object viewed edge-on can consist almost entirely of subpixel triangles.

Under the point test, each such triangle has a probability proportional to its area of covering a sample point, and the expected number of covered pixels per triangle is its area in pixels. Half a million triangles of 0.01 pixels each produce around five thousand fragments in total rather than the tens of thousands of pixels they physically span, and the holes are scattered rather than concentrated, so they appear as noise. The distribution is not uniform either: because sample positions are fixed in the pixel grid, a mesh whose triangles align with the grid systematically misses or systematically hits, which turns the noise into a visible pattern that moves with the camera.

The lost geometry also affects any query that relies on fragment counts. An occlusion query counting samples that pass the depth test under-counts whenever geometry falls between sample points, so an object can be judged invisible when it is not, and a bounding-volume test built on such a query becomes unreliable at distance.

The expanded test

Conservative rasterization expands the triangle by half a pixel in every direction and tests the pixel’s sample point against the expansion. Equivalently, it tests whether the pixel’s square — the axis-aligned unit square centred on the sample point — intersects the triangle. The equivalence holds because the pixel is a square and the expansion of the triangle by a square’s half-extent produces exactly the set of sample points whose squares touch the triangle.

The implementation is a change to the edge functions’ acceptance criterion. Instead of requiring every edge function to be non-negative, the test requires every edge function to be non-negative after subtracting a margin that represents the pixel’s half-extent projected onto the edge’s normal. For an edge with normal direction (nx, ny), the margin is the half-extent times the absolute value of the normal’s dominant component, or more precisely half the pixel’s width times |nx| plus half its height times |ny|. Because the margin depends only on the edge’s direction, it can be computed once per edge at setup and applied as a constant offset.

/* Conservative coverage for one sample point: the pixel square intersects
   the triangle if every edge function, diminished by the edge's margin,
   is still non-negative. Screen space, y downward, interior is >= 0. */
#include <math.h>
#include <stdbool.h>

struct e { double ax, ay, bx, by; };   /* edge endpoints, pixel units */

/* The pixel is a unit square centred on the sample point, so its extent
   along the edge's unit normal (nx, ny) is (|nx| + |ny|) / 2. Multiplying
   by the normal's length gives the same extent in edge-function units,
   which are twice the signed area: (|dy| + |dx|) / 2. */
static double margin(const struct e *e)
{
    return 0.5 * (fabs(e->by - e->ay) + fabs(e->bx - e->ax));
}

bool covers_conservative(const struct e e[3], double px, double py)
{
    for (int i = 0; i < 3; i++) {
        double v = (e[i].bx - e[i].ax) * (py - e[i].ay)
                 - (e[i].by - e[i].ay) * (px - e[i].ax);
        /* v is twice the signed area; the margin is in the same units. */
        if (v + margin(&e[i]) < 0.0) return false;
    }
    return true;
}

Two properties of this test matter beyond the obvious. First, it is conservative in the set-theoretic sense: a pixel the triangle touches always passes, and a pixel that passes always touches the triangle. There is no over- or under-coverage beyond the geometric definition. Second, the overlap between adjacent triangles’ coverage sets grows. Two triangles sharing an edge both cover the pixels along that edge, because each pixel’s square touches both. A mesh rasterized conservatively produces roughly one extra ring of fragments along every interior edge, and the count of fragments is closer to the perimeter of the mesh in pixels plus its area than to its area alone.

That expansion is the source of the technique’s characteristic artifact. A pixel covered by both a triangle and its neighbour gets two fragments, and its shading is performed twice. For an opaque render with depth testing, the duplicate is rejected and the result is correct but slower; for a blended render, the shared pixels are blended twice and the seam brightens or darkens; for a voxelization that accumulates, the shared pixels are counted twice. Conservative rasterization must therefore be paired with a depth test or with a merge step that deduplicates.

Inner coverage and the deduplication problem

The over-coverage variant is sometimes called outer conservative, because it expands outward from the true footprint. Its complement, inner conservative, covers only pixels entirely inside the triangle. The inner variant is used when the question is “which pixels are fully covered”, for example to identify pixels that need no neighbouring data and can be shaded without a border — a common need in post-processing filters and in generating a conservative mask for a later pass.

The distinction matters because the two variants produce sets that, for a triangle, do not partition the screen. The difference is the one-pixel ring along the triangle’s boundary, which belongs to neither the inner set of the triangle nor the inner set of its neighbour. A pass that requires an exact partition — a parameterisation that must assign every touched pixel to exactly one triangle — has to pick one of the two and deduplicate, typically by preferring the triangle with the lower identifier and rejecting the other’s claim.

Deduplication in the fixed-function pipeline is done with a depth or stencil test that keeps the first fragment per pixel. A stencil test that rejects a pixel already written, with the stencil buffer reset per pass, is the straightforward form: the first triangle to touch a pixel writes it, the rest are rejected. The state is per-pixel, so one full-screen clear per pass is the cost, plus the stencil write for every accepted fragment.

Cost and the bandwidth ordering

Conservative rasterization multiplies the fragment count of thin geometry by a factor that depends on the triangle’s aspect ratio. A triangle one pixel wide and a hundred pixels long covers roughly a hundred pixels under the point test and roughly a hundred and fifty under the conservative test, so the multiplier is small. A triangle a tenth of a pixel wide and a hundred pixels long covers roughly ten pixels under the point test and roughly a hundred and fifty under the conservative test, so the multiplier is fifteen. The worst case is a long, thin triangle, and it is exactly the case that the technique exists to handle.

The cost therefore concentrates where the geometry is thinnest, and a conservative pass over a tessellated surface has a work distribution that follows the surface’s silhouette rather than its area. For voxelization, where the output is one voxel per pixel, the fragment count is bounded by the number of voxels touched by the surface, which is the surface’s pixel area — a quantity independent of the tessellation. That bound is the point of the technique: it makes the cost depend on the result rather than on the input.

#version 450
// A voxelising pass: each fragment emits the voxel coordinate it covers.
// The invocation count is bounded by the covered surface, not the triangle count.
layout(location = 0) in vec4 world_pos;
layout(location = 1) flat in uint face_id;
layout(early_fragment_tests) in;   // no discard; depth test may hoist

layout(binding = 0) uniform image3D voxel_grid;

void main()
{
    ivec3 cell = ivec3(floor(world_pos.xyz * 32.0));
    imageStore(voxel_grid, cell, vec4(float(face_id), 1.0, 1.0, 1.0));
}

Bandwidth, not shading, is the limit on this style of pass. Every covered fragment writes an image element, and image writes are not merged by the framebuffer’s blend hardware for an integer grid. The ordering hazard is genuine as well: two fragments writing the same cell from different triangles race, and the pipeline does not order image writes between fragments of the same draw. The usual fix is to make the write idempotent or to resolve per face in separate passes, which trades throughput for determinism.

Precision at the boundary

The expanded test is exact arithmetic on a margin, but the margin itself must be computed without error at the pixel boundary. A triangle edge that runs exactly along a pixel’s boundary is the case where the formulation’s rounding matters: the true answer is that the pixel is touched, and any arithmetic that underestimates the margin reports it untouched. The result is a one-pixel hole along a surface exactly aligned to the grid — a case that arises constantly with axis-aligned geometry such as boxes and walls.

The implementations that handle it correctly pad the margin by a small epsilon proportional to the coordinate magnitude, so the boundary case falls on the conservative side. The padding increases over-coverage by a negligible amount (a fraction of a pixel) and removes the aligned-geometry hole. Implementations that omit the padding are correct for general geometry and wrong for aligned geometry, which is why the technique’s specification tends to state the guarantee in terms of the pixel’s closed region rather than its open one.

The other precision hazard is that the expanded edge functions no longer share a zero boundary across a shared edge, so the top-left rule’s deduplication property disappears. As noted above, every edge’s pixels are claimed from both sides, and the fill convention that keeps a normal rasterizer seam-free has no analogue here. The conservative pass must deduplicate explicitly, and the choice of which triangle wins the shared pixel is visible in the output as a bias toward the earlier triangle in the draw order.