Canvas flood fill not filling to edge


Answers

Canvas - floodfill leaves white pixels at edges

Yes, the "white" spots left out aren't actually white as there's a tiny gradient going on between white and black. Try giving it some leeway around these lines:

 if ((r <= curColor.r + 10 && r >= curColor.r - 10)  && (r >= curColor.g - 10 && r <= curColor.g + 10) && (b >= curColor.b - 10 && b <= curColor.b + 10)) {
        return false;
    }

You can modify the 10 factor until it looks good. Just tweak it until it's okay. (Might be bad code , I just woke up but you should get the picture :D )

You could also preprocess the image in a separate buffer and reduce the number of colors. That way it's easier to fill the beginning of gradients, thus reducing or elimitating the undesired effect you are describing.

Question

I am using a flood fill algorithm to fill in circles drawn on the canvas. The issue I am having is that the algorithm isn't filling right up to the edge of the circle.

Here is the algorithm based on this blog post:

function paintLocation(startX, startY, r, g, b) {
    var colorLayer = context1.getImageData(0, 0, canvasWidth, canvasHeight);
    pixelPos = (startY * canvasWidth + startX) * 4;

    startR = colorLayer.data[pixelPos];
    startG = colorLayer.data[pixelPos + 1];
    startB = colorLayer.data[pixelPos + 2];

    var pixelStack = [
        [startX, startY]
    ];

    var drawingBoundTop = 0;
    while (pixelStack.length) {
        var newPos, x, y, pixelPos, reachLeft, reachRight;
        newPos = pixelStack.pop();
        x = newPos[0];
        y = newPos[1];

        pixelPos = (y * canvasWidth + x) * 4;
        while (y-- >= drawingBoundTop && matchStartColor(colorLayer, pixelPos, startR, startG, startB)) {
            pixelPos -= canvasWidth * 4;
        }
        pixelPos += canvasWidth * 4;
        ++y;
        reachLeft = false;
        reachRight = false;
        while (y++ < canvasHeight - 1 && matchStartColor(colorLayer, pixelPos, startR, startG, startB)) {
            colorPixel(colorLayer, pixelPos, r, g, b);

            if (x > 0) {
                if (matchStartColor(colorLayer, pixelPos - 4, startR, startG, startB)) {
                    if (!reachLeft) {
                        pixelStack.push([x - 1, y]);
                        reachLeft = true;
                    }
                } else if (reachLeft) {
                    reachLeft = false;
                }
            }

            if (x < canvasWidth - 1) {
                if (matchStartColor(colorLayer, pixelPos + 4, startR, startG, startB)) {
                    if (!reachRight) {
                        pixelStack.push([x + 1, y]);
                        reachRight = true;
                    }
                } else if (reachRight) {
                    reachRight = false;
                }
            }

            pixelPos += canvasWidth * 4;
        }
    }
    context1.putImageData(colorLayer, 0, 0);
}

Please see the JSFiddle or the below image to see what I mean. Clicking inside any circles will change the colour between yellow and black (the issue is far more visible with black).

I've read that the issue could be something to do with the anti-aliasing and I have tried turning it off with context1.imageSmoothingEnabled = true; but it didn't make a difference.

I have also tried changing my matchStartColour function as per this question but that doesn't help.

function matchStartColor(colorLayer, pixelPos, startR, startG, startB) {
    var r = colorLayer.data[pixelPos];
    var g = colorLayer.data[pixelPos + 1];
    var b = colorLayer.data[pixelPos + 2];

    return (r == startR && g == startG && b == startB);
}

I think it might have something to do with the fact that the circles have no fill colour and the background of the canvas isn't white but it is transparent black. I have tried changing the canvas background to white but that also didn't help.




I suggest two changes:

  1. Blend pixel & fill color instead of hard override
  2. Restrict fill area based on intensity gradient changes instead of simple threshold

Filling in horizontal and vertical direction until the sign of the intensity gradient flips from either + to - OR - to + lets us fill the whole area including 'half' of the black border. By inspecting the gradient we just make sure not to overstep the intensity minimum and thus avoid filling a neighboring area.

Have a look at the following demo:

// Get pixel intensity:
function getIntensity(data, i) {
  return data[i] + data[i + 1] + data[i + 2];
}

// Set pixel color:
function setColor(data, i, r, g, b) {
  data[i] &= r;
  data[i + 1] &= g;
  data[i + 2] &= b;
}

