Jump to content
Sign in to follow this  
Maury Markowitz

Flood fill test

Recommended Posts

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.

Share this post


Link to post
Share on other sites

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 by tebe
  • Like 2

Share this post


Link to post
Share on other sites

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:

post-18634-0-69121600-1525464978_thumb.png

 

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

post-18634-0-94629900-1525464986_thumb.png

 

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.

  • Like 1

Share this post


Link to post
Share on other sites
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... ;)

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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 by Rybags

Share this post


Link to post
Share on other sites

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 by Irgendwer

Share this post


Link to post
Share on other sites

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 by tebe

Share this post


Link to post
Share on other sites

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 by Irgendwer

Share this post


Link to post
Share on other sites

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

Edited by tebe
  • Like 1

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...