javascript - getcontext - ¿Cómo puedo realizar el relleno de inundación con HTML Canvas?

getcontext canvas

Question

¿Alguien ha implementado un algoritmo de relleno de inundación en JavaScript para usarlo con HTML Canvas?

Mis requisitos son simples: inundar con un solo color a partir de un único punto, donde el color del límite es cualquier color mayor que un cierto delta del color en el punto especificado.

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) {
  ...
}

Actualizar:

Escribí mi propia implementación de relleno de inundación, que sigue. Es lento, pero preciso. Aproximadamente el 37% del tiempo se utiliza en dos funciones de matriz de bajo nivel que forman parte del marco prototipo. Ellos son llamados por push y pop, supongo. La mayor parte del resto del tiempo se gasta en el ciclo principal.

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); 
  }

};

Por cierto, cuando llamo esto, uso un stopFunction personalizado:

  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;
  },

Si alguien puede ver una forma de mejorar el rendimiento de este código, lo agradecería. La idea básica es: 1) El color de la semilla es el color inicial en el punto donde comienza la inundación. 2) Pruebe cuatro puntos adyacentes: arriba, derecha, abajo e izquierda un pixel. 3) Si el punto está fuera de rango o ya ha sido visitado, sáltelo. 4) De lo contrario, empuje el punto hacia la pila de puntos interesantes. 5) Pop el siguiente punto interesante de la pila. 6) Si el color en ese punto es un color de parada (como se define en la función stop), deje de procesar ese punto y salte al paso 5. 7) De lo contrario, salte al paso 2. 8) Cuando no hay más puntos interesantes para visitar , deja de buclear

Recordar que un punto ha sido visitado requiere una matriz con la misma cantidad de elementos que píxeles.

Answer 1

No trataría el lienzo como una imagen de mapa de bits.

En su lugar, mantendría una colección de objetos de pintura y modificaría esa colección. Entonces, por ejemplo, puede completar una ruta o forma o agregar una nueva forma que tenga los límites de los objetos que intenta llenar.

No puedo ver cómo el relleno "normal" tiene sentido en el dibujo vectorial ...

Answer 2

Aquí hay una implementación en la que he estado trabajando. Puede ser realmente lento si el color de reemplazo es demasiado cercano al color original. Es bastante más rápido en Chrome que en Firefox (no lo he probado en ningún otro navegador).

Tampoco he realizado pruebas exhaustivas todavía, por lo que puede haber casos extremos en los que no funcione.

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);
}