views:

226

answers:

2

Has anyone implemented a flood fill algorithm in javascript for use with HTML Canvas?

My requirements are simple: flood with a single color starting from a single point, where the boundary color is any color greater than a certain delta of the color at the specified point.

var r1, r2; // red values
var g1, g2; // green values
var b1, b2; // blue values
var actualColorDelta = Math.sqrt((r1 - r2)*(r1 - r2) + (g1 - g2)*(g1 - g2) + (b1 - b2)*(b1 - b2))

function floodFill(canvas, x, y, fillColor, borderColorDelta) {
  ...
}

Update:

I wrote my own implementation of flood fill, which follows. It is slow, but accurate. About 37% of the time is taken up in two low-level array functions that are part of the prototype framework. They are called by push and pop, I presume. Most of the rest of the time is spent in the main loop.

var ImageProcessing;

ImageProcessing = {

  /* Convert HTML color (e.g. "#rrggbb" or "#rrggbbaa") to object with properties r, g, b, a. 
   * If no alpha value is given, 255 (0xff) will be assumed.
   */
  toRGB: function (color) {
    var r, g, b, a, html;
    html = color;

    // Parse out the RGBA values from the HTML Code
    if (html.substring(0, 1) === "#")
    {
      html = html.substring(1);
    }

    if (html.length === 3 || html.length === 4)
    {
      r = html.substring(0, 1);
      r = r + r;

      g = html.substring(1, 2);
      g = g + g;

      b = html.substring(2, 3);
      b = b + b;

      if (html.length === 4) {
        a = html.substring(3, 4);
        a = a + a;
      }
      else {
        a = "ff";
      }
    }
    else if (html.length === 6 || html.length === 8)
    {
      r = html.substring(0, 2);
      g = html.substring(2, 4);
      b = html.substring(4, 6);
      a = html.length === 6 ? "ff" : html.substring(6, 8);
    }

    // Convert from Hex (Hexidecimal) to Decimal
    r = parseInt(r, 16);
    g = parseInt(g, 16);
    b = parseInt(b, 16);
    a = parseInt(a, 16);
    return {r: r, g: g, b: b, a: a};
  },

  /* Get the color at the given x,y location from the pixels array, assuming the array has a width and height as given.
   * This interprets the 1-D array as a 2-D array.
   *
   * If useColor is defined, its values will be set. This saves on object creation.
   */
  getColor: function (pixels, x, y, width, height, useColor) {
    var redIndex = y * width * 4 + x * 4;
    if (useColor === undefined) {
      useColor = { r: pixels[redIndex], g: pixels[redIndex + 1], b: pixels[redIndex + 2], a: pixels[redIndex + 3] };
    }
    else {
      useColor.r = pixels[redIndex];
      useColor.g = pixels[redIndex + 1]
      useColor.b = pixels[redIndex + 2];
      useColor.a = pixels[redIndex + 3];
    }
    return useColor;
  },

  setColor: function (pixels, x, y, width, height, color) {
    var redIndex = y * width * 4 + x * 4;
    pixels[redIndex] = color.r; 
    pixels[redIndex + 1] = color.g, 
    pixels[redIndex + 2] = color.b;
    pixels[redIndex + 3] = color.a;
  },

/*
 * fill: Flood a canvas with the given fill color.
 *
 * Returns a rectangle { x, y, width, height } that defines the maximum extent of the pixels that were changed.
 *
 *    canvas .................... Canvas to modify.
 *    fillColor ................. RGBA Color to fill with.
 *                                This may be a string ("#rrggbbaa") or an object of the form { r: red, g: green, b: blue, a: alpha }.
 *    x, y ...................... Coordinates of seed point to start flooding.
 *    bounds .................... Restrict flooding to this rectangular region of canvas. 
 *                                This object has these attributes: { x, y, width, height }.
 *                                If undefined or null, use the whole of the canvas.
 *    stopFunction .............. Function that decides if a pixel is a boundary that should cause
 *                                flooding to stop. If omitted, any pixel that differs from seedColor
 *                                will cause flooding to stop. seedColor is the color under the seed point (x,y).
 *                                Parameters: stopFunction(fillColor, seedColor, pixelColor).
 *                                Returns true if flooding shoud stop.
 *                                The colors are objects of the form { r: red, g: green, b: blue, a: alpha }
 */
 fill: function (canvas, fillColor, x, y, bounds, stopFunction) {
    // Supply default values if necessary.
    var ctx, minChangedX, minChangedY, maxChangedX, maxChangedY, wasTested, shouldTest, imageData, pixels, currentX, currentY, currentColor, currentIndex, seedColor, tryX, tryY, tryIndex, boundsWidth, boundsHeight, pixelStart, fillRed, fillGreen, fillBlue, fillAlpha;
    if (Object.isString(fillColor)) {
      fillColor = ImageProcessing.toRGB(fillColor);
    }
    x = Math.round(x);
    y = Math.round(y);
    if (bounds === null || bounds === undefined) {
      bounds = { x: 0, y: 0, width: canvas.width, height: canvas.height };
    }
    else {
      bounds = { x: Math.round(bounds.x), y: Math.round(bounds.y), width: Math.round(bounds.y), height: Math.round(bounds.height) };
    }
    if (stopFunction === null || stopFunction === undefined) {
      stopFunction = new function (fillColor, seedColor, pixelColor) {
        return pixelColor.r != seedColor.r || pixelColor.g != seedColor.g || pixelColor.b != seedColor.b || pixelColor.a != seedColor.a;
      }
    }
    minChangedX = maxChangedX = x - bounds.x;
    minChangedY = maxChangedY = y - bounds.y;
    boundsWidth = bounds.width;
    boundsHeight = bounds.height;

    // Initialize wasTested to false. As we check each pixel to decide if it should be painted with the new color,
    // we will mark it with a true value at wasTested[row = y][column = x];
    wasTested = new Array(boundsHeight * boundsWidth);
    /*
    $R(0, bounds.height - 1).each(function (row) { 
      var subArray = new Array(bounds.width);
      wasTested[row] = subArray;
    });
    */

    // Start with a single point that we know we should test: (x, y). 
    // Convert (x,y) to image data coordinates by subtracting the bounds' origin.
    currentX = x - bounds.x;
    currentY = y - bounds.y;
    currentIndex = currentY * boundsWidth + currentX;
    shouldTest = [ currentIndex ];

    ctx = canvas.getContext("2d");
    //imageData = ctx.getImageData(bounds.x, bounds.y, bounds.width, bounds.height);
    imageData = ImageProcessing.getImageData(ctx, bounds.x, bounds.y, bounds.width, bounds.height);
    pixels = imageData.data;
    seedColor = ImageProcessing.getColor(pixels, currentX, currentY, boundsWidth, boundsHeight);
    currentColor = { r: 0, g: 0, b: 0, a: 1 };
    fillRed = fillColor.r;
    fillGreen = fillColor.g;
    fillBlue = fillColor.b;
    fillAlpha = fillColor.a;
    while (shouldTest.length > 0) {
      currentIndex = shouldTest.pop();
      currentX = currentIndex % boundsWidth;
      currentY = (currentIndex - currentX) / boundsWidth;
      if (! wasTested[currentIndex]) {
        wasTested[currentIndex] = true;
        //currentColor = ImageProcessing.getColor(pixels, currentX, currentY, boundsWidth, boundsHeight, currentColor);
        // Inline getColor for performance.
        pixelStart = currentIndex * 4;
        currentColor.r = pixels[pixelStart];
        currentColor.g = pixels[pixelStart + 1]
        currentColor.b = pixels[pixelStart + 2];
        currentColor.a = pixels[pixelStart + 3];

        if (! stopFunction(fillColor, seedColor, currentColor)) {
          // Color the pixel with the fill color. 
          //ImageProcessing.setColor(pixels, currentX, currentY, boundsWidth, boundsHeight, fillColor);
          // Inline setColor for performance
          pixels[pixelStart] = fillRed;
          pixels[pixelStart + 1] = fillGreen;
          pixels[pixelStart + 2] = fillBlue;
          pixels[pixelStart + 3] = fillAlpha;

          if (minChangedX < currentX) { minChangedX = currentX; }
          else if (maxChangedX > currentX) { maxChangedX = currentX; }
          if (minChangedY < currentY) { minChangedY = currentY; }
          else if (maxChangedY > currentY) { maxChangedY = currentY; }

          // Add the adjacent four pixels to the list to be tested, unless they have already been tested.
          tryX = currentX - 1;
          tryY = currentY;
          tryIndex = tryY * boundsWidth + tryX;
          if (tryX >= 0 && ! wasTested[tryIndex]) {
            shouldTest.push(tryIndex); 
          }
          tryX = currentX;
          tryY = currentY + 1;
          tryIndex = tryY * boundsWidth + tryX;
          if (tryY < boundsHeight && ! wasTested[tryIndex]) {
            shouldTest.push(tryIndex); 
          }
          tryX = currentX + 1;
          tryY = currentY;
          tryIndex = tryY * boundsWidth + tryX;
          if (tryX < boundsWidth && ! wasTested[tryIndex]) {
            shouldTest.push(tryIndex); 
          }
          tryX = currentX;
          tryY = currentY - 1;
          tryIndex = tryY * boundsWidth + tryX;
          if (tryY >= 0 && ! wasTested[tryIndex]) {
            shouldTest.push(tryIndex); 
          }
        }
      }
    }
    //ctx.putImageData(imageData, bounds.x, bounds.y);
    ImageProcessing.putImageData(ctx, imageData, bounds.x, bounds.y);

    return { x: minChangedX + bounds.x, y: minChangedY + bounds.y, width: maxChangedX - minChangedX + 1, height: maxChangedY - minChangedY + 1 };
  },

  getImageData: function (ctx, x, y, w, h) { 
    return ctx.getImageData(x, y, w, h); 
  },

  putImageData: function (ctx, data, x, y) { 
    ctx.putImageData(data, x, y); 
  }

};

