¿Cómo puedo realizar el relleno de inundación con HTML 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) { 
    ... 
} 

Actualización:

escribir mi propia aplicació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 a esto, yo 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 con cuatro puntos adyacentes: arriba, derecha, abajo e izquierda un píxel. 3) Si el punto está fuera de rango o ya ha sido visitado, sáltelo. 4) De lo contrario, apúntelo a la pila de puntos interesantes. 5) Aparece 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) entonces deje de procesar ese punto y salte al paso 5. 7) De lo contrario, salte al paso 2. 8) Cuando ya no hay más puntos para visitar, dejar de buclear.

Recordando 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, me gustaría tener una colección de objetos de pintura y modificar esa colección. Luego, 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 como "normal" floodFill tiene sentido en el dibujo vectorial ..

Answer 2

Aquí es una implementación 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 hecho pruebas exhaustivas todavía, por lo que puede haber casos de bordes donde no funciona.

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