[net.graphics] fill algorithms

fishkin@ucbvax.ARPA (Ken Fishkin) (05/23/85)

	Recently, a couple of algorithms have been posted for
filling. I've spent about the last year researching these guys,
and have cooked up an algorithm that will be presented at the Graphics
Interface conference next week.
	If y'all want a copy, here's the source:

			Ken Fishkin
			Berkeley Computer Graphics Lab
			ucbvax!fishkin	fishkin@berkeley

An explanation of some of the weirder stuff:
1) Start() is a pointer to a procedure that initializes whatever variables
	the particular fill algorithm uses
2) Inside(x,y) reads a pixel and returns TRUE iff it is inside the region,
	and has not been set.
3) Set(x,y) writes a pixel.
#
#define	STACK_HEIGHT	20000


#define	PUSH(a,b,c,dd,e,f)	{\
tos++; \
if (tos >= STACK_HEIGHT) {\
    fprintf(stderr,"STACK OVERFLOW!!\n"); \
} \
Stack[tos].MyLx = a; \
Stack[tos].MyRx = b; \
Stack[tos].DadLx = c; \
Stack[tos].DadRx = dd; \
Stack[tos].Myy = e; \
Stack[tos].Mydir = f; \
}
#define	POP()	{\
lx = Stack[tos].MyLx; \
rx = Stack[tos].MyRx; \
DadLx = Stack[tos].DadLx; \
DadRx = Stack[tos].DadRx; \
y = Stack[tos].Myy; \
direction = Stack[tos].Mydir; \
tos--; \
}

/* it turns to be faster to store *not* (DadLx,DadRx),
but rather (DadLx - 1, DadRx + 1) (the first pixels *outside*
dad, rather than the *last* pixels *inside* dad)	*/

#define	STACK(direction,DadLx,DadRx,lx,rx,y)	{\
/* note that we stack the bigger piece first. this is good. */ \
    pushrx = rx + 1; pushlx = lx - 1; \
    PUSH(lx,rx,pushlx,pushrx,y+direction,direction); \
    if (rx > DadRx) { \
	/* stack a little piece, heading right, on Dad's y */ \
	PUSH(DadRx+1,rx,pushlx,pushrx,y-direction,-direction); \
    } \
    if (lx < DadLx) { \
	/* stack a little piece, heading left, on Dad's y */ \
	PUSH(lx,DadLx-1,pushlx,pushrx,y-direction,-direction); \
    } \
}
KenFill(x2,y2,Start,Inside,Set,Left,Right,Top,Bottom)
int	x2,y2;
void	(*Start) ();
BOOLEAN	(*Inside) ();
void	(*Set)();
int	Left,Right,Top,Bottom;
    {
    int	x,y;
    int	lx,rx,DadLx,DadRx;
    int	pushlx,pushrx;
    int	direction;
    BOOLEAN	WasIn;	/* are the pixels from [lx..x) in a run?	*/
    struct {
	int	MyLx, MyRx;
	int	DadLx, DadRx;
	int	Myy, Mydir;
    } Stack[STACK_HEIGHT];

    int	tos = -1;

    (*Start) ();

    if (!InRange(y2,Top,Bottom)) {
	printf("abort: y not in range.\n");
	return;
    }
    if ((!(*Inside) (x2,y2)))  {
	printf("abort: seed pixel not inside.\n");
	return;
    }
    (*Set) (x2,y2);
    lx = x2 - 1;
    while ( ((*Inside)(lx,y2)) AND (lx >= Left)) {
	(*Set) (lx,y2);
	lx--;
    }
    lx++;

    rx = x2 + 1;

    while ( ((*Inside)(rx,y2)) AND (rx <= Right)) {
	(*Set) (rx,y2);
	rx++;
    }
    rx--;

    PUSH(lx,rx,lx,rx,y2+1,1);
    PUSH(lx,rx,lx,rx,y2-1,-1);
    while (tos >= 0) {
	POP();
	if ( (y < Top) OR (y > Bottom)) {
	    /* y out of bounds */
	    continue;
	}
	/* three cases; can grow left, can grow right, or can grow both ways */
	x = lx + 1;
	if (WasIn = (*Inside)(lx,y)) {
	    (*Set)(lx,y);
	    lx--;
	    while ((*Inside)(lx,y) AND (lx >= Left)) {
		(*Set)(lx,y);
		lx--;
	    }
	    lx++;
	}
	/* now looking at pixel (x).
	    if (WasIn), then an inside a run of pixels from [lx..x)
	    else, lx is meaningless	*/
	while (x <= Right) {
	    if (WasIn) {
		if ((*Inside)(x,y)) {
		    (*Set)(x,y);
		} else {
		    /* just found the end of a run */
		    STACK(direction,DadLx,DadRx,lx,(x-1),y);
		    WasIn = FALSE;
		}
	    } else {
		if (x > rx) break;
		if ((*Inside)(x,y)) {
		    (*Set)(x,y);
		    /* just found the start of a run */
		    WasIn = TRUE;
		    lx = x;
		}
	    }
	    x++;
	}
	if (WasIn) {
	    /* hit an edge while inside a run */
	    STACK(direction,DadLx,DadRx,lx,(x-1),y);
	}
    }
}
-- 
		Ken Fishkin		Berkeley Computer Graphics Lab
		ucbvax!fishkin		fishkin@berkeley