BTW, when I call this, I use a custom stopFunction:

  stopFill : function (fillColor, seedColor, pixelColor) {
    // Ignore alpha difference for now.
    return Math.abs(pixelColor.r - seedColor.r) > this.colorTolerance || Math.abs(pixelColor.g - seedColor.g) > this.colorTolerance || Math.abs(pixelColor.b - seedColor.b) > this.colorTolerance;
  },

If anyone can see a way to improve performance of this code, I would appreciate it. The basic idea is: 1) Seed color is the initial color at the point to start flooding. 2) Try four adjacent points: up, right, down and left one pixel. 3) If point is out of range or has been visited already, skip it. 4) Otherwise push point onto to the stack of interesting points. 5) Pop the next interesting point off the stack. 6) If the color at that point is a stop color (as defined in the stopFunction) then stop processing that point and skip to step 5. 7) Otherwise, skip to step 2. 8) When there are no more interesting points to visit, stop looping.

Remembering that a point has been visited requires an array with the same number of elements as there are pixels.

A: 

I would not treat the canvas as a bitmap image.

Instead I would keep a collection of painting-objects and modify that collection. Then for example you can fill a path or shape or add a new shape that has the boundaries of the objects you are trying to fill.

I can't see how "normal" floodFill makes sense in vector drawing..

