[comp.graphics] faster flood fill

fishkin@pixar.UUCP (Ken Fishkin) (05/09/88)

In article <288@nccnat.UUCP> shields@yunccn.UUCP writes:
>There's a paper kicking around somewhere by someone at Berkeley, circa 1986, 
>analyzing all previously known fill algorithms and presenting a new one. 
    I'm that "someone at Berkeley". The paper was
"An Analysis and Algorithm for Filling Propagation", by Fishkin&Barsky,
in "Proceedings of Graphics Interface '85", pp. 203-212.
>
>A friend of mine at IBM has optimized this alogorithm, achieving high-
>performance fills for multiply-connected regions:
    Glad to hear that someone else is using it! Yes indeedy, the
algorithm boasts:
    1.0 visits per pixel for simply-connected regions (i.e. w/o holes)
    1.5 visits per pixel worst-case
    1.05 visits per pixel average-case on our test data;
    schmart exploration behavior, where "schmart" is explained in the paper.
    but it *DOES* require a "visited" bit/pixel (like most do).

to give you some comparison, here was the average-number-of-visits-per-pixel
and average-CPU-time for the published algs I knew about:
    alg		visits/pixel	CPU time, relative to Smith 82

    Shani 80	1.09		217.2
    Smith 82	2.02		100.0
    Levoy 82	1.55		83.5
    Fishkin 85	1.05		60.2


Since the article is not what you would call easily available,
I'll repost the ending algoritm in pseudo-C for all you net.graphics folks.
I'm typing this in from the article, so don't be surprised if it has minor
typos and such.  It assumes that there are other procedures as follows:
    START() - does whatever start-up processing your particular fill needs.
    Boolean INSIDE(x,y) - returns TRUE iff the pixel at (x,y) is inside
the region you are filling.
    SET(x,y) - set the pixel at (x,y) to whatever new color you want
it to have. SET(x,y) also must ensure that future calls to INSIDE(x,y)
will return FALSE.
    For examples of various INSIDE and SET procedures, may I shamelessly
promote another article of mine:
    "A Familiy of Algorithms for Soft Filling", SIGGRAPH '84, 181-185.


And so, without further ado:
------------------------------------------------------------------
struct {
    int MyLx, MyRx; /* endpoints of this shadow */
    int DadLx, DadRx; /* and parent span */
    int Myy; /* my shadow y coord */
    TWO_VAL Mydir; /* only +1 or -1 */
    } Stack[STACK_HEIGHT];

macro PUSH(a,b,c,d,e,f)
    - push a shadow with MyLx of (a), MyRx of (b),
    - with Myy of (e), with Mydir of (f),
    - with DadLx of (c), and DadRx of (d)

macro POP()
    - pop the top-of-stack shadow into local variables
    - lx (from MyLx)
    - rx (from MyRx)
    - y (from Myy)
    - direction (from Mydir)
    - DadLx (from DadLx)
    - DadRx (from DadRx)

    /*
    * stack a shadow on the stack. The current span is
    * [lx..rx] on line y, the parent is [DadLx..DadRx],
    * and the current direction is (direction)
    */
macro STACK(direction,DadLx,DadRx,lx,rx,y) {
    /* store the shoulders of the span, to simplify testing */
    pushrx = rx + 1; pushlx = lx + 1;
    PUSH(lx,rx,pushlx,pushrx,y+direction,direction);
    if (rx > DadRx) { /* U turn to the right */
	PUSH(DadRx+1,rx,pushlx,pushrx,y-direction,-direction);
    }
    if (lx < DadLx) { /* U turn to the left */
	PUSH(lx,DadLx-1,pushlx,pushrx,y-direction,-direction);
    }
    /* W turn handled implicitly */
}

    /* fill a region, with seed at (seedx,seedy) */
Fill(seedx,seedy)
int seedx,seedy;
{
    int x,y;
    int lx,rx,DadLx,DadRx;
    int pushlx, pushrx;
    int direction;
    Boolean wasIn; /* are the pixels from [lx..rx] in a run? */

    START();

    -- find the span containing the seed point.
    -- suppose it goes from (lx) to (rx), inclusive.
    PUSH(lx,rx,lx,rx,seedy+1,1);
    PUSH(lx,rx,lx,rx,seedy-1,-1);

    while (Stack.tos >= 0) {
	POP();
	/* Top, Bottom are the edges of the window/frame-buffer */
	if (y < Top || y > Bottom) continue;
	x = lx + 1;
	if ((wasIn = INSIDE(lx,y)) {
	    SET(lx,y); lx--;
	    /* Left,Right are the edges of the window/frame-buffer */
	    while (INSIDE(lx,y) && (lx >= Left)) {
		SET(lx,y); lx--;
	    }
	    lx++;
	}
	/* now looking at at pixel (x).
	* if (wasIn) then am inside a run of pixels from [lx..x).
	* else, lx is meaningless
	*/
	while (lx <= Right) {
	    if (wasIn) {
		if (INSIDE(x,y)) {
		    SET(x,y);
		} else { /* found the end of a run */
		    STACK(direction,DadLx,DadRx,lx,x-1,y);
		}
	    } else {
		if (x > rx) break;
		if (INSIDE(x,y)) { /* found the start of a run */
		    SET(x,y); wasIn = TRUE; lx = x;
		}
	    }
	    x++;
	}
	if (wasIn) {
	    /* hit right edge while still inside span */
	    STACK(direction,DadLx,DadRx,lx,x-1,y);
	}
    }
}
---------------------------------------------------------------
-- 
Ken Fishkin	...{ucbvax,sun}!pixar!fishkin