Flood fill test

Maury Markowitz · May 4, 2018

An interesting thread has started over on the retrocomputing SO board:

https://retrocomputing.stackexchange.com/questions/2998/what-implementations-of-basic-had-a-robust-flood-fill-operator

Is anyone willing to try this on their Atari? The second post, for the Amstrad, should port fairly directly.

JamesD · May 4, 2018

An interesting thread has started over on the retrocomputing SO board:

https://retrocomputing.stackexchange.com/questions/2998/what-implementations-of-basic-had-a-robust-flood-fill-operator

Is anyone willing to try this on their Atari? The second post, for the Amstrad, should port fairly directly.

I think the first BASIC to include a flood fill that was built in, was Extended Color BASIC on the CoCo.

I remember running out of mem when doing a flood fill on a screen with a spiral pattern.

Most flood fills use the stack for temporary storage, and the BASIC stack is usually pretty small.

That could be an even bigger problem on the 6502.

tebe · May 4, 2018

mad pascal/lib/graph.inc

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;

the same code i used in Atari Graphics Studio (AGS)

Edited May 4, 2018 by tebe

dmsc · May 4, 2018

Hi!

An interesting thread has started over on the retrocomputing SO board:

https://retrocomputing.stackexchange.com/questions/2998/what-implementations-of-basic-had-a-robust-flood-fill-operator

Is anyone willing to try this on their Atari? The second post, for the Amstrad, should port fairly directly.

All flood-fill algorithms can run out of buffer space if you fill a complex enough area, look at this TurboBasic XL program, converted from the second one in the link:

If you run it, it runs out of space at about 75% of completion:

TurboBasic XL uses a scan-line fill algorithm, this avoids using too much memory on simpler paths and is faster than naive point at a time algorithms.

Fell free to post above program (and the result) over stackexchange.com if you want.

Irgendwer · May 4, 2018

