Rasterisation: triangles, depth, and draw order

Foundations produced screen positions. This chapter fills the space between them.

Three things differ from the 2D scanline polygon fill: everything is a triangle, each pixel carries a depth as well as a colour, and values varying across the surface cannot be interpolated linearly once perspective is involved.

Canvases here are small enough to print, so every figure is what the code produced.

Why triangles

Three points always lie in one plane, and a triangle is always convex. Neither holds for a general polygon: four points can be non-planar, and a concave outline needs the crossing-pair logic the 2D scanline fill carried. So geometry is tessellated into triangles first, and a triangle is the only primitive from here on.

The render target

A colour buffer and a depth buffer of the same size, the latter holding the distance to the nearest surface written so far, starting further than anything.

sub new_target {
    my ($w, $h) = @_;
    return { w => $w, h => $h,
             px    => [ map { [ ('.') x $w ] } 1 .. $h ],
             depth => [ map { [ (9e9) x $w ] } 1 .. $h ] };
}

Characters stand in for colours so the results print directly.

The inside test

One function carries the rasteriser. Given three points it returns twice the signed area of the triangle they form:

sub edge {
    my ($a, $b, $c) = @_;
    return ($b->[0] - $a->[0]) * ($c->[1] - $a->[1])
         - ($b->[1] - $a->[1]) * ($c->[0] - $a->[0]);
}

With a and b fixed as a line, the sign says which side c is on: positive one side, negative the other, zero exactly on it.

A point is inside the triangle when it is on the same side of all three edges, so run edge once per edge and check the signs agree.

my $w0 = edge($v1, $v2, $p);
my $w1 = edge($v2, $v0, $p);
my $w2 = edge($v0, $v1, $p);
next unless ($w0 >= 0 && $w1 >= 0 && $w2 >= 0)
         || ($w0 <= 0 && $w1 <= 0 && $w2 <= 0);

Accepting both sign conventions takes a triangle wound either way. Sampling at the pixel centre ($x + 0.5, $y + 0.5) is the 2D guide’s half-pixel offset: an integer coordinate names a corner, so coverage is decided at the middle.

Loop over the triangle’s bounding box. A 20 by 10 target:

....................
.########...........
..##############....
...###########......
...#########........
....#######.........
.....####...........
......#.............
....................
....................

54 pixels. No scanlines, edge lists or sorting: the same three comparisons at every candidate pixel, independent of each other, which is why hardware uses this formulation.

Winding and culling

edge on the triangle’s own vertices gives its signed area, and the sign says which way it winds on screen:

print edge([1,1], [17,2], [6,8]);    # 107
print edge([1,1], [6,8], [17,2]);    # -107

Same points, opposite order, opposite sign. That sign distinguishes the front of a surface from the back.

A closed object is built so every triangle winds the same way seen from outside; rotate it and the ones now facing away flip sign. Those are invisible, so they can be discarded before any pixel work. That is back-face culling:

my $area = edge($v0, $v1, $v2);
return 0 if $opt{cull} && $area <= 0;

Both windings with culling on: 54 pixels front-facing, 0 reversed. On a closed mesh this discards roughly half the triangles for one sign test. It is also why a model with inconsistent winding renders with holes; each hole is a triangle culled that should not have been.

Barycentric interpolation

Divided by the total area, the three edge results are the barycentric coordinates of the point: weights summing to 1 giving each vertex’s contribution.

my ($b0, $b1, $b2) = ($w0 / $area, $w1 / $area, $w2 / $area);
my $z = $b0 * $v0->[2] + $b1 * $v1->[2] + $b2 * $v2->[2];

At a vertex its own weight is 1 and the others 0; at the centre they are equal. Any per-vertex value interpolates this way: depth here, equally a colour, a normal or a texture coordinate.

The depth buffer

Two triangles overlap on screen. Which does the viewer see?

