From albanycs!leah:rsb584 Fri Apr 29 12:48:52 1988
Received: by albanycs.albany.edu (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: 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=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);
}
}
