We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
IndexProgramming Questions & HelpPrograms › floodfill help (stackerror)
Page Index Toggle Pages: 1
floodfill help (stackerror) (Read 4092 times)
floodfill help (stackerror)
Jan 31st, 2006, 4:02pm
 
Hi, I've implemented a floodfill algoritihm and it's like this:

void floodeja(int i, int j){
 color c=pintar.pixels[j*width+i];
 pintar.set(i,j,px);
 if((i<width)&&(pintar.pixels[j*width+(i+1)]==c)) floodeja(i+1,j);
 if((i>0)&&(pintar.pixels[j*width+(i-1)]==c))floodeja(i-1,j);
 if((j>0)&&(pintar.pixels[(j-1)*width+i]==c))floodeja(i,j-1);
 if((j<height)&&(pintar.pixels[(j+1)*width+i]==c))floodeja(i,j+1);
}

As you can see, it checks for the next pixel color, and if it's the same as the one you're, it floods again. The problem it's that with big regions crashes with a stackOverflowError. Can you think any kind of improve wich lend me flood big areas?

Sorry for my bad english, and thanks in advanced.
Re: floodfill help (stackerror)
Reply #1 - Jan 31st, 2006, 7:55pm
 
you need to test if i<(width-1), since you access j*width+(i+1) since i=width is outside of the image, it goes from 0 to width-1 and 0 to height-1.
Re: floodfill help (stackerror)
Reply #2 - Feb 1st, 2006, 2:18am
 
Already tried it. Problem it's not here Sad Is there a way to give more memory to the stack? I really don't know what to do :/

Re: floodfill help (stackerror)
Reply #3 - Feb 1st, 2006, 12:05pm
 
Have you changed the test on j as well? since that will overflow too.

The problem isn't that the stack is too small, it's that you're trying to read/write to part fo the stack that wasn't allocateto the area you're trying to access.

E.g. you'll get that error if you do:
Code:

int []a=new int[2];
a[0]=0;
a[1]=1;
a[2]=2; // <--- this will cause a stack overflow, a only contains 2 elements
// a[0] and a[1]. a[2] is outside the array and so you're trying to write to
//an arbitary location on the stack which isn't allowed.
Re: floodfill help (stackerror)
Reply #4 - Feb 1st, 2006, 1:33pm
 
Yes, I changed j as well. Anyway, the problem is not here, as I'm "floodfilling" an area wich is not near the sides of the image, and it keeps crashing...

full code: http://pastebin.com/533626


image : http://www.linkyourfiles.com/files/125/rod.jpg


thanks for all Smiley
Re: floodfill help (stackerror)
Reply #5 - Feb 1st, 2006, 2:03pm
 
hey,

maybe a different algorithm would help you to reduce the "pressure" put on the Java stack...

Here's a really oldskool floodfiller converted from some old TurboBasicXL code I still got flying around... This one's got to be more stack friendly since the RAM limitations back then were a bit more extreme... Wink

example: http://toxi.co.uk/p5/floodfill/ - click to fill shapes with random colour

Code:
void setup() {
size(800,800);
//image(loadImage("test.gif"),0,0);
noFill();
stroke(255);
for(int i=0; i<20; i++) {
ellipse(random(width),random(height),random(width),random(height));
}
loadPixels();
}

void draw() {
}

void mouseReleased() {
floodFill(
new Vec2D(mouseX,mouseY), /* current mouse pos as point object */
0xff<<24|(int)random(0xffffff), /* random colour (need to set alpha too) */
get(mouseX,mouseY) /* current colour under mouse position */
);
updatePixels();
}

/**
* a stack friendly scanline flood filler
* based on some old atari turbobasic code
*/
void floodFill(Vec2D p, int col, int prevCol) {
int xx,idx;
int h1=height-1;
boolean scanUp,scanDown;

// don't run if fill colour the same as bg
if(prevCol==col) return;

// use the default java stack:
// http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html
Stack stack=new Stack();

// the Stack class is throwing exceptions
// when we're trying to pop() too often...
// so we need to wrap code inside a try - catch block
try {
while(p!=null) {
xx = p.x;
// compute current index in pixel buffer array
idx=p.y*width+xx;
// find left boundary in current scanline...
while(xx >= 0 && pixels[idx] == prevCol) {
xx--;
idx--;
}
scanUp = scanDown = false;
// ...now continue scanning/filling to the right,
// checking neighbouring pixel rows
while(++xx < width && pixels[++idx] == prevCol) {
pixels[idx] = col;
if(!scanUp && p.y > 0 && pixels[idx-width] == prevCol) {
stack.push(new Vec2D(xx, p.y-1));
scanUp = true;
}
else if(scanUp && p.y > 0 && pixels[idx-width] != prevCol) {
scanUp = false;
}
if(!scanDown && p.y < h1 && pixels[idx+width] == prevCol) {
stack.push(new Vec2D(xx, p.y+1));
scanDown = true;
}
else if(scanDown && p.y < h1 && pixels[idx+width] != prevCol) {
scanDown = false;
}
}
p=(Vec2D)stack.pop();
}
}
// catch exceptions...
// stack is empty when we're finished filling, so just ignore
catch(EmptyStackException e) {
}
// catch other exceptions
// e.g. OutOfMemoryException, though shouldn't be caused by filler
catch(Exception e) {
}
}

