Fill
The Fill tool paints a whole area at once.
You click one pixel. Every pixel connected to it by the same colour changes to the new colour, and the fill stops at any other colour.
That set of pixels is the region. The work is finding it.
The region is found a few pixels at a time
We cannot know the region’s shape in advance. We only know the first pixel.
Its neighbours with the same colour are in the region too. Their neighbours with the same colour are in it as well, and so on.
So each pixel we accept can reveal more pixels to look at.
Recursion is the short answer, and the wrong one
The shortest way to write this is a function that fills one pixel and then calls itself on its four neighbours.
It is short and it is wrong for a paint program.
Each call waits for the calls it makes, so the calls nest. Filling an empty 640 by 400 layer nests 256,000 calls deep. Each call needs some stack space, and a thread’s stack is usually 8 MiB or less, and much less in a browser. The program stops partway through the fill.
A queue and a visited map
Instead we keep a list of pixels still to look at, called a queue, and work through it from the front:
- Put the clicked pixel in the queue.
- Take the next pixel from the queue.
- For each of its four neighbours: if it has the target colour and we have not seen it yet, mark it seen and add it to the queue.
- Repeat from step 2 until the queue is empty.
The marks live in a bit set: one bit per pixel of the image. A 640 by 400 image needs 256,000 bits, which is 32,000 bytes.
/// Find the region of `pixels` connected to (`x`, `y`) that has exactly the
/// colour at (`x`, `y`).
pub fn find(
gpa: std.mem.Allocator,
pixels: []const Rgba,
width: u32,
height: u32,
x: u32,
y: u32,
) !Region {
const total = @as(usize, width) * height;
var inside: std.bit_set.Dynamic = try .initEmpty(gpa, total);
errdefer inside.deinit(gpa);
// Every pixel enters the queue at most once, because it is marked when it
// goes in rather than when it comes out. So the queue never needs more
// room than the image has pixels, and a plain array with a read position
// is enough: nothing is ever moved.
const queue = try gpa.alloc(u32, total);
defer gpa.free(queue);
var head: usize = 0;
var tail: usize = 0;
const target = pixels[@as(usize, y) * width + x];
const start: u32 = y * width + x;
inside.set(start);
queue[tail] = start;
tail += 1;
var bounds: Rect = .{ .x0 = x, .y0 = y, .x1 = x + 1, .y1 = y + 1 };
while (head < tail) {
const i = queue[head];
head += 1;
const px = i % width;
const py = i / width;
bounds = bounds.join(.{ .x0 = px, .y0 = py, .x1 = px + 1, .y1 = py + 1 });
// The four neighbours, skipping any that would fall off an edge.
const neighbours = [4]?u32{
if (px > 0) i - 1 else null,
if (px + 1 < width) i + 1 else null,
if (py > 0) i - width else null,
if (py + 1 < height) i + width else null,
};
for (neighbours) |maybe| {
const n = maybe orelse continue;
if (inside.isSet(n)) continue;
if (!std.meta.eql(pixels[n], target)) continue;
inside.set(n);
queue[tail] = n;
tail += 1;
}
}
return .{ .inside = inside, .bounds = bounds, .count = tail };
}Why the queue never needs to grow
A pixel is marked when it goes into the queue, not when it comes out.
That small choice means no pixel can enter the queue twice. So the queue never holds more entries than the image has pixels, and we can allocate exactly that much up front.
And because nothing is ever removed from the front, there is no need to move anything. head is where we read and tail is where we write. Both only move forward.
For 640 by 400 the queue is 256,000 u32 values, 1,024,000 bytes. It is freed when find returns.
Four neighbours, and the fringe
The fill checks four neighbours: left, right, up and down.
So two pixels that touch only at a corner are not connected. A fill stops at a diagonal gap.
The match is also exact. A pixel is in the region only if all four of its bytes equal the starting pixel’s.
The soft edge of a brush stroke is made of pixels that are partly covered, so none of them match exactly. A fill inside a soft circle stops before the edge and leaves a thin ring of the old colour. Paint programs offer a tolerance setting for this reason. This engine leaves it out to keep the region rule simple.
Filling and undo
The document’s fillAt finds the region, saves its bounding rectangle for undo, and changes every pixel in the region:
/// Fill the area around (`x`, `y`) on the active layer with an opaque
/// colour. Returns false if there was nothing to change.
pub fn fillAt(d: *Document, x: u32, y: u32, color: [3]u8) !bool {
if (d.stroke != null or x >= d.width or y >= d.height) return false;
const layer = d.layers[d.active_layer];
const new: Rgba = .opaqueRgb(color);
// Filling a region with the colour it already has would find the
// whole region and change nothing.
if (std.meta.eql(layer[@as(usize, y) * d.width + x], new)) return false;
var region = try fill.find(d.gpa, layer, d.width, d.height, x, y);
defer region.deinit(d.gpa);
d.history_ok = d.history.record(d.gpa, d.active_layer, layer, d.width, region.bounds);
var it = region.inside.iterator(.{});
while (it.next()) |i| layer[i] = new;
d.stale = d.stale.join(region.bounds);
return true;
}It also checks the colour first. Filling a region with the colour it already has would search the whole region and change nothing, and leave an undo step that does nothing.
errdefer in find matters here. If the queue cannot be allocated, the bit set that was already allocated is freed before the error goes back to the caller. A test checks this by failing each allocation in turn.
Checks
A closed shape with a box inside it. The fill finds the 9 pixels around the box and not the one pixel inside it:
test "a closed shape fills inside and stops at its walls" {
const p = picture(&.{
"#######",
"#.....#",
"#.###.#",
"#.#.#.#",
"#######",
});
var r = try find(testing.allocator, &p, 7, 5, 1, 1);
defer r.deinit(testing.allocator);
// The 9 dots around the inner box (5 + 2 + 2), not the one inside it.
try testing.expectEqual(@as(usize, 9), r.count);
try testing.expect(!r.inside.isSet(3 * 7 + 3));
try testing.expectEqual(Rect{ .x0 = 1, .y0 = 1, .x1 = 6, .y1 = 4 }, r.bounds);
}The diagonal gap:
test "four neighbours do not leak through a diagonal gap" {
const p = picture(&.{
".#",
"#.",
});
var r = try find(testing.allocator, &p, 2, 2, 0, 0);
defer r.deinit(testing.allocator);
try testing.expectEqual(@as(usize, 1), r.count);
}A whole empty 640 by 400 layer, the case recursion cannot do:
test "a whole empty 640 by 400 image fills without recursion" {
const gpa = testing.allocator;
const p = try gpa.alloc(Rgba, 640 * 400);
defer gpa.free(p);
@memset(p, .transparent);
var r = try find(gpa, p, 640, 400, 320, 200);
defer r.deinit(gpa);
try testing.expectEqual(@as(usize, 640 * 400), r.count);
try testing.expectEqual(Rect{ .x0 = 0, .y0 = 0, .x1 = 640, .y1 = 400 }, r.bounds);
}Explain before reading the answer
A queue takes from the front. A stack takes from the back.
If find took the newest pixel instead of the oldest, would it still find the same region?
Yes. It would visit the pixels in a different order, going deep in one direction before coming back, but every pixel it can reach is still reached exactly once. The region is the same. Only the order of the visits changes.