Making HTML5 canvas floodfill efficient

Question

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.

Try pulling the `getImageData` and `putImageData` out of the loop. Get the entire image data to start, modify it, then write it all back instead of going through a read/write cycle for every pixel. — George, Jun 26 '13 at 19:55
Also, switched to createImageData as suggested here: http://stackoverflow.com/questions/4899799/whats-the-best-way-to-set-a-single-pixel-in-an-html5-canvas Still very slow, but slightly better. — Jack Guy, Jun 26 '13 at 20:28
Additional info needed: You say "I have mouse coordinate details for all the painting". Does that mean you can create a canvas path for any part of the painting that needs to be floodfilled? — markE, Jun 26 '13 at 21:21
After some thought, I can’t figure out how to get around the concurrency issues of floodfill. Consider the example when I’m just getting ready to close a circle and you issue a floodfill at the center of my incomplete circle. Since there is latency, The fill command may execute either before or after I complete my circle. If **before** then pixels outside my circle are filled. If **after** then no pixels outside my circle are filled. Any thoughts on resolving these race conditions? — markE, Jun 27 '13 at 04:01
I have a stack of commands. With a forEach, every command is executed until completion and then the stack proceeds to the next one. The floodfill begins when the iterator reaches it in the stack. That way no matter what additions to the drawing, the original fill is preserved. I'm considering using the floodfill algorithm to obtain the shape, and then converting the coordinates of the border into a continuous path to a shape that I can fill on the canvas. Any ideas on the practicality/how I might go about that? — Jack Guy, Jun 27 '13 at 04:20
there is an efficient and versatile image processing library for js [FILTER.js](https://github.com/foo123/FILTER.js) it will feature a fast floodfill plugin (using scanline algorithm) in next update (ps i'm author) — Nikos M., May 04 '15 at 11:46

score 2 · Accepted Answer · answered Nov 17 '14 at 20:49

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/

Making HTML5 canvas floodfill efficient

1 Answers1

Linked

Related