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