Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!cbatt!ihnp4!inuxc!inuxf!matt
From: matt@inuxf.UUCP
Newsgroups: comp.graphics
Subject: Re: fast fill algorithm wanted
Message-ID: <265@inuxf.UUCP>
Date: Thu, 23-Apr-87 09:15:38 EST
Article-I.D.: inuxf.265
Posted: Thu Apr 23 09:15:38 1987
Date-Received: Sat, 25-Apr-87 07:11:26 EST
References: <2921@well.UUCP>
Organization: AT&T Consumer Products, Indianapolis
Lines: 19

> I'm trying to find a real whizzy fill algorithm that will give
> good results on irregular shapes.  I've tried the 8-connected
> boundary fill given in Foley and Van Dam, and was wondering if
> anyone knew of a faster one.  Thanks.
> 
> Matthew McClure			{ptsfa,hoptoad,lll-crg,apple,hplabs}!well!mmc
> International Technology Development Corporation
> 1990 Lombard Street, #250, San Francisco, CA 94123		 415-929-0924

As a matter of fact the algorithm described on page 450 of Foley/Van Dam under
the heading 'Decreasing the Recursion Depth' is MUCH faster than the 8-connected
recursive algorithm.  Implemented in assembly language it should be so whizzy
as to cause dizziness to the viewer.  I have implemented it in C language and
it is acceptably fast on a Compaq deskpro 286.  One thing to change in the 
description is to use a queue instead of a stack for holding the end points
of the runs.  A stack causes the fill to progress in a very wierd and disconserting
manner (at least to this viewer).

Matt Verner     AT&T Graphics Software Labs   ihnp4!inuxc!gslabs!matt