Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!ucsd!ucbvax!pasteur!miro.Berkeley.EDU!ph
From: ph@miro.Berkeley.EDU (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Re: Fast Flooding algorithm: anyone got one?. (want to find a centroid)
Message-ID: <28839@pasteur.Berkeley.EDU>
Date: 16 Oct 90 02:45:58 GMT
References: <1990Oct15.022751.10968@hades.ausonics.oz.au>
Sender: news@pasteur.Berkeley.EDU
Reply-To: ph@miro.Berkeley.EDU (Paul Heckbert)
Organization: University of California at Berkeley
Lines: 33

In article <1990Oct15.022751.10968@hades.ausonics.oz.au>
greyham@hades.ausonics.oz.au (Greyham Stoney) writes:
> So; does anyone know how fast graphics packages do flood-fills?

Most people use a stack of horizontal line segments, I believe.
Most of the fill algorithms in the literature are based on this idea.
C source for a simple fill algorithm is available in the book
"Graphics Gems" from Academic Press.  You can buy the book and read
the articles by Ken Fishkin and myself discussing the algorithms,
or if all you want is code, it's available via ftp (does that work
from Australia?)

Here's how to get Graphics Gems source via ftp:

    All C source files in the book are available via anonymous
    ftp from site 'weedeater.math.yale.edu'.  To download the files,
    connect to this site with an ftp program.  For user name type
    the word 'anonymous'; for password enter your last name.  When
    you are logged in, type 'cd pub/GraphicsGems/src'.  Each program
    from the book is stored in its own plaintext file.  I suggest you 
    first download the file README (type 'get README', then quit ftp 
    and open the file with any text editor); among other things it 
    describes how to download the rest of the directory, identifies
    the administrator of the site (who will collect bug reports, etc.),
    and provides a table of contents so you can identify the source files
    with their corresponding Gems.

After you get all the files, look at SeedFill.c; that may help you
with your problem.

Paul Heckbert, Computer Science Dept.
570 Evans Hall, UC Berkeley		INTERNET: ph@miro.berkeley.edu
Berkeley, CA 94720			UUCP: ucbvax!miro.berkeley.edu!ph