javascript - Canvas flood fill not filling to edge

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.

Answer 1

Use flood fill to create a Mask

I just happened to do a floodFill the other day that addresses the problem of antialiased edges.

Rather than paint to the canvas directly, I paint to a byte array that is then used to create a mask. The mask allows for the alpha values to be set.

The fill can have a tolerance and a toleranceFade that control how it deals with colours that approch the tolerance value.

When pixel's difference between the start colour and tolerance are greater than (tolerance - toleranceFade) I set the alpha for that pixel to 255 - ((differance - (tolerance - toleranceFade)) / toleranceFade) * 255 which creates a nice smooth blend at the edges of lines. Though it does not work for all situations for high contrast situations it is an effective solution.

The example below shows the results of with and without the toleranceFade. The blue is without the toleranceFade, the red is with the tolerance set at 190 and the toleranceFade of 90.

You will have to play around with the setting to get the best results for your needs.

function showExample(){
    var canvas = document.createElement("canvas");
    canvas.width = 200;
    canvas.height = 200;
    var ctx = canvas.getContext("2d");
    document.body.appendChild(canvas);
    ctx.fillStyle = "white"
    ctx.fillRect(0,0,canvas.width,canvas.height)
    ctx.lineWidth = 4;
    ctx.strokeStyle = "black"
    ctx.beginPath();
    ctx.arc(100,100,90,0,Math.PI * 2);
    ctx.arc(120,100,60,0,Math.PI * 2);
    ctx.stroke();
    ctx.fillStyle = "blue";
    floodFill.fill(100,100,1,ctx)
    ctx.fillStyle = "red";
    floodFill.fill(40,100,190,ctx,null,null,90)
}

