Learn Zig Series (#158) - Circle and Ellipse Rasterization

scipio(71)
Published in
StemSocial
Words
4397
Reading
20 min
Listen
Play
22d

Learn Zig Series (#158) - Circle and Ellipse Rasterization

zig.png

What will I learn?

  • Why a circle fights the pixel grid even harder than a line does, and why the obvious y = sqrt(r*r - x*x) approach leaves ugly gaps near the sides;
  • The midpoint circle algorithm -- Bresenham's integer decision-variable idea pointed at a rounder target, plotting one octant and mirroring it eight ways with nothing but add and compare;
  • How to turn a circle outline into a filled disc with horizontal spans, and why that is almost free once you have the symmetry;
  • The midpoint ellipse algorithm: two regions, two decision variables, and why the axis of steepest descent changes halfway round;
  • How Zig's i64 coordinate API and clipping-inside-setPixel keep every one of these routines safe no matter how far off-canvas the shape runs;
  • How an anytype plot context lets the same circle generator fill pixels, count them, or measure a bounding box with no screen at all;
  • How to test a curve with no display, and how C, Rust and Go draw the exact same integer circle.

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 signed-coordinate setPixel/getPixel from episode 156, plus the drawLine we built in episode 157 -- we lean on both today;
  • Signed integers, control flow 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 (#158) - Circle and Ellipse Rasterization

Last episode we tamed the straight line -- Bresenham's integer error term, no floats, no drift, one loop for all eight octants. And I ended by dropping a hint in exercise 3: that same integer-decision-variable trick is not really about lines at all, it is about walking a discrete grid to approximate a continuous shape. Today we cash that hint in. We draw circles and ellipses with nothing but integer add and compare, we fill them, and we do it in a way that cannot scribble outside the buffer no matter how far off-canvas the shape wanders. Here we go!

Solutions to Episode 157 Exercises

Before we round any corners, the three line exercises from last time.

Exercise 1 -- break drawLine on purpose, then prove the fix. The bug was replacing the dx in the y-branch with dy. The lesson is in the test: a shallow line barely touches the y-branch, so you need a steep line to expose it. Here is the correct routine and the steep-line test that pins a midpoint pixel down. If you introduce the bug (change err += dx to err += dy in the second if), this test fails or loops -- that is the point:

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 drawLine(fb: *Framebuffer, x0: i64, y0: i64, x1: i64, y1: i64, color: Rgba) void {
    var x = x0;
    var y = y0;
    const dx: i64 = @intCast(@abs(x1 - x0));
    const dy: i64 = -@as(i64, @intCast(@abs(y1 - y0)));
    const sx: i64 = if (x0 < x1) 1 else -1;
    const sy: i64 = if (y0 < y1) 1 else -1;
    var err = dx + dy;
    while (true) {
        fb.setPixel(x, y, color);
        if (x == x1 and y == y1) break;
        const e2 = 2 * err;
        if (e2 >= dy) {
            err += dy;
            x += sx;
        }
        if (e2 <= dx) {
            err += dx; // the y-branch MUST add dx -- swapping in dy is the bug
            y += sy;
        }
    }
}

test "steep line lights its midpoint (catches the dy-for-dx bug)" {
    var pixels: [4 * 10]Rgba = undefined;
    var fb = Framebuffer{ .pixels = &pixels, .width = 4, .height = 10 };
    @memset(fb.pixels, .{ .r = 0, .g = 0, .b = 0 });
    const white = Rgba{ .r = 255, .g = 255, .b = 255 };
    drawLine(&fb, 0, 0, 2, 8, white); // y is the long axis: exercises the y-branch hard
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(1, 4).?.r); // on the true line
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(2, 8).?.r); // endpoint
}

The insight I want you to keep: "hits both endpoints" is a necessary test but not a sufficient one. A whole class of bugs hides in the branch that only fires when the minor axis advances, and only a steep case drives that branch enough to catch them.

Exercise 2 -- thick lines. Run Bresenham as normal, and at each plotted point stamp a small filled square of the requested width. It is not the fanciest thick-line (the corners are square, not rounded), but it is correct, it clips for free through setPixel, and it is honest about what it does:

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 drawThickLine(fb: *Framebuffer, x0: i64, y0: i64, x1: i64, y1: i64, width: i64, color: Rgba) void {
    const half = @divTrunc(width, 2);
    var x = x0;
    var y = y0;
    const dx: i64 = @intCast(@abs(x1 - x0));
    const dy: i64 = -@as(i64, @intCast(@abs(y1 - y0)));
    const sx: i64 = if (x0 < x1) 1 else -1;
    const sy: i64 = if (y0 < y1) 1 else -1;
    var err = dx + dy;
    while (true) {
        var oy: i64 = -half; // stamp a width-by-width square centred on the point
        while (oy < width - half) : (oy += 1) {
            var ox: i64 = -half;
            while (ox < width - half) : (ox += 1) {
                fb.setPixel(x + ox, y + oy, color);
            }
        }
        if (x == x1 and y == y1) break;
        const e2 = 2 * err;
        if (e2 >= dy) {
            err += dy;
            x += sx;
        }
        if (e2 <= dx) {
            err += dx;
            y += sy;
        }
    }
}

test "a horizontal thick line of width 3 lights three rows" {
    var pixels: [12 * 8]Rgba = undefined;
    var fb = Framebuffer{ .pixels = &pixels, .width = 12, .height = 8 };
    @memset(fb.pixels, .{ .r = 0, .g = 0, .b = 0 });
    const white = Rgba{ .r = 255, .g = 255, .b = 255 };
    drawThickLine(&fb, 2, 4, 8, 4, 3, white);
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(5, 3).?.r); // row above
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(5, 4).?.r); // centre row
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(5, 5).?.r); // row below
}

