Learn Zig Series (#159) - Polygon Filling: Scanline

@scipio 72

12 days ago

StemSocial

Learn Zig Series (#159) - Polygon Filling: Scanline

What will I learn?

Why an arbitrary polygon cannot lean on the tidy symmetry that made circles and ellipses easy to fill;
The even-odd (parity) rule: how a horizontal ray crossing a shape's outline tells you, crossing by crossing, whether you are inside or outside;
A scanline polygon fill written from scratch in Zig -- for every row, find where the edges cross it, sort those x-values, and paint the spans between pairs;
The half-open edge rule that stops shared vertices from being counted twice (the bug that leaves a stray dark pixel or bleeds a whole extra span);
How Zig's error unions and allocator make the "how many crossings can there be" question honest instead of a magic fixed array;
The active-edge idea -- decompose the polygon into edges once, keep only the edges the current row actually touches, and step each crossing incrementally with pure integer math;
Where scanline fill really lives (fonts, SVG, every vector renderer), and how C, Rust and Go write the exact same loop.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org) -- the code here is written and tested against Zig 0.16;
The Framebuffer, Rgba pixel and the clipping signed-coordinate setPixel/getPixel from episode 156, and the fills we grew out of circles and ellipses in episode 158 -- today generalises that filling to any shape;
std.mem.sort, signed integers, and the anytype comptime-duck-typing trick we have used since episode 13;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#159) - Polygon Filling: Scanline

Last episode we filled circles and ellipses, and the trick that made it easy was symmetry. A circle hands you eight mirrored points for the price of one octant; an ellipse hands you four. The fills fell out almost for free because the shape told us, at every row, exactly where its left and right edges were. But most of the shapes you actually want to fill -- a triangle, a five-pointed star, the outline of the letter A, a country on a map -- have no symmetry at all. So today we throw the crutch away and build the fill that works for any closed polygon: the scanline fill. It is one of those ideas that feels almost too simple once it clicks, and it is the exact algorithm sitting under every font renderer and vector engine you have ever used. Here we go!

Solutions to Episode 158 Exercises

Three exercises last time, all of them about turning our curve routines into something more. Here are my solutions.

Exercise 1 -- arcs, not whole circles. The task: draw only some of the eight octants, enough to build a rounded-rectangle corner. The clean approach keeps the midpoint loop untouched and simply guards each of the eight setPixel calls behind whether its octant is in the requested range. I number the octants 0 through 7 going clockwise from due east, and a tiny helper decides membership:

const std = @import("std");

const Rgba = packed struct { r: u8, g: u8, b: u8, a: u8 = 255 };

const Framebuffer = struct {
    pixels: []Rgba,
    width: usize,
    height: usize,

    fn setPixel(self: *Framebuffer, x: i64, y: i64, color: Rgba) void {
        if (x < 0 or y < 0) return;
        const ux: usize = @intCast(x);
        const uy: usize = @intCast(y);
        if (ux >= self.width or uy >= self.height) return;
        self.pixels[uy * self.width + ux] = color;
    }

    fn getPixel(self: Framebuffer, x: i64, y: i64) ?Rgba {
        if (x < 0 or y < 0) return null;
        const ux: usize = @intCast(x);
        const uy: usize = @intCast(y);
        if (ux >= self.width or uy >= self.height) return null;
        return self.pixels[uy * self.width + ux];
    }
};

fn octantOn(o: usize, start: usize, end: usize) bool {
    return o >= start and o <= end;
}

fn drawArc(fb: *Framebuffer, cx: i64, cy: i64, radius: i64, start: usize, end: usize, color: Rgba) void {
    var x: i64 = radius;
    var y: i64 = 0;
    var err: i64 = 0;
    while (x >= y) {
        if (octantOn(0, start, end)) fb.setPixel(cx + x, cy - y, color);
        if (octantOn(1, start, end)) fb.setPixel(cx + y, cy - x, color);
        if (octantOn(2, start, end)) fb.setPixel(cx - y, cy - x, color);
        if (octantOn(3, start, end)) fb.setPixel(cx - x, cy - y, color);
        if (octantOn(4, start, end)) fb.setPixel(cx - x, cy + y, color);
        if (octantOn(5, start, end)) fb.setPixel(cx - y, cy + x, color);
        if (octantOn(6, start, end)) fb.setPixel(cx + y, cy + x, color);
        if (octantOn(7, start, end)) fb.setPixel(cx + x, cy + y, color);
        y += 1;
        err += 1 + 2 * y;
        if (2 * (err - x) + 1 > 0) {
            x -= 1;
            err += 1 - 2 * x;
        }
    }
}

test "single-octant arc lights its end and leaves the far side dark" {
    var pixels: [21 * 21]Rgba = undefined;
    var fb = Framebuffer{ .pixels = &pixels, .width = 21, .height = 21 };
    @memset(fb.pixels, .{ .r = 0, .g = 0, .b = 0 });
    const white = Rgba{ .r = 255, .g = 255, .b = 255 };
    drawArc(&fb, 10, 10, 8, 0, 0, white); // octant 0 only
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10 + 8, 10).?.r); // east endpoint lit
    try std.testing.expectEqual(@as(u8, 0), fb.getPixel(10 - 8, 10).?.r); // west stays dark
}