Peter Hagström
My application has two kinds of layers: vector layers and bitmap layers. I need the flood fill for the bitmap layers, principally the background layer (which holds colored terrain that underlies contour lines for a topographic map).
Paul Chernoch
+1  A: 

Here's an implementation that I've been working on. It can get really slow if the replacement color is too close to the original color. It's quite a bit faster in Chrome than Firefox (I haven't tested it in any other browsers).

I also haven't done exhaustive testing yet, so there may be edge cases where it doesn't work.

function getPixel(pixelData, x, y) {
    if (x < 0 || y < 0 || x >= pixelData.width || y >= pixelData.height) {
        return NaN;
    }
    var pixels = pixelData.data;
    var i = (y * pixelData.width + x) * 4;
    return ((pixels[i + 0] & 0xFF) << 24) |
           ((pixels[i + 1] & 0xFF) << 16) |
           ((pixels[i + 2] & 0xFF) <<  8) |
           ((pixels[i + 3] & 0xFF) <<  0);
}

function setPixel(pixelData, x, y, color) {
    var i = (y * pixelData.width + x) * 4;
    var pixels = pixelData.data;
    pixels[i + 0] = (color >>> 24) & 0xFF;
    pixels[i + 1] = (color >>> 16) & 0xFF;
    pixels[i + 2] = (color >>>  8) & 0xFF;
    pixels[i + 3] = (color >>>  0) & 0xFF;
}