Exercise 3 -- extend the error term to a curve. This is the one that sets up today's whole episode. The task was a drawCircle that steps one octant with an integer error term and mirrors each point into the other seven by symmetry. Here it is, with the eight setPixel calls written out so you can see the symmetry before we tidy it away:

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 drawCircle(fb: *Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void {
    var x: i64 = radius;
    var y: i64 = 0;
    var err: i64 = 0;
    while (x >= y) {
        // one plotted (x, y) mirrors into all eight octants
        fb.setPixel(cx + x, cy + y, color);
        fb.setPixel(cx - x, cy + y, color);
        fb.setPixel(cx + x, cy - y, color);
        fb.setPixel(cx - x, cy - y, color);
        fb.setPixel(cx + y, cy + x, color);
        fb.setPixel(cx - y, cy + x, color);
        fb.setPixel(cx + y, cy - x, color);
        fb.setPixel(cx - y, cy - x, color);
        y += 1;
        err += 1 + 2 * y;
        if (2 * (err - x) + 1 > 0) {
            x -= 1;
            err += 1 - 2 * x;
        }
    }
}

test "drawCircle lights the four cardinal points" {
    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 };
    drawCircle(&fb, 10, 10, 8, white);
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10 + 8, 10).?.r); // east
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10 - 8, 10).?.r); // west
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10 + 8).?.r); // south
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10 - 8).?.r); // north
}

Good. That circle is the seed of everything below. Now let us understand why it works, then grow it into filled discs and ellipses.

Why a circle fights the pixel grid

The line was hard because the pixel grid is discrete and a line is continuous. A circle is worse, because its slope changes at every point. Your first instinct -- and mine, once -- is high-school geometry again: a circle of radius r around the origin is x*x + y*y = r*r, so solve for y, step x across the diameter, and plot y = round(sqrt(r*r - x*x)) above and below. Let us write exactly that, into the same episode-156 framebuffer (widened to i64 coordinates in episode 157), so we can feel the problem:

const std = @import("std");

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

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];
    }
};