The lesson is that octant selection costs you nothing at runtime that matters -- you still walk the same loop, you simply skip stores. For a rounded rectangle you call drawArc four times, one quarter each, and stitch straight edges between them.

Exercise 2 -- a proper scanline fill of the disc. Our fillCircle overdrew the diagonals; the task was to write each row exactly once. For every vertical offset dy from -radius to +radius, we want the largest half-width hw with dy*dy + hw*hw <= r*r, computed with integers only, then one horizontal span:

const std = @import("std");

const Rgba = packed struct { r: u8, g: u8, b: u8, a: u8 = 255 };

const Framebuffer = struct {
    pixels: []Rgba,
    width: usize,
    height: usize,

    fn setPixel(self: *Framebuffer, x: i64, y: i64, color: Rgba) void {
        if (x < 0 or y < 0) return;
        const ux: usize = @intCast(x);
        const uy: usize = @intCast(y);
        if (ux >= self.width or uy >= self.height) return;
        self.pixels[uy * self.width + ux] = color;
    }

    fn getPixel(self: Framebuffer, x: i64, y: i64) ?Rgba {
        if (x < 0 or y < 0) return null;
        const ux: usize = @intCast(x);
        const uy: usize = @intCast(y);
        if (ux >= self.width or uy >= self.height) return null;
        return self.pixels[uy * self.width + ux];
    }
};

fn fillCircleScan(fb: *Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void {
    var dy: i64 = -radius;
    while (dy <= radius) : (dy += 1) {
        var hw: i64 = 0;
        while ((hw + 1) * (hw + 1) + dy * dy <= radius * radius) hw += 1;
        var x: i64 = cx - hw;
        while (x <= cx + hw) : (x += 1) fb.setPixel(x, cy + dy, color);
    }
}

test "scanline circle fill matches the disc area exactly (no pixel twice, none missed)" {
    var pixels: [21 * 21]Rgba = undefined;
    var fb = Framebuffer{ .pixels = &pixels, .width = 21, .height = 21 };
    @memset(fb.pixels, .{ .r = 0, .g = 0, .b = 0 });
    const white = Rgba{ .r = 255, .g = 255, .b = 255 };
    const cx: i64 = 10;
    const cy: i64 = 10;
    const r: i64 = 8;
    fillCircleScan(&fb, cx, cy, r, white);

    // independently sum the expected area from the same half-width rule
    var expected: i64 = 0;
    var dy: i64 = -r;
    while (dy <= r) : (dy += 1) {
        var hw: i64 = 0;
        while ((hw + 1) * (hw + 1) + dy * dy <= r * r) hw += 1;
        expected += 2 * hw + 1;
    }
    var lit: i64 = 0;
    for (fb.pixels) |px| {
        if (px.r == 255) lit += 1;
    }
    try std.testing.expectEqual(expected, lit); // equal count => each row drawn once
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10).?.r); // centre
    try std.testing.expectEqual(@as(u8, 0), fb.getPixel(2, 2).?.r); // corner outside the disc
}

The test is the interesting part: because the number of lit pixels equals the area summed independently from the same rule, we have proven no pixel got written twice and none got skipped. That is a stronger statement than "the middle looks filled".

