Return-Path: <ph@miro.Berkeley.EDU>
Received: from miro.Berkeley.EDU ([128.32.149.20]) by Xerox.COM ; 03 MAY 90 18:04:45 PDT
Received: by miro.Berkeley.EDU (4.1/1.41)
 id AA07956; Thu, 3 May 90 18:04:40 PDT
Date: Thu, 3 May 90 18:04:40 PDT
From: ph@miro.Berkeley.EDU (Paul Heckbert)
Message-Id: <9005040104.AA07956@miro.Berkeley.EDU>
To: bloomenthal.pa
Subject: Re: fill?

yes, it's coming out as a gem. Here it is.

/*
* fill.c : simple seed fill program
* Calls pixelread() to read pixels, pixelwrite() to write pixels.
*
* Paul Heckbert 13 Sept 1982, 28 Jan 1987
*/

typedef struct {  /* window: a discrete 2-D rectangle */
int x0, y0;   /* xmin and ymin */
int x1, y1;   /* xmax and ymax (inclusive) */
} Window;

typedef int Pixel;  /* 1-channel frame buffer assumed */

Pixel pixelread();

typedef struct {short y, xl, xr, dy;} Segment;
/*
* Filled horizontal segment of scanline y for xl$<=$x$<=$xr.
* Parent segment was on line y-dy. dy=1 or -1
*/

#define MAX 10000  /* max depth of stack */

#define PUSH(Y, XL, XR, DY) /* push new segment on stack */ \
if (sp<stack+MAX && Y+(DY)>=win->y0 && Y+(DY)<=win->y1) \
{sp->y = Y; sp->xl = XL; sp->xr = XR; sp->dy = DY; sp++;}

#define POP(Y, XL, XR, DY) /* pop segment off stack */ \
{sp--; Y = sp->y+(DY = sp->dy); XL = sp->xl; XR = sp->xr;}

/*
* fill: set the pixel at (x,y) and all of its 4-connected neighbors
* with the same pixel value to the new pixel value nv.
* A 4-connected neighbor is a pixel above, below, left, or right of a pixel.
*/

fill(x, y, win, nv)
int x, y; /* seed point */
Window *win; /* screen window */
Pixel nv; /* new pixel value */
{
int l, x1, x2, dy;
Pixel ov; /* old pixel value */
Segment stack[MAX], *sp = stack; /* stack of filled segments */

ov = pixelread(x, y);  /* read pv at seed point */
if (ov==nv || x<win->x0 || x>win->x1 || y<win->y0 || y>win->y1) 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);
 /*
  * segment of scan line y-dy for x1<=x<=x2 was previously filled,
  * now explore adjacent pixels in scan line y
  */
 for (x=x1; x>=win->x0 && 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<=win->x1 && 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);
}
}
]
----

.EQ
delim $$
.EN
.so ../codemac.nr
{
fill: set the pixel at (x,y) and all of its 4-connected neighbors
with the same pixel value to the new pixel value nv.
A 4-connected neighbor is a pixel above, below, left, or right of a pixel.

Paul Heckbert 13 Sept 1982, 28 Jan 1987, 18 Dec 1989
}

Pixel: type $<-$ int;
Window: type $<-$ record [xmin, ymin, xmax, ymax: int]; {inclusive window}

procedure fill(
x, y: int;     {seed point}
nv: int;     {new pixel value}
win: Window;    {screen window}
pixelread: function(x, y: int): Pixel; {procedure for reading pixels}
pixelwrite: procedure(x, y: int; pv: Pixel);{procedure for writing pixels}
);

l, x1, x2, dy: int;
ov: Pixel;    {old pixel value}

Segment: type $<-$ record [y, xl, xr, dy: int];
{
Filled horizontal segment of scanline y for xl$<=$x$<=$xr.
Parent segment was on line y-dy. dy=1 or -1
}

max: const int $<-$ 10000;   {max depth of stack}
stack: array[0..max-1] of Segment; {stack of filled segments}
sp: int $<-$ 0;    {stack pointer}

procedure push(y, xl, xr, dy: int); {push new segment on stack}
begin
if sp<max and y+dy$>=$win.ymin and y+dy$<=$win.ymax then begin
 stack[sp].y $<-$ y;
 stack[sp].xl $<-$ xl;
 stack[sp].xr $<-$ xr;
 stack[sp].dy $<-$ dy;
 sp $<-$ sp+1;
 end;
endproc push;

procedure pop(y, xl, xr, dy: ref int); {pop segment off stack}
begin
sp $<-$ sp-1;
dy $<-$ stack[sp].dy;
y $<-$ stack[sp].y+dy;
xl $<-$ stack[sp].xl;
xr $<-$ stack[sp].xr;
endproc pop;

begin
ov $<-$ pixelread(x, y);  {read pv at seed point}
if ov=nv or x<win.xmin or x>win.xmax or y<win.ymin or y>win.ymax then
 return;
push(y, x, x, 1);   {needed in some cases}
push(y+1, x, x, -1);  {seed segment (popped 1st)}

while sp>0 do
 {pop segment off stack and fill a neighboring scan line}
 pop(y, x1, x2, dy);
 {
  segment of scan line y-dy for x1$<=$x$<=$x2 was previously filled,
  now explore adjacent pixels in scan line y
  }
 x $<-$ x1;
 while x$>=$win.xmin and pixelread(x, y)=ov do
  pixelwrite(x, y, nv);
  x $<-$ x-1;
  endloop;
 if x$>=$x1 then goto skip;
 l $<-$ x+1;
 if l<x1 then push(y, l, x1-1, -dy);  {leak on left?}
 x $<-$ x1+1;
 loop do
  while x$<=$win.xmax and pixelread(x, y)=ov do
  pixelwrite(x, y, nv);
  x $<-$ x+1;
  endloop;
  push(y, l, x-1, dy);
  if x>x2+1 then push(y, x2+1, x-1, -dy); {leak on right?}
skip:  x $<-$ x+1;
  while x$<=$x2 and pixelread(x, y)$!=$ov do
  x $<-$ x+1;
  endloop;
  l $<-$ x;
  while x$<=$x2;
 endloop;
endproc fill;
----
.\" format with ditroff -ms
.nr PO 1.35i \" page offset
.TL
A Seed Fill Algorithm
.AU
Paul S. Heckbert
.AI
Computer Science Dept.
UC Berkeley
Berkeley CA 94720

December 1989
.LP
Below is pseudo-Pascal code for seed fill.
Given a seed point (x,y), it sets this pixel and all of its 4-connected
neighbors with the same pixel value to a new pixel value.
This is useful operation in paint programs.

Unfortunately, many of the published algorithms for seed fill
stress simplicity to the point of inefficiency.
A near-optimal algorithm for seed fill is actually not much more complex
than the simplest one,
as demonstrated by the code below.
Optimality can be measured by the number of times a pixel is read.
One of the earliest published algorithms for seed fill reads each pixel twice:
[Alvy Ray Smith,
``Tint Fill'',
\fISIGGRAPH '79 Proceedings\fP,
Aug. 1979,
pp. 276-283].
The algorithm below reads each pixel just a bit more than once, on average,
as does the similar algorithm described in:
[Kenneth P. Fishkin,
Brian A. Barsky,
``An Analysis and Algorithm for Filling Propagation'',
\fIProc. Graphics Interface '85\fP,
May 1985,
pp. 203-212].
Fishkin gives a good analysis of previous fill algorithms.

This code below stops filling with any change in pixel value,
but other stopping rules, such as "stop at a specific pixel value"
are often useful.
The code could easily be generalized in this way.