pub fn drawCircleFloat(fb: *Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void {
    var x: i64 = -radius;
    while (x <= radius) : (x += 1) {
        const fx: f64 = @floatFromInt(x);
        const fr: f64 = @floatFromInt(radius);
        const fy = @sqrt(fr * fr - fx * fx); // a square root PER COLUMN
        const y: i64 = @intFromFloat(@round(fy));
        fb.setPixel(cx + x, cy + y, color);
        fb.setPixel(cx + x, cy - y, color);
    }
}

This draws a recognisable circle, but it has two sins. The obvious one is the @sqrt on every column -- expensive, and unavailable on a chip with no floating-point unit, the exact target Zig loves. The subtler, uglier one is gaps. Near the left and right edges of the circle the curve is almost vertical: stepping x by one makes y jump by several pixels, so the outline breaks into disconnected dots, precisely the gap problem we saw with the naive line last episode. You could paper over it by also stepping y across the top and bottom, but now you are writing two loops and stitching them. There is a far better way, and (no surprise) it is Bresenham wearing a different hat.

The midpoint circle: Bresenham in a dress

Look back at exercise 3. It walks a single octant -- the arc from due east round to the north-east diagonal, where x >= y -- and mirrors every point eight ways. Inside that octant the curve never gets steeper than 45 degrees, so stepping the major axis by one never skips a row: no gaps, ever. And the decision of whether x should shrink this step is made by an integer error term that measures how far the true circle has drifted from the current pixel, exactly like the line's error term. No sqrt, no floats, no division.

The eight setPixel calls scream to be factored out. Let us give the symmetry its own helper -- we will reuse it in a moment for the generic version -- and read the loop carefully:

fn plot8(fb: *Framebuffer, cx: i64, cy: i64, x: i64, y: i64, color: Rgba) void {
    fb.setPixel(cx + x, cy + y, color);
    fb.setPixel(cx - x, cy + y, color);
    fb.setPixel(cx + x, cy - y, color);
    fb.setPixel(cx - x, cy - y, color);
    fb.setPixel(cx + y, cy + x, color);
    fb.setPixel(cx - y, cy + x, color);
    fb.setPixel(cx + y, cy - x, color);
    fb.setPixel(cx - y, cy - x, color);
}

pub fn drawCircle(fb: *Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void {
    var x: i64 = radius; // start at due east: (radius, 0)
    var y: i64 = 0;
    var err: i64 = 0;
    while (x >= y) { // stay in the one octant where the slope is gentle
        plot8(fb, cx, cy, x, y, color);
        y += 1;
        err += 1 + 2 * y; // moving y out always increases the error
        if (2 * (err - x) + 1 > 0) { // has the true circle crossed inside x - 0.5?
            x -= 1;
            err += 1 - 2 * x; // pulling x in pays the error back
        }
    }
}

Read err as "how far outside the ideal circle is my current pixel, in units of r*r". Each step moves y outward by one, which always pushes the error up by 1 + 2*y (the algebra of (y+1)^2 - y^2). When that error grows past the point where the pixel one column inward is closer to the true circle, we decrement x and refund 1 - 2*x. The whole thing is add, compare, add -- and because x only ever shrinks and y only ever grows, the loop marches cleanly from (radius, 0) up to the diagonal and stops. That is the entire algorithm. It has been drawing the circles on your screen, in one form or another, since the 1960s.

Filling a circle is almost free

An outline is nice, but half the time you want a solid disc -- a filled button, a bullet, a pie slice. Here the symmetry pays a second dividend. At each step the octant gives us a pair of x-extents at a given y: everything between cx - x and cx + x on row cy + y is inside the circle. So instead of plotting eight points, we draw four horizontal spans. A span is just a clipped horizontal run, and (as we learned last episode) a horizontal run is the cache-friendliest write there is:

fn hSpan(fb: *Framebuffer, xa: i64, xb: i64, y: i64, color: Rgba) void {
    var x = @min(xa, xb);
    const hi = @max(xa, xb);
    while (x <= hi) : (x += 1) {
        fb.setPixel(x, y, color); // setPixel clips, so off-canvas spans are safe
    }
}

pub fn fillCircle(fb: *Framebuffer, cx: i64, cy: i64, radius: i64, color: Rgba) void {
    var x: i64 = radius;
    var y: i64 = 0;
    var err: i64 = 0;
    while (x >= y) {
        hSpan(fb, cx - x, cx + x, cy + y, color); // wide bands near the equator
        hSpan(fb, cx - x, cx + x, cy - y, color);
        hSpan(fb, cx - y, cx + y, cy + x, color); // tall thin caps near the poles
        hSpan(fb, cx - y, cx + y, cy - x, color);
        y += 1;
        err += 1 + 2 * y;
        if (2 * (err - x) + 1 > 0) {
            x -= 1;
            err += 1 - 2 * x;
        }
    }
}

test "fillCircle fills the centre and the cardinal extremes, but not outside" {
    var fb = try Framebuffer.init(std.testing.allocator, 21, 21);
    defer fb.deinit();
    fb.clear(.{ .r = 0, .g = 0, .b = 0 });
    const c = Rgba{ .r = 255, .g = 255, .b = 255 };
    fillCircle(&fb, 10, 10, 8, c);
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10).?.r); // centre
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10 + 8, 10).?.r); // east edge
    try std.testing.expectEqual(@as(u8, 255), fb.getPixel(10, 10 + 8).?.r); // south edge
    try std.testing.expectEqual(@as(u8, 0), fb.getPixel(10 + 8, 10 + 8).?.r); // corner outside the disc: black (proves disc, not square)
    try std.testing.expectEqual(@as(u8, 0), fb.getPixel(2, 2).?.r); // well outside the disc
}