Exercise 3 -- fill the ellipse. Same idea, but the per-row half-width now obeys the ellipse relation hw*hw*b2 + dy*dy*a2 <= a2*b2. I deliberately did not reuse the two-region outline walk here -- the outline's region hand-off is exactly where you accidentically draw the equator row twice. The per-row half-width version cannot double-draw a row, because it visits each row once by construction:

const std = @import("std");

const Rgba = packed struct { r: u8, g: u8, b: u8, a: u8 = 255 };

const Framebuffer = struct {
    pixels: []Rgba,
    width: usize,
    height: usize,

    fn setPixel(self: *Framebuffer, x: i64, y: i64, color: Rgba) void {
        if (x < 0 or y < 0) return;
        const ux: usize = @intCast(x);
        const uy: usize = @intCast(y);
        if (ux >= self.width or uy >= self.height) return;
        self.pixels[uy * self.width + ux] = color;
    }

    fn getPixel(self: Framebuffer, x: i64, y: i64) ?Rgba {
        if (x < 0 or y < 0) return null;
        const ux: usize = @intCast(x);
        const uy: usize = @intCast(y);
        if (ux >= self.width or uy >= self.height) return null;
        return self.pixels[uy * self.width + ux];
    }
};

fn fillEllipse(fb: *Framebuffer, cx: i64, cy: i64, a: i64, b: i64, color: Rgba) void {
    const a2 = a * a;
    const b2 = b * b;
    var dy: i64 = -b;
    while (dy <= b) : (dy += 1) {
        var hw: i64 = 0;
        while ((hw + 1) * (hw + 1) * b2 + dy * dy * a2 <= a2 * b2) hw += 1;
        var x: i64 = cx - hw;
        while (x <= cx + hw) : (x += 1) fb.setPixel(x, cy + dy, color);
    }
}

test "filled ellipse is solid in the centre and lit at all four vertices" {
    var pixels: [41 * 31]Rgba = undefined;
    var fb = Framebuffer{ .pixels = &pixels, .width = 41, .height = 31 };
    @memset(fb.pixels, .{ .r = 0, .g = 0, .b = 0 });
    const white = Rgba{ .r = 255, .g = 255, .b = 255 };
    fillEllipse(&fb, 20, 15, 18, 12, white);
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(20, 15).?.r); // centre now solid
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(20 + 18, 15).?.r); // right vertex
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(20 - 18, 15).?.r); // left vertex
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(20, 15 + 12).?.r); // bottom vertex
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(20, 15 - 12).?.r); // top vertex
}

That per-row half-width trick is really scanline filling in disguise, specialised to a shape whose left and right extents we can compute in closed form. Now we generalise it to a shape where we cannot.

When the symmetry runs out

Give me a triangle with vertices at (2, 2), (16, 4) and (8, 17). There is no formula for "the left and right edge at row y" that I can write once and reuse -- the answer depends on which pair of edges the row happens to cut through, and that changes as y moves down the shape. So we flip the question around. Instead of asking the shape where its edges are, we ask each edge where it crosses the current row. Every closed polygon is just a loop of straight edges, and a straight edge crosses a given horizontal line in at most one point. Collect those crossing points for a row, and you have the row's left and right boundaries handed to you.

First, the surface we draw on -- the same episode-156 framebuffer with i64 clipping coordinates, plus a plain integer Point. Everything today builds on this:

const std = @import("std");

pub const Rgba = packed struct { r: u8, g: u8, b: u8, a: u8 = 255 };

pub const Point = struct { x: i64, y: i64 };

pub const Framebuffer = struct {
    pixels: []Rgba,
    width: usize,
    height: usize,
    allocator: std.mem.Allocator,

    pub fn init(allocator: std.mem.Allocator, width: usize, height: usize) !Framebuffer {
        return .{
            .pixels = try allocator.alloc(Rgba, width * height),
            .width = width,
            .height = height,
            .allocator = allocator,
        };
    }

    pub fn deinit(self: *Framebuffer) void {
        self.allocator.free(self.pixels);
    }

    pub fn clear(self: *Framebuffer, color: Rgba) void {
        @memset(self.pixels, color);
    }

    pub fn setPixel(self: *Framebuffer, x: i64, y: i64, color: Rgba) void {
        if (x < 0 or y < 0) return;
        const ux: usize = @intCast(x);
        const uy: usize = @intCast(y);
        if (ux >= self.width or uy >= self.height) return;
        self.pixels[uy * self.width + ux] = color;
    }

    pub fn getPixel(self: Framebuffer, x: i64, y: i64) ?Rgba {
        if (x < 0 or y < 0) return null;
        const ux: usize = @intCast(x);
        const uy: usize = @intCast(y);
        if (ux >= self.width or uy >= self.height) return null;
        return self.pixels[uy * self.width + ux];
    }
};

