# FloodFill stack overflow

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 03-12-2002
VirtualAce
FloodFill stack overflow
I'm doing a small drawing program and trying to implement a floodfill.

My problem is that the stack keeps overflowing, obviously because the recursion is to deep. I've tried this code in DOS and in Windows and both cause stack overflows. I've also looked for an iterative algorithm for this, but all the docs and sites use the recursive one. However, they fail to mention that since you are pushing return addresses on the stack every time you call a function, that the stack can overflow if it does not return.

Code:

```//256 color example //hi-color would use RGB color or RGBA color void FloodFill(int x,int y,int color,int oldcolor) {   if (x<left || x>right || y<top || y>bottom) return;   int test=GetPixel(x,y);     if (test==oldcolor)   {     PlotPixel(x,y,color);     FloodFill(x+1,y,color,oldcolor);     FloodFill(x,y+1,color,oldcolor);     FloodFill(x-1,y,color,oldcolor);     FloodFill(x,y-1,color,oldcolor);   }   else return; }```
But this will cause the stack to overflow even with a stack size of 64000 bytes, which is very large.

There has to be a way to floodfill w/o overflowing the stack.

On hi-res screens, this will need a very large stack ((width*height)/4) and for hi-color it will need even more.
Is there a better way?

• 03-19-2002
kbw
As you may already know, iterative and recursive algorithms are interchangeable. As far as I can tell, your algorithm is equivalent to:

void fill(int left, int right, int top, int bottom, int oldcol, int newcol)
{
int x, y;
for (x = left; x <= right; x++)
for (y = top; y <= bottom; y++)
if (GetPixel(x, y) == oldcol)
PlotPixel(x, y, newcol);
}

That changes all pixels within the ranged rectangle. I've thought of floodfills filling areas bounded by a different colour. Which effect do you want?
• 03-19-2002
VirtualAce
No those two functions are not equivalent at all.

Your function will only fill a square. My function will fill any shape, within certain limits. It can get stuck in corners and tight spots but normally it works well.

I'm trying to find a way to stop the stack from overflowing.
• 04-03-2002
sean
There was a similar post in this forum very recently about how to get more memory. They mention some .SYS and .386 (and if you're using XP at all, .386 probably won't work) files, and they somehow helped you get more RAM available to the program. Look it up.
• 04-03-2002
VirtualAce
No, no, no. That will not help, trust me. The problem is the stack, not the memory. The stack will overflow because each time you call a function, the return address and any parameters are pushed onto the stack. In my function, the parameters are popped off of the stack, and the return address is popped off at the end of each function and finally at the end of each call. However, the problem is that prior to these being popped off of the stack, they are causing the stack to overflow. I've tried this with a very large stack and it still overflows. Memory, or at least the way you are thinking about it, has nothing whatsoever to do with my problem.

Stacks use memory, but it is not how you are thinking. Now it might be possible to set my stack segment to the EMS page frame, but that logical frame is only 16kb in size. I would also have to check if the stack is larger than that and if so map diff logical pages to the physical page. However, this program would crash hard, because the stack would have to be unwound inside of EMS and across multiple logical pages, which is both too complex and too risky to implement in pure C.

STACK
..parameter4
..parameter3
..parameter2
..parameter1

This is the stack frame (simplified) upon entry during the first iteration. After 1 complete iteration it will look like this.

STACK
..first return address -> first call -> DWORD
..parameter4 -> WORD
..parameter3 -> WORD
..parameter2 -> WORD
..parameter1 -> WORD
..second return address ->same as above for all calls
..parameter4
..parameter3
..parameter2
..parameter1
..parameter4
..parameter3
..parameter2
..parameter1
..parameter4
..parameter3
..parameter2
..parameter1

This will continue until the function is done. If you know how the stack works, you can easily see why it can overflow very quickly.
• 04-03-2002
VirtualAce
The stack will actually be much larger than that on the first complete iteration, but I simplified it for the post.
• 04-04-2002
muttski
Does that actually work as a flood fill, thats really quite simple compared to what I thought it would have to be. I dont quite understand how it works, it fills in the area sourounded by a certain color???
• 04-04-2002
muttski
Ok I see, it replaces every certain color on the screen with a new color, not quite a flood fill, or am I wrong? If I were you I would re-write it so it doesnt have to call its self.
• 04-04-2002
muttski
Sorry sorry sorry, im wrong I didnt see the "else return", thats a quite cleaver idea for floodfill, mind if I use it? Im not sure how to help you with the stack, but I have an idea how to make it better:

Code:

``` int MuttFloodFill(int x, int y, int col) {   BubbaFloodFill(x, y, col, getpixel(x, y));   return 0; }```
• 04-04-2002
Magos
Deja vu
I had the exact same problem as you do, I found no solution however. I wanted a filling function for my drawing program as well (see the link in my signature). The fill-function is commented in the source, it is not functional though :(...
• 04-04-2002
muttski
Damn, thats hard.
• 04-04-2002
VirtualAce
Muttski you crack me up with your posts. LOL

BubbaFloodFill() - LOL

Actually, I got the algo off of a website somewhere and it works very well, except for the stack overflow which is bugging me cuz I don't know how to fix it.

If anyone knows how to fix this problem, I'd love to hear it.
• 04-05-2002
doubleanti
>iterative and recursive algorithms are interchangeable

not necessarily... for example in the mandlebrot set, if you could calculate it without partial sums and checks for divergence in a reiterative calculation... why... my dream of a high color realtime set browser would have been done years ago...

oh and for this.. hmm... here's my recommendation... suppose an upper limit for recursive process [before stack overflow] were set... [suppose 10 pixels]... so you'd scan your image every 10 pixels in both axis, and check for adjacency [indicating a solid pathway between nodes] if it checked out, you could flood both sections... else it was a seperate piece... this is some really genius code... and either partitioning, or saving coordinates to globals and unwinding your reiteration would be my best shots at your problem bubba...
• 04-05-2002
VirtualAce
Well I have tried some of those techniques and they work, except that the floodfill quality suffers and more areas are missed than normal. This, in itself, is totally unacceptable for a floodfill.

The only thing I have not tried to do is unwind the stack manually after so many iterations. Since I know what the stack looks like and how much is on the stack (in bytes, and bytes per iteration), I could manually unwind the stack, but this would, in theory, cause many more problems.
• 04-05-2002
muttski
Well, your screwed cause that wont work cause dont functions need to keep important stuff like where to return and stuff? so if someone fills a small 320x200 screen each function call will take 4 at least bytes, and you get the idea. If you figure it out without big scary 10000000 line code please pm me.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last