Flood Fill tool P5.js

0
votes

I'm here again because I'm still having trouble trying to implement a flood fill tool in my drawing app.

I am attempting to make a fairly simple 2d paint application using p5.js with each drawing tool having its own constructor function. I've been having trouble understanding what I am doing wrong and why it is not working which is causing lots of frustration.

I have read a few articles on here and followed a tutorial on youtube but I still don't quite understand it. I will include what I have done so far so you can see. Specifically, I am not sure what to write for the draw function. I would like the flood fill to happen on mouseX and mouseY coordinates when the mouse is pressed. Also, I would like for the target colour to be a colour selected from a separate constructor function ColourPalette().

HTML:

        <!DOCTYPE html>
        <html>
          <head>
            <script src="lib/p5.min.js"></script>
            <script src="lib/p5.dom.js"></script>
        
            <script src="sketch.js"></script>
        
            <!-- add extra scripts below -->
...
            <script src="fillTool.js"></script>
        
          </body>
        </html>

The sketch file:

function setup() {
    

    //create a canvas to fill the content div from index.html
    canvasContainer = select('#content');
    var c = createCanvas(canvasContainer.size().width, canvasContainer.size().height);
    c.parent("content");
    

    //create helper functions and the colour palette
    helpers = new HelperFunctions();
    colourP = new ColourPalette();

...
    toolbox.addTool(new FillTool());
    background(255);

}

function draw() {
    //call the draw function from the selected tool.
    //if there isn't a draw method the app will alert the user
    if (toolbox.selectedTool.hasOwnProperty("draw")) {
        toolbox.selectedTool.draw();
    } else {
        alert("it doesn't look like your tool has a draw method!");
    }
}

The flood fill constructor function I need help with. I'm getting "Uncaught ReferenceError: floodFill is not defined" for line 112 (within the draw function) in the console and I'm a little stuck on how to fix it.:

function FillTool() {
    
//set an icon and a name for the object
this.icon = "assets/freehand.jpg";
this.name = "FillTool";
    
var colourNew = ColourPalette(colourP); //Placeholder - How do I do this?

    
function getPixelData(x,y){
  var colour = [];

  for (var i = 0; i < d; i++) {
    for (var j = 0; j < d; j++) {
      idx = 4 * ((y * d + j) * width * d + (x * d + i));
      colour[0] = pixels[idx];
      colour[1] = pixels[idx+1];
      colour[2] = pixels[idx+2];
      colour[3] = pixels[idx+3];
    }
  }

  return colour;
}

function setPixelData(x, y, colourNew) {
  for (var i = 0; i < d; i++) {
    for (var j = 0; j < d; j++) {
      idx = 4 * ((y * d + j) * width * d + (x * d + i));
      pixels[idx] = colourNew[0];
      pixels[idx+1] = colourNew[1];
      pixels[idx+2] = colourNew[2];
      pixels[idx+3] = colourNew[3];
    }
  }
}

function matchColour(xPos,yPos,oldColour){    
    var current = get(xPos,yPos);
    if(current[0] == oldColour[0] && current[1] == oldColour[1] && current[2] == oldColour[2] && current[3] == oldColour[3]){        
        return true;
    }    
}

function checkPixel(x1,y1,pixelArray){    
    for (var i = 0 ; i < pixelArray.length; i+=2){        
        if(x1 == pixelArray[i] && y1 == pixelArray[i+1]){                       
            return false;                    
           }
        else {               
           console.log(pixelArray.length)
           return true;             
            }
    } 
}


function floodFill (xPos,yPos){
    loadPixels();
    colourOld = getPixelData(xPos, yPos);
    var stack = [];
    var pixelList = [];
    stack.push(xPos,yPos);
    pixelList.push(xPos,yPos);
    console.log(stack);

    while(stack.length > 0){
        var yPos1 = stack.pop();
        var xPos1 = stack.pop();
        setPixelData(xPos1,yPos1,colourNew);

        if(xPos1 + 1 <= width && xPos1 + 1 > 0 ){
            if(matchColour(xPos1+1,yPos1,colourOld) && checkPixel(xPos1+1,yPos1,pixelList)){
                stack.push(xPos1+1,yPos1);
                pixelList.push(xPos1+1,yPos1);
            }
        }

        if(xPos1+1 <= width && xPos1+1 > 0 ){
            if(matchColour(xPos1-1,yPos1,colourOld) && checkPixel(xPos1-1,yPos1,pixelList)){
                stack.push(xPos1-1,yPos1);
                pixelList.push(xPos1-1,yPos1);
            }
        }
        if(yPos1+1 <= height && yPos1+1 > 0 ){
            if(matchColour(xPos1,yPos1+1,colourOld) && checkPixel(xPos1,yPos1+1,pixelList)){
                stack.push(xPos1,yPos1+1);
                pixelList.push(xPos1,yPos1+1);
            }
        }

        if(yPos1-1 <= height && yPos1-1 > 0 ){
            if(matchColour(xPos1,yPos1-1,colourOld) && checkPixel(xPos1,yPos1-1,pixelList)){
                stack.push(xPos1,yPos1-1);
                pixelList.push(xPos1,yPos1-1);
            }
        }
    }

    updatePixels();
    console.log(pixelList);
}  
}

this.draw = function() {

    if(mouseIsPressed){
        floodFill(mouseX,mouseY);
    }
}

Sorry if its a bit of a mess, it's an accurate representation of my brain at the moment.

