Thread: FloodFill stack overflow

  1. #1
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607

    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.

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1
    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?

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    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.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  6. #6
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    The stack will actually be much larger than that on the first complete iteration, but I simplified it for the post.

  7. #7
    muttski
    Guest
    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???

  8. #8
    muttski
    Guest
    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.

  9. #9
    Registered User
    Join Date
    Apr 2002
    Posts
    129
    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;
    }
    flashdaddee.com rocks!!!

  10. #10
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145

    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 ...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  11. #11
    Registered User
    Join Date
    Apr 2002
    Posts
    129
    Damn, thats hard.

  12. #12
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  13. #13
    Linguistic Engineer... doubleanti's Avatar
    Join Date
    Aug 2001
    Location
    CA
    Posts
    2,459
    >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...
    hasafraggin shizigishin oppashigger...

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  15. #15
    Registered User
    Join Date
    Apr 2002
    Posts
    129
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack overflow errors in 3 areas
    By ulillillia in forum C Programming
    Replies: 13
    Last Post: 04-29-2007, 03:20 PM
  2. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 10:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 06:27 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM