CODEWITHSUNDEEP
javascriptperformancealgorithmhtml5-canvasflood-fill
Jack Guy
Jack Guy

Reputation: 8523

Making HTML5 canvas floodfill efficient

I'm creating a collaborative image drawing application using socket.io and canvas. By necessity, the canvas has to refresh fairly often, currently around every 50 milliseconds. I wanted to add a fill tool to the application, so I used my limited knowledge of flood-fill to create one. Because all of this data has to be transferred, I store every fill command as a simple object

{
    tool: 'fill',
    coordinate: {
        x: 5,
        y: 5
    }
    fillcolor: '#000'
}

Then each client's canvas runs the algorithm and fills using "getImageData" and "putImageData" for each individual pixel. Here's an (abbreviated) version of my implementation.

function floodfill (start,target_color,fill_color)
{
    var pixelStack = [start]; //the stack of pixels to check

    while (pixelStack.length > 0) 
    {
        var current = pixelStack[pixelStack.length-1]; //check the last pixel of the pixelstack
        pixelStack.pop(); //delete current from stack

        if (isSameColor(current)) //matches our target color
        {
            var mydat = ctx.createImageData(1,1);
            mydat.data = new Array();
            mydat.data[0] = hexToRGB(fill_color).r; //red
            mydat.data[1] = hexToRGB(fill_color).g; //green
            mydat.data[2] = hexToRGB(fill_color).b; //blue
            mydat.data[3] = 255;
            ctx.putImageData(mydat,current.x,current.y);

            pixelStack.push(bit(current.x+1,current.y)); //right
            pixelStack.push(bit(current.x-1,current.y)); //left
            pixelStack.push(bit(current.x,current.y+1)); //up
            pixelStack.push(bit(current.x,current.y-1)); //down
        }
    }

    function isSameColor (pixel)
    {
        var imgdat = ctx.getImageData(pixel.x,pixel.y,1,1).data;
        if (imgdat[0]== hexToRGB(target_color).r && imgdat[1]== hexToRGB(target_color).g, imgdat[2]== hexToRGB(target_color).b)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    function hexToRGB (hex)
    {
        var result = /^#?([a-f\d]{2})([a-f\d]{2})([a-f\d]{2})$/i.exec(hex);
        return result ? {
            r: parseInt(result[1], 16),
            g: parseInt(result[2], 16),
            b: parseInt(result[3], 16),
            rgb: parseInt(result[1], 16) + ", " + parseInt(result[2], 16) + ", " + parseInt(result[3], 16)
        } : null;
    }
}

Unfortunately, once the algorithm has been run canvas drawing is absurdly slow. Since I have mouse coordinate details for all the painting, I considering trying to use vectors to fill it, but my mathematical background isn't really strong enough to do it without help.

What's the slow part of my application? How can I fix it?

EDIT: As I mentioned in the comments, I've tried both using just one large putImageData (very slow), and using createImageData instead of getImageData (marginally faster).

EDIT2: Every paint brush stroke is stored as a series of x-y coordinates that are recorded when a user clicks and drags. However, they are not closed paths. Instead they are drawn as a series of lines, and when the user lifts the mouse, move-to's.

Code updated to reflect my current implementation.

Upvotes: 0

Views: 4075

Answers (1)

Aerik
Aerik

Reputation: 2317

I realize this is a very old question, but if you're still working on this, temporarily put in some code timing the various parts of your function to find where it's slowest. Definitely pull the calls to getimagedata and putimagedata out of the loop - only call each once for each "fill". Once you have the imagedata, get and set the colors of the pixels through it's underlying buffer, viewed as a Uint32Array.

See https://hacks.mozilla.org/2011/12/faster-canvas-pixel-manipulation-with-typed-arrays/

Upvotes: 2

Related Questions