1
javascriptloopsrecursionp5.js
Could you make a minimal working example. Use <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.0.0/p5.min.js"></script> in the html. Only put setup, draw, FillTool and the supporting functions and variables. This way you'll find more help then last time. - Dominique Fortin

1 Answers

0
votes

The function checkPixel was very very slow because pixelArray grows as you draw new pixels, so verifying if a new pixel was in the stack or had already been drawn took longer each time.

In javascript it is possible to use an object {} to store key/value pair like :

var colours = { 'red':{'r':255,'g':0,'b':0,'a':255}, 'black':{'r':0,'g':0,'b':0,'a':255} };

And calling the method hasOwnPorperty to verify the presence of the key is very fast.

colours.hasOwnPorperty('red') // is true
colours.hasOwnPorperty('green') // is false

If you had a 1,000,000 colours in colours, it would not take longer for hasOwnPorperty to find a colour in colours than if you had only 1 colour in colours. (It's O(1) has opposed to O(n) for your version of checkPixel)

Try clicking inside the circle ... or outside

let toolbox, d;

function setup() {
  createCanvas(600, 400);
  d = pixelDensity();

  //create helper functions and the colour palette
  //...
  let colourRed = ColourPalette(255,0,0,255);
  //...

  toolbox = {'selectedTool': new FillTool() }; 

  toolbox.selectedTool.setColour(colourRed);

  background(255);

  push();
  strokeWeight(1);
  stroke(0);
  circle(75,75,100);
  noStroke();
  fill(0,255,0,255);            
  circle(125,75,100);
  pop();
}

function draw() {
  if (! toolbox.selectedTool.hasOwnProperty("draw")) {
    alert("it doesn't look like your tool has a draw method!");
    return;
  }

  toolbox.selectedTool.draw();
}

function FillTool() {
  let self = this;

  //set an icon and a name for the object
  self.icon = "assets/freehand.jpg";
  self.name = "FillTool";
  self.colour = ColourPalette(0,0,0,255);

  self.draw = function () {
    if (mouseIsPressed) {
      floodFill(mouseX, mouseY);
    }
  };

  self.setColour = function (col) {
    self.colour = col;
  };

  function matchColour (pos, oldColour) {
    var current = getPixelData(pos.x, pos.y);
    return (   current[0] === oldColour[0] && current[1] === oldColour[1] 
            && current[2] === oldColour[2] && current[3] === oldColour[3] );
  }

  function getKey (pos) {
    return ""+pos.x+"_"+pos.y;
  }

  function checkPixel(pos, positionSet) { 
    return ! positionSet.hasOwnProperty( getKey(pos) );
  }

  function floodFill (xPos, yPos) {

    var stack = [];
    var pixelList = {};

    var first = {'x':xPos,'y':yPos};
    stack.push( first );
    pixelList[ getKey(first) ] = 1;

    //console.log( JSON.stringify(stack) );

    loadPixels();
    var firstColour = getPixelData(xPos, yPos);

    while (stack.length > 0) {

      var pos1 = stack.pop();

      setPixelData(pos1.x, pos1.y, self.colour);

      var up = {'x':pos1.x,  'y':pos1.y-1};
      var dn = {'x':pos1.x,  'y':pos1.y+1};
      var le = {'x':pos1.x-1,'y':pos1.y};
      var ri = {'x':pos1.x+1,'y':pos1.y};

      if (0 <= up.y && up.y < height && matchColour(up, firstColour)) addPixelToDraw(up);
      if (0 <= dn.y && dn.y < height && matchColour(dn, firstColour)) addPixelToDraw(dn);
      if (0 <= le.x && le.x < width  && matchColour(le, firstColour)) addPixelToDraw(le);
      if (0 <= ri.x && ri.x < width  && matchColour(ri, firstColour)) addPixelToDraw(ri);
    }

    updatePixels();

    //console.log( JSON.stringify(pixelList) );

    function addPixelToDraw (pos) {

      if (checkPixel(pos, pixelList)  ) {
        stack.push( pos );
        pixelList[ getKey(pos) ] = 1;
      }
    }
  }  

}


function ColourPalette (r,g,b,a) { 
  var self = (this !== window ? this : {});
  if (arguments.length === 0) {
    self['0'] = 0; self['1'] = 0; self['2'] = 0; self['3'] = 0;
  } else if (arguments.length === 1) {
    self['0'] = r[0]; self['1'] = r[1]; self['2'] = r[2];  self['3'] = r[3]; 
  } else if (arguments.length === 4) {
    self['0'] = r; self['1'] = g; self['2'] = b; self['3'] = a;
  } else {
    return null;
  }
  return self;
}


function getPixelData (x, y) {
  var colour = [];
  for (var i = 0; i < d; ++i) {
    for (var j = 0; j < d; ++j) {
      let idx = 4 * ((y * d + j) * width * d + (x * d + i));
      colour[0] = pixels[idx];
      colour[1] = pixels[idx+1];
      colour[2] = pixels[idx+2];
      colour[3] = pixels[idx+3];
    }
  }
  return colour;
}

function setPixelData (x, y, colour) {
  for (var i = 0; i < d; ++i) {
    for (var j = 0; j < d; ++j) {
      let idx = 4 * ((y * d + j) * width * d + (x * d + i));
      pixels[idx]   = colour[0];
      pixels[idx+1] = colour[1];
      pixels[idx+2] = colour[2];
      pixels[idx+3] = colour[3];
    }
  }
}
body { background-color:#efefef; }
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.0.0/p5.min.js"></script>