HTML5 Canvas - Anti-aliasing and Paint Bucket / Flood Fill
If you simply want to change a color of a line: don't use bucket paint fill at all.
Store all your lines and shapes as objects/arrays and redraw them when needed.
This not only allow you to change canvas size without losing everything on it, but to change a color is simply a matter of changing a color property on your object/array and redraw, as well as scaling everything based on vectors instead of raster.
This will be faster than a bucket fill as redrawing is handled in most part internally and not by pixel-by-pixel in JavaScript as is needed with a bucket fill.
That being said: you cannot, unfortunately, disable anti-alias for shapes and lines, only for images (using the imageSmoothingEnabled property).
An object could look like this:
function myLine(x1, y1, x2, y2, color) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
this.color = color;
return this;
}
And then allocate it by:
var newLine = new myLine(x1, y1, x2, y2, color);
Then store this to an array:
/// globally:
var myLineStack = [];
/// after x1/x2/y1/y2 and color is achieved in the draw function:
myLineStack.push(new myLine(x1, y1, x2, y2, color));
Then it is just a matter of iterating through the objects when an update is needed:
/// some index to a line you want to change color for:
myLineStack[index].color = newColor;
/// Redraw all (room for optimizations here...)
context.clearRect( ... );
for(var i = 0, currentLine; currentLine = myLineStack[i]; i++) {
/// new path
context.beginPath();
/// set the color for this line
context.strokeStyle = currentLine.color;
/// draw the actual line
context.moveTo(currentLine.x1, currentLine.y1);
context.lineTo(currentLine.x2, currentLine.y2);
context.stroke();
}
(For optimizations you can for example clear only the area that needs redraw and draw a single index. You can also group lines/shapes with the same colors and draw then with a single setting of strokeStyle etc.)
Making HTML5 canvas floodfill efficient
I realize this is a very old question, but if you're still working on this, temporarily put in some code timing the various parts of your function to find where it's slowest. Definitely pull the calls to getimagedata and putimagedata out of the loop - only call each once for each "fill". Once you have the imagedata, get and set the colors of the pixels through it's underlying buffer, viewed as a Uint32Array.
See
https://hacks.mozilla.org/2011/12/faster-canvas-pixel-manipulation-with-typed-arrays/
Canvas flood fill not filling to edge
Use flood fill to create a Mask
I just happened to do a floodFill the other day that addresses the problem of antialiased edges.
Rather than paint to the canvas directly, I paint to a byte array that is then used to create a mask. The mask allows for the alpha values to be set.
The fill can have a tolerance and a toleranceFade that control how it deals with colours that approch the tolerance value.
When pixel's difference between the start colour and tolerance are greater than (tolerance - toleranceFade) I set the alpha for that pixel to 255 - ((differance - (tolerance - toleranceFade)) / toleranceFade) * 255 which creates a nice smooth blend at the edges of lines. Though it does not work for all situations for high contrast situations it is an effective solution.
The example below shows the results of with and without the toleranceFade. The blue is without the toleranceFade, the red is with the tolerance set at 190 and the toleranceFade of 90.
You will have to play around with the setting to get the best results for your needs.
function showExample(){
var canvas = document.createElement("canvas");
canvas.width = 200;
canvas.height = 200;
var ctx = canvas.getContext("2d");
document.body.appendChild(canvas);
ctx.fillStyle = "white"
ctx.fillRect(0,0,canvas.width,canvas.height)
ctx.lineWidth = 4;
ctx.strokeStyle = "black"
ctx.beginPath();
ctx.arc(100,100,90,0,Math.PI * 2);
ctx.arc(120,100,60,0,Math.PI * 2);
ctx.stroke();
ctx.fillStyle = "blue";
floodFill.fill(100,100,1,ctx)
ctx.fillStyle = "red";
floodFill.fill(40,100,190,ctx,null,null,90)
}
// FloodFill2D from https://github.com/blindman67/FloodFill2D
var floodFill = (function(){
"use strict";
const extent = {
top : 0,
left : 0,
bottom : 0,
right : 0,
}
var keepMask = false; // if true then a mask of the filled area is returned as a canvas image
var extentOnly = false; // if true then the extent of the fill is returned
var copyPixels = false; // if true then creating a copy of filled pixels
var cutPixels = false; // if true and copyPixels true then filled pixels are removed
var useBoundingColor = false; // Set the colour to fill up to. Will not fill over this colour
var useCompareColor = false; // Rather than get the pixel at posX,posY use the compareColours
var red, green, blue, alpha; // compare colours if
var canvas,ctx;
function floodFill (posX, posY, tolerance, context2D, diagonal, area, toleranceFade) {
var w, h, painted, x, y, ind, sr, sg, sb, sa,imgData, data, data32, RGBA32, stack, stackPos, lookLeft, lookRight, i, colImgDat, differance, checkColour;
toleranceFade = toleranceFade !== undefined && toleranceFade !== null ? toleranceFade : 0;
diagonal = diagonal !== undefined && diagonal !== null ? diagonal : false;
area = area !== undefined && area !== null ? area : {};
area.x = area.x !== undefined ? area.x : 0;
area.y = area.y !== undefined ? area.y : 0;
area.w = area.w !== undefined ? area.w : context2D.canvas.width - area.x;
area.h = area.h !== undefined ? area.h : context2D.canvas.height - area.y;
// vet area is on the canvas.
if(area.x < 0){
area.w = area.x + area.w;
area.x = 0;
}
if(area.y < 0){
area.h = area.y + area.h;
area.y = 0;
}
if(area.x >= context2D.canvas.width || area.y >= context2D.canvas.height){
return false;
}
if(area.x + area.w > context2D.canvas.width){
area.w = context2D.canvas.width - area.x;
}
if(area.y + area.h > context2D.canvas.height){
area.h = context2D.canvas.height - area.y;
}
if(area.w <= 0 || area.h <= 0){
return false;
}
w = area.w; // width and height
h = area.h;
x = posX - area.x;
y = posY - area.y;
if(extentOnly){
extent.left = x; // set up extent
extent.right = x;
extent.top = y;
extent.bottom = y;
}
if(x < 0 || y < 0 || x >= w || y >= h){
return false; // fill start outside area. Don't do anything
}
if(tolerance === 255 && toleranceFade === 0 && ! keepMask){ // fill all
if(extentOnly){
extent.left = area.x; // set up extent
extent.right = area.x + w;
extent.top = area.y;
extent.bottom = area.y + h;
}
context2D.fillRect(area.x,area.y,w,h);
return true;
}
if(toleranceFade > 0){ // add one if on to get correct number of steps
toleranceFade += 1;
}
imgData = context2D.getImageData(area.x,area.y,area.w,area.h);
data = imgData.data; // image data to fill;
data32 = new Uint32Array(data.buffer);
painted = new Uint8ClampedArray(w*h); // byte array to mark painted area;
function checkColourAll(ind){
if( ind < 0 || painted[ind] > 0){ // test bounds
return false;
}
var ind4 = ind << 2; // get index of pixel
if((differance = Math.max( // get the max channel difference;
Math.abs(sr - data[ind4++]),
Math.abs(sg - data[ind4++]),
Math.abs(sb - data[ind4++]),
Math.abs(sa - data[ind4++])
)) > tolerance){
return false;
}
return true
}
// check to bounding colour
function checkColourBound(ind){
if( ind < 0 || painted[ind] > 0){ // test bounds
return false;
}
var ind4 = ind << 2; // get index of pixel
differance = 0;
if(sr === data[ind4] && sg === data[ind4 + 1] && sb === data[ind4 + 2] && sa === data[ind4 + 3]){
return false
}
return true
}
// this function checks the colour of only selected channels
function checkColourLimited(ind){ // check only colour channels that are not null
var dr,dg,db,da;
if( ind < 0 || painted[ind] > 0){ // test bounds
return false;
}
var ind4 = ind << 2; // get index of pixel
dr = dg = db = da = 0;
if(sr !== null && (dr = Math.abs(sr - data[ind4])) > tolerance){
return false;
}
if(sg !== null && (dg = Math.abs(sg - data[ind4 + 1])) > tolerance){
return false;
}
if(sb !== null && (db = Math.abs(sb - data[ind4 + 2])) > tolerance){
return false;
}
if(sa !== null && (da = Math.abs(sa - data[ind4 + 3])) > tolerance){
return false;
}
diferance = Math.max(dr, dg, db, da);
return true
}
// set which function to check colour with
checkColour = checkColourAll;
if(useBoundingColor){
sr = red;
sg = green;
sb = blue;
if(alpha === null){
ind = (y * w + x) << 2; // get the starting pixel index
sa = data[ind + 3];
}else{
sa = alpha;
}
checkColour = checkColourBound;
useBoundingColor = false;
}else if(useCompareColor){
sr = red;
sg = green;
sb = blue;
sa = alpha;
if(red === null || blue === null || green === null || alpha === null){
checkColour = checkColourLimited;
}
useCompareColor = false;
}else{
ind = (y * w + x) << 2; // get the starting pixel index
sr = data[ind]; // get the start colour that we will use tolerance against.
sg = data[ind + 1];
sb = data[ind + 2];
sa = data[ind + 3];
}
stack = []; // paint stack to find new pixels to paint
lookLeft = false; // test directions
lookRight = false;
stackPos = 0;
stack[stackPos++] = x;
stack[stackPos++] = y;
while (stackPos > 0) { // do while pixels on the stack
y = stack[--stackPos]; // get the pixel y
x = stack[--stackPos]; // get the pixel x
ind = x + y * w;
while (checkColour(ind - w)) { // find the top most pixel within tollerance;
y -= 1;
ind -= w;
}
//checkTop left and right if allowing diagonal painting
if(diagonal && y > 0){
if(x > 0 && !checkColour(ind - 1) && checkColour(ind - w - 1)){
stack[stackPos++] = x - 1;
stack[stackPos++] = y - 1;
}
if(x < w - 1 && !checkColour(ind + 1) && checkColour(ind - w + 1)){
stack[stackPos++] = x + 1;
stack[stackPos++] = y - 1;
}
}
lookLeft = false; // set look directions
lookRight = false; // only look is a pixel left or right was blocked
while (checkColour(ind) && y < h) { // move down till no more room
if(toleranceFade > 0 && differance >= tolerance-toleranceFade){
painted[ind] = 255 - (((differance - (tolerance - toleranceFade)) / toleranceFade) * 255);
painted[ind] = painted[ind] === 0 ? 1 : painted[ind]; // min value must be 1
}else{
painted[ind] = 255;
}
if(extentOnly){
extent.left = x < extent.left ? x : extent.left; // Faster than using Math.min
extent.right = x > extent.right ? x : extent.right; // Faster than using Math.min
extent.top = y < extent.top ? y : extent.top; // Faster than using Math.max
extent.bottom = y > extent.bottom ? y : extent.bottom; // Faster than using Math.max
}
if (checkColour(ind - 1) && x > 0) { // check left is blocked
if (!lookLeft) {
stack[stackPos++] = x - 1;
stack[stackPos++] = y;
lookLeft = true;
}
} else if (lookLeft) {
lookLeft = false;
}
if (checkColour(ind + 1) && x < w -1) { // check right is blocked
if (!lookRight) {
stack[stackPos++] = x + 1;
stack[stackPos++] = y;
lookRight = true;
}
} else if (lookRight) {
lookRight = false;
}
y += 1; // move down one pixel
ind += w;
}
if(diagonal && y < h){ // check for diagonal areas and push them to be painted
if(checkColour(ind - 1) && !lookLeft && x > 0){
stack[stackPos++] = x - 1;
stack[stackPos++] = y;
}
if(checkColour(ind + 1) && !lookRight && x < w - 1){
stack[stackPos++] = x + 1;
stack[stackPos++] = y;
}
}
}
if(extentOnly){
extent.top += area.y;
extent.bottom += area.y;
extent.left += area.x;
extent.right += area.x;
return true;
}
canvas = document.createElement("canvas");
canvas.width = w;
canvas.height = h;
ctx = canvas.getContext("2d");
ctx.fillStyle = context2D.fillStyle;
ctx.fillRect(0, 0, w, h);
colImgDat = ctx.getImageData(0, 0, w, h);
if(copyPixels){
i = 0;
ind = 0;
if(cutPixels){
while(i < painted.length){
if(painted[i] > 0){
colImgDat.data[ind] = data[ind];
colImgDat.data[ind + 1] = data[ind + 1];
colImgDat.data[ind + 2] = data[ind + 2];
colImgDat.data[ind + 3] = data[ind + 3] * (painted[i] / 255);
data[ind + 3] = 255 - painted[i];
}else{
colImgDat.data[ind + 3] = 0;
}
i ++;
ind += 4;
}
context2D.putImageData(imgData, area.x, area.y);
}else{
while(i < painted.length){
if(painted[i] > 0){
colImgDat.data[ind] = data[ind];
colImgDat.data[ind + 1] = data[ind + 1];
colImgDat.data[ind + 2] = data[ind + 2];
colImgDat.data[ind + 3] = data[ind + 3] * (painted[i] / 255);
}else{
colImgDat.data[ind + 3] = 0;
}
i ++;
ind += 4;
}
}
ctx.putImageData(colImgDat,0,0);
return true;
}else{
i = 0;
ind = 3;
while(i < painted.length){
colImgDat.data[ind] = painted[i];
i ++;
ind += 4;
}
ctx.putImageData(colImgDat,0,0);
}
if(! keepMask){
context2D.drawImage(canvas,area.x,area.y,w,h);
}
return true;
}
return {
fill : function(posX, posY, tolerance, context2D, diagonal, area, toleranceFade){
floodFill(posX, posY, tolerance, context2D, diagonal, area, toleranceFade);
ctx = undefined;
canvas = undefined;
},
getMask : function(posX, posY, tolerance, context2D, diagonal, area, toleranceFade){
keepMask = true;
floodFill(posX, posY, tolerance, context2D, diagonal, area, toleranceFade);
ctx = undefined;
keepMask = false;
return canvas;
},
getExtent : function(posX, posY, tolerance, context2D, diagonal, area, toleranceFade){
extentOnly = true;
if(floodFill(posX, posY, tolerance, context2D, diagonal, area, toleranceFade)){
extentOnly = false;
return {
top : extent.top,
left : extent.left,
right : extent.right,
bottom : extent.bottom,
width : extent.right - extent.left,
height : extent.bottom - extent.top,
}
}
extentOnly = false;
return null;
},
cut : function(posX, posY, tolerance, context2D, diagonal, area, toleranceFade){
cutPixels = true;
copyPixels = true;
floodFill(posX, posY, tolerance, context2D, diagonal, area, toleranceFade);
cutPixels = false;
copyPixels = false;
ctx = undefined;
return canvas;
},
copy : function(posX, posY, tolerance, context2D, diagonal, area, toleranceFade){
cutPixels = false;
copyPixels = true;
floodFill(posX, posY, tolerance, context2D, diagonal, area, toleranceFade);
copyPixels = false;
ctx = undefined;
return canvas;
},
setCompareValues : function(R,G,B,A){
if(R === null && G === null && B === null && A === null){
return;
}
red = R;
green = G;
blue = B;
alpha = A;
useBoundingColor = false;
useCompareColor = true;
},
setBoundingColor : function(R,G,B,A){
red = R;
green = G;
blue = B;
alpha = A;
useCompareColor = false;
useBoundingColor = true;
}
}
}());
showExample();Red floodFill.fill(40,100,190,ctx,null,null,90) tolerance 190, tolerance fade 90<br>Blue floodFill.fill(100,100,1,ctx) tolerance 1.<br>Is there any way to make this flood fill faster in HTML5 canvas?
MS Paint is written in native code (C or C++ converted to machine code), which is far faster and, if correctly written, more efficient at rendering than canvas/javascript. Consider also that MS Paint might use the video rendering facilities of the hardware on the computer, which I don't think canvas does by default in most browsers.
Also, MS Paint's flood/filling algorithm may be different than the one you're using. There's always more than one way to achieve something. Have you tried a simple line by line scan, filling in white pixels as you go? You could try it, just for benchmarking purposes.
Is there a way to fill from a point till it hits a border using HTML Canvas and JavaScript?
You can use Flood fill to fill a region. It takes a starting point (or the seed point) as an input and recursively fills the region, by attempting to fill its empty neighbors.
A simple stack-based implementation in JavaScript:
// Takes the seed point as input
var floodfill = function(point) {
var stack = Array();
stack.push(point); // Push the seed
while(stack.length > 0) {
var currPoint = stack.pop();
if(isEmpty(currPoint)) { // Check if the point is not filled
setPixel(currPoint); // Fill the point with the foreground
stack.push(currPoint.x + 1, currPoint.y); // Fill the east neighbour
stack.push(currPoint.x, currPoint.y + 1); // Fill the south neighbour
stack.push(currPoint.x - 1, currPoint.y); // Fill the west neighbour
stack.push(currPoint.x, currPoint.y - 1); // Fill the north neighbour
}
}
};
isEmpty(point) is the function that tests whether the point (x, y) is filled with the boundary color (light green, in this case) or not.
setPixel(point) fills the point (x, y) with the foreground color (dark green, in your case).
The implementation of these functions is trivial, and I leave it to you.
The implementation above uses a 4-connected neighborhood. But it can easily be extended to 6 or 8-connected neighborhoods.
Canvas flood fill stroke color
The match stroke function:
function matchstrokeColor(r, g, b, a) {
// never recolor the initial black divider strokes
// must check for near black because of anti-aliasing
return (r + g + b < 100 && a === 155);
}
is only check whether rgb is a small number and is a painted stroke, as you directly paint your image on that canvas, rgb should now become something else, and alpha is now 255(or unpredictable if your image has alpha).
Try change it to something that is aware of the storke's color, like sqrt distance:
// A small threshold would make it fill closer to stroke.
var strokeThreshold = 1;
function matchstrokeColor(r, g, b, a) {
// Use sqrt difference to decide its storke or not.
var diffr = r - strokeColor.r;
var diffg = g - strokeColor.g;
var diffb= b - strokeColor.b;
var diff = Math.sqrt(diffr * diffr + diffg * diffg + diffb * diffb) / 3;
return (diff < strokeThreshold);
}
See Example jsfiddle
Related Topics
Jquery.Getjson - Access-Control-Allow-Origin Issue
Random Alpha-Numeric String in JavaScript
Is Reading the 'Length' Property of an Array Really That Expensive an Operation in JavaScript
How to Get Class Object's Name as a String in JavaScript
JavaScript Regular Expressions and Sub-Matches
How to Remove a Key from a JavaScript Object
What Is Difference Between Axios and Fetch
How to Rotate a 3D Object on Axis Three.Js
How to Determine If an Image Has Loaded, Using JavaScript/Jquery
Search Recursively for Value in Object by Property Name
How to Build Query String with JavaScript
Regex Created via New Regexp(Mystring) Not Working (Backslashes)
Retrieving Binary File Content Using JavaScript, Base64 Encode It and Reverse-Decode It Using Python
Generate HTML Table from 2D JavaScript Array