[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Re: recursion, stacksize & linux
From:       Michael Matz <matzmich () cs ! tu-berlin ! de>
Date:       2000-12-12 7:47:06
[Download RAW message or body]

Hi,

On Mon, 11 Dec 2000, John Califf wrote:
> I have a question about recursion vis-a-vis a flood fill method for some
> graphics apps (kiconedit and krayon).  Kiconedit uses a recursive flood
> fill algorithm which is rather elegant and I ported it to krayon as
> well. 

The method you use (one call/pixel) is not flood fill, but the slowest and
most space consuming method known ;) (Consider e.g. that it looks at each
pixel multiple times just to see, that it already is colored).

Try to avoid implicit recursion for graphics algorithms working on pixel
level like hell. Some systems (e.g. Solaris) don't have a big stack space,
and if you even run to a limit on linux you are screwed.

A good simple algorithm is to fill run-wise. A run is a line of pixels
bound by left and right coordinate. You start somewhere, and fill the
current line greedy left and right, thereby noting pixels above, not
already colored (put them on stack). You color those. Then you consider
pixels below the current line. This avoids most duplicate work. There are
some border cases, watch out. Variations of this thing are the fastest
filling methods.


Ciao,
Michael.

 
>> Visit http://master.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<

[prev in list] [next in list] [prev in thread] [next in thread]