How can I perform flood fill with HTML Canvas?
Solution 1:
To create a flood fill you need to be able to look at the pixels that are there already and check they aren't the color you started with so something like this.
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, [255, 0, 0, 255]);
function getPixel(imageData, x, y) {
if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
return [-1, -1, -1, -1]; // impossible color
} else {
const offset = (y * imageData.width + x) * 4;
return imageData.data.slice(offset, offset + 4);
}
}
function setPixel(imageData, x, y, color) {
const offset = (y * imageData.width + x) * 4;
imageData.data[offset + 0] = color[0];
imageData.data[offset + 1] = color[1];
imageData.data[offset + 2] = color[2];
imageData.data[offset + 3] = color[0];
}
function colorsMatch(a, b) {
return a[0] === b[0] && a[1] === b[1] && a[2] === b[2] && a[3] === b[3];
}
function floodFill(ctx, x, y, fillColor) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// get the color we're filling
const targetColor = getPixel(imageData, x, y);
// check we are actually filling a different color
if (!colorsMatch(targetColor, fillColor)) {
fillPixel(imageData, x, y, targetColor, fillColor);
// put the data back
ctx.putImageData(imageData, 0, 0);
}
}
function fillPixel(imageData, x, y, targetColor, fillColor) {
const currentColor = getPixel(imageData, x, y);
if (colorsMatch(currentColor, targetColor)) {
setPixel(imageData, x, y, fillColor);
fillPixel(imageData, x + 1, y, targetColor, fillColor);
fillPixel(imageData, x - 1, y, targetColor, fillColor);
fillPixel(imageData, x, y + 1, targetColor, fillColor);
fillPixel(imageData, x, y - 1, targetColor, fillColor);
}
}<canvas></canvas>There's at least 2 problems with this code though.
-
It's deeply recursive.
So you might run out of stack space
-
It's slow.
No idea if it's too slow but JavaScript in the browser is mostly single threaded so while this code is running the browser is frozen. For a large canvas that frozen time might make the page really slow and if it's frozen too long the browser will ask if the user wants to kill the page.
The solution to running out of stack space is to implement our own stack. For example instead of recursively calling fillPixel we could keep an array of positions we want to look at. We'd add the 4 positions to that array and then pop things off the array until it's empty
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, [255, 0, 0, 255]);
function getPixel(imageData, x, y) {
if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
return [-1, -1, -1, -1]; // impossible color
} else {
const offset = (y * imageData.width + x) * 4;
return imageData.data.slice(offset, offset + 4);
}
}
function setPixel(imageData, x, y, color) {
const offset = (y * imageData.width + x) * 4;
imageData.data[offset + 0] = color[0];
imageData.data[offset + 1] = color[1];
imageData.data[offset + 2] = color[2];
imageData.data[offset + 3] = color[0];
}
function colorsMatch(a, b) {
return a[0] === b[0] && a[1] === b[1] && a[2] === b[2] && a[3] === b[3];
}
function floodFill(ctx, x, y, fillColor) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// get the color we're filling
const targetColor = getPixel(imageData, x, y);
// check we are actually filling a different color
if (!colorsMatch(targetColor, fillColor)) {
const pixelsToCheck = [x, y];
while (pixelsToCheck.length > 0) {
const y = pixelsToCheck.pop();
const x = pixelsToCheck.pop();
const currentColor = getPixel(imageData, x, y);
if (colorsMatch(currentColor, targetColor)) {
setPixel(imageData, x, y, fillColor);
pixelsToCheck.push(x + 1, y);
pixelsToCheck.push(x - 1, y);
pixelsToCheck.push(x, y + 1);
pixelsToCheck.push(x, y - 1);
}
}
// put the data back
ctx.putImageData(imageData, 0, 0);
}
}<canvas></canvas>The solution to it being too slow is either to make it run a little at a time OR to move it to a worker. I think that's a little too much to show in the same answer though here's an example.
I tested the code above on a 4096x4096 canvas and it took 16 seconds to fill a blank canvas on my machine so yes it's arguably too slow but putting it in a worker brings new problems which is that the result will be asynchronous so even though the browser wouldn't freeze you'd probably want to prevent the user from doing something until it finishes.
Another issue is you'll see the lines are antialiased and so filling with a solid color fills close the the line but not all the way up to it. To fix that you can change colorsMatch to check for close enough but then you have a new problem that if targetColor and fillColor are also close enough it will keep trying to fill itself. You could solve that by making another array, one byte or one bit per pixel to track places you've ready checked.
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, [255, 0, 0, 255], 128);
function getPixel(imageData, x, y) {
if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
return [-1, -1, -1, -1]; // impossible color
} else {
const offset = (y * imageData.width + x) * 4;
return imageData.data.slice(offset, offset + 4);
}
}
function setPixel(imageData, x, y, color) {
const offset = (y * imageData.width + x) * 4;
imageData.data[offset + 0] = color[0];
imageData.data[offset + 1] = color[1];
imageData.data[offset + 2] = color[2];
imageData.data[offset + 3] = color[0];
}
function colorsMatch(a, b, rangeSq) {
const dr = a[0] - b[0];
const dg = a[1] - b[1];
const db = a[2] - b[2];
const da = a[3] - b[3];
return dr * dr + dg * dg + db * db + da * da < rangeSq;
}
function floodFill(ctx, x, y, fillColor, range = 1) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// flags for if we visited a pixel already
const visited = new Uint8Array(imageData.width, imageData.height);
// get the color we're filling
const targetColor = getPixel(imageData, x, y);
// check we are actually filling a different color
if (!colorsMatch(targetColor, fillColor)) {
const rangeSq = range * range;
const pixelsToCheck = [x, y];
while (pixelsToCheck.length > 0) {
const y = pixelsToCheck.pop();
const x = pixelsToCheck.pop();
const currentColor = getPixel(imageData, x, y);
if (!visited[y * imageData.width + x] &&
colorsMatch(currentColor, targetColor, rangeSq)) {
setPixel(imageData, x, y, fillColor);
visited[y * imageData.width + x] = 1; // mark we were here already
pixelsToCheck.push(x + 1, y);
pixelsToCheck.push(x - 1, y);
pixelsToCheck.push(x, y + 1);
pixelsToCheck.push(x, y - 1);
}
}
// put the data back
ctx.putImageData(imageData, 0, 0);
}
}<canvas></canvas>Note that this version of colorsMatch is kind of naive. It might be better to convert to HSV or something or maybe you want to weight by alpha. I don't know what a good metric is for matching colors.
Update
Another way to speed things up is of course to just optimize the code. Kaiido pointed out an obvious speedup which is to use a Uint32Array view on the pixels. That way looking up a pixel and setting a pixel there's just one 32bit value to read or write. Just that change makes it about 4x faster. It still takes 4 seconds to fill a 4096x4096 canvas though. There might be other optimizations like instead of calling getPixels make that inline but don't push a new pixel on our list of pixels to check if they are out of range. It might be 10% speed up (no idea) but won't make it fast enough to be an interactive speed.
There are other speedups like checking across a row at a time since rows are cache friendly and you can compute the offset to a row once and use that while checking the entire row whereas now for every pixel we have to compute the offset multiple times.
Those will complicate the algorithm so they are best left for you to figure out.
Let me also add, given the answer above freezes the browser while the fill is happening and that on a larger canvas that freeze could be too long, you can easily make the algorithm span over time using ES6 async/await. You need to choose how much work to give each segment of time. Choose too small and it will take a long time to fill. Choose too large and you'll get jank as the browser freezes.
Here's an example. Set ticksPerUpdate to speed up or slow down the fill rate
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(100, 145);
ctx.lineTo(110, 105);
ctx.lineTo(130, 125);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, 0xFF0000FF);
function getPixel(pixelData, x, y) {
if (x < 0 || y < 0 || x >= pixelData.width || y >= pixelData.height) {
return -1; // impossible color
} else {
return pixelData.data[y * pixelData.width + x];
}
}
async function floodFill(ctx, x, y, fillColor) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// make a Uint32Array view on the pixels so we can manipulate pixels
// one 32bit value at a time instead of as 4 bytes per pixel
const pixelData = {
width: imageData.width,
height: imageData.height,
data: new Uint32Array(imageData.data.buffer),
};
// get the color we're filling
const targetColor = getPixel(pixelData, x, y);
// check we are actually filling a different color
if (targetColor !== fillColor) {
const ticksPerUpdate = 50;
let tickCount = 0;
const pixelsToCheck = [x, y];
while (pixelsToCheck.length > 0) {
const y = pixelsToCheck.pop();
const x = pixelsToCheck.pop();
const currentColor = getPixel(pixelData, x, y);
if (currentColor === targetColor) {
pixelData.data[y * pixelData.width + x] = fillColor;
// put the data back
ctx.putImageData(imageData, 0, 0);
++tickCount;
if (tickCount % ticksPerUpdate === 0) {
await wait();
}
pixelsToCheck.push(x + 1, y);
pixelsToCheck.push(x - 1, y);
pixelsToCheck.push(x, y + 1);
pixelsToCheck.push(x, y - 1);
}
}
}
}
function wait(delay = 0) {
return new Promise((resolve) => {
setTimeout(resolve, delay);
});
}<canvas></canvas>update update
Instead of setTimeout which is throttled by the browser, you can abuse postMessage which is not
function makeExposedPromise() {
let resolve;
let reject;
const promise = new Promise((_resolve, _reject) => {
resolve = _resolve;
reject = _reject;
});
return { promise, resolve, reject };
}
const resolveFns = [];
window.addEventListener('message', (e) => {
const resolve = resolveFns.shift();
resolve();
});
function wait() {
const {resolve, promise} = makeExposedPromise();
resolveFns.push(resolve);
window.postMessage('');
return promise;
}
If you use that it there's less need to choose a number of operations. Also note: the slowest part is calling putImageData. The reason it's inside the loop above is only so we can see the progress. Move that to the end and it will run much faster
function makeExposedPromise() {
let resolve;
let reject;
const promise = new Promise((_resolve, _reject) => {
resolve = _resolve;
reject = _reject;
});
return { promise, resolve, reject };
}
const resolveFns = [];
window.addEventListener('message', (e) => {
const resolve = resolveFns.shift();
resolve();
});
function wait() {
const {resolve, promise} = makeExposedPromise();
resolveFns.push(resolve);
window.postMessage('');
return promise;
}
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(100, 145);
ctx.lineTo(110, 105);
ctx.lineTo(130, 125);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, 0xFF0000FF);
function getPixel(pixelData, x, y) {
if (x < 0 || y < 0 || x >= pixelData.width || y >= pixelData.height) {
return -1; // impossible color
} else {
return pixelData.data[y * pixelData.width + x];
}
}
async function floodFill(ctx, x, y, fillColor) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// make a Uint32Array view on the pixels so we can manipulate pixels
// one 32bit value at a time instead of as 4 bytes per pixel
const pixelData = {
width: imageData.width,
height: imageData.height,
data: new Uint32Array(imageData.data.buffer),
};
// get the color we're filling
const targetColor = getPixel(pixelData, x, y);
// check we are actually filling a different color
if (targetColor !== fillColor) {
const pixelsToCheck = [x, y];
while (pixelsToCheck.length > 0) {
const y = pixelsToCheck.pop();
const x = pixelsToCheck.pop();
const currentColor = getPixel(pixelData, x, y);
if (currentColor === targetColor) {
pixelData.data[y * pixelData.width + x] = fillColor;
await wait();
pixelsToCheck.push(x + 1, y);
pixelsToCheck.push(x - 1, y);
pixelsToCheck.push(x, y + 1);
pixelsToCheck.push(x, y - 1);
}
}
// put the data back
ctx.putImageData(imageData, 0, 0);
}
}<canvas></canvas>It's still better to choose a number of operations per call to wait
There are also faster algorithms. The issue with the one above is there is for every pixel that matches, 4 are added to the stack of things to pixels to check. That's lots of allocations and multiple checking. A faster way is to it by span.
For a given span, check as far left as you can, then as far right as you can, now fill that span. Then, check the pixels above and/or below the span you just found and add the spans you find to your stack. Pop the top span off, and try to expand it left and right. There's no need to check the pixels in the middle since you already checked them. Further, if this span was generated from one below then you don't need to check the pixels below the starting sub-span of this span since you know that area was already filled. Similarly if this pan was generated from one above then you don't need to check the pixels above the starting sub-span of this span for the same reason.
function main() {
const ctx = document.querySelector("canvas").getContext("2d");
ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(100, 145);
ctx.lineTo(110, 105);
ctx.lineTo(130, 125);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();
floodFill(ctx, 40, 50, 0xFF0000FF);
}
main();
function getPixel(pixelData, x, y) {
if (x < 0 || y < 0 || x >= pixelData.width || y >= pixelData.height) {
return -1; // impossible color
} else {
return pixelData.data[y * pixelData.width + x];
}
}
function floodFill(ctx, x, y, fillColor) {
// read the pixels in the canvas
const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
// make a Uint32Array view on the pixels so we can manipulate pixels
// one 32bit value at a time instead of as 4 bytes per pixel
const pixelData = {
width: imageData.width,
height: imageData.height,
data: new Uint32Array(imageData.data.buffer),
};
// get the color we're filling
const targetColor = getPixel(pixelData, x, y);
// check we are actually filling a different color
if (targetColor !== fillColor) {
const spansToCheck = [];
function addSpan(left, right, y, direction) {
spansToCheck.push({left, right, y, direction});
}
function checkSpan(left, right, y, direction) {
let inSpan = false;
let start;
let x;
for (x = left; x < right; ++x) {
const color = getPixel(pixelData, x, y);
if (color === targetColor) {
if (!inSpan) {
inSpan = true;
start = x;
}
} else {
if (inSpan) {
inSpan = false;
addSpan(start, x - 1, y, direction);
}
}
}
if (inSpan) {
inSpan = false;
addSpan(start, x - 1, y, direction);
}
}
addSpan(x, x, y, 0);
while (spansToCheck.length > 0) {
const {left, right, y, direction} = spansToCheck.pop();
// do left until we hit something, while we do this check above and below and add
let l = left;
for (;;) {
--l;
const color = getPixel(pixelData, l, y);
if (color !== targetColor) {
break;
}
}
++l
let r = right;
for (;;) {
++r;
const color = getPixel(pixelData, r, y);
if (color !== targetColor) {
break;
}
}
const lineOffset = y * pixelData.width;
pixelData.data.fill(fillColor, lineOffset + l, lineOffset + r);
if (direction <= 0) {
checkSpan(l, r, y - 1, -1);
} else {
checkSpan(l, left, y - 1, -1);
checkSpan(right, r, y - 1, -1);
}
if (direction >= 0) {
checkSpan(l, r, y + 1, +1);
} else {
checkSpan(l, left, y + 1, +1);
checkSpan(right, r, y + 1, +1);
}
}
// put the data back
ctx.putImageData(imageData, 0, 0);
}
}<canvas></canvas>Note: I didn't test this well, there might be an off by 1 error or other issue. I'm 99% sure I wrote the span method in 1993 for My Paint but don't remember if I have the source. But in any case, it's fast enough there's no need for wait
Solution 2:
Here's an implementation that I've been working on. It can get really slow if the replacement color is too close to the original color. It's quite a bit faster in Chrome than Firefox (I haven't tested it in any other browsers).
I also haven't done exhaustive testing yet, so there may be edge cases where it doesn't work.
function getPixel(pixelData, x, y) {
if (x < 0 || y < 0 || x >= pixelData.width || y >= pixelData.height) {
return NaN;
}
var pixels = pixelData.data;
var i = (y * pixelData.width + x) * 4;
return ((pixels[i + 0] & 0xFF) << 24) |
((pixels[i + 1] & 0xFF) << 16) |
((pixels[i + 2] & 0xFF) << 8) |
((pixels[i + 3] & 0xFF) << 0);
}
function setPixel(pixelData, x, y, color) {
var i = (y * pixelData.width + x) * 4;
var pixels = pixelData.data;
pixels[i + 0] = (color >>> 24) & 0xFF;
pixels[i + 1] = (color >>> 16) & 0xFF;
pixels[i + 2] = (color >>> 8) & 0xFF;
pixels[i + 3] = (color >>> 0) & 0xFF;
}
function diff(c1, c2) {
if (isNaN(c1) || isNaN(c2)) {
return Infinity;
}
var dr = ((c1 >>> 24) & 0xFF) - ((c2 >>> 24) & 0xFF);
var dg = ((c1 >>> 16) & 0xFF) - ((c2 >>> 16) & 0xFF);
var db = ((c1 >>> 8) & 0xFF) - ((c2 >>> 8) & 0xFF);
var da = ((c1 >>> 0) & 0xFF) - ((c2 >>> 0) & 0xFF);
return dr*dr + dg*dg + db*db + da*da;
}
function floodFill(canvas, x, y, replacementColor, delta) {
var current, w, e, stack, color, cx, cy;
var context = canvas.getContext("2d");
var pixelData = context.getImageData(0, 0, canvas.width, canvas.height);
var done = [];
for (var i = 0; i < canvas.width; i++) {
done[i] = [];
}
var targetColor = getPixel(pixelData, x, y);
delta *= delta;
stack = [ [x, y] ];
done[x][y] = true;
while ((current = stack.pop())) {
cx = current[0];
cy = current[1];
if (diff(getPixel(pixelData, cx, cy), targetColor) <= delta) {
setPixel(pixelData, cx, cy, replacementColor);
w = e = cx;
while (w > 0 && diff(getPixel(pixelData, w - 1, cy), targetColor) <= delta) {
--w;
if (done[w][cy]) break;
setPixel(pixelData, w, cy, replacementColor);
}
while (e < pixelData.width - 1 && diff(getPixel(pixelData, e + 1, cy), targetColor) <= delta) {
++e;
if (done[e][cy]) break;
setPixel(pixelData, e, cy, replacementColor);
}
for (cx = w; cx <= e; cx++) {
if (cy > 0) {
color = getPixel(pixelData, cx, cy - 1);
if (diff(color, targetColor) <= delta) {
if (!done[cx][cy - 1]) {
stack.push([cx, cy - 1]);
done[cx][cy - 1] = true;
}
}
}
if (cy < canvas.height - 1) {
color = getPixel(pixelData, cx, cy + 1);
if (diff(color, targetColor) <= delta) {
if (!done[cx][cy + 1]) {
stack.push([cx, cy + 1]);
done[cx][cy + 1] = true;
}
}
}
}
}
}
context.putImageData(pixelData, 0, 0, 0, 0, canvas.width, canvas.height);
}