non-recursive flood fill
Gerry Panganiban
Does anyone know of a good non-recursive flood fill algorithm? All the
ones I've seen use recursion in some form or another....
-Gerry
Matthew Palmer
"Gerry Panganiban" <panga...@btw.com> wrote:
>Does anyone know of a good non-recursive flood fill algorithm? All the
>ones I've seen use recursion in some form or another....
I'd bet it's possible to imitate the recursion using a while
loop, and instead of calling the same function as the recursion
does, just push that location or whatever onto a stack.
Mat
morg
On Tue, 29 Jul 1997 03:23:39 GMT, lil...@fastlane.net (Matthew Palmer)
wrote:
Exactly, you can always rewrite a recursive funtion using a local
stack
morg
Brent A Ellingson
Gerry Panganiban wrote:
>
> Does anyone know of a good non-recursive flood fill algorithm? All the
> ones I've seen use recursion in some form or another....
>
I was once told that it was "impossible" to do a general flood fill
without using recursion. If that's the case, I would imagine that
someone, somewhere, has the maths to prove it. I don't, but
I have an "intuitive" feel that it's true. :-{
As someone pointed out, you can replace the "automagic" recursive
call stack with a program maintained one, but you're still using
recursion there.
Warning: the above post contains NO actual information. If you
thought you saw something imformative, read again.
Brent Ellingson
John Krsek
Gerry Panganiban wrote:
>
> Does anyone know of a good non-recursive flood fill algorithm? All the
> ones I've seen use recursion in some form or another....
>
> -Gerry
I went to write a fill a couple years ago and I was thinking I had done
something like this when I wrote a fill back in ~1981. I couldn't find
the code and I couldn't figure out what I had done. The best I could do
was come up with a fill that uses a reduced stack on the order of the
height of the screen which was better than the brute force
out-of-control stack approach.
In the end I was left wondering how I had done it in 81. Perhaps I
didn't have control of the stack. I do remember the fill took place in a
specific order cause when you watched it, it filled like water (low
points first and it would 'spill over').
If you want the reduced stack one, let me know.
John Krsek
http://www.iquest.net/~krsek
Jeff Erickson
Brent A Ellingson wrote:
> As someone pointed out, you can replace the "automagic" recursive
> call stack with a program maintained one, but you're still using
> recursion there.
If you really really hate recursion, use a queue instead of a stack.
The algorithm will still work. (The only difference is that you're
doing breadth first search instead of depth first search.)
Better yet, use a sweep-line algorithm to break the polygon up into
trapezoids with horizontal sides, and then call a trapezoid-filling
algorithm. Filling trapezoids is just two calls to Bresenham's
line-drawing algorithm (on the edges of the original polygon, not the
non-horizontal edges of the trapezoid!!)
--
Jeff Erickson Center for Geometric Computing
je...@cs.duke.edu Department of Computer Science
http://www.cs.duke.edu/~jeffe Duke University
Patrick J. Melody
This is based on some code I wrote a number of years ago. It implements
the flood fill described on pp980-982 of Foley/van Dam's "Computer Graphics:
Principles and Practice 2nd Ed." Essentially it works by popping a seed
off a stack and filling the horizontal span the seed is in, then startegically
pushing more seeds from the row above and below the current span. Repeat
until the stack is empty. I didn't find speed to be a problem. There are
prototypes for some simple routines you must write at the top, then the
kick off routine, then the main routine, then a span filling routine used
by the main routine.
/////////////////////////////////////
// nb: this implementation assumes the region to be filled is not bounded
// by the edge of the screen, but is bounded on all sides by pixels of
// the specified boundary color. This exercise is left to the student...
// pixel setter and getter
void SetPixel(int x, int y, Color c);
Color GetPixel(int x, int y);
// this algorithm uses a global stack of pixel coordinates
void pushSeed(int x, int y);
bool popSeed(int *x, int *y); // returns false iff stack was empty
// the set it up and kick it off routine.
void SeedFill(int x, int y, Color bound, Color fill)
{
// we assume the stack is created empty, and that no other
// routines or threads are using this stack for anything
pushSeed(x, y);
FillSeedsOnStack(bound, fill);
}
// the main routine
void FillSeedsOnStack(Color bound, Color fill)
{
Color col1, col2;
int x, y; // current seed pixel
int xLeft, xRight; // current span boundary locations
int i;
while (popSeed(&x, &y)) {
if (GetPixel(x, y) != bound) {
FillContiguousSpan(x, y, bound, fill, &xLeft, &xRight);
// single pixel spans handled as a special case in the else clause
if (xLeft != xRight) {
// handle the row above you
y++;
for(i=xLeft+1; i<=xRight; i++) {
col1 = GetPixel(i-1, y);
col2 = GetPixel(i, y);
if (col1 != bound && col1 != fill && col2 == bound)
pushSeed(i-1, y);
}
if (col2 != bound && col2 != fill)
pushSeed(xRight, y);
// handle the row below you
y -= 2;
for(i=xLeft+1; i<=xRight; i++) {
col1 = GetPixel(i-1, y);
col2 = GetPixel(i, y);
if (col1 != bound && col1 != fill && col2 == bound)
pushSeed(i-1, y);
}
if (col2 != bound && col2 != fill)
pushSeed(xRight, y);
} else {
col1 = GetPixel(xLeft, y+1);
col2 = GetPixel(xLeft, y-1);
if (col1 != fill)
pushSeed(xLeft, y+1);
if (col2 != fill)
pushSeed(xLeft, y-1);
}
} // end if (GetPixel)
} // end while (popSeed)
}
// fill pixels to the left and right of the seed pixel until you hit
// boundary pixels. Return the locations of the leftmost and rightmost
// filled pixels.
void FillContiguousSpan(int x, int y, Color bound, Color fill, int *xLeft, int *xRight)
{
Color col;
int i;
// fill pixels to the right until you reach a boundary pixel
i = x;
col = GetPixel(i, y);
while(col != bound) {
SetPixel(i, y, fill);
i++;
col = GetPixel(i, y);
}
*xRight = i-1;
// fill pixels to the left until you reach a boundary pixel
i = x-1;
col = GetPixel(i, y);
while(col != bound) {
SetPixel(i, y, fill);
i--;
col = GetPixel(i, y);
}
*xLeft = i+1;
}
mapson
>Gerry Panganiban wrote:
>> Does anyone know of a good non-recursive flood fill algorithm? All the
>> ones I've seen use recursion in some form or another....
>I was once told that it was "impossible" to do a general flood fill
>without using recursion. If that's the case, I would imagine that
>someone, somewhere, has the maths to prove it. I don't, but
>I have an "intuitive" feel that it's true. :-{
Hey, let's get to the bottom of this! I wasn't interested before, but
now it soudns interesting.... For a start, what's floodfill anyway,
and why would it potentially be impossible without recursion?
Sofus Macskassy
map...@mapson.com (mapson) writes:
Flood fill: starting at a given point, fill in the screen (or map) stopping
when reaching a border. (ie: fill in the color red, stopping when you see
green. If green completely surrounds the given point, the red will then fill
out only to that point). I feel this was not a good explanation, but it
should get the point across.
Actually, you _can_ do it without recursion, but you then need to have an
extra data structure to remember past points where the flood fill could have
gone other ways. Then, when you reach a point where you can't continue
further, you go back to a previous point, and continue from there.
This is pretty much what recursion does as well, so while this is not true
recursion, it functionally works the same way.
As far as I know, there is no other way to do it.
-Sofus Macskassy.
-sof...@cesl.rutgers.edu
Werner Van Belle
morg (mor...@cs.uoregon.edu) wrote:
: On Tue, 29 Jul 1997 03:23:39 GMT, lil...@fastlane.net (Matthew Palmer)
: wrote:
:
: >I'd bet it's possible to imitate the recursion using a while
: >loop, and instead of calling the same function as the recursion
: >does, just push that location or whatever onto a stack.
: Exactly, you can always rewrite a recursive funtion using a local
: stack
that doesn't change the memory-overhead, which was propably his problem.
Werner,-
Chea Chee Weng
Gerry Panganiban (panga...@btw.com) wrote:
: Does anyone know of a good non-recursive flood fill algorithm? All the
: ones I've seen use recursion in some form or another....
: -Gerry
Most of the well-known flood fill algorithms use some-sort of simulated
recursion to overcome the stack overflow problem. Generally speaking,
i prefer the filling algorithm by Fishkin as discussed in Graphics Gems 2.
It is said to be the fastest filling algorithm. By the way, when i
implemented the flood-fill algorithms eons ago, it seems like a circular
queue could be used and conserved more space than using a usual stack.
The size of the circular queue is dependent on twice the horizontal
extent of the image.
Rob Rodgers
wer...@igwe8.vub.ac.be (Werner Van Belle) wrote:
>that doesn't change the memory-overhead, which was propably his problem.
You can't really get away from that.
You can do an non-recursive, utterly simple looping flood fill by
spiraling (take the point where the flood fill begins, draw a
continuous line NSEW, then trace the edges until you can't any longer
-- even works with complex shapes) but this is going to be
(1) hideously slow
(2) involve bazillions of references to memory
(3) a good entry in the Inelegant Graphics Code Contest
This is such a godawful idea that even a completely dumb optimization
on the same idea (draw a single outline and then do dumb scanline
filling, writing while "in" the outline and skipping pixels while
"out" of the outline) will vastly outperform it principally by
eliminating the thousands of checks to see whether the current pixel
is fillable.
If _reads_ are the main concern, this might just be worth
investigating...
Then there are the largest box style (divide the area into boxes, fast
fill the boxes) and similar algorithms which actually work pretty well
if you have hardware rectangular blits or linedraw...
----
[ kn...@acm.org ] [ Speed has always been important, otherwise ]
[ one wouldn't need the computer. Seymore Cray ]
[ etch tee tee pee colon slash slash double-u-double-u-double-u dot wam ]
[ dot you em dee dot ee de you slash squiggle ar ess ar oh dee gee ee ar ]
http://www.wam.umd.edu/~rsrodger
Wayne O. Cochran
Brent A Ellingson wrote:
>
> Gerry Panganiban wrote:
> >
> > Does anyone know of a good non-recursive flood fill algorithm? All the
> > ones I've seen use recursion in some form or another....
> >
> > -Gerry
<aside> Those of you versed in computational theory know
that "recursive" is synonomous with "computable." In this
light, the above question is more interesting.</aside>
> I was once told that it was "impossible" to do a general flood fill
> without using recursion. If that's the case, I would imagine that
> someone, somewhere, has the maths to prove it. I don't, but
> I have an "intuitive" feel that it's true. :-{
Iterative algorithms exist for floodfilling in a finite frame buffer.
proof:
A simple proof would be constructive. Consider the algorithm
that allocated a binary buffer where each bit had a 1-to-1
correspondance with each pixel in the frame buffer.
First, set the bit in this buffer corresponding to the seed
pixel location and clear the remaining bits. Then,
for each pixel in the frame buffer that has the same original value
(i.e. color) as the seed pixel and corresponds to a zero
in the allocated bit buffer and is adjacent to (i.e. 4-connected
to) a non-zero bit in the bit buffer do the following:
color that pixel with the new seed pixel color and set the
corresponding bit in the bit buffer. Repeat this process
until the bit buffer remains unchanged. This algorithm is
guaranteed to terminate since, in the worst case, every bit
in the bit buffer would be set and would remain unaltered
in the following iteration.
Now this would be a horrible implementation in terms of memory
and time, but indeed correctly performs the floodfill and
is completely iterative. QED.
As outrageous as the above algorithm sounds, varieties of it exist
for floodfilling and determining connected components (used heavily
in computer vision e.g. optical character recognition).
The point of the matter is *not* whether an algorithm can be
constructed which is non-recursive (in the lay programmers
terminology), but can an algorithm be constructed that does not
require memory proportional to the frame buffer size and its
speed is linear with respect to the size of the connected component
(i.e. the area of or number of pixels in the flood fill).
I would surmise (without proof) that floodfilling is worst case
O(B) in terms of memory where B is the size of the frame buffer.
The worst case scenarios generally consist of regions that are
highly non-convex.
> As someone pointed out, you can replace the "automagic" recursive
> call stack with a program maintained one, but you're still using
> recursion there.
Again, whether you are using the program stack, a user allocated
stack, or allocating a bit-buffer as above they all require memory
proportional to the frame buffer size in the worst case.
> Warning: the above post contains NO actual information. If you
> thought you saw something imformative, read again.
That is why I chose to respond to this part of the thread.
This could be said for 98% of usenet postings; The information
entropy of usenet is indeed increasing.
> Brent Ellingson
-- wayne
Wayne O. Cochran
wcoc...@eecs.wsu.edu
http://www.eecs.wsu.edu/~wcochran
Ecclesiastes 3:11
George Kinney
Werner Van Belle <wer...@igwe8.vub.ac.be> wrote in article
<5rqo0j$f...@rc1.vub.ac.be>...
> morg (mor...@cs.uoregon.edu) wrote:
> : On Tue, 29 Jul 1997 03:23:39 GMT, lil...@fastlane.net (Matthew Palmer)
> : wrote:
> :
> : >I'd bet it's possible to imitate the recursion using a while
> : >loop, and instead of calling the same function as the recursion
> : >does, just push that location or whatever onto a stack.
> :
> : Exactly, you can always rewrite a recursive funtion using a local
> : stack
>
Maybe, maybe not.
There's bound to be more free RAM than is allocated for the program's
stack.
Recursive functions will eat the program's stack, but if you are using an
iterative approach, you can grab whatever RAM is available and use it.
It isn't always a solution, but generally, you'll have more RAM than stack
space available by default on many platforms.
Most of the cases where I've run out of stack space, I've opted for using
an iterative approach. Mainly because alloc'ing a larger stack at startup
just eats RAM that could be used by other processes. Using an iterative
approach, I can grab and release RAM as needed for my algo's stack.
Then again, there were cases where the recursion was critical (or I was too
lazy to re-do it :) and just setting up a deeper stack was the ticket.
I'm sure we all know the golden rule of programming by now:
Some algos are better than others, except when they aren't. :)
Valient Gough
Brent A Ellingson wrote:
> Gerry Panganiban wrote:
> >
> > Does anyone know of a good non-recursive flood fill algorithm? All
> the
> > ones I've seen use recursion in some form or another....
> >
> > -Gerry
>
> I was once told that it was "impossible" to do a general flood fill
> without using recursion. If that's the case, I would imagine that
> someone, somewhere, has the maths to prove it. I don't, but
> I have an "intuitive" feel that it's true. :-{
>
It is completely possible to do a non-recursive flood-fill. I've been
using one for a couple years. I originally designed it for fast region
growing for machine vision problems.
First, find a border of your area, then follow the border around the
perimeter of your area to fill. While following the border, you add new
border points to a scanline (one scanline list for each Y, of course).
Then, fill the scan intervals, checking each pixel for inclusion in your
area. If you find a non-included pixel (a hole in your area), run the
border following on the hole, adding those border points to your scan
line lists. This has the effect of cutting out the holes.
Continue until you have checked each pixel.
There is no recursion, and no stack or queue based pseudo recursion. If
this isn't clear, consider the following pseudo-code (showing the call
sequence).
-fillArea: startPoint
region = [self boundaryTrace: startPoint];
[self floodFill: region];
-floodFill: region
for each scanline
for each interval
for each point in interval
if ![self inArea: point]
// found a hole, remove it
[self boundaryTrace: point intoRegion:
region];
break; // skip to next interval
regards,
Val Gough
barrym
George Kinney (goo...@mail.net) wrote:
:
: Most of the cases where I've run out of stack space, I've opted for using
: an iterative approach. Mainly because alloc'ing a larger stack at startup
: just eats RAM that could be used by other processes. Using an iterative
: approach, I can grab and release RAM as needed for my algo's stack.
There is a third alternative, although this would probably have to be
done in asm. That's to create a temporary stack in that larger free
ram area at the beginning of the fill routine, and then restore the
old stack pointers.
I've never actually done anything like this from within a c program but
my guess would be the whole fill routine would have to be in asm to
avoid interfering with c, which probably likes knowing where the stack
is. But, who knows, if there isnt any stack checking code, c might not
mind at all. A little experimenting and studying the compiler output
would answer that.
Barry