[comp.graphics] References to Flood Fill Routines

kory@avatar.UUCP (Kory Hamzeh) (05/04/90)

Can someone give me some references (or example code) to a fast flood
fill routine? All of the standard comp graphics text books utilize the recursive
method which is very elegant, but slow and causes alot of stack faults on
demand paged machines.

Thanks,
--kory



-- 
-------------------------------------------------------------------------------
Kory Hamzeh             UUCP: avatar!kory or ..!uunet!psivax!quad1!avatar!kory
                    INTERNET: avatar!kory@quad.com

cs122cv@ux1.cso.uiuc.edu (05/06/90)

Here is Fortran code for a non-recursive flood-fill...

c	Given array dimensions x and y, some array field(x,y),
c	arrays xstack() and ystack() (each dimensioned to some
c	sufficiently large number), and seed {start_x,start_y}...
c
c	Field should be all 0's except for the border of the area
c	to be filled, which should be -1.  Upon exit, the area within
c	the border will be filled with 1's.

	  stack_count=1
  	  xstack(stack_count)=start_x
	  ystack(stack_count)=start_y

	  do while (stack_count.gt.0)
	    xpixel=xstack(stack_count)
	    ypixel=ystack(stack_count)
	    stack_count=stack_count-1
	    rxpixel=real(xpixel)
	    rypixel=real(ypixel)

	    field(xpixel,ypixel)=1
	    if (field(xpixel+1,ypixel).eq.0) then
	        stack_count=stack_count+1
	        xstack(stack_count)=xpixel+1
	        ystack(stack_count)=ypixel
	    end if
	    if (field(xpixel-1,ypixel).eq.0) then
	        stack_count=stack_count+1
	        xstack(stack_count)=xpixel-1
	        ystack(stack_count)=ypixel
	    end if
	    if (field(xpixel,ypixel-1).eq.0) then
	        stack_count=stack_count+1
	        xstack(stack_count)=xpixel
	        ystack(stack_count)=ypixel-1
	    end if
	    if (field(xpixel,ypixel+1).eq.0) then
	        stack_count=stack_count+1
	        xstack(stack_count)=xpixel
	        ystack(stack_count)=ypixel+1
	    end if
	  end do

---Marc Andreessen
   Materials Research Lab, University of Illinois
   andreessen%uimrl.dnet@uimrl5.mrl.uiuc.edu