Path: utzoo!yunexus!stpl!gen1!yunccn!nccnat!root
From: root@nccnat.UUCP (Paul Shields)
Newsgroups: comp.graphics
Subject: Re: FAST flood fill
Summary: far faster fills found: avg 1.05 visits per pel!
Message-ID: <288@nccnat.UUCP>
Date: 30 Apr 88 20:06:26 GMT
Article-I.D.: nccnat.288
Posted: Sat Apr 30 16:06:26 1988
References: <1210@sbcs.sunysb.edu> <23807@ucbvax.BERKELEY.EDU>
Reply-To: shields@yunccn.UUCP
Organization: York University, Toronto Canada
Lines: 40

In article <23807@ucbvax.BERKELEY.EDU>, ph@miro.Berkeley.EDU.berkeley.edu (Paul Heckbert) writes:
> In article <1210@sbcs.sunysb.edu> rayk@sbcs.sunysb.edu (Raymond T Kreisel) asks:
> >What is the FASTEST flood fill algorithm ?
> 
[...] 
> I've always been amazed that the published code for fill algorithms, including
> Smith and Foley/van Dam, is so inefficient!

So have I. But examples in books are not meant for production algorithms;
they illustrate propagation methods. They also have little or no error 
handling (stack overflow=crash, no clipping, etc.)

There's a paper kicking around somewhere by someone at Berkeley, circa 1986, 
analyzing all previously known fill algorithms and presenting a new one. 

A friend of mine at IBM has optimized this alogorithm, achieving high-
performance fills for multiply-connected regions:
	- worst case 1.5 visits per pel;
	- best case 1.0 vists per pel;
	- avg = 1.05.  

For simply-connected regions, it's 1.0 visits per pel always.

Stack growth is limited and finite in pathological cases, eg. for: 

	 * * * * * * * * 

	 * * * * * * * * 

	 * * * * * * * * 

	 * * * * * * * * 

Source is about 25-30 lines of C, plus 50-60 lines of supporting code. 

Drawback:  it cannot do gradient fills without large memory overhead.

Does anyone have anything better?  If not, send me mail and I'll 
dig up all of the references. 
-- 
Paul Shields, shields@yunccn.UUCP   If you think you have a subconscious,
or yunccn!nccnat!root               you have a software integration problem.