Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!bloom-beacon!mit-eddie!ll-xn!ames!pasteur!ucbvax!miro.Berkeley.EDU!ph
From: ph@miro.Berkeley.EDU.berkeley.edu (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Re: FAST flood fill
Message-ID: <23807@ucbvax.BERKELEY.EDU>
Date: 28 Apr 88 22:16:34 GMT
References: <1210@sbcs.sunysb.edu>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: ph@miro.Berkeley.EDU.UUCP (Paul Heckbert)
Organization: University of California, Berkeley
Lines: 88

In article <1210@sbcs.sunysb.edu> rayk@sbcs.sunysb.edu (Raymond T Kreisel) asks:
>What is the FASTEST flood fill algorithm ?

This same question came up one year ago so I'll post my solution again.
I guess that makes this problem a good candidate for the "Summary Sheet for
Common Questions" that Andrew Glassner suggested back in March.


Here's C source for a fast, simple scan-line oriented 4-connected fill program.
I don't know if it's the fastest of all fill algorithms, but it's the simplest
of all the scanline methods I've seen.  Scanline methods are generally
much faster than pixel-by-pixel methods on frame buffers with DMA
interface, where the overhead on each image memory access is high.
On such a frame buffer I would implement readpixel or modify this code so
that scan lines are buffered.

I've always been amazed that the published code for fill algorithms, including
Smith and Foley/van Dam, is so inefficient!

Paul Heckbert, CS grad student
508-7 Evans Hall, UC Berkeley		UUCP: ucbvax!miro.berkeley.edu!ph
Berkeley, CA 94720			ARPA: ph@miro.berkeley.edu

---------------------------------------------------------
/*
 * fill.c : one page seed fill program, 1 channel frame buffer version
 *
 * doesn't read each pixel twice like the BASICFILL algorithm in
 *	Alvy Ray Smith, "Tint Fill", SIGGRAPH '79
 *
 * Paul Heckbert	13 Sept 1982, 28 Jan 1987
 */

typedef int pixel;
pixel pixelread();
extern int wx1, wx2, wy1, wy2;	/* screen window */

struct seg {short y, xl, xr, dy;};	/* horizontal segment of scan line y */
#define MAX 10000		/* max depth of stack */

#define PUSH(Y, XL, XR, DY) \
    if (sp<stack+MAX && Y+(DY)>=wy1 && Y+(DY)<=wy2) \
    {sp->y = Y; sp->xl = XL; sp->xr = XR; sp->dy = DY; sp++;}

#define POP(Y, XL, XR, DY) \
    {sp--; Y = sp->y+(DY = sp->dy); XL = sp->xl; XR = sp->xr;}

/*
 * fill: set the pixel at (x,y) and all of its 4-connected neighbors
 * with the same pixel value to the new pixel value nv.
 * A 4-connected neighbor is a pixel above, below, left, or right of a pixel.
 */
fill(x, y, nv)
int x, y;	/* seed point */
pixel nv;	/* new pixel value */
{
    int l, x1, x2, dy;
    pixel ov;	/* old pixel value */
    struct seg stack[MAX], *sp = stack;	/* stack of filled segments */

    ov = pixelread(x, y);		/* read pv at seed point */
    if (ov==nv || x<wx1 || x>wx2 || y<wy1 || y>wy2) return;
    PUSH(y, x, x, 1);			/* needed in some cases */
    PUSH(y+1, x, x, -1);		/* seed segment (popped 1st) */

    while (sp>stack) {
	/* pop segment off stack and fill a neighboring scan line */
	POP(y, x1, x2, dy);
	/*
	 * segment of scan line y-dy for x1<=x<=x2 was previously filled,
	 * now explore adjacent pixels in scan line y
	 */
	for (x=x1; x>=wx1 && pixelread(x, y)==ov; x--)
	    pixelwrite(x, y, nv);
	if (x>=x1) goto skip;
	l = x+1;
	if (l<x1) PUSH(y, l, x1-1, -dy);		/* leak on left? */
	x = x1+1;
	do {
	    for (; x<=wx2 && pixelread(x, y)==ov; x++)
		pixelwrite(x, y, nv);
	    PUSH(y, l, x-1, dy);
	    if (x>x2+1) PUSH(y, x2+1, x-1, -dy);	/* leak on right? */
skip:	    for (x++; x<=x2 && pixelread(x, y)!=ov; x++);
	    l = x;
	} while (x<=x2);
    }
}