/**
* simple 2D coordinate wrapper
*/
class Vec2D {
public int x,y;

Vec2D(int x,int y) {
this.x=x;
this.y=y;
}
}
Re: floodfill help (stackerror)
Reply #6 - Feb 1st, 2006, 2:13pm
 
I put your function in a while structure and it works:

Code:

PImage pintar;
void setup(){
pintar = loadImage("rod.jpg");
size(pintar.width, pintar.height);
int i=pintar.width/2;
int j=pintar.height/2;
boolean b=true;
while(b){
pintar.loadPixels();
color c=pintar.pixels[j*width+i];
pintar.set(i,j,color(0,255,0));
if((i<width-1)&&(pintar.pixels[j*width+(i+1)]==c)){
i++;
}
else if((i-1>0)&&(pintar.pixels[j*width+(i-1)]==c)){
i--;
}
else if((j-1>0)&&(pintar.pixels[(j-1)*width+i]==c)){
j--;
}
else if((j<height-1)&&(pintar.pixels[(j+1)*width+i]==c)){
j++;
}
else{
b=false;
}
pintar.updatePixels();
}

}

void draw(){
image(pintar,0,0);
}

Re: floodfill help (stackerror)
Reply #7 - Feb 2nd, 2006, 12:23am
 
to eskimoblood:

If tried your code.. and it doesn't work... it does not paint all the region. Anyway, thank for taking your time! Smiley

to toxi:

Nice one! I'll try to use it, alhought it seems a bit slow. Thanks to you too!

Thanks both, you guys are worth Wink
Re: floodfill help (stackerror)
Reply #8 - Feb 2nd, 2006, 1:50pm
 
my code above was actually quite wasteful by missing opportunities to fill when scanning along a pixel row to the left. below is an updated version to fix this (and a few other tidbits), also updated the example online. it's still not the non-plus-ultra but in general should be much faster than your original recursive method.

btw. another reason why the previous demo applet felt quite sluggish is because using updatePixels() with the P2D renderer is very slow. For the new one i switched to P3D...

Code:
/**
* (updated) stack friendly scanline flood filler
*/
void floodFill(Vec2D p, int col, int bg) {
int xx,yy,idx,idxUp,idxDown;
int h1=height-1;
boolean scanUp,scanDown;

// don't run if fill colour the same as bg
if(bg==col) return;

// use the default java stack:
// http://java.sun.com/j2se/1.4.2/docs/api/java/util/Stack.html
Stack stack=new Stack();

// the Stack class is throwing an exception
// when we're trying to pop() too often...
// so we need to wrap code inside a try - catch block
try {
while(true) {
xx = p.x;
yy = p.y;
// compute current index in pixel buffer array
idx=yy*width+xx;
idxUp=idx-width;
idxDown=idx+width;
scanUp = scanDown = false;
// fill until left boundary in current scanline...
// checking neighbouring pixel rows
while(xx >= 0 && pixels[idx] == bg) {
pixels[idx] = col;
if (yy>0) {
if (pixels[idxUp--]==bg && !scanUp) {
stack.push(new Vec2D(xx, yy-1));
scanUp = true;
}
else if (scanUp) scanUp=false;
}
if (yy < h1) {
if (pixels[idxDown--]==bg && !scanDown) {
stack.push(new Vec2D(xx, yy+1));
scanDown = true;
}
else if (scanDown) scanDown=false;
}
xx--;
idx--;
}
// ...now continue scanning/filling to the right
xx = p.x;
yy = p.y;
idx = yy*width+xx;
idxUp=idx-width;
idxDown=idx+width;
scanUp = scanDown = false;
while(++xx < width && pixels[++idx] == bg) {
pixels[idx] = col;
if (yy>0) {
if (pixels[++idxUp]==bg && !scanUp) {
stack.push(new Vec2D(xx, yy-1));
scanUp = true;
}
else if (scanUp) scanUp=false;
}
if (yy<h1) {
if (pixels[++idxDown]==bg && !scanDown) {
stack.push(new Vec2D(xx, yy+1));
scanDown = true;
}
else if (scanDown) scanDown=false;
}
}
p=(Vec2D)stack.pop();
}
}
// catch exceptions...
// stack is empty when we're finished filling, so just ignore
catch(EmptyStackException e) {
}
// catch other exceptions
// e.g. OutOfMemoryException, though shouldn't be caused by filler
catch(Exception e) {
}
}
Re: floodfill help (stackerror)
Reply #9 - Aug 19th, 2009, 6:37pm
 