function diff(c1, c2) {
    if (isNaN(c1) || isNaN(c2)) {
        return Infinity;
    }

    var dr = ((c1 >>> 24) & 0xFF) - ((c2 >>> 24) & 0xFF);
    var dg = ((c1 >>> 16) & 0xFF) - ((c2 >>> 16) & 0xFF);
    var db = ((c1 >>>  8) & 0xFF) - ((c2 >>>  8) & 0xFF);
    var da = ((c1 >>>  0) & 0xFF) - ((c2 >>>  0) & 0xFF);

    return dr*dr + dg*dg + db*db + da*da;
}

function floodFill(canvas, x, y, replacementColor, delta) {
    var current, w, e, stack, color, cx, cy;
    var context = canvas.getContext("2d");
    var pixelData = context.getImageData(0, 0, canvas.width, canvas.height);
    var done = [];
    for (var i = 0; i < canvas.width; i++) {
        done[i] = [];
    }

    var targetColor = getPixel(pixelData, x, y);
    delta *= delta;

    stack = [ [x, y] ];
    done[x][y] = true;
    while ((current = stack.pop())) {
        cx = current[0];
        cy = current[1];

        if (diff(getPixel(pixelData, cx, cy), targetColor) <= delta) {
            setPixel(pixelData, cx, cy, replacementColor);

            w = e = cx;
            while (w > 0 && diff(getPixel(pixelData, w - 1, cy), targetColor) <= delta) {
                --w;
                if (done[w][cy]) break;
                setPixel(pixelData, w, cy, replacementColor);
            }
            while (e < pixelData.width - 1 && diff(getPixel(pixelData, e + 1, cy), targetColor) <= delta) {
                ++e;
                if (done[e][cy]) break;
                setPixel(pixelData, e, cy, replacementColor);
            }

            for (cx = w; cx <= e; cx++) {
                if (cy > 0) {
                    color = getPixel(pixelData, cx, cy - 1);
                    if (diff(color, targetColor) <= delta) {
                        if (!done[cx][cy - 1]) {
                            stack.push([cx, cy - 1]);
                            done[cx][cy - 1] = true;
                        }
                    }
                }
                if (cy < canvas.height - 1) {
                    color = getPixel(pixelData, cx, cy + 1);
                    if (diff(color, targetColor) <= delta) {
                        if (!done[cx][cy + 1]) {
                            stack.push([cx, cy + 1]);
                            done[cx][cy + 1] = true;
                        }
                    }
                }
            }
        }
    }

    context.putImageData(pixelData, 0, 0, 0, 0, canvas.width, canvas.height);
}
Matthew Crumley
I will give yours a try when I get a chance. I ended up implementing my own Flood fill algorithm. It is accurate but slow. If most of the canvas needs to be repainted it takes 8-9 seconds in Firefox (for an 800x520 pixel canvas).
Paul Chernoch