// FloodFill2D from https://github.com/blindman67/FloodFill2D
var floodFill = (function(){
    "use strict";
    const extent = {
        top : 0,
        left : 0,
        bottom : 0,
        right : 0,        
    }
    var keepMask = false; // if true then a mask of the filled area is returned as a canvas image
    var extentOnly = false;  // if true then the extent of the fill is returned
    var copyPixels = false; // if true then creating a copy of filled pixels
    var cutPixels = false;  // if true and copyPixels true then filled pixels are removed
    var useBoundingColor = false; // Set the colour to fill up to. Will not fill over this colour
    var useCompareColor = false; // Rather than get the pixel at posX,posY use the compareColours
    var red, green, blue, alpha; // compare colours if 
    var canvas,ctx;    
    function floodFill (posX, posY, tolerance, context2D, diagonal, area, toleranceFade) {
        var w, h, painted, x, y, ind, sr, sg, sb, sa,imgData, data, data32, RGBA32, stack, stackPos, lookLeft, lookRight, i, colImgDat, differance, checkColour;
        toleranceFade = toleranceFade !== undefined && toleranceFade !== null ? toleranceFade : 0;
        diagonal = diagonal !== undefined && diagonal !== null ? diagonal : false;
        area = area !== undefined && area !== null ? area : {};
        area.x = area.x !== undefined ? area.x : 0;
        area.y = area.y !== undefined ? area.y : 0;
        area.w = area.w !== undefined ? area.w : context2D.canvas.width - area.x;
        area.h = area.h !== undefined ? area.h : context2D.canvas.height - area.y;
        // vet area is on the canvas.
        if(area.x < 0){
            area.w = area.x + area.w;
            area.x = 0;
        }
        if(area.y < 0){
            area.h = area.y + area.h;
            area.y = 0;
        }
        if(area.x >= context2D.canvas.width || area.y >= context2D.canvas.height){
            return false;
        }
        if(area.x + area.w > context2D.canvas.width){
            area.w = context2D.canvas.width - area.x;
        }
        if(area.y + area.h > context2D.canvas.height){
            area.h = context2D.canvas.height - area.y;
        }
        if(area.w <= 0 || area.h <= 0){
            return false;
        }    
        w = area.w;   // width and height
        h = area.h;
        x = posX - area.x;   
        y = posY - area.y;    
        if(extentOnly){
            extent.left = x; // set up extent
            extent.right = x;
            extent.top = y;
            extent.bottom = y;
        }
        
        if(x < 0 || y < 0 || x >= w || y >= h){
            return false;  // fill start outside area. Don't do anything
        }
        if(tolerance === 255 && toleranceFade === 0 && ! keepMask){  // fill all 
            if(extentOnly){
                extent.left = area.x; // set up extent
                extent.right = area.x + w;
                extent.top = area.y;
                extent.bottom = area.y + h;
            }
            context2D.fillRect(area.x,area.y,w,h);
            return true;
        }
        if(toleranceFade > 0){   // add one if on to get correct number of steps
            toleranceFade += 1;
        }


        imgData = context2D.getImageData(area.x,area.y,area.w,area.h);
        data = imgData.data; // image data to fill;
        data32 = new Uint32Array(data.buffer);
        painted = new Uint8ClampedArray(w*h);  // byte array to mark painted area;
        function checkColourAll(ind){
            if( ind < 0 || painted[ind] > 0){  // test bounds
                return false;
            }
            var ind4 = ind << 2;  // get index of pixel           
            if((differance = Math.max(        // get the max channel difference;
                Math.abs(sr - data[ind4++]),
                Math.abs(sg - data[ind4++]),
                Math.abs(sb - data[ind4++]),                
                Math.abs(sa - data[ind4++])
                )) > tolerance){    
                return false;
            }        
            return true
        }         
        // check to bounding colour
        function checkColourBound(ind){
            if( ind < 0 || painted[ind] > 0){  // test bounds
                return false;
            }
            var ind4 = ind << 2;  // get index of pixel
            differance = 0;
            if(sr === data[ind4] && sg === data[ind4 + 1] && sb === data[ind4 + 2] && sa === data[ind4 + 3]){
                return false
            }
            return true
        }         
        // this function checks the colour of only selected channels
        function checkColourLimited(ind){ // check only colour channels that are not null
            var dr,dg,db,da;
            if( ind < 0 || painted[ind] > 0){  // test bounds
                return false;
            }
            var ind4 = ind << 2;  // get index of pixel
            dr = dg = db = da = 0;
            if(sr !== null && (dr = Math.abs(sr - data[ind4])) > tolerance){
                return false;
            }
            if(sg !== null && (dg = Math.abs(sg - data[ind4 + 1])) > tolerance){
                return false;
            }
            if(sb !== null && (db = Math.abs(sb - data[ind4 + 2])) > tolerance){
                return false;
            }
            if(sa !== null && (da = Math.abs(sa - data[ind4 + 3])) > tolerance){
                return false;
            }
            diferance = Math.max(dr, dg, db, da);
            return true
        }         
        // set which function to check colour with
        checkColour = checkColourAll;
        if(useBoundingColor){
            sr = red;
            sg = green;
            sb = blue;
            if(alpha === null){
                ind = (y * w + x) << 2;  // get the starting pixel index
                sa = data[ind + 3];                     
            }else{
                sa = alpha;            
            }
            checkColour = checkColourBound;
            useBoundingColor = false;
        }else if(useCompareColor){
            sr = red;
            sg = green;
            sb = blue;
            sa = alpha;
            if(red === null || blue === null || green === null || alpha === null){
                checkColour = checkColourLimited;
            }
            useCompareColor = false;            
        }else{
            ind = (y * w + x) << 2;  // get the starting pixel index
            sr = data[ind];        // get the start colour that we will use tolerance against.
            sg = data[ind + 1];
            sb = data[ind + 2];
            sa = data[ind + 3];     
        }
        stack = [];          // paint stack to find new pixels to paint
        lookLeft = false;    // test directions
        lookRight = false;

        stackPos = 0;
        stack[stackPos++] = x;
        stack[stackPos++] = y;
        while (stackPos > 0) {   // do while pixels on the stack
            y = stack[--stackPos];  // get the pixel y
            x = stack[--stackPos];  // get the pixel x
            ind = x + y * w;
            while (checkColour(ind - w)) {  // find the top most pixel within tollerance;
                y -= 1;
                ind -= w;
            }
            //checkTop left and right if allowing diagonal painting
            if(diagonal && y > 0){
                if(x > 0 && !checkColour(ind - 1) && checkColour(ind - w - 1)){
                    stack[stackPos++] = x - 1;
                    stack[stackPos++] = y - 1;
                }
                if(x < w - 1 && !checkColour(ind + 1) && checkColour(ind - w + 1)){
                    stack[stackPos++] = x + 1;
                    stack[stackPos++] = y - 1;
                }
            }
            lookLeft = false;  // set look directions
            lookRight = false; // only look is a pixel left or right was blocked
            while (checkColour(ind) && y < h) { // move down till no more room
                if(toleranceFade > 0 && differance >= tolerance-toleranceFade){
                    painted[ind] = 255 - (((differance - (tolerance - toleranceFade)) / toleranceFade) * 255);
                    painted[ind] = painted[ind] === 0 ? 1 : painted[ind]; // min value must be 1
                }else{
                    painted[ind] = 255; 
                }
                if(extentOnly){
                    extent.left   = x < extent.left   ? x : extent.left;    // Faster than using Math.min
                    extent.right  = x > extent.right  ? x : extent.right;   // Faster than using Math.min
                    extent.top    = y < extent.top    ? y : extent.top;     // Faster than using Math.max
                    extent.bottom = y > extent.bottom ? y : extent.bottom;  // Faster than using Math.max
                }
                if (checkColour(ind - 1) && x > 0) {  // check left is blocked
                    if (!lookLeft) {        
                        stack[stackPos++] = x - 1;
                        stack[stackPos++] = y;
                        lookLeft = true;
                    }
                } else if (lookLeft) {
                    lookLeft = false;
                }
                if (checkColour(ind + 1) && x < w -1) {  // check right is blocked
                    if (!lookRight) {
                        stack[stackPos++] = x + 1;
                        stack[stackPos++] = y;
                        lookRight = true;
                    }