What causes the stackoverflow? And how can I resolve it?

Question

I was doing the homework for computer graphics. We need to use floodfill to paint an area, but no matter how I changed the reserve stack of Visual Studio, it would always jump out stackoverflow.

void Polygon_FloodFill(HDC hdc, int x0, int y0, int fillColor, int borderColor) {
int interiorColor;
interiorColor = GetPixel(hdc, x0, y0);
if ((interiorColor != borderColor) && (interiorColor != fillColor)) {
    SetPixel(hdc, x0, y0, fillColor);
    Polygon_FloodFill(hdc, x0 + 1, y0, fillColor, borderColor);
    Polygon_FloodFill(hdc, x0, y0 + 1, fillColor, borderColor);
    Polygon_FloodFill(hdc, x0 - 1 ,y0, fillColor, borderColor);
    Polygon_FloodFill(hdc, x0, y0 - 1, fillColor, borderColor);
}

I don't know about the question, but the title resonates – Gnudiff Mar 30 '19 at 14:00 — Gnudiff, Mar 30 '19 at 14:00

score 1 · Answer 1 · answered Mar 30 '19 at 15:40

You may have too large an area to fill, which causes recursive calls to consume all of the execution stack in your program.

Your options:

grow the execution stack even further, if you can
reduce the area (how about just 100x100 or 20x20?)
stop using the execution stack and use a data structure that works similarly but can contain more elements (by being more efficient and/or being able to grow/be larger)
use a different algorithm (e.g. consider going from individual pixels to horizontal spans of pixels, there will be many fewer of the latter than the former)

chux - Reinstate Monica · Answer 2 · 2019-03-31T05:46:35.037

What causes the stackoverflow?

What is the range of x0? +/- 2,000,000,000? That is your stack depth potential.

Code does not obviously prevent going out of range unless GetPixel(out-of-range) returns a no-match value.

And how can I resolve it?

Code needs to be more selective on recursive calls.
When a row of pixels can be set, do so without recursion.
Then examine that row's neighbors and only recurse when the neighbors were not continuously in need of setting.

A promising approach would handle the middle and then look at the 4 cardinal directions.

// Pseudo code
Polygon_FloodFill(x,y,c)
  if (pixel(x,y) needs filling) {    
    set pixel(x,y,c);
    for each of the 4 directions 
      // example: east
      i = 1; 
      // fill the east line first  
      while (pixel(x+i,y) needs filling) {     
        i++;
        set pixel(x,y,c);
      }
      // now examine the line above the "east" line
      recursed = false;
      for (j=1; j<i; j++) {
        if (pixel(x+j, y+j) needs filling) {     
          if (!recursed) {
            recursed = true;
            Polygon_FloodFill(x+j,y+j,c)
          } else  {
            // no need to call Polygon_FloodFill as will be caught with previous call
          }
        } else {
          recursed = false;
        }
      }
      // Same for line below the "east" line

      // do same for south, west, north.
    }

score 0 · Answer 3 · answered Mar 31 '19 at 09:30

how many pixels to fill? each pixel is one level deep of recursion and you got a lot of variables all local ones and operands of the recursive function + return value and address so for reach pixel you store this:

void Polygon_FloodFill(HDC hdc, int x0, int y0, int fillColor, int borderColor) {
int interiorColor;

in 32 bit environment I estimate this in [Bytes]:

4 Polygon_FloodFill return address
4 HDC hdc ?
4 int x0
4 int y0
4 int fillColor
4 int borderColor
4 int interiorColor
-------------------
~ 7*4 = 28 Bytes

There might be even more depending on the C engine and calling sequence.

Now if your filled area has for example 256x256 pixel then you need:

7*4*256*256 = 1.75 MByte

of memory on the stack/heap. How much memory you got depends on the settings you compile/link with so go to project option and look for memory stack/heap limits...

How to deal with this?

lower the stack/heap trashing

simply do not use operands for your flood_fill instead move them to global variables:

HDC floodfill_hdc;
int floodfill_x0,floodfill_y0,floodfill_fillColor,floodfill_borderColor;
void _Polygon_FloodFill()
 {
 // here your original filling code
 int interiorColor;
 ...
 }
void PolygonFloodFill(HDC hdc, int x0, int y0, int fillColor, int borderColor) // this is what you call when want to fill something
 {
 floodfill_hdc=hdc;
 floodfill_x0=x0;
 floodfill_y0=y0;
 floodfill_fillColor=fillColor;
 floodfill_borderColor=borderColor;
 _Polygon_FloodFill();
 }

this will allow to fill ~14 times bigger area.

limit recursion depth

This is also sometimes called priority que ... You just add one gobal counter that is counting actual depth of recursion and if hit limit value then do not allow recursion. Instead add pixel position to some list that will be processed after actual recursion stops.
change filling from pixels to lines

this simply eliminates a lot of recursive calls in wildly rough estimate to sqrt(n) recursions from n... You simply fill whole line from a start point to predetermined direction until you hit the border ... So you would have just recursion call per each line instead of per pixel. Here example (see [edit2]):
- Paint algorithm leaving white pixels at the edges when I color

However the function name Polygon_FloodFill implies you got the border polygon in vector form. If the case than filling it will be much faster using polygon rasterization techniques like:

how to rasterize rotated rectangle (in 2d by setpixel)

but for that the polygon must be convex one so if not the case you need to triangulate or break down to convex polygons first (for example with Ear clipping).

What causes the stackoverflow? And how can I resolve it?

3 Answers3