The even-odd rule: parity as a compass

Here is the whole idea in one sentence: imagine a ray shot horizontally from far away toward a point; each time it crosses the polygon's outline it flips between outside and inside. Start outside (crossings = 0, even). Cross one edge -- now you are inside (odd). Cross a second -- back outside (even). So a point is inside the polygon exactly when the number of edge crossings strictly to one side of it is odd. This is the even-odd rule, and it works for any polygon, convex or concave, without knowing anything about its shape.

We can test the rule directly with a point-in-polygon check, which is a warm-up for the fill (same crossing math, one point instead of a whole row):

pub fn pointInPolygon(points: []const Point, px: i64, py: i64) bool {
    var inside = false;
    var j: usize = points.len - 1;
    var i: usize = 0;
    while (i < points.len) : (i += 1) {
        const a = points[i];
        const b = points[j];
        j = i;
        // does the edge a-b straddle the ray's height, and cross to the right of px?
        if ((a.y > py) != (b.y > py)) {
            const cross_x = a.x + @divFloor((py - a.y) * (b.x - a.x), b.y - a.y);
            if (px < cross_x) inside = !inside;
        }
    }
    return inside;
}

test "point-in-polygon agrees with the even-odd rule on a concave arrow" {
    const arrow = [_]Point{
        .{ .x = 0, .y = 0 },  .{ .x = 10, .y = 5 }, .{ .x = 0, .y = 10 },
        .{ .x = 3, .y = 5 },
    };
    try std.testing.expect(pointInPolygon(&arrow, 6, 5)); // between the notch and the tip, inside
    try std.testing.expect(!pointInPolygon(&arrow, 1, 5)); // in the concave bite on the left, outside
    try std.testing.expect(!pointInPolygon(&arrow, 20, 5)); // way off to the right, outside
}

The (a.y > py) != (b.y > py) test is doing something sneaky and important: it is asking "does this edge have one endpoint above the ray and one at-or-below it?". By treating the comparison as strictly above versus not above, it counts each edge on a half-open interval -- and that is what stops a vertex shared by two edges from being counted as two crossings (which would break parity). Hold that thought; it is the single most common polygon-fill bug, and we are about to meet it head-on.

A scanline fill from scratch

The fill is the point-in-polygon test promoted from one point to an entire row at a time. For each scanline y between the polygon's top and bottom, we walk every edge, keep the ones that straddle y, compute where each crosses, sort those x-values, and paint the spans between consecutive pairs -- pair [0,1] is inside, [2,3] is inside, and so on, straight out of the even-odd rule:

pub fn fillPolygon(fb: *Framebuffer, points: []const Point, color: Rgba) void {
    if (points.len < 3) return;

    var min_y = points[0].y;
    var max_y = points[0].y;
    for (points) |p| {
        min_y = @min(min_y, p.y);
        max_y = @max(max_y, p.y);
    }

    var xs: [64]i64 = undefined; // crossings for the current row (fixed cap for now)
    var y = min_y;
    while (y <= max_y) : (y += 1) {
        var n: usize = 0;
        var j: usize = points.len - 1;
        var i: usize = 0;
        while (i < points.len) : (i += 1) {
            const a = points[i];
            const b = points[j];
            j = i;
            const lo = @min(a.y, b.y);
            const hi = @max(a.y, b.y);
            if (y >= lo and y < hi) { // half-open: each edge counted once at a shared vertex
                const lower = if (a.y < b.y) a else b;
                const upper = if (a.y < b.y) b else a;
                const cross_x = lower.x + @divFloor((y - lower.y) * (upper.x - lower.x), upper.y - lower.y);
                if (n < xs.len) {
                    xs[n] = cross_x;
                    n += 1;
                }
            }
        }
        std.mem.sort(i64, xs[0..n], {}, std.sort.asc(i64));
        var k: usize = 0;
        while (k + 1 < n) : (k += 2) {
            var x = xs[k];
            while (x <= xs[k + 1]) : (x += 1) fb.setPixel(x, y, color);
        }
    }
}

