Anybody have a good flood fill code snippet?

[tschak909]

Does anyone have a good flood fill code snippet?

 

On a lark, I implemented a 4-way recursive flood fill (aka the classic textbook fill) in C, and ran out of stack space on anything bigger than a gnat's arse...

 

(I'll post it here anyway)

/**
 * screen_paint - Paint screen (recursive function)
 */
void _screen_paint(short x, short y)
{
  if (tgi_getpixel(x,y)==0)
    {
      tgi_setpixel(x,y);
      _screen_paint(x+1,y);
      _screen_paint(x-1,y);
      _screen_paint(x,y+1);
      _screen_paint(x,y-1);
    }
}

/**
 * screen_paint - Paint the screen
 * Calling convention is different due to this needing to be recursive.
 */
void screen_paint(padPt* Coord)
{
#ifdef __ATARI__
  _screen_paint(mul0625(Coord->x),mul0375(Coord->y^0x1FF));
#else
  _screen_paint(scalex[Coord->x],scaley[Coord->y]);
#endif
}

[R0ger]

Don't have any code segment, but I've done it several times. The trick is to do as much as possible without stack (or queue). Something like this:

 

- go up till border

- go left till border

- start filling to the right, till border

- go 1 pixel down, and left till the border

- go to step 3

 

That will fill most of the picture. During the filling, you only store locations, where there is empty non-border, non-filled pixel above the one you are filling. And after you finish filling, you restart from the stored locations.

Typically some form queue is used. Obviously you don't use direct recursion, that has to store return address and possibly other stuff, so it's not effective.

You can also limit the size of the queue. That's useful in programs like graphics editors, where people can create worst case scenarios beyond your control. Not filling the border perfectly is less of a problem than program crashing.

 

The worst case in typically 25% pattern .. in every 2x2 pixels 1 pixel is set as border. That way you have to store width*height/4 locations, which is usually way too much for 8 bit systems. But for more typical cases, this system works just fine.

 

Edit: hmm .. just an idea .. if you processed the queue every time you got to the next line .. you could improve the max queue space used. Just fill the line, add the coordinates of the next line to the end of the queue, and start processing the queue.

[Irgendwer]

http://atariage.com/forums/topic/278446-flood-fill-test/?view=findpost&p=4021268

[Rybags]

I've not seen anything more memory efficient than the diamond method.

And that is referring to a genuine fill that is autonomous and doesn't rely on the user or caller to present an easy situation or do recursive calls to pick up missed areas.

But it is somewhat slower from what I've seen than the flood method.

[phaeron]

I went through a bunch of iterations of this when reimplementing TBXL's PAINT command. Various tweaks can reduce the number of duplicate items in the stack -- mainly avoiding re-pushing where you came from -- but it's hard to avoid redundant entries staying around in the stack for a long time. Ultimately the key to fixing the problem was switching from depth first search to breadth first search, which cut down the memory usage by an order of magnitude in stress tests. The current implementation in Altirra Extended BASIC is a span-based algorithm with a singly linked list for the draw queue and a node free list fed from a stack.

[tschak909]

I followed one of Irgendwer's threads, and put this together, which almost works:

 

 

/**
 * screen_paint - Paint screen scanline_fill
 */
void _screen_paint(unsigned short x, unsigned short y)
{
  static unsigned char xStack[512];
  static unsigned char yStack[512];
  unsigned char stackentry = 1;
  unsigned char spanAbove, spanBelow;
 
  unsigned char oldColor = tgi_getpixel(x,y);
 
  if (oldColor == 1)
    return;
 
  do
    {
      while (x > 0 && tgi_getpixel(x-1,y) == oldColor)
        --x;
 
      spanAbove = spanBelow = false;
      while(tgi_getpixel(x,y) == oldColor)
        {
          tgi_setpixel(x,y);
 
          if (y < (191))
            {
              unsigned char belowColor = tgi_getpixel(x, y+1);
              if (!spanBelow  && belowColor == oldColor)
                {
                  xStack[stackentry]  = x;
                  yStack[stackentry]  = y+1;
                  ++stackentry;
                  spanBelow = true;
                }
              else if (spanBelow && belowColor != oldColor)
                spanBelow = false;
            }
 
          if (y > 0)
            {
              unsigned char aboveColor = tgi_getpixel(x, y-1);
              if (!spanAbove  && aboveColor == oldColor)
                {
                  xStack[stackentry]  = x;
                  yStack[stackentry]  = y-1;
                  ++stackentry;
                  spanAbove = true;
                }
              else if (spanAbove && aboveColor != oldColor)
                spanAbove = false;
            }
 
          ++x;
        }
      --stackentry;
      x = xStack[stackentry];
      y = yStack[stackentry];
    }
  while (stackentry);
}

 

Why is this one having trouble plotting pixels past 256?

 

-Thom

[Irgendwer]

I followed one of Irgendwer's threads, and put this together, which almost works:

...
  static unsigned char xStack[512];
...
      x = xStack[stackentry];

Why is this one having trouble plotting pixels past 256?

 

-Thom

 

Because in hi-res case 8 bits for X are not sufficient.

512 stack entries are quite comfortable. About 128 are in most cases more than enough.

[tschak909]

but I'm not using chars for x or y. you can see, they're defined as short (16-bit).

 

-Thom

[EdwardianDuck]

Just a thought, but would changing these to short help?

  static unsigned char xStack[512];
  static unsigned char yStack[512];
  unsigned char stackentry = 1;

i.e.

  static unsigned short xStack[512];
  static unsigned short yStack[512];
  unsigned short stackentry = 1;

Because otherwise I think x will get truncated to 8 bits.

 

It might not be necessary to change yStack though.

 

Jeremy

[tebe]

FloodFill - Diamond (test PASS, 'fill_test_2.pas')

Dye - Horizontal Line (test FAIL, 'fill_test_1.pas')

 

procedure FloodFill(a,b: smallint; newcolor: byte);
//----------------------------------------------------------------------------------------------
// Fill an area with a given color, seed fill algorithm
//----------------------------------------------------------------------------------------------
var ir, nf: word;
    c: cardinal;
    oldcolor: byte;
    FloodFillStack: array [0..0] of cardinal;


procedure FloodFillExec;
var i: byte;
    xr,yr: smallint;
    yes: Boolean;
begin

 for i:=0 to 3 do begin

  case i of

   0: begin
	xr:=a+1;
	yr:=b;

	yes:=(xr<smallint(ScreenWidth));
      end;

   1: begin
	xr:=a-1;
//	yr:=b;

	yes:=(xr>=0);
      end;

   2: begin
	xr:=a;
	yr:=b+1;

	yes:=(yr<smallint(ScreenHeight));
      end;

   3: begin
//	xr:=a;
	yr:=b-1;

	yes:=(yr>=0);
      end;

  end;


  if yes then
   if GetPixel(xr,yr) = oldcolor then begin

    PutPixel(xr, yr);

    inc(nf);

    FloodFillStack[nf]:= word(xr) shl 16 + word(yr);
   end;

 end;

end;


begin

 FloodFillStack:=pointer(dpeek(560)-2048);

 SetColor(newcolor);

 oldcolor:=GetPixel(a,b);

 nf := 1;
 ir := 1;
 FloodFillStack[nf] := word(a) shl 16 + word(b);

 FloodFillExec;

 while nf>ir do begin

  inc(ir);

  c:=FloodFillStack[ir];

  a := hi(c);
  b := lo(c);

  FloodFillExec;

  if (nf>500) then begin

   nf := nf-ir;

   if nf>500 then exit;

   move(FloodFillStack[ir+1], FloodFillStack[1], nf shl 2);

//   for i := 1 to nf do fill[i] := fill[ir+i];

   ir := 0;

  end;

 end;

end;

procedure Dye(x,y: smallint; color: byte);
const
    FILLSTACKSIZE = 1024;

var xStack, yStack: array [0..0] of smallint;
    stackEntry: word;
    spanAbove, spanBelow: Boolean;
    oldColor, belowColor, aboveColor: byte;
begin
	oldColor := GetPixel(x,y);

	if (oldColor = color) then exit;

	SetColor(color);

	stackEntry := 1;

	xStack:=pointer(dpeek(560)-FILLSTACKSIZE*2);
	yStack:=pointer(dpeek(560)-FILLSTACKSIZE);

	repeat

		while (x > 0) and (GetPixel(x-1,y) = oldColor) do dec(x);

		spanAbove := false;
		spanBelow := false;

		while (GetPixel(x,y) = oldColor) do begin

			PutPixel(x,y);

			if (y < smallint(ScreenHeight-1)) then begin

				belowColor := GetPixel(x, y+1);

				if (spanBelow=false) and (belowColor = oldColor) then begin

					xStack[stackEntry]  := x;
					yStack[stackEntry]  := y+1;
					inc(stackEntry);
					spanBelow := true;
				end
				else if (spanBelow=true) and (belowColor <> oldColor) then
					spanBelow := false;
			end;

			if (y > 0) then begin

				aboveColor := GetPixel(x, y-1);

				if (spanAbove=false) and (aboveColor = oldColor) then begin

					xStack[stackEntry]  := x;
					yStack[stackEntry]  := y-1;
					inc(stackEntry);
					spanAbove := true;
				end
				else if (spanAbove=true) and (aboveColor <> oldColor) then
					spanAbove := false;
			end;

			inc(x);
		end;
		dec(stackEntry);
		x := xStack[stackEntry];
		y := yStack[stackEntry];

	until stackentry=0;

end;

floodfill_test.zip

Edited October 18, 2018 by tebe

[JamesD]

https://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm

[tschak909]

Oh my sweet jeebus. Yeah, the stack entries were too short for the X. Changed that, and the fill works. Not the fastest, but fast enough, and it doesn't murder the stack. so I call this algorithm a workable solution that's simple enough to understand for those needing a flood fill.

 

-Thom

[tschak909]

FWIW, I've sent in the snippet to the CC65 ppl, and hopefully we'll try to work that into a pull request to get a fill plopped into CC65's TGI.

 

-Thom

[tschak909]

[Irgendwer]

...
	xStack:=pointer(dpeek(560)-FILLSTACKSIZE*2);
	yStack:=pointer(dpeek(560)-FILLSTACKSIZE);
...

 

This is a wild guess, but doesn't result this in overlapping component stacks?

What are you trying to demonstrate?

Edited October 18, 2018 by Irgendwer

[Irgendwer]

Yeah, the stack entries were too short for the X.

 

Like I quoted...

 

Not the fastest, but fast enough, and it doesn't murder the stack. so I call this algorithm a workable solution that's simple enough to understand for those needing a flood fill.

 

If you read the other thread you may noticed my comment regarding speed improvements. (Single plots are slower than drawing lines (best when there is a special function for quick horizontal ones).)

 

You may like to adapt that code accordingly: Remember your entry x for the inner loop and draw a line till the exit x -1:

...
	do
	{
		XCOORDINATEDATATYPE startx; 
		while (x > 0 && Locate(x-1,y) == oldColor)
			--x;

		spanAbove = spanBelow = false;
		startx = x;

		while(Locate(x,y) == oldColor)
		{
                      // NO PLOT HERE!
			...
			++x;
		}
		DrawLine(startx, y, x-1, y);
...

Should be faster.

 

FWIW, I've sent in the snippet to the CC65 ppl, and hopefully we'll try to work that into a pull request to get a fill plopped into CC65's TGI.

 

Being on the list of contributors I never had this idea myself - especially not before creating an optimized assembler version...

 

[Irgendwer]

Dye - Horizontal Line (test FAIL, 'fill_test_1.pas')

 

Ok, now I see: I thought you have to reserve double the size for x than for y, but you put always "smallint" on the stack, so having 512 entries.

 

There is a "trick" in 'dye' why my routine doesn't work like intended in your sample: The left border has a different color(-code) so I don't have to check the horizontal limit each time. For unbounded areas the code has to look like this:

...	
	do
	{
		while (x > 0 && Locate(x-1,y) == oldColor)
			--x;

		spanAbove = spanBelow = false;
		while( (x<IMAGEWIDTH) && Locate(x,y) == oldColor)
		{
...

@tschak909: You have to adapt this too!

 

That said, the routine fills now your pattern (quite quick), but exhausts the stack after ~ 1/8 area (if it was that what you tried to demonstrate).

[sack-c0s]

if your use-case is right for the job, couldn't you use an EOR filler instead?