mmc@well.UUCP (04/22/87)
I'm trying to find a real whizzy fill algorithm that will give
good results on irregular shapes. I've tried the 8-connected
boundary fill given in Foley and Van Dam, and was wondering if
anyone knew of a faster one. Thanks.
Matthew McClure {ptsfa,hoptoad,lll-crg,apple,hplabs}!well!mmc
International Technology Development Corporation
1990 Lombard Street, #250, San Francisco, CA 94123 415-929-0924matt@inuxf.UUCP (04/23/87)
> I'm trying to find a real whizzy fill algorithm that will give > good results on irregular shapes. I've tried the 8-connected > boundary fill given in Foley and Van Dam, and was wondering if > anyone knew of a faster one. Thanks. > > Matthew McClure {ptsfa,hoptoad,lll-crg,apple,hplabs}!well!mmc > International Technology Development Corporation > 1990 Lombard Street, #250, San Francisco, CA 94123 415-929-0924 As a matter of fact the algorithm described on page 450 of Foley/Van Dam under the heading 'Decreasing the Recursion Depth' is MUCH faster than the 8-connected recursive algorithm. Implemented in assembly language it should be so whizzy as to cause dizziness to the viewer. I have implemented it in C language and it is acceptably fast on a Compaq deskpro 286. One thing to change in the description is to use a queue instead of a stack for holding the end points of the runs. A stack causes the fill to progress in a very wierd and disconserting manner (at least to this viewer). Matt Verner AT&T Graphics Software Labs ihnp4!inuxc!gslabs!matt
ph@pixar.UUCP (Paul Heckbert) (04/27/87)
In article <2921@well.UUCP>, mmc@well.UUCP (Matthew McClure) writes: > I'm trying to find a real whizzy fill algorithm that will give > good results on irregular shapes. I've tried the 8-connected > boundary fill given in Foley and Van Dam, and was wondering if > anyone knew of a faster one. Thanks. Here's C source for a fast, simple scan-line oriented 4-connected fill program. I've always been amazed that the published code for fill algorithms, including Smith and Foley/van Dam, is so inefficient! It shouldn't be difficult to adapt this for 8-connected fill. Paul Heckbert PIXAR 415-499-3600 P.O. Box 13719 UUCP: {sun,ucbvax}!pixar!ph San Rafael, CA 94913 ARPA: ph%pixar.uucp@ucbvax.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 */ /* * segment of scan line y for xl<=x<=xr was filled, * now explore adjacent pixels in scan line y+dy */ struct seg {short y, xl, xr, dy;}; #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(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; 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); 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); } }