The 2D answer was draw order, last one wins: the painter’s algorithm. It fails as soon as draw order does not match depth order. A is near (z = 2), B is far (z = 8).

Drawing B then A gives the right image, but only because that order happened to match the depth order:

....................
..AAAAAAAAAAA.......
..AAAAAAAAABBBBBBB..
..AAAAAAAABBBBBBBB..
..AAAAAA..BBBBBBBB..
..AAAA......BBBBBB..
..AAA.........BBBB..
..A............BBB..
.................B..
....................

Reversed, A then B, the same code produces a wrong image. The figure below is the bug, not the goal:

....................
..AAAAAAAAAAA.......
..AAAAABBBBBBBBBBB..
..AAAAAAABBBBBBBBB..
..AAAAAA..BBBBBBBB..
..AAAA......BBBBBB..
..AAA.........BBBB..
..A............BBB..
.................B..
....................

The far triangle has painted over the near one. The geometry is fine; the algorithm has no idea which is nearer.

Sorting back to front does not fix it: two long triangles can each be partly in front of the other, and three can form a cycle with no valid order. The answer must work per pixel:

next if $z >= $t->{depth}[$y][$x];    # something nearer is already here
$t->{depth}[$y][$x] = $z;
$t->{px}[$y][$x] = $ch;

Keep the nearest depth per pixel, skip anything further. Both draw orders now produce the same image, confirmed pixel by pixel in the harness. Triangles can arrive in any sequence.

That is the Z-buffer, named and deferred in the 2D guide’s foundations. It costs one screen-sized buffer and one compare per pixel.

Perspective-correct interpolation

Linear interpolation in screen space is wrong for everything except depth. A receding surface covers less screen per unit of surface, so equal steps across the screen are not equal steps across the surface. A naively interpolated texture slides and warps, most visibly on a floor.

Interpolate the value divided by w, interpolate 1/w alongside it, and divide at the end. An edge from z = 1 to z = 5 carrying a coordinate from 0 to 1:

t      screen-linear  perspective
0.00   0.000          0.000
0.25   0.250          0.062
0.50   0.500          0.167
0.75   0.750          0.375
1.00   1.000          1.000

Halfway across the screen is 17 percent along the surface, not 50. The two agree at the endpoints and diverge between, so the bug looks like a texture correct at the corners and wrong in the middle.

Depth needs no correction: 1/w is what the depth buffer should store, and that interpolates linearly in screen space already.

Near-plane clipping

A vertex behind the camera has w <= 0, and dividing by it produces garbage. Such vertices must go before the divide. The test is w > near, and a segment crossing it is cut:

sub clip_near {
    my ($a, $b) = @_;                 # each [x, y, z, w]
    my ($da, $db) = ($a->[3] - $near, $b->[3] - $near);
    return ($a, $b) if $da >= 0 && $db >= 0;      # wholly in front
    return ()       if $da <  0 && $db <  0;      # wholly behind
    my $t = $da / ($da - $db);                    # where it crosses
    my $m = [ map { $a->[$_] + ($b->[$_] - $a->[$_]) * $t } 0 .. 3 ];
    return $da >= 0 ? ($a, $m) : ($m, $b);
}

A segment from w = 4 to w = -2 cuts at [5.20, 0.00, 0.00, 0.10], exactly on the near plane; both ends behind returns nothing. Clipping a triangle runs this against each edge, which can leave four vertices, so the result is re-triangulated before rasterising.

The far plane works the same way. The other four sides need no clipping here, because the bounding box is already clamped to the screen.

In hardware

All of the above is fixed-function silicon on a graphics card: edge functions, barycentric weights, depth compare, perspective divide, run per triangle in parallel. What you supply is the vertex positions going in and the colour decision coming out.

That is why the GPU scene chapter reads as familiar vocabulary: a depth test you enable, a cull-face mode you pick a winding for, and interpolated values that arrive perspective-correct.

The next chapter decides what colour a covered pixel is.