Drawing primitives from scratch

Every graphics library hands you line, circle, fill, and blur. This chapter implements them in plain Perl so that when a library draws them for you, nothing is magic. These are the classic algorithms, and they are classic because they are the right answers: fast, integer where they can be, and correct at the awkward cases. You will not ship these implementations (a C library will always be faster), but knowing them tells you why a library behaves the way it does, and gives you the tools for the one case the library did not anticipate.

Throughout, the canvas is the nested-array raster from the foundations chapter: a grid of [r, g, b] pixels addressed by integer (x, y), origin top-left.

sub new_canvas {
    my ($w, $h) = @_;
    return { w => $w, h => $h,
             px => [ map { [ map { [255, 255, 255] } 1 .. $w ] } 1 .. $h ] };
}

sub set_px {
    my ($c, $x, $y, $color) = @_;
    return if $x < 0 || $y < 0 || $x >= $c->{w} || $y >= $c->{h};
    $c->{px}[$y][$x] = $color;
}

Lines: Bresenham

A line from (x0, y0) to (x1, y1) has to choose, for each column it crosses, which row of pixels to light. The naive approach computes y = m*x + b with floating point per step; Bresenham’s algorithm does it with integer addition only, by tracking an error term that says how far the ideal line has drifted from the pixels chosen so far.

The insight is that at each step you either stay on the same cross-axis row or move one, and a running integer error decides which. The version below handles every slope and direction in one loop by working with absolute deltas and step signs:

sub draw_line {
    my ($c, $x0, $y0, $x1, $y1, $color) = @_;
    my $dx = abs($x1 - $x0);
    my $dy = -abs($y1 - $y0);
    my $sx = $x0 < $x1 ? 1 : -1;
    my $sy = $y0 < $y1 ? 1 : -1;
    my $err = $dx + $dy;                   # error accumulator
    while (1) {
        set_px($c, $x0, $y0, $color);
        last if $x0 == $x1 && $y0 == $y1;
        my $e2 = 2 * $err;
        if ($e2 >= $dy) { $err += $dy; $x0 += $sx; }   # step in x
        if ($e2 <= $dx) { $err += $dx; $y0 += $sy; }   # step in y
    }
}

No multiplication, no division, no floating point in the loop. That is why Bresenham survived from 1962: it is the line-drawing you would build in hardware. Every library’s thin, aliased line is this or a direct descendant.

Circles: the midpoint method

A circle has eight-fold symmetry: compute one octant and mirror it into the other seven. The midpoint circle algorithm walks one octant with the same integer-error idea as Bresenham, deciding at each step whether to move straight or diagonally by testing a decision variable against zero.

sub draw_circle {
    my ($c, $cx, $cy, $r, $color) = @_;
    my ($x, $y) = ($r, 0);
    my $err = 1 - $r;                      # decision variable
    while ($x >= $y) {
        # eight mirrored points, one per octant
        for my $p ([$x,$y],[$y,$x],[-$x,$y],[-$y,$x],
                   [$x,-$y],[$y,-$x],[-$x,-$y],[-$y,-$x]) {
            set_px($c, $cx + $p->[0], $cy + $p->[1], $color);
        }
        $y++;
        if ($err < 0) { $err += 2 * $y + 1; }
        else          { $x--; $err += 2 * ($y - $x) + 1; }
    }
}

Compute one eighth, draw eight. The same symmetry trick, with the error test adjusted, gives ellipses and arcs.

Filling polygons: the scanline method

Drawing a shape’s outline is one problem; filling its interior is another. The scanline fill sweeps a horizontal line down the image, and for each scanline finds where it crosses the polygon’s edges. Those crossings come in pairs, and the interior is between each pair: the even-odd rule. Sort the x crossings, then fill between the first and second, the third and fourth, and so on.

# poly is an arrayref of [x, y] vertices, in order, implicitly closed
sub fill_polygon {
    my ($c, $poly, $color) = @_;
    my ($ymin, $ymax) = ($poly->[0][1], $poly->[0][1]);
    for my $v (@$poly) {
        $ymin = $v->[1] if $v->[1] < $ymin;
        $ymax = $v->[1] if $v->[1] > $ymax;
    }
    for my $y ($ymin .. $ymax) {
        my @xs;
        for my $i (0 .. $#$poly) {
            my $a = $poly->[$i];
            my $b = $poly->[($i + 1) % @$poly];
            my ($ay, $by) = ($a->[1], $b->[1]);
            # does this edge straddle the scanline?
            next if ($ay <= $y) == ($by <= $y);
            # x where the edge crosses y (linear interpolation)
            my $t = ($y - $ay) / ($by - $ay);
            push @xs, $a->[0] + $t * ($b->[0] - $a->[0]);
        }
        @xs = sort { $a <=> $b } @xs;
        # fill between crossing pairs
        for (my $i = 0; $i + 1 < @xs; $i += 2) {
            for my $x (int($xs[$i] + 0.5) .. int($xs[$i + 1] - 0.5)) {
                set_px($c, $x, $y, $color);
            }
        }
    }
}