// Fill a horizontal line:
function fill(x, y, data, width, r, g, b) {
  var i_start = y * (width << 2);
  var i = i_start + (x << 2);
  var i_end = i_start + (width << 2);
  var i_intensity = getIntensity(data, i);

  // Horizontal line to the right:
  var prev_gradient = 0;
  var prev_intensity = i_intensity;
  for (var j = i; j < i_end; j += 4) {
    var intensity = getIntensity(data, j);
    gradient = intensity - prev_intensity;
    prev_intensity = intensity;
    if ((prev_gradient > 0 && gradient < 0) || (prev_gradient < 0 && gradient > 0)) break;
    if (gradient != 0) prev_gradient = gradient;

    setColor(data, j, 255, 0, 0);
  }

  // Horizontal line to the left:
  prev_gradient = 0;
  prev_intensity = i_intensity;
  for (var j = i - 4; j > i_start; j -= 4) {
    var intensity = getIntensity(data, j);
    gradient = intensity - prev_intensity;
    prev_intensity = intensity;
    if ((prev_gradient > 0 && gradient < 0) || (prev_gradient < 0 && gradient > 0)) break;
    if (gradient != 0) prev_gradient = gradient;

    setColor(data, j, 255, 0, 0);
  }
}

// Demo canvas:
var canvas = document.getElementById('canvas');
var context = canvas.getContext('2d');

// Fill horizontal line on click:
canvas.addEventListener('mousedown', event => {
  var rect = canvas.getBoundingClientRect();
  var x = event.clientX - rect.left | 0;
  var y = event.clientY - rect.top | 0;

  var imageData = context.getImageData(0, 0, canvas.width, canvas.height);
  fill(x, y, imageData.data, imageData.width);
  context.putImageData(imageData, 0, 0);
});

// Load a sample image:
var image = new Image();
image.addEventListener('load', event => {
  context.drawImage(event.target, 0, 0, canvas.width, canvas.height);
});
image.src = 'data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAsAAAACCAIAAAABwbG5AAAAA3NCSVQICAjb4U/gAAAAGXRFWHRTb2Z0d2FyZQBnbm9tZS1zY3JlZW5zaG907wO/PgAAACZJREFUCJlj+I8Kbt68mZeXd/PmTbgIw38MsG/fvoKCgqdPn0K4ACAfPGrloJp1AAAAAElFTkSuQmCC';
<canvas id="canvas"></canvas>

You can improve the performance by tracing only one color channel instead of summing all three for your getIntensity function.

Also, you would need to deal with 'clearing' an already filled area before filling it again with another color, due to the blending mode.

You could e. g. keep a single-channel grayscale image data array of the background image in memory and use it as the source image for your fill algorithm.

It might be even more performant to (manually or automatically) transform all your grayscale images to 1-bit outlines with binary boundaries and use them as the source for your floodfill algorithm, blending the result smoothly with the grayscale image.




In Progress...

Please expect evolution here, especially where diagrams and code can improve the answer. The work takes time.

Hopefully it will only involve one more edit, when the solution is complete.

----------

There are several near solutions. My implementation will degrade gracefully, so I'm using more than one, but I'll try to keep the components separate here, in order to help others more; some people may only want one part.

Solution 1 (for me only a stop-gap)

Compromise on vector-only solution, with a raster of just the back

I don't want to rely on this but it is a great stop-gap that looks perfect.

It isn't a final answer because it's hard to predict all the consequences of rasterisation for different display devices. I hate early rasters. I can try a screen, and a laser cutter. Without giving too much irrelevant detail about my applications, vectors almost always feel more correct for the things I find myself doing.

One of the things a friend is learning is the use of a laser cutter for instance, and I am tying it into my work. I have yet to investigate how it rasterises.

< EDITME For an illustration of roughly what this looks like but entirely with the vector graphics that closer to my first language. I will reuse the one I posted earlier. It isn't perfect; you'll still see red because I've not backed them with fully white silhouettes; I've backed white pieces (in black) with black pieces (in white) and I've backed black pieces (top layer in black again) with white pieces (bottom layer in white again). These are almost complements -- but not quite -- in most browsers, depending on your font.

