-
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?
Please help.
-
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?
-
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.
-
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.
-
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
..first return address
..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
..third return address
..parameter4
..parameter3
..parameter2
..parameter1
..fourth return address
..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.
-
The stack will actually be much larger than that on the first complete iteration, but I simplified it for the post.
-
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???
-
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.
-
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;
}
-
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 :(...
-
-
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.
-
>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...
-
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.
-
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.
-
>except that the floodfill quality suffers
how's that? the idea of segmenting the target image, checking adjacency, and running through your call with a maximum reiterative depth should work as well as if you didn't have the problem of the stack. and i might do this before dealing with the stack manually, but as i'm aware you are more handy with the stack than i am so it's at your discretion...
-
Yes the quality does suffer. Since the algorithm is recursive, any small adjustment to the main algo, or the way in which it is called can cause catastrophic effects. Remember, that one mistake or incosistency will be multiplied literally thousands of times resulting in poor floodfill.
-
-
well it doesn't have be completely reiterative... for example call a setup function which does call the filling function with adjacently connected solid colorstate... if your maximum possibly filled coordinate plane is 640 by 480, call every hmm... 10 pixels [2d isometricallly tho, since those are the nature of the rate of spreading in your function...]... hmm we'll have to talk about this in live bubba, get online if you can... asap... it'd be easier to describe... oh, or you could use salem's references btw, but that wouldn't be as fun would it! :) DOS- ON!
-
Salem you are talking about the parity algo. You check on the line that was clicked and go left and right from origin. If the value is 1, you have left the figure, if the number is 2, you are back in the figure, if the number is 3, draw a line on current scanline between 2 and 3, and so on, and so on.
That would work. And it should fill arbitrary shapes. I saw that algo in my research, I just was not sure whether to use it or not.
Similar to the polygon fill algo which is used to get a solid fill of polygons at an arbitrary angle.
There is one problem, that I can see. What if there is another figure left/right of the current figure and the same color as the current one, but not attached to the current figure. It would still fill that shape since it met the requirements.
-
The second link looks more promising than the first. I need to fill an area that does not have defined points - like drawing a shape in a drawing program and then filling it.
I already know how to fill/texture vertex based polies.
Thanks Salem for the links. I looked through several pages of searches, but did not find the second link. I did find the first on my own, however.
-
oh i see the behaivior now... if you do unwinding with a switch on the reiterative statement, [setting a static unwinding flag, which if set takes the case of an empty function, thus returning until the depth of recursion is to a lower level], you'd have to save the coordinates where to redo the loop, as well as save those coordinates where the path diverged [first began to reiterate, to fill the left holes after each unwinding which are lost when you lose the recursion from manual unwinding]. Hmm that's a mouthful...
-
Hey. I am new to C++ but from what i have read of this thread, the stack is receiving every single parameter you pass, and thus making it stack up very quickly. (f i am wrong in my thinking anywhere, feel free to let me know)
In order to lessen your parameters, you could use a static variable or a global variable to get the parameters through without using them as parameters, or you could group parameters together with a class or struct and just pass that (or a ref to that if speed is a concern).
I may be wrong!
thanx for taking the time to read.
~Inquirer
