example-canvas-fill Faster floodfill

Faster floodfill

Open 99991 opened this issue 2 years ago • 1 comments

Here is a faster floodfill implementation. The main differences are:

This implementation does not create millions of string keys to remember which pixels have already been visited. That would be very slow.
Pixels are filled in cache-friendly order (scanlines).

To run:

Copy the following code into an HTML file.
Put an image file named airplane.png into the same directory.
Serve the files using some server, e.g. python -m http.server.
Visit the URL, e.g. http://127.0.0.1:8000
Click somewhere in the image to colorize it. You can also select different colors.

The largest area takes about 7 ms to flood fill on my laptop (after initial warmup).

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>Floodfill</title>
</head>
<body>
    <canvas id="canvas"></canvas>
    <img id="image" src="airplane.png" style="display: none;">
    <div>
        <div style="background-color: rgba(0, 255, 0, 1); width: 50px; height: 50px; display: inline-block;" onclick="setColor(this)"></div>
        <div style="background-color: rgba(255, 0, 0, 1); width: 50px; height: 50px; display: inline-block;" onclick="setColor(this)"></div>
        <div style="background-color: rgba(0, 0, 255, 1); width: 50px; height: 50px; display: inline-block;" onclick="setColor(this)"></div>
        <div style="background-color: rgba(255, 255, 0, 1); width: 50px; height: 50px; display: inline-block;" onclick="setColor(this)"></div>
        <div style="background-color: rgba(0, 255, 255, 1); width: 50px; height: 50px; display: inline-block;" onclick="setColor(this)"></div>
        <div style="background-color: rgba(255, 0, 255, 1); width: 50px; height: 50px; display: inline-block;" onclick="setColor(this)"></div>
    </div>
<script>
function floodfill(rgba, width, height, x, y, color){
    // Floodfill an RGBA image array of a given width and height
    // starting at (x, y) with a color.
    
    var visited = new Uint8Array(width * height);
    var queue = new Int32Array(2 * width * height);

    // Only non-black pixels can be visited
    for (var i = 0; i < width * height; i++){
        var r = rgba[i * 4 + 0];
        var g = rgba[i * 4 + 1];
        var b = rgba[i * 4 + 2];
        var a = rgba[i * 4 + 3];

        var isBlack = a > 100 && r + g + b == 0

        visited[i] = isBlack;
    }
    
    // Add initial pixel to queue
    var n = 0;
    queue[n++] = x;
    queue[n++] = y;
    
    // Mark initial pixel as visited
    var i = x + y * width;
    visited[i] = 1;
    rgba[i * 4 + 0] = color[0];
    rgba[i * 4 + 1] = color[1];
    rgba[i * 4 + 2] = color[2];
    rgba[i * 4 + 3] = 255;

    // While we have not processed all pixels yet
    while (n > 0){
        // Pop pixel from queue
        var y = queue[--n];
        var x = queue[--n];

        // Scan to the left
        var x1 = x;
        while (x1 > 0 && !visited[x1 - 1 + y * width]) x1--;

        // Scan to the right
        var x2 = x;
        while (x2 < width - 1 && !visited[x2 + 1 + y * width]) x2++;

        // Mark all pixels in scan line as visited
        for (var x = x1; x <= x2; x++){
            var i = x + y * width
            visited[i] = 1;
            rgba[i * 4 + 0] = color[0];
            rgba[i * 4 + 1] = color[1];
            rgba[i * 4 + 2] = color[2];
            rgba[i * 4 + 3] = 255;
        }

        // Add pixels above scan line to queue
        if (y + 1 < height){
            for (var x = x1; x <= x2; x++){
                var i = x + (y + 1) * width;
                if (!visited[i]){
                    visited[i] = 1;
                    queue[n++] = x;
                    queue[n++] = y + 1;
                }
            }
        }

        // Add pixels below scan line to queue
        if (y > 0){
            for (var x = x1; x <= x2; x++){
                var i = x + (y - 1) * width;
                if (!visited[i]){
                    visited[i] = 1;
                    queue[n++] = x;
                    queue[n++] = y - 1;
                }
            }
        }
    }
}

var canvas = document.getElementById('canvas');
var context = canvas.getContext('2d');
var image = document.getElementById('image');

image.onload = function(){
    canvas.width = image.width;
    canvas.height = image.height;

    context.drawImage(image, 0, 0);
}

var color = [0, 255, 0];

function setColor(element){
    color = element.style.backgroundColor.match(/\d+/g).map(Number);
}

canvas.onmousedown = function(e){
    var rect = canvas.getBoundingClientRect();
    var x = e.clientX - rect.left | 0;
    var y = e.clientY - rect.top | 0;

    var imageData = context.getImageData(0, 0, canvas.width, canvas.height);
    var rgba = imageData.data;

    var startTime = window.performance.now();

    floodfill(rgba, canvas.width, canvas.height, x, y, color);

    var elapsedTime = window.performance.now() - startTime;

    console.log('Time: ' + elapsedTime + ' ms');

    context.putImageData(imageData, 0, 0);
}
</script>
</body>
</html>

May 24 '23 14:05 99991

Whoa that is fast! I'll try that out on my full app (kidzfun.art) and see if there are any edge cases I run into.

May 29 '23 14:05 shaneosullivan

example-canvas-fill example-canvas-fill copied to clipboard

Faster floodfill

example-canvas-fill
example-canvas-fill copied to clipboard