Why is stack getting overflowed in this code?

Question

Hi, I wrote this function for filling closed loop, pixvali is declared globally to store the color value of the pixel where the first click will be done (inside the closed loop).

But the problem is that this recursion doesn't terminate when its first fill(..,..)get over, and it says stack is overflowed...

void fill(int x,int y)
{
    GLfloat pixval[3];
    glReadPixels(x,y,1,1,GL_RGB,GL_FLOAT,pixval);
    if(pixval[0]==pixvali[0] && pixval[1]==pixvali[1] && pixval[2]== pixvali[2])
    {
     glBegin(GL_POINTS);
      glVertex2i(x,y);
     glEnd();
     glFlush();
     fill(x-1,y);
     fill(x+1,y);
     fill(x,y-1);
     fill(x,y+1);
    } 
}

Answer 1

instead you may use the following if it does not hurt the code;

...
    fill(x-1,y);
    fill(x,y-1);
    fill(x,y+1);
    fill(x+1,y); // change order
...

Answer 2

The stack overflows because you are using recursion, and the depth of the recursion is linear in the number of pixels in the shape you're filling.

It may also be that you are trying to fill the shape in the same color as it already is. That is, the current gl color is the same as pixvali. In that case, you'll get infinite recursion.

Answer 3

It's kind of hard to tell from the question, but my guess would be that, you begin going in a loop of pixels.

For example, think that you have only 4 pixels that you need to color (0,0), (0,1), (1,0), (1,1).

You begin coloring (0,0). Then your recursion will enter (1,0) since(-1,0) doesn't need coloring. then (0,0) again since, it's the pixel that is (x-1, y) again and so on.

You need to add some way to mark pixels that have been colored already. But that's just a guess because you can't really see what's going on outside that functions.

Answer 4

implement your own stack, don't use recursion for flood fill unless you are filling shapes with relatively small surface area in terms of pixels.

a typical implementation is:

Stack stack; 
stack.push(firstPoint);

while(!stack.isEmpty()){
   Point currentPoint= stack.pop();
   //do what ever you want to do here, namely paint.
   //boundary check ur surrounding points and push them in the stack if they are inbounds
}

Answer 5

Not sure of the implementation details, but if the 12 byte local array is allocated on the stack (3 floats a 4 bytes each), then you have 4 bytes each for the x and y parameters, and probably four bytes for the return address. That gives at least 24 every time you recurse. That means you only need a bit more than 40'000 calls to blow through 1MB of stack space, if there's nothing else on it, which won't be true.

To put that in perspective, 43'690 pixels is only about 10% of an 800x600 display.

Answer 6

You need to check what pixels are you editing.

e.g. If you have an image from 0,0 to 10,10 and you edit 11,10 you will get outside of memory.

So you need to check if x,y is between the boundaries of the image.

x>=left&&x<=right&&y>=top&&y<=bottom

Answer 7

At first glance, the algorithm looks good. I'm a bit worried about the "==" because they don't work well with float values. I suggest to use

abs(val1 - val2) < limit

instead (where limit is < 1 and > 0. Try 0.0001, for example).

To track down the bug, I suggest to add a printf() at the beginning of the function. When you see what the function tries to fill, that will help. Maybe it is stuck somewhere and calls itself again and again with the same coordinates?

Also, the stack may simple be too small for the area you try to fill. Try with a small area first, say a small rectangle only 4 by 3 pixels. Don't try to click it with the mouse but start with a known good point inside (just call fill() in your code).

Also printing the values for the color could help.