There is quit some overdraw here -- the four spans overlap along the diagonals, so the corner pixels get written twice. For a solid fill that is harmless (writing the same colour twice looks identical), and the code stays tiny. If you were blending semi-transparent colours it would matter, and you would switch to a scanline fill that computes each row exactly once; that is exactly the trade-off exercise 2 asks you to explore.

From circle to ellipse

A circle is an ellipse whose two radii happen to be equal. Drop that coincidence and the eight-way symmetry collapses to four-way (an ellipse has no diagonal symmetry, only across its two axes), and -- here is the interesting part -- the arc from one axis to the other has a point where its slope passes through 45 degrees. Before that point x is the major axis; after it, y is. So the midpoint ellipse algorithm runs in two regions, switching the axis it steps when the slope tips over. Two decision variables, one per region, each still pure integer arithmetic:

fn plot4(fb: *Framebuffer, cx: i64, cy: i64, x: i64, y: i64, color: Rgba) void {
    fb.setPixel(cx + x, cy + y, color);
    fb.setPixel(cx - x, cy + y, color);
    fb.setPixel(cx + x, cy - y, color);
    fb.setPixel(cx - x, cy - y, color);
}

pub fn drawEllipse(fb: *Framebuffer, cx: i64, cy: i64, a: i64, b: i64, color: Rgba) void {
    const a2 = a * a;
    const b2 = b * b;
    var x: i64 = 0;
    var y: i64 = b; // start at the top of the ellipse
    var px: i64 = 0; // 2*b2*x, kept incrementally
    var py: i64 = 2 * a2 * y; // 2*a2*y, kept incrementally
    plot4(fb, cx, cy, x, y, color);

    // Region 1: gentle slope, x is the major axis -- step x every iteration
    var p1: i64 = b2 - a2 * b + @divTrunc(a2, 4);
    while (px < py) {
        x += 1;
        px += 2 * b2;
        if (p1 < 0) {
            p1 += b2 + px;
        } else {
            y -= 1;
            py -= 2 * a2;
            p1 += b2 + px - py;
        }
        plot4(fb, cx, cy, x, y, color);
    }

    // Region 2: steep slope, y is the major axis -- step y every iteration
    var p2: i64 = @divTrunc(b2 * (2 * x + 1) * (2 * x + 1), 4) + a2 * (y - 1) * (y - 1) - a2 * b2;
    while (y > 0) {
        y -= 1;
        py -= 2 * a2;
        if (p2 > 0) {
            p2 += a2 - py;
        } else {
            x += 1;
            px += 2 * b2;
            p2 += a2 - py + px;
        }
        plot4(fb, cx, cy, x, y, color);
    }
}