void 
Dye(BYTE x, BYTE y, BYTE color)
{
	static BYTE xStack[FILLSTACKSIZE];
	static BYTE yStack[FILLSTACKSIZE];
	BYTE stackentry = 1;
	BOOL spanAbove, spanBelow;

	BYTE oldColor = Locate(x,y);

	if (oldColor == color)
		return;

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

		spanAbove = spanBelow = false;
		while(Locate(x,y) == oldColor)
		{
			PLOT(x,y,color);
			//Plot(x, y, color);

			if (y < (IMAGEHEIGHT-1))
			{
				BYTE belowColor = Locate(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)
			{
				BYTE aboveColor = Locate(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);		
}

Guess the game...

flashjazzcat · May 4, 2018

Interesting discussion. I remember trying to write a flood-fill in assembler in the early Nineties (I recall eventually giving up). I think it scanned lines and pushed boundaries (above and below the current line) onto a stack as it found them. I never quite decided how to cope with a pattern fill scenario, however, since unless every pixel will filled with the same colour, my algorithm would have failed completely (since - if using a dithered fill - it would have pushed new coordinates onto the stack every other pixel, believing them to be potential new areas to fill).

Rybags · May 5, 2018

I remember Analog magazine had a diamond algorithm fill that I played around with using a more efficient pixel plot routine.

It's a somewhat slower algorithm than the flood fill but has the big advantage that the required buffer can be much smaller - IIRC equal to about 4 times the largest possible 45 degree line length for the given mode.

I played around with flood fill, don't remember if I only used Basic or did it in assembler. I think it could actually exceed the bitmap data size in extreme cases for the buffer requirement.

Found it - Analog #16 from Feb 1984: http://www.atarimania.com/mags/pdf/analog_no_16.pdf

The Atarimania magazine PDF is big and annoyingly slow though - found another copy of the article with the program https://web.archive.org/web/20060308092706fw_/http://www.cyberroach.com:80/analog/an16/default.htm

ed - that took an eternity to download. Sadly the PDF has pretty poor OCR and the text even when you can select it is full of errors.

So, I typed in the listing for 4-way fill assembler routine:

; Fill routine using CIO
;
; CIO equates used
;
cio = $e456
iccom = $342
icblen = $348
cgbinr = $07
cpbinr = $0b
;
bufa = $cb ; addresses for ind,y
bufb = $cd ; addressing for
bufc = $cf ; pixel coordinate
bufd = $d4 ; storage
;
xpos = $55 ; x coordinate see OS
ypos = $54 ; y coordinate
;
color = $d1 ; color to plot
;
; the following locations can only
; be used temporarily because they
; are reserved for the floating point
; routines.
;
colover = $e6 ; color to cover
countnew = $e7 ; # new pixels
countold = $e8 ; # pixels to test around
;
xpstor = $e9 ; store original xpos
ypstor = $ea
xp = $d6
yp = $d7
tem = $eb ; to store y index
;
; the fill routine uses page 6
;
  *=$600
; or use .org $600
;
  pla ; # of args
  pla ; high byte not used
  pla ; the color to plot
  sta color
  lda $6fe ; bufd address stored
  sta bufd ; here because of the 
  lda $6ff ; limited free space
  sta bufd+1 ; in page 0
;
  lda #0
  sta countnew ; initialization
  ldy #1 ; one pixel first time
  lda xpos ; from os
  sta (bufa),y
  sta xpstor
  sta xp ; for the first locate
  lda ypos ; from os
  sta (bufb),y
  sta ypstor
  sta yp ; for the first locate
  sty countold ; one pixel
  jsr locate ; get pixel to cover
  sta colover
  cmp color ; itself?
  bne preloop
  rts ; if itself quite or get
; infinite loop!
;
preloop  jsr plot
loop  lda (bufa),y
  sta xp ; x for current pixel
  lda (bufb),y
  sta yp ; y for current pixel
;
loop0  inc xp ; test to right
  cmp #80 ; rhs limit to screen
  bcs loop1
  jsr locate ; if within screen
; then see if the pixel contains
; the color to be overwritten.
; the locate routine contains
; the compare.
;
  bne loop1
  jsr keep ; plot it and mark it
; for its own test the next time
; through the list of locations.
;
loop1  dec xp
  dec xp
  lda xp
  cmp #255 ; check screen lhs
  beq loop2
  jsr locate
  bne loop2
  jsr keep
;
loop2  inc xp
  inc yp ; test below
  lda yp
  cmp #80 ; bottom of screen
  bcs loop3
  jsr locate
  bne loop3
  jsr keep
;
loop3  dec yp
  dec yp
  lda yp
  cmp #255
  beq loop4
  jsr locate
  bne loop4
  jsr keep
;
loop4  dec countold
  beq doneloop ; all points done
  iny ; else do next point
  jmp loop
;
doneloop  ldy countnew
  beq return0 ; if no new points
; in the color to cover remain
;
  sty countold ; this becomes the
; new # pixels to plot and test
;
transfer  lda (bufd),y
  sta (bufb),y
  lda (bufc),y
  sta (bufa),y
  dey
  bne transfer ; move buffers
  ldy #1
  lda #0
  sta countnew ; initialize
  jmp loop ; begin again
;
; the subroutines
;
keep  jsr plot ; y reg in tem
  inc countnew
  beq return2 ; buffer overflows
  ldy countnew
  lda xp ; store the coord
  sta (bufc),y ; of this pixel
  lda yp ; for plotting and
  sta (bufd),y ; testing
  ldy tem ; recover y reg
;
locate  jsr pos
  lda #cgbinr
  sta iccom,x
  jsr cio ; cio locate
  ldy tem
  cmp colover ; pixel in a reg.
  rts
;
pos  sty tem
  lda xp
  sta xpos ; position x
  lda yp
  sta ypos ; and y
  ldx #$60 ; to use in locate
  lda #0 ; and in plot
  sta icblen,x ; one pixel as
  sta icblen+1,x ; in accum.
  rts
;
plot  jsr pos
  lda #cpbinr
  sta iccom,x
  lda color ; the one to plot
  jsr cio
  ldy tem
  rts
;
return0  lda ypstor
  sta ypos
  lda xpstor
  sta xpos
  rts
;
return2  jsr return0
  pla ; we exited a subroutine
  pla ; so pop return address
  rts ; to basic
;

Edited May 5, 2018 by Rybags

tebe · May 6, 2018

thx Irgendwer for the example 'fill by horizontal line'

fill_test_1 -> horizontal

fill_test_2 -> diamond

'Diamond' algorithm is more efficient then 'Horizontal Line'

floodfill_test.zip

floodfill_color.zip

Edited May 6, 2018 by tebe

Irgendwer · May 6, 2018

thx for the comparison

'Diamond' algorithm is more efficient then 'Horizontal Line'

Not really. I used the single plot since the speed was fast enough for my game and I liked to have a traceable way of filling for the user so decided against "high-speed".

The advantage of the horizontal line is, that you normally estimate a span for filling and draw then the complete horizontal span, which is way faster than plotting single pixels. Drawing diagonal lines involves more calculations...

Edit: And you second (color) example runs even faster in horizontal mode anyway? (while your first gives an obvious advantage due to the more "diagonal-base-pattern"?)

Edited May 6, 2018 by Irgendwer

+CharlieChaplin · May 6, 2018

Hmmm, my children once tested a flood fill mode in the bathroom by opening the water tap...

think it used a horizontal line... and the parents were not happy !

Irgendwer · October 18, 2018

Just to prevent unsuccessful tries using the code I posted above, here is a correction:

http://atariage.com/forums/topic/284075-anybody-have-a-good-flood-fill-code-snippet/?do=findComment&comment=4136733

tebe · October 19, 2018

stack array 2048 bytes

procedure FloodFill(a,b: smallint; newcolor: byte);
//----------------------------------------------------------------------------------------------
// Fill an area with a given color, seed fill algorithm
//----------------------------------------------------------------------------------------------
const
    FILLSTACKSIZE = 512;

var stackPointer, stackEntry: word;
    c: cardinal;
    oldcolor: byte;
    FloodFillStack: array [0..FILLSTACKSIZE-1] 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 < ScreenWidth);
      end;

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

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

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

	yes:=(yr < 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(stackEntry);

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

   end;

 end;

end;


begin

 SetColor(newcolor);

 oldcolor:=GetPixel(a,b);

 stackEntry := 1;
 stackPointer := 1;

 FloodFillStack[stackEntry] := word(a) shl 16 + word(b);

 FloodFillExec;

 while stackEntry > stackPointer do begin

  inc(stackPointer);

  c:=FloodFillStack[stackPointer];

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

  FloodFillExec;

  if (stackEntry > FILLSTACKSIZE shr 1) then begin

   stackEntry := stackEntry - stackPointer;

   if stackEntry > FILLSTACKSIZE shr 1 then exit;

   move(FloodFillStack[stackPointer+1], FloodFillStack[1], stackEntry shl 2);

   stackPointer := 0;

  end;

 end;

end;

stack array 8192 bytes

procedure Dye(x,y: smallint; color: byte);
var xStack, yStack: array [0..4095] 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;

	repeat

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

		spanAbove := false;
		spanBelow := false;

		while (x < ScreenWidth) and (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);

					if stackEntry > sizeof(xStack) then exit;

					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);

					if stackEntry > sizeof(xStack) then exit;

					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;

test is failed if stack array is smaller

floodfill_test2.zip

Edited October 19, 2018 by tebe

Irgendwer · October 19, 2018

test is failed if stack array is smaller

* there was never any doubt that the diamond algorithm memory usage is more conservative

* you spoil 512 bytes for the diamond fill and 2048 for the scan line one, so the numbers are more or less 1,5k vs. 6k

* your synthetic test fits better to the diamond fill, anyhow the scan line one is a bit faster: approx: 5:34 vs. 5:25

* changing (like suggested) to draw lines for the fill (attached), you get the following numbers: 5:34 vs. 4:30 (even I do not know how well the madpascal line function is optimized for horizontal lines and the test case is again very badly suited for horizontal spans)

* I'm not participating in a contest - I still have problems what are you trying to demonstrate. That the madpascal flood-fill is superior? Depends on the time-constraints. (Maybe the usual trade memory vs. speed story?)

* I even may change a future version of "dye" to use the diamond fill, not because it uses less memory (enough there - and for the images in the game a page of stack is sufficient), but for "entertainment" purposes: I find the process of the filling more attractive and like said, speed doesn't matter in this case.

Have fun!

fill_test_1.zip

Edited October 19, 2018 by Irgendwer

tebe · October 19, 2018

it's not contest, i search more efficient solution (speed, size of code, size of array), and i learn with you

Edited October 19, 2018 by tebe

Irgendwer · October 19, 2018

it's not contest, i search more efficient solution (speed, size of code, size of array), and i learn with you

Regarding your skills and output I doubt that you can learn very much from me... ;-)

Flood fill test

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members