The ($ay <= $y) == ($by <= $y) test is the crossing check written to count each vertex exactly once, so a scanline passing through a shared vertex does not double-count and leak the fill. That half-open convention is the detail that separates a correct fill from one with occasional stray lines, and it is why libraries and this code agree on where an edge ”belongs“.

Anti-aliasing: coverage instead of on-or-off

The line and circle above are aliased: each pixel is fully on or fully off, and a diagonal edge looks like a staircase. Anti-aliasing softens that by setting a pixel’s intensity to how much of it the shape actually covers. A pixel the edge crosses at 40 percent coverage gets 40 percent of the shape color blended with 60 percent of the background, which is exactly the source-over compositing from the last chapter with alpha equal to coverage.

The cheapest way to approximate coverage is supersampling: draw at several times the resolution with the aliased algorithm, then average each block of high-resolution pixels down to one. Averaging a 2x2 block where three sub-pixels are on gives 75 percent coverage for free:

# downsample a 2x-oversampled canvas by averaging 2x2 blocks
sub downsample_2x {
    my ($big) = @_;
    my ($w, $h) = ($big->{w} / 2, $big->{h} / 2);
    my $out = new_canvas($w, $h);
    for my $y (0 .. $h - 1) {
        for my $x (0 .. $w - 1) {
            my @sum = (0, 0, 0);
            for my $dy (0, 1) {
                for my $dx (0, 1) {
                    my $p = $big->{px}[2 * $y + $dy][2 * $x + $dx];
                    $sum[$_] += $p->[$_] for 0 .. 2;
                }
            }
            $out->{px}[$y][$x] = [ map { int($_ / 4 + 0.5) } @sum ];
        }
    }
    return $out;
}

Real libraries compute coverage analytically rather than by brute-force supersampling, but the effect is identical: the staircase becomes a smooth ramp of intensities. When Cairo gives you a crisp anti-aliased curve and Imager offers an aa flag on its primitives, this is what they are doing.

Tessellation: breaking shapes into triangles

Hardware and many algorithms only really know how to fill triangles; everything more complex is first broken into triangles, a process called tessellation or triangulation. A convex polygon triangulates trivially by fanning from one vertex:

# fan triangulation of a convex polygon -> list of [v0, v1, v2] triangles
sub triangulate_convex {
    my ($poly) = @_;
    my @tris;
    for my $i (1 .. $#$poly - 1) {
        push @tris, [ $poly->[0], $poly->[$i], $poly->[$i + 1] ];
    }
    return @tris;
}

Concave polygons need a real algorithm (ear clipping is the standard one: repeatedly find a triangle that pokes out with no other vertex inside it, snip it off, repeat). The convex fan is enough to see the idea, and it is the idea that carries straight into 3D, where every surface is ultimately a mesh of triangles. In two dimensions you meet tessellation whenever you fill a complex vector path; in the planned 3D sequel it is the foundation of everything.

Convolution: blur, sharpen, and edges

A whole family of image effects comes from one operation: convolution, sliding a small grid of weights (a kernel) over the image and replacing each pixel with the weighted sum of its neighbors. A kernel of all equal weights averages, which blurs. A kernel that subtracts the neighbors and adds a large center sharpens.

# apply a 3x3 kernel to a canvas; divisor normalises the weights
sub convolve_3x3 {
    my ($c, $kernel, $divisor) = @_;
    $divisor ||= 1;
    my $out = new_canvas($c->{w}, $c->{h});
    for my $y (1 .. $c->{h} - 2) {
        for my $x (1 .. $c->{w} - 2) {
            my @sum = (0, 0, 0);
            for my $ky (0 .. 2) {
                for my $kx (0 .. 2) {
                    my $wgt = $kernel->[$ky][$kx];
                    my $p = $c->{px}[$y + $ky - 1][$x + $kx - 1];
                    $sum[$_] += $p->[$_] * $wgt for 0 .. 2;
                }
            }
            $out->{px}[$y][$x] =
                [ map { my $v = int($_ / $divisor + 0.5);
                        $v < 0 ? 0 : $v > 255 ? 255 : $v } @sum ];
        }
    }
    return $out;
}

my $box_blur = [[1,1,1],[1,1,1],[1,1,1]];   # divisor 9
my $sharpen  = [[0,-1,0],[-1,5,-1],[0,-1,0]]; # divisor 1

The box blur divides by 9 to keep brightness constant; the sharpen kernel sums to 1 so it needs no divisor. Swap in a kernel that responds to intensity change and you get edge detection, which is where image processing shades into computer vision. That boundary is deliberate: this guide uses convolution as a drawing tool (blur a shadow, sharpen a downscaled sprite) and stops there. Analysis, feature detection, and recognition are a different subject, out of scope here.

What the libraries do for you

Everything above is what a graphics library implements in optimized C, usually with SIMD and careful edge handling you would not want to write by hand. Knowing the algorithms means you can read a library’s documentation and know what ”anti-aliased“, ”even-odd fill rule“, ”convolution matrix“, and ”triangulated path“ mean, and you can drop to your own pixel loop for the rare effect no library ships. The next chapter picks up Imager, where these primitives are one method call away and running at C speed.