The shape of it mirrors the circle: keep running totals (px, py) so the per-step work is a couple of adds, and let a decision variable pick when to advance the minor axis. The one wrinkle is the @divTrunc(..., 4) terms. The exact midpoint maths involves halves and quarters ((x + 0.5)^2 and a2/4), and rather than drag floats back in we scale into integers and truncate. That truncation makes the decision very slightly approximate at the sub-pixel level, but for integer pixel coordinates the drawn ellipse is indistinguishable from the exact one -- and we have kept the whole routine FPU-free. The px < py test is what detects the 45-degree tipping point: it is comparing 2*b2*x against 2*a2*y, i.e. the two partial slopes, and the moment the x-side wins we are done with region 1. When a == b, by the way, this degenerates back into a circle -- a nice sanity check on the whole construction.

Testing a curve with no screen

Same discipline as always: perform the operation, read the pixels back, assert. For an ellipse the sharpest cheap test is that all four axis extremes are lit -- (cx +/- a, cy) and (cx, cy +/- b) -- because those are exactly the points the two-region hand-off has to get right. If region 2 stops one step early or late, or the initial p2 is off, one of these four goes dark:

test "ellipse lights all four axis extremes" {
    var fb = try Framebuffer.init(std.testing.allocator, 41, 31);
    defer fb.deinit();
    fb.clear(.{ .r = 0, .g = 0, .b = 0 });
    const c = Rgba{ .r = 255, .g = 255, .b = 255 };
    drawEllipse(&fb, 20, 15, 18, 12, c);
    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
    try std.testing.expectEqual(@as(u8, 0), fb.getPixel(20, 15).?.r); // centre stays hollow (outline only)
}

That last assertion is a small one I like: it proves we drew an outline and not, through some bug, a filled blob. Cheap, but it catches a whole category of "I accidentically filled it" mistakes.

Decoupling the generator from the surface

Just like Bresenham, the midpoint circle does not truly care that it writes to a framebuffer. It generates a sequence of integer points; consuming them is the caller's business. The same anytype trick from episode 157 (and the type-erasure idea from episode 13) applies cleanly: take a context with a plot method. Now the identical circle generator can paint pixels, count them, or -- as here -- compute a bounding box with no framebuffer allocated at all:

pub fn midpointCircle(cx: i64, cy: i64, radius: i64, ctx: anytype) void {
    var x: i64 = radius;
    var y: i64 = 0;
    var err: i64 = 0;
    while (x >= y) {
        ctx.plot(cx + x, cy + y);
        ctx.plot(cx - x, cy + y);
        ctx.plot(cx + x, cy - y);
        ctx.plot(cx - x, cy - y);
        ctx.plot(cx + y, cy + x);
        ctx.plot(cx - y, cy + x);
        ctx.plot(cx + y, cy - x);
        ctx.plot(cx - y, cy - x);
        y += 1;
        err += 1 + 2 * y;
        if (2 * (err - x) + 1 > 0) {
            x -= 1;
            err += 1 - 2 * x;
        }
    }
}

const Bounds = struct {
    min_x: i64 = 0,
    max_x: i64 = 0,
    min_y: i64 = 0,
    max_y: i64 = 0,
    fn plot(self: *Bounds, x: i64, y: i64) void {
        self.min_x = @min(self.min_x, x);
        self.max_x = @max(self.max_x, x);
        self.min_y = @min(self.min_y, y);
        self.max_y = @max(self.max_y, y);
    }
};

