perry (04/14/83)
There has been a lot of requests on net.micro for a filling algorithm which
would handle arbitrary polygons. A while back I needed a quick and dirty
black and white flooder so I reached for my nearest set of Siggraph
Proceedings and Notes (I thought everybody had a ``nearest set of Siggraph
Proceedings...), turned to any one of several articles by A. R. Smith
(formerly of NYIT now at that great graphics lab on Tatooine) and perverted
what lay therein. So, with the caveat that this code was not intended for
any other eyes other than those residing on the first board on the left in
the cpu bucket, here's der code.
----------------------------------------------------------------------------
Meant to run with an off bus frame buffer - most of the code is there to
cache scan lines (to reduce i/o overhead). Also, there is some code left
in here from some other diddling I was doing at about the same time (so
lint might find some unused routines).
----------------------------------------------------------------------------
#include <stdio.h>
/*
permission is hereby granted to copy this code where ever you like
just as long as you bow down and utter thanks in the direction of
Lucasfilm. In most parts of the country that will cause your
posterior to face Stony Brook, but thats ok with me.
perry s. kivolowitz
allegra!sbcs!perry
perry@suny-sbcs
*/
#define LEFT 0
#define RIGHT 511
#define TOP 511
#define BOTTOM 0
#define STACK_LIMIT 100
#define STACKNOTEMPTY (sp > stack)
struct frame {
int x;
int y;
};
struct frame stack[STACK_LIMIT] , *sp;
int x , y , lx , rx , yref , lxref , rxref;
int new , old;
push()
{
if (sp - stack >= STACK_LIMIT) {
printf("Ooops! Stack Overflow\n");
exit();
}
sp->x = x;
sp->y = y;
sp++;
}
pop()
{
if (--sp < stack) {
printf("Ooops! Stack Underflow\n");
exit();
}
x = sp->x;
y = sp->y;
}
init_stack()
{
sp = stack;
}
dump_stack()
{
struct frame *tsp;
tsp = stack;
printf("Stack Dump:\n");
while (tsp != sp) {
printf("x: %3d y: %3d\n" , tsp->x , tsp->y);
tsp++;
}
}
static last_y = -1;
static last_left = 0; last_right = 511;
static dirty_line = 0;
static short int scan_line[512];
get()
{
register int i;
if (last_y != y) {
last_left = last_left < 0 ? 0 : last_left;
last_left = last_left > 511 ? 511 : last_left;
last_right = last_right < 0 ? 0 : last_right;
last_right = last_right > 511 ? 511 : last_right;
if (dirty_line)
gcwlw(scan_line + last_left ,
last_left ,
last_y ,
last_right - last_left + 1 ,
0 , 0 , 13 , 0
);
dirty_line = 0;
if (last_y != -1) {
last_left = lx;
last_right = rx;
}
gcrlw(last_left ,
y ,
last_right - last_left + 1 ,
1 , scan_line+last_left
);
}
if (x < last_left) {
i = last_left / 2; /* shift right by 2 to the 0 bits */
i = x < i ? x : i;
gcrlw(i , y , last_left - i , 1 , scan_line + i);
last_left = i;
}
if (x > last_right) {
i = last_right + (511 - last_right) / 2;
i = x > i ? x : i;
gcrlw(last_right + 1 , y , i - last_right , 1 ,
scan_line + last_right + 1
);
last_right = i;
}
last_y = y;
return((int) scan_line[x]);
}
set()
{
scan_line[x] = new;
dirty_line = 1;
}
basic_fill(seed_x , seed_y , new_pv)
int seed_x , seed_y , new_pv;
{
x = seed_x;
y = seed_y;
new = new_pv;
old = get();
if (old == new) return;
yref = y;
push();
while (STACKNOTEMPTY) {
pop();
if (get() == new) continue;
fill_line();
if (hi_neighbor()) {
/* printf("Hi_Neighbor True\n"); */
scan_hi();
}
else if (lo_neighbor()) {
/* printf("Hi_Neighbor False\n");
printf("Lo_Neighbor True\n"); */
scan_low();
}
else {
/* printf("Both Hi and Lo are False\n"); */
scan_hi();
scan_low();
}
yref = y;
lxref = lx;
rxref = rx;
}
}
hi_neighbor()
{
if ((y == yref + 1) &&
(lx >= lxref - 1) &&
(rx <= rxref +1))
return(1);
else
return(0);
}
lo_neighbor()
{
if ((y == yref - 1) &&
(lx >= lxref - 1) &&
(rx <= rxref +1))
return(1);
else
return(0);
}
fill_line()
{
fill_right();
fill_left();
}
fill_right()
{
auto int tx = x;
while ((get() == old) && (x <= RIGHT)) {
set();
x++;
}
rx = x - 1;
x = tx;
}
fill_left()
{
auto int tx = x;
x--;
while ((get() == old) && (x >= LEFT)) {
set();
x--;
}
lx = x + 1;
x = tx;
}
scan_hi()
{
auto int tx = x , ty = y;
/* printf("Greetings from sunny scan_hi!\n"); */
if ((y + 1) > TOP) {
/* printf("scan_hi taking y+1 > top return\n"); */
return;
}
x = lx;
y++;
while (x <= rx) {
while ((get() != old) && (x <= rx)) x++;
if (x > rx) {
/* printf("scan_hi taking x > rx break\n"); */
break;
}
push();
while ((get() == old) && (x <= rx)) x++;
}
/* printf("scan_hi leaving via bottom of me\n"); */
x = tx;
y = ty;
}
scan_low()
{
auto int tx = x , ty = y;
if ((y - 1) < BOTTOM) return;
x = lx;
y--;
while (x <= rx) {
while ((get() != old) && (x <= rx)) x++;
if (x > rx) break;
push();
while ((get() == old) && (x <= rx)) x++;
}
x = tx;
y = ty;
}
gcwlw(data,x,y,l,dw,dh,cm,zc)
short data[],x,y,l,dw,dh,cm,zc;
{
grwlw_(data,&x , &y , &l , &dw , &dh , &cm , &zc);
}
snap_stack()
{
printf("X: %3d Y: %3d SP: %3d\n" , x , y , sp - stack);
}