test "fillPolygon fills a triangle interior and clears the outside" {
    var fb = try Framebuffer.init(std.testing.allocator, 20, 20);
    defer fb.deinit();
    fb.clear(.{ .r = 0, .g = 0, .b = 0 });
    const c = Rgba{ .r = 255, .g = 255, .b = 255 };
    const tri = [_]Point{ .{ .x = 2, .y = 2 }, .{ .x = 16, .y = 4 }, .{ .x = 8, .y = 17 } };
    fillPolygon(&fb, &tri, c);
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(8, 8).?.r); // clearly inside
    try std.testing.expectEqual(@as(u8, 0), fb.getPixel(1, 1).?.r); // outside, top-left
    try std.testing.expectEqual(@as(u8, 0), fb.getPixel(18, 18).?.r); // outside, bottom-right
}

Three design decisions carry the whole thing. The half-open y >= lo and y < hi is the parity guard from the last section, in fill form: a vertex where two edges meet contributes to exactly one of them, so a row passing through a shared vertex sees an even, sensible number of crossings. Horizontal edges are skipped for free -- when a.y == b.y, lo == hi, the test is never true, and we never divide by that edge's zero height. And I compute cross_x from the lower endpoint every time, with @divFloor, so the rounding is deterministic and orientation-independent (walk the polygon clockwise or anti-clockwise, you get the identical pixels). The one wart is xs: [64]i64 -- a fixed cap that silently drops crossings for a polygon with more than 64 edges through one row. That is a lie waiting to happen, and Zig gives us a nicer way to tell the truth.

Letting the type system carry the weight

How many crossings can a row have? Up to one per edge, so up to points.len. A fixed [64] array is a guess; the honest answer is "allocate exactly that many, and admit that allocation can fail". That is precisely what Zig's error unions are for -- the function's type becomes !void, the caller must acknowledge the one real failure mode, and defer guarantees we give the memory back on every path:

pub fn fillPolygonAlloc(
    fb: *Framebuffer,
    allocator: std.mem.Allocator,
    points: []const Point,
    color: Rgba,
) !void {
    if (points.len < 3) return;

    const xs = try allocator.alloc(i64, points.len); // at most one crossing per edge, exactly
    defer allocator.free(xs);

    var min_y = points[0].y;
    var max_y = points[0].y;
    for (points) |p| {
        min_y = @min(min_y, p.y);
        max_y = @max(max_y, p.y);
    }

    var y = min_y;
    while (y <= max_y) : (y += 1) {
        var n: usize = 0;
        var j: usize = points.len - 1;
        var i: usize = 0;
        while (i < points.len) : (i += 1) {
            const a = points[i];
            const b = points[j];
            j = i;
            const lo = @min(a.y, b.y);
            const hi = @max(a.y, b.y);
            if (y >= lo and y < hi) {
                const lower = if (a.y < b.y) a else b;
                const upper = if (a.y < b.y) b else a;
                xs[n] = lower.x + @divFloor((y - lower.y) * (upper.x - lower.x), upper.y - lower.y);
                n += 1;
            }
        }
        std.mem.sort(i64, xs[0..n], {}, std.sort.asc(i64));
        var k: usize = 0;
        while (k + 1 < n) : (k += 2) {
            var x = xs[k];
            while (x <= xs[k + 1]) : (x += 1) fb.setPixel(x, y, color);
        }
    }
}

test "the allocating fill needs no arbitrary cap and matches the fixed version" {
    var fb = try Framebuffer.init(std.testing.allocator, 20, 20);
    defer fb.deinit();
    fb.clear(.{ .r = 0, .g = 0, .b = 0 });
    const c = Rgba{ .r = 255, .g = 255, .b = 255 };
    const tri = [_]Point{ .{ .x = 2, .y = 2 }, .{ .x = 16, .y = 4 }, .{ .x = 8, .y = 17 } };
    try fillPolygonAlloc(&fb, std.testing.allocator, &tri, c);
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(8, 8).?.r);
    try std.testing.expectEqual(@as(u8, 0), fb.getPixel(1, 1).?.r);
}

