Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!mit-eddie!genrad!decvax!ucbvax!ucsfcgl!pixar!ph
From: ph@pixar.UUCP (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Re: fast fill algorithm wanted
Message-ID: <696@pixar.UUCP>
Date: Mon, 27-Apr-87 03:17:59 EDT
Article-I.D.: pixar.696
Posted: Mon Apr 27 03:17:59 1987
Date-Received: Tue, 28-Apr-87 01:10:09 EDT
References: <2921@well.UUCP>
Organization: Pixar -- Marin County, California
Lines: 76
Keywords: fill flood algorithm scan-line conversion
Summary: some C source

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);
    }
}