From albanycs!leah:rsb584 Fri Apr 29 12:48:52 1988
Received: by (5.54/4.8)
	id AA04817; Fri, 29 Apr 88 11:56:02 EDT
Date: Fri, 29 Apr 88 11:56:00 EDT
From: albanycs!leah:rsb584 (Raymond S Brand)
Received: by leah.Albany.EDU (5.58/1.1)
	id AA28518; Fri, 29 Apr 88 11:56:00 EDT
Message-Id: <8804291556.AA28518@leah.Albany.EDU>
To: albanycs:beowulf!rsbx
Subject: fill.c

>From ph@miro.Berkeley.EDU.UUCP Thu Apr 28 18:16:34 1988
Path: leah!itsgw!nysernic!cmx!batcomputer!cornell!rochester!bbn!mit-eddie!ll-xn!ames!pasteur!ucbvax!miro.Berkeley.EDU!ph
From: (Paul Heckbert)
Subject: Re: FAST flood fill
Message-ID: <23807@ucbvax.BERKELEY.EDU>
Date: 28 Apr 88 22:16:34 GMT
References: <>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: ph@miro.Berkeley.EDU.UUCP (Paul Heckbert)
Organization: University of California, Berkeley
Lines: 88

In article <> (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!!ph
Berkeley, CA 94720			ARPA:

 * 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=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 || xwx2 || ywy2) 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 (lx2+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);