CODEWITHSUNDEEP
javascriptp5.jsflood-fill
Idan Lottan
Idan Lottan

Reputation: 138

Flood fill algorithm for bucket tool in P5.js electron paint application

I'm trying to create a bucket tool for my paint application made with electron.js and P5.js for the canvas stuff. everytime a user clicks on the canvas and his mode variable is equal to "fill", it calls the floodFill function. i tried to implement the algorithm from here: https://en.wikipedia.org/wiki/Flood_fill#Pseudocode (Stack-based recursive implementation (four-way)), but i have a problem - i'm reaching maximum call stack. the way i render everything to the screen is i have an array called drawing and there are constructor functions for the types of things you can draw (Circle, Square) so i created a Pixel constructor function so that i can render it everytime, i cannot call updatePixels() because i render everything every frame with the draw() function. this is my floodFill function:

function floodFill(x, y, target_col, replace_col) {
   if (x >= 0 && y >= 0 && x <= width && y <= height) {
        let index = (x + y * width) * 4;
        if (target_col === replace_col) {
            return;
        } else if (
            pixels[index] !== target_col.levels[0] &&
            pixels[index + 1] !== target_col.levels[1] &&
            pixels[index + 2] !== target_col.levels[2] &&
            pixels[index + 3] !== target_col.levels[3]
        ) {
            return;
        } else {
            drawing.push(new Pixel(x, y, replace_col));
            floodFill(x, y - 1, target_col, replace_col);
            floodFill(x, y + 1, target_col, replace_col);
            floodFill(x - 1, y, target_col, replace_col);
            floodFill(x + 1, y, target_col, replace_col);
        }
    }
}

this is how i call the function:

if (mode === "fill") {
    loadPixels();
    let index = (mouseX + mouseY * width) * 4;

    // target_color = what the user wants to replace
    let target_color = color(
        pixels[index],
        pixels[index + 1],
        pixels[index + 2],
        pixels[index + 3]
    );
   // replacement_color = the color that will be instead of the target_color
   let replacement_color = color(current_color);
    floodFill(mouseX, mouseY, target_color, replacement_color);
}

by the way in the floodFill function in the else if i used this technique because simply doing color(pixels[index], pixels[index + 1], pixels[index + 2], pixels[index + 3]) !== target_col didn't work

EDIT: I realized i had an error with the floodFill function, my else if is almost never true because it also tries to check if the alphas are not equal and they are almost always 255. so i added to the else if this:

else if (
     (pixels[index] !== target_col.levels[0] &&
         pixels[index + 1] !== target_col.levels[1] &&
        pixels[index + 2] !== target_col.levels[2]) ||
    pixels[index + 3] !== target_col.levels[3]
 ) {

now what happens is if i try to fill something it draws a straight line up until it reaches the other color, but then reaches maximum stack size, example: paint this is probably because in the floodFill function the first recursive call i make is to y - 1 (up). I would love to hear more suggestions

ANOTHER EDIT: i figured out that in the floodFill in the recursive section im calling it with y - 1 then with y + 1 which makes no sense because it goes up and then down means it stays at the same pixel, so i edited it to be like this:

floodFill(x, y - 1, target_col, replace_col);
floodFill(x - 1, y, target_col, replace_col);
floodFill(x, y + 1, target_col, replace_col);
floodFill(x + 1, y, target_col, replace_col);

now it shows up like this: paint

Upvotes: 1

Views: 2456

Answers (1)

Spongman
Spongman

Reputation: 9881

here's a fill example in p5.js.

draw a closed shape in the cavas, and then shift-click inside it.

var stack = [];
var oldColor;
var fillColor


function setup() {
  createCanvas(windowWidth, windowHeight);
  noSmooth();
  fillColor = color(0, 255, 0);
}

function windowResized() {
  resizeCanvas(windowWidth, windowHeight);
}

function draw() {

  function matches(c, x, y) {
    return JSON.stringify(get(x, y)) === JSON.stringify(c);
  }

  if (!stack.length) return;

  let p = stack.pop();
  let x1 = p.x, y = p.y;
  while (x1 > 0 && matches(oldColor, x1 - 1, y))
    x1--;

  let spanAbove = false, spanBelow = false;

  for (let x2 = x1 + 1; x2 < width && matches(oldColor, x2, y); ++x2) {
    set(x2, y, fillColor);

    if (y > 0 && spanAbove !== matches(oldColor, x2, y - 1)) {
      if (!spanAbove)
        stack.push({ x: x2, y: y - 1 });
      spanAbove = !spanAbove;
    }
    if (y < height - 1 && spanBelow !== matches(oldColor, x2, y + 1)) {
      if (!spanBelow)
        stack.push({ x: x2, y: y + 1 });
      spanBelow = !spanBelow;
    }
  }

  updatePixels();
}

function mouseDragged() {
  if (keyIsDown(SHIFT)) return;
  stroke(255);
  strokeWeight(2);
  line(pmouseX, pmouseY, mouseX, mouseY);
}

function mouseClicked() {
  if (keyIsDown(SHIFT)) {
    oldColor = get(mouseX, mouseY);
    loadPixels();
    stack = [];
    stack.push({ x: mouseX, y: mouseY });
  }
}
html,
body {
  margin: 0;
  padding: 0;
  border: none;
  background: black;
}

canvas {
  display: block;
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.3/p5.js"></script>

Upvotes: 2

Related Questions