Notice what the !void bought us. The [64] version could not fail at the type level, which sounds nice until you realise it was papering over a real limit by corrupting the output instead. The allocating version can fail, says so, and the compiler will not let a caller forget -- that is Zig's whole philosophy in miniature: no hidden control flow, no silent truncation, the cost visible in the signature. Having said that, for the common case of small polygons the fixed-array version is genuinely fine and allocation-free; the point is to choose that trade-off deliberately, not to stumble into a magic 64.

Making it fast: the active-edge idea

The naive fill re-examines every edge on every row. A glyph with a few hundred edges over a few hundred rows is tens of thousands of straddle tests, most of them answered "no" -- quit some wasted effort. The classic fix is the active edge table: decompose the polygon into edges once, and for each row consider only the edges that actually span it. While we are at it, we store each edge in a normalised form so computing its crossing is a single multiply-and-floor with no branching on orientation:

const Edge = struct {
    y_min: i64, // scanline where this edge becomes active
    y_max: i64, // first scanline where it is no longer active (half-open)
    x_at_ymin: i64, // x of the lower-y endpoint
    dx: i64, // run  (upper.x - lower.x)
    dy: i64, // rise (upper.y - lower.y), always positive

    fn xAt(self: Edge, y: i64) i64 {
        return self.x_at_ymin + @divFloor((y - self.y_min) * self.dx, self.dy);
    }
};

pub fn fillPolygonAET(
    fb: *Framebuffer,
    allocator: std.mem.Allocator,
    points: []const Point,
    color: Rgba,
) !void {
    if (points.len < 3) return;

    const edges = try allocator.alloc(Edge, points.len);
    defer allocator.free(edges);

    var ne: usize = 0;
    var min_y = points[0].y;
    var max_y = points[0].y;
    var j: usize = points.len - 1;
    var i: usize = 0;
    while (i < points.len) : (i += 1) {
        const a = points[i];
        const b = points[j];
        j = i;
        min_y = @min(min_y, a.y);
        max_y = @max(max_y, a.y);
        if (a.y == b.y) continue; // drop horizontal edges: they contribute no crossing
        const lower = if (a.y < b.y) a else b;
        const upper = if (a.y < b.y) b else a;
        edges[ne] = .{
            .y_min = lower.y,
            .y_max = upper.y,
            .x_at_ymin = lower.x,
            .dx = upper.x - lower.x,
            .dy = upper.y - lower.y,
        };
        ne += 1;
    }

    const xs = try allocator.alloc(i64, ne);
    defer allocator.free(xs);

    var y = min_y;
    while (y <= max_y) : (y += 1) {
        var n: usize = 0;
        for (edges[0..ne]) |e| {
            if (y >= e.y_min and y < e.y_max) { // only the edges this row actually touches
                xs[n] = e.xAt(y);
                n += 1;
            }
        }
        std.mem.sort(i64, xs[0..n], {}, std.sort.asc(i64));
        var k: usize = 0;
        while (k + 1 < n) : (k += 2) {
            var x = xs[k];
            while (x <= xs[k + 1]) : (x += 1) fb.setPixel(x, y, color);
        }
    }
}

test "AET fill agrees pixel-for-pixel with the reference on a concave polygon" {
    const poly = [_]Point{
        .{ .x = 2, .y = 2 },   .{ .x = 18, .y = 2 }, .{ .x = 18, .y = 18 },
        .{ .x = 10, .y = 10 }, .{ .x = 2, .y = 18 },
    };
    var a = try Framebuffer.init(std.testing.allocator, 20, 20);
    defer a.deinit();
    var b = try Framebuffer.init(std.testing.allocator, 20, 20);
    defer b.deinit();
    a.clear(.{ .r = 0, .g = 0, .b = 0 });
    b.clear(.{ .r = 0, .g = 0, .b = 0 });
    const c = Rgba{ .r = 255, .g = 255, .b = 255 };
    fillPolygon(&a, &poly, c);
    try fillPolygonAET(&b, std.testing.allocator, &poly, c);
    for (a.pixels, b.pixels) |pa, pb| {
        try std.testing.expectEqual(pa.r, pb.r); // identical output, faster route
    }
}