test "midpointCircle reports a tight bounding box, no screen needed" {
    var b = Bounds{};
    midpointCircle(0, 0, 10, &b);
    try std.testing.expectEqual(@as(i64, -10), b.min_x);
    try std.testing.expectEqual(@as(i64, 10), b.max_x);
    try std.testing.expectEqual(@as(i64, -10), b.min_y);
    try std.testing.expectEqual(@as(i64, 10), b.max_y);
}

Because ctx is anytype, Bounds.plot is inlined at compile time -- no vtable, no allocation, the whole thing compiles down to register arithmetic. A FramebufferSink whose plot calls setPixel would be exactly as cheap. This is the same "generate versus consume" separation the whole series keeps returning to, and it is why one small routine can serve a renderer, a hit-tester, and a layout pass without copy-pasting the maths.

Performance, and where the cost really is

Count the work, like last episode. drawCircleFloat pays a @sqrt, a @round and a float-to-int cast per column. drawCircle pays two integer adds and one compare per octant step, and produces eight pixels for that price. On a microcontroller with no FPU the float version simply does not run; on a desktop it runs but is measurably slower and, worse, gappy. So the integer midpoint routine wins on both correctness and speed -- a rare and pleasant combination.

For fills, the real cost is the span writes, and there the lesson is again draw with the grain of memory: hSpan walks contiguous pixels, so a big filled disc streams through the cache beautifully. The overdraw along the diagonals is the price of the tiny code; if you are fill-rate bound (say, a particle system spraying thousands of discs a frame) you switch to computing each scanline's extent once and issue one @memset-style run per row. As always: get it correct and clipped first, measure, and only then reach for the specialised version -- and lean on your read-back tests so the fast path cannot silently start corrupting pixels.

Where circles and ellipses show up

This little routine is everywhere the line routine is not. Every rounded rectangle in a UI is four fillCircle quarter-arcs plus some rectangles. Every scatter-plot point, every map pin, every "recording" dot, every radio button and progress ring is a circle or an arc. Anti-aliased or not, the geometry underneath is this midpoint walk. Ellipses turn up wherever perspective squashes a circle -- the selection halo under a game character, an orbit diagram, the rounded end-caps of a thick line drawn properly. Having said that, when you want smooth edges rather than the crisp aliased staircase these give you, you reach for a coverage-based approach (shading boundary pixels by how much of the pixel the shape covers), which -- like Xiaolin Wu's line -- trades the integers back for a little floating point. Crisp and fast versus soft and pretty: pick per use-case, and most UI chrome is perfectly happy crisp.

The same shape in C, Rust and Go

Because it is pure integer arithmetic, the midpoint circle ports almost character-for-character. What changes across languages, exactly as with the line, is the safety story around the pixel write. In C, the eight stores are raw pointer arithmetic and the bounds check is your problem -- forget it and an off-canvas circle corrupts memory instead of clipping:

// C: midpoint circle, raw buffer, manual clipping on every store
void draw_circle(uint32_t *buf, int w, int h, int cx, int cy, int r, uint32_t color) {
    int x = r, y = 0, err = 0;
    while (x >= y) {
        int pts[8][2] = {
            {cx+x, cy+y}, {cx-x, cy+y}, {cx+x, cy-y}, {cx-x, cy-y},
            {cx+y, cy+x}, {cx-y, cy+x}, {cx+y, cy-x}, {cx-y, cy-x},
        };
        for (int i = 0; i < 8; i++) {
            int px = pts[i][0], py = pts[i][1];
            if (px >= 0 && px < w && py >= 0 && py < h) // clip by hand, or corrupt the heap
                buf[py * w + px] = color;
        }
        y += 1;
        err += 1 + 2 * y;
        if (2 * (err - x) + 1 > 0) { x -= 1; err += 1 - 2 * x; }
    }
}