<?xml version="1.0" standalone="no"?><svg xmlns:xlink="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg" width="440" height="440" style="font-size: 34px;"><defs><style type="text/css">.large{fill:#700;}.small{fill:#eee;}</style></defs><rect x="0" y="0" width="440" height="440" fill="white"/><rect x="0" y="20" width="20" height="20" class="small"/><rect x="20" y="0" width="20" height="20" class="small"/><rect x="20" y="40" width="20" height="20" class="small"/><rect x="40" y="20" width="20" height="20" class="small"/><rect x="60" y="0" width="20" height="20" class="small"/><rect x="60" y="40" width="20" height="20" class="small"/><rect x="80" y="20" width="20" height="20" class="small"/><rect x="100" y="0" width="20" height="20" class="small"/><rect x="100" y="40" width="20" height="20" class="small"/><rect x="120" y="20" width="20" height="20" class="small"/><rect x="140" y="0" width="20" height="20" class="small"/><rect x="140" y="40" width="20" height="20" class="small"/><rect x="160" y="20" width="20" height="20" class="small"/><rect x="180" y="0" width="20" height="20" class="small"/><rect x="180" y="40" width="20" height="20" class="small"/><rect x="200" y="20" width="20" height="20" class="small"/><rect x="220" y="0" width="20" height="20" class="small"/><rect x="220" y="40" width="20" height="20" class="small"/><rect x="240" y="20" width="20" height="20" class="small"/><rect x="260" y="0" width="20" height="20" class="small"/><rect x="260" y="40" width="20" height="20" class="small"/><rect x="280" y="20" width="20" height="20" class="small"/><rect x="300" y="0" width="20" height="20" class="small"/><rect x="300" y="40" width="20" height="20" class="small"/><rect x="320" y="20" width="20" height="20" class="small"/><rect x="340" y="0" width="20" height="20" class="small"/><rect x="340" y="40" width="20" height="20" class="small"/><rect x="360" y="20" width="20" height="20" class="small"/><rect x="380" y="0" width="20" height="20" class="small"/><rect x="380" y="40" width="20" height="20" class="small"/><rect x="400" y="20" width="20" height="20" class="small"/><rect x="420" y="0" width="20" height="20" class="small"/><rect x="420" y="40" width="20" height="20" class="small"/><rect x="0" y="20" width="20" height="20" class="small"/><rect x="0" y="60" width="20" height="20" class="small"/><rect x="0" y="100" width="20" height="20" class="small"/><rect x="0" y="140" width="20" height="20" class="small"/><rect x="0" y="180" width="20" height="20" class="small"/><rect x="0" y="220" width="20" height="20" class="small"/><rect x="0" y="260" width="20" height="20" class="small"/><rect x="0" y="300" width="20" height="20" class="small"/><rect x="0" y="340" width="20" height="20" class="small"/><rect x="20" y="0" width="20" height="20" class="small"/><rect x="20" y="40" width="20" height="20" class="small"/><rect x="20" y="80" width="20" height="20" class="small"/><rect x="20" y="120" width="20" height="20" class="small"/><rect x="20" y="160" width="20" height="20" class="small"/><rect x="20" y="200" width="20" height="20" class="small"/><rect x="20" y="240" width="20" height="20" class="small"/><rect x="20" y="280" width="20" height="20" class="small"/><rect x="20" y="320" width="20" height="20" class="small"/><rect x="20" y="360" width="20" height="20" class="small"/><rect x="40" y="20" width="20" height="20" class="small"/><rect x="40" y="60" width="20" height="20" class="small"/><rect x="40" y="100" width="20" height="20" class="small"/><rect x="40" y="140" width="20" height="20" class="small"/><rect x="40" y="180" width="20" height="20" class="small"/><rect x="40" y="220" width="20" height="20" class="small"/><rect x="40" y="260" width="20" height="20" class="small"/><rect x="40" y="300" width="20" height="20" class="small"/><rect x="40" y="340" width="20" height="20" class="small"/><rect x="380" y="0" width="20" height="20" class="small"/><rect x="380" y="40" width="20" height="20" class="small"/><rect x="380" y="80" width="20" height="20" class="small"/><rect x="380" y="120" width="20" height="20" class="small"/><rect x="380" y="160" width="20" height="20" class="small"/><rect x="380" y="200" width="20" height="20" class="small"/><rect x="380" y="240" width="20" height="20" class="small"/><rect x="380" y="280" width="20" height="20" class="small"/><rect x="380" y="320" width="20" height="20" class="small"/><rect x="380" y="360" width="20" height="20" class="small"/><rect x="400" y="20" width="20" height="20" class="small"/><rect x="400" y="60" width="20" height="20" class="small"/><rect x="400" y="100" width="20" height="20" class="small"/><rect x="400" y="140" width="20" height="20" class="small"/><rect x="400" y="180" width="20" height="20" class="small"/><rect x="400" y="220" width="20" height="20" class="small"/><rect x="400" y="260" width="20" height="20" class="small"/><rect x="400" y="300" width="20" height="20" class="small"/><rect x="400" y="340" width="20" height="20" class="small"/><rect x="420" y="0" width="20" height="20" class="small"/><rect x="420" y="40" width="20" height="20" class="small"/><rect x="420" y="80" width="20" height="20" class="small"/><rect x="420" y="120" width="20" height="20" class="small"/><rect x="420" y="160" width="20" height="20" class="small"/><rect x="420" y="200" width="20" height="20" class="small"/><rect x="420" y="240" width="20" height="20" class="small"/><rect x="420" y="280" width="20" height="20" class="small"/><rect x="420" y="320" width="20" height="20" class="small"/><rect x="420" y="360" width="20" height="20" class="small"/><rect x="0" y="380" width="20" height="20" class="small"/><rect x="0" y="420" width="20" height="20" class="small"/><rect x="20" y="400" width="20" height="20" class="small"/><rect x="40" y="380" width="20" height="20" class="small"/><rect x="40" y="420" width="20" height="20" class="small"/><rect x="60" y="400" width="20" height="20" class="small"/><rect x="80" y="380" width="20" height="20" class="small"/><rect x="80" y="420" width="20" height="20" class="small"/><rect x="100" y="400" width="20" height="20" class="small"/><rect x="120" y="380" width="20" height="20" class="small"/><rect x="120" y="420" width="20" height="20" class="small"/><rect x="140" y="400" width="20" height="20" class="small"/><rect x="160" y="380" width="20" height="20" class="small"/><rect x="160" y="420" width="20" height="20" class="small"/><rect x="180" y="400" width="20" height="20" class="small"/><rect x="200" y="380" width="20" height="20" class="small"/><rect x="200" y="420" width="20" height="20" class="small"/><rect x="220" y="400" width="20" height="20" class="small"/><rect x="240" y="380" width="20" height="20" class="small"/><rect x="240" y="420" width="20" height="20" class="small"/><rect x="260" y="400" width="20" height="20" class="small"/><rect x="280" y="380" width="20" height="20" class="small"/><rect x="280" y="420" width="20" height="20" class="small"/><rect x="300" y="400" width="20" height="20" class="small"/><rect x="320" y="380" width="20" height="20" class="small"/><rect x="320" y="420" width="20" height="20" class="small"/><rect x="340" y="400" width="20" height="20" class="small"/><rect x="360" y="380" width="20" height="20" class="small"/><rect x="360" y="420" width="20" height="20" class="small"/><rect x="380" y="400" width="20" height="20" class="small"/><rect x="400" y="380" width="20" height="20" class="small"/><rect x="400" y="420" width="20" height="20" class="small"/><rect x="420" y="400" width="20" height="20" class="small"/><rect x="60" y="100" width="40" height="40" class="large"/><rect x="60" y="180" width="40" height="40" class="large"/><rect x="60" y="260" width="40" height="40" class="large"/><rect x="60" y="340" width="40" height="40" class="large"/><rect x="100" y="60" width="40" height="40" class="large"/><rect x="100" y="140" width="40" height="40" class="large"/><rect x="100" y="220" width="40" height="40" class="large"/><rect x="100" y="300" width="40" height="40" class="large"/><rect x="140" y="100" width="40" height="40" class="large"/><rect x="140" y="180" width="40" height="40" class="large"/><rect x="140" y="260" width="40" height="40" class="large"/><rect x="140" y="340" width="40" height="40" class="large"/><rect x="180" y="60" width="40" height="40" class="large"/><rect x="180" y="140" width="40" height="40" class="large"/><rect x="180" y="220" width="40" height="40" class="large"/><rect x="180" y="300" width="40" height="40" class="large"/><rect x="220" y="100" width="40" height="40" class="large"/><rect x="220" y="180" width="40" height="40" class="large"/><rect x="220" y="260" width="40" height="40" class="large"/><rect x="220" y="340" width="40" height="40" class="large"/><rect x="260" y="60" width="40" height="40" class="large"/><rect x="260" y="140" width="40" height="40" class="large"/><rect x="260" y="220" width="40" height="40" class="large"/><rect x="260" y="300" width="40" height="40" class="large"/><rect x="300" y="100" width="40" height="40" class="large"/><rect x="300" y="180" width="40" height="40" class="large"/><rect x="300" y="260" width="40" height="40" class="large"/><rect x="300" y="340" width="40" height="40" class="large"/><rect x="340" y="60" width="40" height="40" class="large"/><rect x="340" y="140" width="40" height="40" class="large"/><rect x="340" y="220" width="40" height="40" class="large"/><rect x="340" y="300" width="40" height="40" class="large"/><rect x="60" y="60" width="320" height="320" style="fill:none; stroke-width:1; stroke:#000;"/><text x="240" y="94" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="200" y="94" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="80" y="94" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="360" y="94" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="160" y="94" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="280" y="94" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="320" y="94" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="120" y="94" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="80" y="134" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="120" y="134" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="160" y="134" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="200" y="134" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="240" y="134" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="280" y="134" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="320" y="134" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="360" y="134" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="240" y="374" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="200" y="374" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="80" y="374" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="360" y="374" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="160" y="374" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="280" y="374" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="320" y="374" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="120" y="374" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="80" y="334" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="120" y="334" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="160" y="334" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="200" y="334" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="240" y="334" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="280" y="334" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="320" y="334" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="360" y="334" stroke-width="0.3" stroke="white" text-anchor="middle" fill="white"></text><text x="240" y="374" text-anchor="middle" fill="black"></text><text x="200" y="374" text-anchor="middle" fill="black"></text><text x="80" y="374" text-anchor="middle" fill="black"></text><text x="360" y="374" text-anchor="middle" fill="black"></text><text x="160" y="374" text-anchor="middle" fill="black"></text><text x="280" y="374" text-anchor="middle" fill="black"></text><text x="320" y="374" text-anchor="middle" fill="black"></text><text x="120" y="374" text-anchor="middle" fill="black"></text><text x="80" y="334" text-anchor="middle" fill="black"></text><text x="120" y="334" text-anchor="middle" fill="black"></text><text x="160" y="334" text-anchor="middle" fill="black"></text><text x="200" y="334" text-anchor="middle" fill="black"></text><text x="240" y="334" text-anchor="middle" fill="black"></text><text x="280" y="334" text-anchor="middle" fill="black"></text><text x="320" y="334" text-anchor="middle" fill="black"></text><text x="360" y="334" text-anchor="middle" fill="black"></text><text x="240" y="94" text-anchor="middle" fill="black"></text><text x="200" y="94" text-anchor="middle" fill="black"></text><text x="80" y="94" text-anchor="middle" fill="black"></text><text x="360" y="94" text-anchor="middle" fill="black"></text><text x="160" y="94" text-anchor="middle" fill="black"></text><text x="280" y="94" text-anchor="middle" fill="black"></text><text x="320" y="94" text-anchor="middle" fill="black"></text><text x="120" y="94" text-anchor="middle" fill="black"></text><text x="80" y="134" text-anchor="middle" fill="black"></text><text x="120" y="134" text-anchor="middle" fill="black"></text><text x="160" y="134" text-anchor="middle" fill="black"></text><text x="200" y="134" text-anchor="middle" fill="black"></text><text x="240" y="134" text-anchor="middle" fill="black"></text><text x="280" y="134" text-anchor="middle" fill="black"></text><text x="320" y="134" text-anchor="middle" fill="black"></text><text x="360" y="134" text-anchor="middle" fill="black"></text></svg>

EDITME >

Solution 2:

2A. Require download of just one specially designed SVG font that makes a clear board position using fill and stroke effects to distinguish the pieces

Done and my newly home-made font looks good but not yet as good as the built in ones

That allows me to retain the Unicode characters so that a user can copy the chess position to a text editor, and other niceties.

It compromises file size, but not by much, especially if I design a font of my own that only includes chess pieces.

It compromises because I actually quite like the chess characters in most built-in fonts, and I would also like to give the user a choice of all fonts, including mine.

It compromises on cross-browser support; of all my browsers, only Safari understands SVG fonts, surprisingly enough. BUT they excite me and I won't be a part of that heel-dragging problem, so I'm including them in my implementation just to learn.

It's a tiny step from SVG to SVG fonts anyway.

2B. Also make the pieces look distinct when typed into a text editor all in a black font colour. (So Unicode 9812 to 9817 are white pieces while 9818 to 9823 are black.)

Current delay: Offsetting paths -- which seems to be a theme in every job I do! -- is necessary for making a really good looking font of my own, and I'm wrapped up in this fun mathematical puzzle at the moment.

This part is less relevant to my original question, but will be very helpful for questions other people are asking on Stack Exchange; I will be answering them in their own place, but I will still include links here for anyone interested in path offsetting; the subjects are closely related.

Solution 3: Compromise on using no external code

Opentype.js may or may not help me with inspecting the browser's internal fonts, but I'm not sure yet. This part of the answer is where I hope to find a shortcut. I want the outermost path of a font that I did not create or download; hopefully it is somehow available through an API, and this is the part I am seeking help on.

I can implement my own, I want to and am now very far along with doing so. But I would still like to access the browser's ability to provide such data, and then fall back to my own code.





Tags