Because both routines compute cross_x from the lower endpoint with the same @divFloor, the AET version is not an approximation of the reference -- it is byte-for-byte identical, just cheaper. The test proves it on a concave shape (the inward notch forces multiple spans per row, which is where a sloppy fill falls apart). There is still one multiply and one divide per active edge per row inside xAt. The final classic optimisation removes even those: because y only ever increases by one, each active edge's crossing advances by dx/dy per row, which you can track with a Bresenham-style integer accumulator -- no multiply, no divide, just add and compare, exactly like the line and circle:

fn advanceX(x: *i64, acc: *i64, dx: i64, dy: i64) void {
    acc.* += dx; // carry the fractional part in the accumulator
    if (dx >= 0) {
        while (acc.* >= dy) : (acc.* -= dy) x.* += 1;
    } else {
        while (acc.* <= -dy) : (acc.* += dy) x.* -= 1;
    }
}

Keep an active list of edges as you sweep, advanceX each one as the row steps down, add edges as their y_min arrives and drop them as their y_max passes, and you have the textbook active-edge-table rasteriser: the fill that has been putting polygons on screens since the 1970s. As always -- get it correct and clipped first, lean on the read-back tests, and only then reach for the incremental version once a profiler says this loop is where the time goes.

Where scanline fill actually lives

This one routine is doing more work in your day than almost any other graphics primitive, you just never see it. Every font you read is stored as filled outlines -- TrueType and OpenType glyphs are closed contours, and turning them into the pixels of a letter is exactly this scanline fill (with anti-aliasing on top). Every SVG <path> with a fill attribute is scanline-filled. Every vector illustration, every filled region in a charting library, every map polygon, every filled shape in a game's 2D HUD -- all of it is this parity-and-spans loop. The even-odd rule you just learned is even a named attribute in the SVG spec (fill-rule="evenodd"), sitting right next to its cousin the nonzero winding rule, which counts edge directions instead of bare crossings so that overlapping sub-paths fill sensibly. Swapping our parity flip for a signed winding counter is a small change and a natural next experiment (it is exercise 3).

The same fill in C, Rust and Go

The algorithm is language-neutral integer arithmetic, so it ports almost line for line -- what changes is, once again, the story around memory. In C you malloc the crossings array yourself, remember to free it, qsort the x-values, and every buffer write is your responsibility to bounds-check:

// C: scanline fill, manual crossings buffer, manual clipping on every store
#include <stdlib.h>

static int cmp_int(const void *pa, const void *pb) {
    int a = *(const int *)pa, b = *(const int *)pb;
    return (a > b) - (a < b);
}

void fill_polygon(uint32_t *buf, int w, int h, const int *px, const int *py, int npts, uint32_t color) {
    int *xs = malloc(sizeof(int) * npts);
    if (!xs) return;                 // OOM handled by hand, or you crash
    int min_y = py[0], max_y = py[0];
    for (int i = 1; i < npts; i++) {
        if (py[i] < min_y) min_y = py[i];
        if (py[i] > max_y) max_y = py[i];
    }
    for (int y = min_y; y <= max_y; y++) {
        int n = 0, j = npts - 1;
        for (int i = 0; i < npts; i++) {
            int lo = py[i] < py[j] ? py[i] : py[j];
            int hi = py[i] < py[j] ? py[j] : py[i];
            if (y >= lo && y < hi) {
                int lx = py[i] < py[j] ? px[i] : px[j];
                int ux = py[i] < py[j] ? px[j] : px[i];
                int ly = py[i] < py[j] ? py[i] : py[j];
                int uy = py[i] < py[j] ? py[j] : py[i];
                xs[n++] = lx + (y - ly) * (ux - lx) / (uy - ly);
            }
            j = i;
        }
        qsort(xs, n, sizeof(int), cmp_int);
        for (int k = 0; k + 1 < n; k += 2)
            for (int x = xs[k]; x <= xs[k + 1]; x++)
                if (x >= 0 && x < w && y >= 0 && y < h)  // clip by hand, or corrupt the heap
                    buf[y * w + x] = color;
    }
    free(xs);
}

