Now, I tried to perform flood fill algorithm to fill up the transparent PNG images using flood fill algorithm from the article How can I avoid exceeding the max call stack size during a flood fill algorithm? which use non recursive method along with Uint32Array to handle color stack with work quite well.
However, this flood fill algorithm has left the white (actually the light grey edge or anti-alias edges) which remain unfilled. Here is my code:
var BrushColorString = '#F3CDA6'; // skin color
canvas.addEventListener('mousedown', function(e) {
const rect = canvas.getBoundingClientRect()
CanvasMouseX = e.clientX - rect.left;
CanvasMouseY = e.clientY - rect.top;
if (mode === 'flood-fill')
{
// test flood fill algorithm
paintAt(context, CanvasMouseX,CanvasMouseY,hexToRgb(BrushColorString));
}
});
function paintAt(ContextOutput,startX, startY,curColor) {
//function paintAt(ctx,startX, startY,curColor) {
// read the pixels in the canvas
const width = ContextOutput.canvas.width,
height = ContextOutput.canvas.height,pixels = width*height;
const imageData = ContextOutput.getImageData(0, 0, width, height);
var data1 = imageData.data;
const p32 = new Uint32Array(data1.buffer);
const stack = [startX + (startY * width)]; // add starting pos to stack
const targetColor = p32[stack[0]];
var SpanLeft = true, SpanRight = true; // logic for spanding left right
var leftEdge = false, rightEdge = false;
// proper conversion of color to Uint32Array
const newColor = new Uint32Array((new Uint8ClampedArray([curColor.r,curColor.g, curColor.b, curColor.a])).buffer)[0];
// need proper comparison of target color and new Color
if (targetColor === newColor || targetColor === undefined) { return } // avoid endless loop
while (stack.length){
let idx = stack.pop();
while(idx >= width && p32[idx - width] === targetColor) { idx -= width }; // move to top edge
SpanLeft = SpanRight = false; // not going left right yet
leftEdge = (idx % width) === 0;
rightEdge = ((idx +1) % width) === 0;
while (p32[idx] === targetColor) {
p32[idx] = newColor;
if(!leftEdge) {
if (p32[idx - 1] === targetColor) { // check left
if (!SpanLeft) {
stack.push(idx - 1); // found new column to left
SpanLeft = true; //
} else if (SpanLeft) {
SpanLeft = false;
}
}
}
if(!rightEdge) {
if (p32[idx + 1] === targetColor) {
if (!SpanRight) {
stack.push(idx + 1); // new column to right
SpanRight = true;
}else if (SpanRight) {
SpanRight = false;
}
}
}
idx += width;
}
}
clearCanvas(ContextOutput);
ContextOutput.putImageData(imageData,0, 0);
};
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),
a: 255
} : null;
};
So far, I have tried using the following suggestion:
- using matchOutlineColor function using RGBA value mentioned in Canvas - floodfill leaves white pixels at edges
- When I tried to implemented "Restrict fill area based on intensity gradient changes instead of simple threshold " mentioned in Canvas - floodfill leaves white pixels at edges which is considered as the most promising algorithm, I still have no clue how to implement this algorithm with minimum change on existing algorithm to handle the anti-alias edge issue for the cases of images with transparent.
- When I take a look at the example on how to apply a tolerance and a toleranceFade mentioned in Canvas flood fill not filling to edge, I still have no clue how implement such a tolerance and a toleranceFade in my case.
- Color Difference method (colorDiff function) within mentioned tolerance in Canvas Javascript FloodFill algorithm left white pixels without color and so far still not working. Similar thing can be said to colorsMatch function to be within Range Square (rangeSq) mentioned in How can I perform flood fill with HTML Canvas? which still unable to solve the anti-alias edge problem.
If you have any idea on how to deal with anti-alias edge problems of the flood-fill algorithm, please response as soon as possible.
Updated:
Here is the revised code on paintAt fucntion from the suggestion that takes tolerance into account:
<div id="container"><canvas id="control" >Does Not Support Canvas Element</canvas></div>
<div><label for="tolerance">Tolerance</label>
<input id="tolerance" type="range" min="0" max="255" value="32" step="1" oninput="this.nextElementSibling.value = this.value"><output>32</output></div>
var canvas = document.getElementById("control");
var context = canvas.getContext('2d');
var CanvasMouseX = -1; var CanvasMouseY = -1;
var BrushColorString = '#F3CDA6'; // skin color
canvas.addEventListener('mousedown', function(e) {
const rect = canvas.getBoundingClientRect()
CanvasMouseX = e.clientX - rect.left;
CanvasMouseY = e.clientY - rect.top;
// testing
if (mode === 'flood-fill')
{
// test flood fill algorithm
paintAt(context,CanvasMouseX,CanvasMouseY,
hexToRgb(BrushColorString),tolerance.value);
}
});
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),
a: 255
} : null;
};
function clearCanvas(ctx) {
ctx.clearRect(0, 0,ctx.canvas.width,ctx.canvas.height);
};
function colorDistance(index, R00,G00,B00,A00, data0)
{
var index1 = index << 2; // multiplyed by 4
const R = R00 - data0[index1 + 0];
const G = G00 - data0[index1 + 1];
const B = B00 - data0[index1 + 2];
const A = A00 - data0[index1 + 3];
return Math.sqrt((R * R) + (B * B) + (G * G) + (A * A));
}
function paintAt(ContextOutput,startX, startY,curColor,tolerance) {
// read the pixels in the canvas
const width = ContextOutput.canvas.width,
height = ContextOutput.canvas.height, pixels = width*height;
const rightEdgeNum = width - 1, bottomEdgeNum = height - 1;
const imageData = ContextOutput.getImageData(0, 0, width, height);
var data1 = imageData.data;
const p32 = new Uint32Array(data1.buffer);
const stack = [startX + (startY * width)]; // add starting pos to stack
const targetColor = p32[stack[0]];
var SpanLeft = true, SpanRight = true; // logic for spanning left right
var leftEdge = false, rightEdge = false, IsBlend = false;
const DistancesArray = new Uint16Array(pixels); // array distance value
var R=-1,G=-1,B=-1,A = -1,idx =0,Distance=0;
var R0 = data1[(4*(startX + (startY * width)))+0],
G0 = data1[(4*(startX + (startY * width)))+1],
B0 = data1[(4*(startX + (startY * width)))+2],
A0 = data1[(4*(startX + (startY * width)))+3];
var CalculatedTolerance = Math.sqrt(tolerance * tolerance * 4);
const BlendR = curColor.r |0, BlendG = curColor.g |0,
BlendB = curColor.b |0, BlendA = curColor.a|0;
// color variable for blending
const newColor = new Uint32Array((new Uint8ClampedArray([BlendR,BlendG,BlendB,BlendA])).buffer)[0];
if (targetColor === newColor || targetColor === undefined) { return }
// avoid endless loop
while (stack.length){
idx = stack.pop();
while (idx >= width &&
colorDistance(idx - width,R0,G0,B0,A0,data1) <= CalculatedTolerance) { idx -= width }; // move to top edge
SpanLeft = SpanRight = false; // not going left right yet
leftEdge = (idx % width) === 0;
rightEdge = ((idx +1) % width) === 0;
while ((Distance = colorDistance(idx,R0,G0,B0,A0,data1)) <= CalculatedTolerance) {
DistancesArray[idx] = (Distance / CalculatedTolerance) * 255 | 0x8000;
p32[idx] = newColor;
if(!leftEdge) {
if (colorDistance(idx - 1,R0,G0,B0,A0,data1) <= CalculatedTolerance) { // check left
if (!SpanLeft) {
stack.push(idx - 1); // found new column to left
SpanLeft = true; //
} else if (SpanLeft) {
SpanLeft = false;
}
}
}
if(!rightEdge) {
if (colorDistance(idx + 1,R0,G0,B0,A0,data1) <= CalculatedTolerance) {
if (!SpanRight) {
stack.push(idx + 1); // new column to right
SpanRight = true;
}else if (SpanRight) {
SpanRight = false;
}
}
}
idx += width;
}
}
idx = 0;
while (idx <= pixels-1) {
Distance = DistancesArray[idx];
if (Distance !== 0) {
if (Distance === 0x8000) {
p32[idx] = newColor;
} else {
IsBlend = false;
const x = idx % width;
const y = idx / width | 0;
if (x >= 1 && DistancesArray[idx - 1] === 0) { IsBlend = true }
else if (x <= rightEdgeNum -1 && DistancesArray[idx + 1] === 0) { IsBlend = true }
else if (y >=1 && DistancesArray[idx - width] === 0) { IsBlend = true }
else if (y <=bottomEdgeNum-1 && DistancesArray[idx + width] === 0) { IsBlend = true }
if (IsBlend) {
// blending at the edge
Distance &= 0xFF;
Distance = Distance / 255;
const invDist = 1 - Distance;
const idx1 = idx << 2;
data1[idx1 + 0] = data1[idx1 + 0] * Distance + BlendR * invDist;
data1[idx1 + 1] = data1[idx1 + 1] * Distance + BlendG * invDist;
data1[idx1 + 2] = data1[idx1 + 2] * Distance + BlendB * invDist;
data1[idx1 + 3] = data1[idx1 + 3] * Distance + BlendA * invDist;
} else {
p32[idx] = newColor;
}
}
}
idx++;
}
// this recursive algorithm works but still not working well due to the issue stack overflow!
clearCanvas(ContextOutput);
ContextOutput.putImageData(imageData,0, 0);
// way to deal with memory leak at the array.
DistancesArray = [];
newColor = [];
p32 = [];
};
However, the results of flood fill have been found wanting as shown in the transition tolerance as shown here:'
How can I deal with this kind problem when tolerance has become too much. Any alternative algorithm would be appreciated.