I know this thread is very old, but i will try anyway.

I am using the above code but i am drawing shapes with noStroke() and only fill(myColor).

I would like the floodfill to color the edges differently.
basically when the code notices that the next pixel is one of a different color that draw the current pixel Black.

i hope some can help.
thanks so much,
stephan.

Re: floodfill help (stackerror)
Reply #10 - Aug 20th, 2009, 9:14am
 
Toxi's implementation is nice!
I played a bit with his code, dropping the old, synchronized Stack in favor of an ArrayList (would use a Deque but it is Java 1.6 so Mac users would be excluded), avoiding duplicate code (going left and right), perhaps at the cost of slight performance hit (not even sure) but being more readable (IMHO). In short, I rewrote it for fun and profit (ie. learning purposes, understanding how it works...).
Oh, and slightly generalized the implementation to accept any PImage (although I haven't tested this yet).

Here is my version:
ShowFloodFill.pde Code:
boolean bWithBorder;

void setup()
{
size(800,800);
image(loadImage("FloodFillTest.png"), 0, 0);
loadPixels();
}

void draw()
{
}

void mouseReleased()
{
if (bWithBorder)
{
FloodFillWithBorder ff = new FloodFillWithBorder();
ff.DoFill(
mouseX, mouseY, // current mouse pos as point object
GetRandomColor(),
GetRandomColor()
);
}
else
{
FloodFill ff = new FloodFill();
ff.DoFill(
mouseX, mouseY, // current mouse pos as point object
GetRandomColor()
);
}
updatePixels();
}

void keyPressed()
{
if (key == 'b')
{
bWithBorder = true;
println("With border");
}
else if (key == 'n')
{
bWithBorder = false;
println("Plain");
}
}

color GetRandomColor()
{
return 0xFF000000 | (int) random(0x1000000); // random color (need to set alpha too)
}

I wrapped the function in a class, a bit wasteful but it was a way to share data between functions without passing lot of parameters...
The implementation itself:
FloodFill.pde Code:
public class FloodFill
{
protected int iw; // Image width
protected int ih; // Image height
protected color[] imagePixels;
protected color backColor; // Color found at given position
protected color fillColor; // Color to apply
// Stack is almost deprecated and slow (synchronized).
// I would use Deque but that's Java 1.6, excluding current (mid-2009) Macs...
protected ArrayList stack = new ArrayList();

public FloodFill()
{
iw = width;
ih = height;
imagePixels = pixels; // Assume loadPixels have been done before
}

public FloodFill(PImage imageToProcess)
{
iw = imageToProcess.width;
ih = imageToProcess.height;
imagePixels = imageToProcess.pixels; // Assume loadPixels have been done before if sketch image
}

public void DoFill(int startX, int startY, color fc)
{
fillColor = fc;
backColor = imagePixels[startX + startY * iw];
// don't run if fill color is the same as background one
if (fillColor == backColor)
return;

stack.add(new PVector(startX, startY));
while (stack.size() > 0)
{
PVector p = (PVector) stack.remove(stack.size() - 1);
FillScanLine((int) p.x, (int) p.y, -1);
FillScanLine((int) p.x + 1, (int) p.y, 1);
}
}

protected void FillScanLine(int x, int y, int dir)
{
// compute current index in pixel buffer array
int idx = x + y * iw;
boolean inColorRunAbove = false;
boolean inColorRunBelow = false;

// fill until boundary in current scanline...
// checking neighbouring pixel rows
while (x >= 0 && x < iw && imagePixels[idx] == backColor)
{
imagePixels[idx] = fillColor;
if (y > 0) // Not on top line
{
if (imagePixels[idx - iw] == backColor)
{
if (!inColorRunAbove)
{
// The above pixel needs to be flooded too, we memorize the fact.
// Only once per run of pixels of back color (hence the inColorRunAbove test)
stack.add(new PVector(x, y-1));
inColorRunAbove = true;
}
}
else // End of color run (or none)
{
inColorRunAbove = false;
}
}
if (y < ih - 1) // Not on bottom line
{
if (imagePixels[idx + iw] == backColor)
{
if (!inColorRunBelow)
{
// Idem with pixel below, remember to process there
stack.add(new PVector(x, y + 1));
inColorRunBelow = true;
}
}
else // End of color run (or none)
{
inColorRunBelow = false;
}
}
// Continue in given direction
x += dir;
idx += dir;
}
}
}

The version with border comes in next message (out of space!).
Re: floodfill help (stackerror)
Reply #11 - Aug 20th, 2009, 9:16am
 
FloodFillWithBorder.pde Code:
public class FloodFillWithBorder extends FloodFill
{
private color borderColor; // Color of border

public FloodFillWithBorder()
{
super();
}

public FloodFillWithBorder(PImage imageToProcess)
{
super(imageToProcess);
}

public void DoFill(int startX, int startY, color fc, color bc)
{
// don't run if border color is the same as background one
if (bc == backColor)
return;
borderColor = bc;
DoFill(startX, startY, fc);
}

protected void FillScanLine(int x, int y, int dir)
{
// compute current index in pixel buffer array
int idx = x + y * iw;
boolean inColorRunAbove = false;
boolean inColorRunBelow = false;
int borderIdx = -1;

// Particular case when start position is just on the left
// of a boundary
if (dir < 0 && x < iw - 1 &&
imagePixels[idx] == backColor &&
imagePixels[idx + 1] != backColor)
{
borderIdx = idx;
}

// fill until boundary in current scanline...
// checking neighbouring pixel rows
while (x >= 0 && x < iw && imagePixels[idx] == backColor)
{
// If we are at a color boundary (in the horizontal axis)
if (dir < 0 && x > 0 && imagePixels[idx - 1] != backColor ||
dir > 0 && x < iw - 1 && imagePixels[idx + 1] != backColor)
{
// We paint the pixel with the border color
imagePixels[idx] = borderColor;
}
else
{
imagePixels[idx] = fillColor;
}
if (y > 0) // Not on top line
{
if (imagePixels[idx - iw] == backColor)
{
if (!inColorRunAbove)
{
// The above pixel needs to be flooded too, we memorize the fact.
// Only once per run of pixels of back color (hence the inColorRunAbove test)
stack.add(new PVector(x, y-1));
inColorRunAbove = true;
}
}
else // End of color run (or none)
{
inColorRunAbove = false;
// If the above line is neither of fill color (we are on boundary)
// nor of border color (it is an already painted border)
if (imagePixels[idx - iw] != fillColor && imagePixels[idx - iw] != borderColor)
{
// We are on a boundary on the vertical axis, paint it
imagePixels[idx] = borderColor;
}
}
}
if (y < ih - 1) // Not on bottom line
{
if (imagePixels[idx + iw] == backColor)
{
if (!inColorRunBelow)
{
// Idem with pixel below, remember to process there
stack.add(new PVector(x, y + 1));
inColorRunBelow = true;
}
}
else // End of color run (or none)
{
inColorRunBelow = false;
// Same as above with below line
if (imagePixels[idx + iw] != fillColor && imagePixels[idx + iw] != borderColor)
{
imagePixels[idx] = borderColor;
}
}
}
// Continue in given direction
x += dir;
idx += dir;
}
if (borderIdx >= 0)
{
imagePixels[borderIdx] = borderColor;
}
}
}
[EDIT] Corrected the artifact described below.
Out of laziness (still avoiding to write redundant code), I just extended the FloodFill class.
If you use only the version with border, you might want to flatten the implementation, it might improve the performance slightly (not even sure...).
The version with border is much slower than the base version, having to do more tests and write more pixels...
Re: floodfill help (stackerror)
Reply #12 - Aug 20th, 2009, 11:01am
 
thanks so much for the fast reply.
Re: floodfill help (stackerror)
Reply #13 - Aug 21st, 2009, 4:48pm
 
Hey PhiLho

I noticed your border finding is not working completly. See image. it leaves out sections. i made it to draw borders black.

I will investigate this myself too but thought maybe you already know why.

http://www.maybevideodoes.de/download/flood.png
...

Thanks,
Stephan
Re: floodfill help (stackerror)
Reply #14 - Aug 22nd, 2009, 4:27am
 
Puzzling thing is that the border depends on where you click...
I finally found out a pattern in the gap, and found a fix.

[EDIT] Moved code from there to the message above, no need to keep an incorrect code.

YaBB is doing something strange to code, it changes some of my space tabulations to hardcoded tabs, indenting too much some lines...

Note: it doesn't put border against the sketch borders. If that's OK, perfect, otherwise the method needs some more conditionals...
Page Index Toggle Pages: 1