It is line-for-line our Zig loop -- because the algorithm is language-neutral; only the store differs. Rust writes the identical integer loop and reaches the buffer through a bounds-checked buf[idx] (which panics on overrun rather than corrupting) or a get_mut returning Option, our ?Rgba again; the tiny-skia and image crates hand you filled circles out of the box. Go leans on the standard image package and golang.org/x/image, with slice writes bounds-checked at runtime and a panic, not corruption, on overrun. The through-line is the same as last episode: everybody runs the identical mid-1960s integer walk, and they differ only in what happens the instant an index escapes the buffer. Zig gives you the raw-C speed and the clip-or-crash safety in one language, with the clip living in exactly one place -- setPixel -- so every routine today inherits it for free.

Exercises

  1. Arcs, not whole circles. Write drawArc(fb, cx, cy, radius, start_octant, end_octant, color) that draws only some of the eight octants of a circle -- enough to build a rounded-rectangle corner (you only want one quarter). The cleanest approach: keep the midpoint loop, but guard each of the eight setPixel calls behind whether its octant is in range. Test that a single-octant arc lights that octant's endpoint and leaves the opposite side of the circle completely dark.

  2. A proper scanline fill. Our fillCircle overdraws the diagonals. Rewrite it so each row of the disc is written exactly once: for every dy from -radius to +radius, compute the half-width hw such that dy*dy + hw*hw <= radius*radius using integer math only (hint: you can track it incrementally, or bite the bullet with one integer @sqrt-free search per row), then draw one hSpan from cx - hw to cx + hw. Test that the filled pixel count matches the naive version but with no pixel written twice (count writes with an anytype counting context).

  3. Fill the ellipse. Combine today's two ideas: take drawEllipse's two-region walk, but instead of plot4 at each step, draw a horizontal hSpan from cx - x to cx + x at rows cy + y and cy - y. Watch out for the region hand-off so you neither miss the equator row nor draw it twice. Test that the centre is now filled (unlike the outline test above) and that the four vertices are still lit.

What we learned

  • A circle fights the grid harder than a line: the y = sqrt(r*r - x*x) approach costs a square root per column and leaves gaps where the curve turns vertical;
  • The midpoint circle algorithm is Bresenham's integer error-term idea aimed at a curve: walk one 45-degree octant (where the slope is always gentle, so no gaps), and mirror each point eight ways by symmetry -- pure integer add and compare;
  • Filling is nearly free: the octant hands you a pair of x-extents per row, so four clipped horizontal spans fill the disc, cache-friendly, at the cost of a little diagonal overdraw;
  • An ellipse has only four-way symmetry and a slope that tips through 45 degrees, so the midpoint ellipse runs in two regions, switching which axis it steps -- still all integers, with a @divTrunc standing in for the exact quarter-pixel maths;
  • Making the coordinate API i64 and clipping inside setPixel means every routine here -- outline, fill, ellipse -- is overflow-proof no matter how far off-canvas the shape runs, with the check written once;
  • An anytype plot context decouples generating the points from consuming them at zero runtime cost, so the same circle drives a framebuffer, a counter, or a bounding-box measurer;
  • C, Rust and Go all run the identical integer walk and differ only in what happens when an index leaves the buffer -- Zig hands you the speed and the safety together.

We can now draw and fill circles and ellipses with not a single floating-point operation, on top of the lines from last episode and the framebuffer before that. Notice the pattern building: every shape so far has been an outline or a flat fill in one colour. The moment you want two shapes to overlap and blend -- a translucent disc softening what is behind it, edges that fade instead of staircase -- you need to think about what a pixel's fourth channel, that a in Rgba we have been quietly carrying since episode 156, actually means. That is exactly where we head next. Keep these routines close -- like the framebuffer and the line before them, the next ideas stack right on top.

Thanks for reading -- de groeten, and see you in the next one! ;-)

scipio@scipio

stem
stemsocial
steemstem
zig
programming
via hiveblog
This post was published via hiveblog. Ecency is not the originator or editor of this content and displays it for discovery purposes only.
23
Learn Zig Series (#158) - Circle and Ellipse Rasterization | Ecency