That is our Zig loop with the safety rails removed: the OOM check is a bare if (!xs), the clip is a hand-written conjunction on every store, and free sits at the bottom hoping every return path reached it (it does here, but add one early exit and you have a leak). Rust writes the same loop with a Vec<i32> you .sort(), panics rather than corrupts on an out-of-range index, and in practice reaches for tiny-skia, lyon or femtovg, which hand you a hardened, anti-aliased polygon fill out of the box. Go uses a slice you sort.Ints, bounds-checked writes that panic on overrun, and the standard image package plus golang.org/x/image/vector for a production rasteriser. The through-line is the one we keep meeting: everybody runs the identical mid-1970s scanline sweep, and they differ only in what happens the instant an index escapes the buffer, or an allocation fails. Zig gives you C's speed with the clip living in exactly one place -- setPixel -- and the failure spelled out in the function's !void.

Exercises

Filled polygon outlines that meet the fill. Combine today's fillPolygonAET with episode 157's drawLine: fill a polygon in one colour, then stroke its edges in another, so the border is crisp. Test that a boundary pixel takes the stroke colour while a deep-interior pixel keeps the fill colour. Watch the half-open rule -- the bottom edge of a filled polygon can come out one row short, and a stroke is a good way to see it.
A star, to prove concavity works. Build the ten vertices of a five-pointed star (alternating outer and inner radius around a centre, using the integer sin/cos table trick or precomputed points) and fill it with fillPolygon. Test that a point in one of the star's arms is lit, a point in a concave notch between two arms is dark, and the centre is lit. This is the shape that separates a real even-odd fill from a convex-only shortcut.
Nonzero winding rule. Replace the parity flip with a signed winding counter: give each edge a direction (+1 if it goes downward, -1 if upward), and instead of toggling inside/outside at each crossing, add the edge's direction and treat "winding != 0" as inside. Fill a shape with a hole wound the opposite way (an outer square anti-clockwise, an inner square clockwise) and test that the hole comes out empty under winding but filled under even-odd -- the classic difference between the two rules.

What we learned

Circles and ellipses fill easily because symmetry hands you each row's extents; an arbitrary polygon has no such gift, so we ask each edge where it crosses the current row instead of asking the shape;
The even-odd rule says a point is inside when a ray from it crosses the outline an odd number of times -- parity is a compass that works for any polygon, convex or concave;
A scanline fill applies that rule a whole row at a time: gather the edge crossings for row y, sort them, and paint the spans between consecutive pairs;
The half-open y >= lo and y < hi edge test is the crucial detail -- it counts each edge once at a shared vertex (keeping parity correct) and skips horizontal edges for free (no divide-by-zero);
Zig's !void and an allocator turn the "how many crossings" question from a magic [64] cap into an honest, exactly-sized allocation with the one failure mode spelled out in the signature;
The active-edge table decomposes the polygon into edges once and touches only the edges each row spans; computing crossings from the lower endpoint makes the fast version byte-for-byte identical to the reference, and a Bresenham-style accumulator removes even the per-row multiply and divide;
Fonts, SVG, maps and every vector renderer are running this exact parity-and-spans sweep; C, Rust and Go write the identical loop and differ only in what happens when an index or an allocation goes wrong.

We can now fill any closed polygon, on top of the lines, circles and ellipses of the last episodes -- our little rasteriser draws real shapes now, not just primitives. But look at how every shape so far has been pinned to fixed pixel coordinates: we hand-typed the star's vertices, the triangle's corners, the circle's centre. The moment you want to move that polygon across the screen, spin it, or scale it to half size, you do not want to recompute every vertex by hand -- you want a single, composable way to transform a whole set of points at once. That machinery -- the matrices that rotate, scale and translate everything we draw -- is exactly where we head next. Keep these fill routines close; they are about to start drawing shapes that move.

Bedankt en tot de volgende keer! ;-)

@scipio

stem stemsocial steemstem zig programming

0.000

0 comments

Learn Zig Series (#159) - Polygon Filling: Scanline

Learn Zig Series (#159) - Polygon Filling: Scanline

What will I learn?

Requirements

Difficulty

Curriculum (of the Learn Zig Series):

Learn Zig Series (#159) - Polygon Filling: Scanline

Solutions to Episode 158 Exercises

When the symmetry runs out

The even-odd rule: parity as a compass

A scanline fill from scratch

Letting the type system carry the weight

Making it fast: the active-edge idea

Where scanline fill actually lives

The same fill in C, Rust and Go

Exercises

What we learned

Curriculum (of the `Learn Zig Series`):