rayk@sbcs.sunysb.edu (Raymond T Kreisel) (04/26/88)
What is the FASTEST flood fill algorithm ?
If anyone has any C programs fragments that
impliment a VERY FAST flood fill, could they
please mail them to me. I currently have
a simple recursive flood fill program running
but it is just too SLOW for my needs.
(I am running it on a Sun 3/50 and Sun 3/110)
thanks,
ray
---------------------------------------------------------------------------
Ray Kreisel CS Dept., SUNY at Stony Brook, Stony Brook NY 11794
UUCP: {allegra, philabs, pyramid, research}!sbcs!rayk
ARPA-Internet: rayk@sbcs.sunysb.edu CSnet: rayk@suny-sb
"If I get home before daylight, I just might get some sleep tonight...."
---------------------------------------------------------------------------mcdonald@uxe.cso.uiuc.edu (04/29/88)
>What is the FASTEST flood fill algorithm ? >If anyone has any C programs fragments that >impliment a VERY FAST flood fill, could they >please mail them to me. I currently have >a simple recursive flood fill program running >but it is just too SLOW for my needs. >(I am running it on a Sun 3/50 and Sun 3/110) I too would like to get a copy of one of these. Doug McDonald (mcdonald@b.scs.uiuc.edu) (please note the different address from the note you presumably read a couple of minuts ago)
ph@miro.Berkeley.EDU.berkeley.edu (Paul Heckbert) (04/29/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); } }
pfarrell@anselm.UUCP (Gladiator Supreme.) (04/29/88)
For those of you who have a fast flood fill algorithm, could you post it as well, I am sure others besides myself want one. Thanks.
root@nccnat.UUCP (Paul Shields) (04/30/88)
In article <23807@ucbvax.BERKELEY.EDU>, ph@miro.Berkeley.EDU.berkeley.edu (Paul Heckbert) writes: > In article <1210@sbcs.sunysb.edu> rayk@sbcs.sunysb.edu (Raymond T Kreisel) asks: > >What is the FASTEST flood fill algorithm ? > [...] > I've always been amazed that the published code for fill algorithms, including > Smith and Foley/van Dam, is so inefficient! So have I. But examples in books are not meant for production algorithms; they illustrate propagation methods. They also have little or no error handling (stack overflow=crash, no clipping, etc.) There's a paper kicking around somewhere by someone at Berkeley, circa 1986, analyzing all previously known fill algorithms and presenting a new one. A friend of mine at IBM has optimized this alogorithm, achieving high- performance fills for multiply-connected regions: - worst case 1.5 visits per pel; - best case 1.0 vists per pel; - avg = 1.05. For simply-connected regions, it's 1.0 visits per pel always. Stack growth is limited and finite in pathological cases, eg. for: * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Source is about 25-30 lines of C, plus 50-60 lines of supporting code. Drawback: it cannot do gradient fills without large memory overhead. Does anyone have anything better? If not, send me mail and I'll dig up all of the references. -- Paul Shields, shields@yunccn.UUCP If you think you have a subconscious, or yunccn!nccnat!root you have a software integration problem.
root@nccnat.UUCP (Paul Shields) (05/05/88)
In article <288@nccnat.UUCP>, I write: > There's a paper kicking around somewhere by someone at Berkeley, circa 1986, > analyzing all previously known fill algorithms and presenting a new one. Fishkin, Kenneth P., and Barsky, Brian A. 1985. "An Analysis and Algorithm for Filling Progagation", Graphics Interface '85. The algorithm takes care of U, S, and W turns. > A friend of mine at IBM has optimized this alogorithm, achieving high- > performance fills for multiply-connected regions: > - worst case 1.5 visits per pel; > - best case 1.0 vists per pel; > - avg = 1.05. > > For simply-connected regions, it's 1.0 visits per pel always. He is, Ian Ameline, Development Analyst, IAD, IBM Canada Lab, TOROLAB2(AMELINE). I have a drop-box here for him, ian@nccnat.UUCP. I believe his optimizations include improved handling of some types of regions and use of memory management routines to reduce thrashing, since Fishkin and Barsky also report avg 1.05 visits per pel, 1.5 worst case, but admit that for simply-connected regions it's not always optimimal. Unfortunately, the (optimized) code is proprietary. But I _may_ be able to convince him to hint at what hasn't been taken care of in the other algorithm. In any case, you can see it at work in the IBM ImagEdit software if you're interested. Disclaimer: I have no connection with IBM or any of its products. Please do not take the above paragraph as an advertisment. -- Paul Shields, shields@yunccn.UUCP If you think you have a subconscious, or yunccn!nccnat!root you have a software integration problem.
daniel@unicom.UUCP (Dan Smith, not your average Lithuanian...) (05/07/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. > >A friend of mine at IBM has optimized this alogorithm, achieving high- >performance fills for multiply-connected regions: > - worst case 1.5 visits per pel; > - best case 1.0 vists per pel; > - avg = 1.05. >Source is about 25-30 lines of C, plus 50-60 lines of supporting code. > post it, don't tease us :-) dan dan smith, island graphics, marin co, ca, good natured infonaut, hoopy frood 4000 civic center dr., san rafael 94903 | dis: they're My thoughts, Buckwheat! uucp: {ucbvax!ucbcad,sun}!island!daniel | ph: +1 (415) 491 1000 (W), 332 FAST, uucp: {pacbell,pixar}!unicom!daniel | 332 EASY (H)| unix/films/rock/feasts