The purpose of Flood Fill is to color an entire area of connected pixels with
the same color. It's the Bucket Tool in many painting programs. Here's an
example: the original image is on the left. Then a floodfill was started inside
the large shape, and the algorithm gave all pixels inside the shape the new
color, leaving it's borders and the pixels outside intact.
The Flood Fill algorithm is also sometimes called Seed Fill: you plant a seed
(the pixel where you start), and, recursively, more and more seeds are planted
around the original seed if those pixels have the correct color. Each new seed
is responsible for coloring the pixel at it's position, and testing for new
pixels around it that have to be colored.
There exist many different floodfill algorithm, 3 of them are discussed here,
and two versions of each: a version with recursion, and a version with a stack.
There also exists the so called Boundary Fill, this is very similar to Flood
Fill, but will color an area with pixels of a certain color as boundary. The
algorithms for boundary fill are very similar apart from the conditions in the
tests for planting new seeds.
Test Program
To test the different flood fill algorithms, we need a test program that allows
you to create shapes to fill. The test program is a small version of the
painting program described in the "Painting" tutorial. It also includes a
benchmark that allows you to compare two different floodfill algorithms and
shows the time in milliseconds it took each of them to fill an area 50 times.
Because floodfilling requires reading pixels, we use a buffer to contain the
pixels (called screenBuffer[w][h]) instead of reading and writing pixels
directly to the screen. All colors used here are integer values, instead of
using the ColorRGB struct.
The code given here includes the full test program except the floodfill
algorithms (which are explained in the rest of this tutorial) and the
paint_drawLine function, which is an exact copy of the drawLine function from
QuickCG.cpp but draws to screenBuffer instead of directly to the screen.
Here are the initializations of all the floodFill functions we'll be making, the
stack used by some of the functions, the auxiliary functions, and the graphics
buffer.
The size of the stack defined here is pretty big (166777216), you can easily
make it much smaller, the only case where it has to be this big is when you want
to try the worse of the floodfill functions on a very large screen. The best
floodfill algorithm doesn't require a big stack at all, unless you're working at
huge resolutions.
//the floodfill algorithms
void floodFill4(int x, int y, int newColor, int oldColor);
void floodFill8(int x, int y, int newColor, int oldColor);
void floodFill4Stack(int x, int y, int newColor, int oldColor);
void floodFill8Stack(int x, int y, int newColor, int oldColor);
void floodFillScanline(int x, int y, int newColor, int oldColor);
void floodFillScanlineStack(int x, int y, int newColor, int oldColor);
//the stack
#define stackSize 16777216
int stack[stackSize];
int stackPointer;
//the auxiliary functions
bool paint_drawLine(int x1, int y1, int x2, int y2, ColorRGB
color);
void clearScreenBuffer(ColorRGB color);
//the graphics buffer
#define screenW 256
#define screenH 256
int screenBuffer[screenW][screenH];
Here's the main function of the test program, it can do 3 different mouse
actions:
If you press the left mouse button, it draws a line between the current
and previous position, so that you can draw shapes, as explained in the
"Painting" tutorial. This allows you to make areas to fill.
If you press the right mouse button, it'll floodFill at that position
with a color defined by the coordinates of that position. This allows you to
floodfill with many different colors without needing a color selector. You
can change the floodfill function used to any of the other 5 functions.
If you press both mouse buttons at the same time, the screen is cleared
to white again.
The benchmark code does 2 floodfill algorithms of your choice 50 times,
remembers the time it took them, displays the resulting times, and sleeps until
you press a key. Start the benchmark by pressing space, it'll perform the
floodfills at the current mouse position.
Here are the stack functions, only used by 3 of the floodFill functions. A stack
is a memory structure where you can push new values on top, or pop them again
off it to read them. You can only access the top value of a stack, and to read
the top value, you have to pop it, thereby removing it.
The stack itself has the integer as data type, but this single integer is used
to store both the x and y coordinate: store it as p = h * x + y, and get the two
values again by using x = p / h, y = p % h.
The pop function takes x and y passed by reference, so that this function can
change the x and y given in it's parameters. The pop function returns 1 if it
successfully got a value from the top of the stack, or 0 if the stack was empty.
The push function returns 1 if it could successfully push a value onto the
stack, or 0 if the stack was full.
The emptyStack function empties the complete stack until 0 values are left on
it.
bool pop(int
&x, int &y)
{
if(stackPointer > 0)
{
int p = stack[stackPointer];
x = p / h;
y = p % h;
stackPointer--;
return 1;
}
else
{
return 0;
}
}
bool push(int x, int y)
{
if(stackPointer < stackSize - 1)
{
stackPointer++;
stack[stackPointer] = h * x + y;
return 1;
}
else
{
return 0;
}
}
void emptyStack()
{
int x, y;
while(pop(x, y));
}
Here's one of the auxiliary functions, clearScreenBuffer. It sets the whole
screenBuffer to the given color. The other function, paint_drawLine isn't given
here because it's quite big and almost the same as the drawLine function in
quickCG.cpp, except that it sets pixels of screenBuffer to the given color,
instead of using pset.
void clearScreenBuffer(ColorRGB color)
{
for(int x = 0; x < w; x++)
for(int y = 0; y < h; y++)
{
screenBuffer[x][y] = RGBtoINT(color);
}
}
Apart from these functions, the test program of course needs you to define the 6
floodFill functions too, but these are given below.
4-Way Recursive Method (floodFill4)
This is the most simple algorithm to make, but also the slowest. Also, since it
uses a recursive function, the recursion stack may overflow making it crash when
filling larger areas.
You call the function with in it's parameters: the start position (where you
clicked for the floodfill to start), the oldColor (the color of the area you're
overdrawing) and the newColor (the color these pixels should get). The recursion
works like this: at the start position, you "plant a seed". Each seed gives the
pixel at it's position the new color, and then plants a new seed at it's 4
neighbors. Each of these new seeds will draw a pixel again and plant even more
seeds, but only if fulfills the following conditions:
The pixel is inside the screen: edges of the screen also count as edges
of the area to be filled.
The pixel has oldColor: if it hasn't, it's either a border of the area
we're filling, or a pixel that has already been given the newColor.
The pixel doesn't have newColor: this condition is only needed if
oldColor is the same as oldColor, otherwise it'll keep running forever since
newly drawn pixels will again have oldColor and thus seeds will be planted
again and again forever.
This is very easy to program:
//Recursive 4-way floodfill, crashes if recursion stack is full
void floodFill4(int x, int y, int newColor, int oldColor)
{
if(x >= 0 && x < w && y >= 0 && y < h &&
screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
{
screenBuffer[x][y] = newColor; //set color before starting recursion
floodFill4(x + 1, y, newColor, oldColor);
floodFill4(x - 1, y, newColor, oldColor);
floodFill4(x, y + 1, newColor, oldColor);
floodFill4(x, y - 1, newColor, oldColor);
}
}
The function will keep calling itself more and more until eventually all pixels
are filled. The order in which you call the floodFill4 functions for the
neighbors doesn't really matter. In the example above it first tries the
neighbor to the right, so the algorithm will first draw a line going to the
right, until it meets an edge. Then the last called floodFill4 function returns
to the pre-last one, which tests the neighbor to the left. Since that one has
been drawn alraedy, it tests the one down. That one isn't drawn yet, and if it
isn't an edge, the algorithm will continue there, testing to the right again,
and so on...
Note how the color is represented as an integer, instead of using the slower
ColorRGB struct.
This screenshot shows the floodFill4 algorithm while it's still busy:
8-Way Recursive Method (floodFill8)
This algorithm is pretty similar to the previous one, except it doesn't test 4
neighbors, but 8. This means, that this version of the floodfill algorithm will
leak through sloped edges of 1 pixel thick:
Both red pixels are now a neighbor of each other, so the algorithm wil continue
behind the sloped black line. The code is very similar to the 4-way one:
//Recursive 8-way floodfill, crashes if recursion stack is full
void floodFill8(int x, int y, int newColor, int oldColor)
{
if(x >= 0 && x < w && y >= 0 && y < h &&
screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
{
screenBuffer[x][y] = newColor; //set color before starting recursion!
floodFill8(x + 1, y, newColor, oldColor);
floodFill8(x - 1, y, newColor, oldColor);
floodFill8(x, y + 1, newColor, oldColor);
floodFill8(x, y - 1, newColor, oldColor);
floodFill8(x + 1, y + 1, newColor, oldColor);floodFill8(x - 1, y - 1, newColor, oldColor);floodFill8(x - 1, y + 1, newColor, oldColor);floodFill8(x + 1, y - 1, newColor, oldColor);
}
}
Unlike the 4-way version, the 8-way version can fill thin lines, for example the
edge of a shape:
The floodFill4 algorithm (the way the bucket tool of painting programs work)
would only have colored a few pixels of the black curve, the pixels which only
touch a corner aren't considered neighbors in that case.
However, you can't use floodFill8 to fill the inside of the shapes because it'll
leak through the sides.
4-Way Method With Stack (floodFill4Stack)
This algorithm does exactly the same as the one with recursion, only it uses a
while loop that loops until the stack is empty, and you push new positions to
the stack instead of starting another recursion. So the only difference is that
we're using our own stack routines now, instead of the ones used for recursive
functions. This means we can control the size of the stack, and properly stop
the floodfill algorithm if the stack overflows, instead of just letting the
program crash. There are also a few other minor differences in the
implementation.
The stack routines were described in the Test Program chapter.
There is very likely to be an error in this chapter. I'll investigate this
later.
This algorithm is based on the following steps:
Start by filling the current vertical line from one end to the other
While filling the current scanline, test for the ends of spans left and
right
For each new free span, plant a seed
Repeat until there are no more seeds
Like the original floodFill4 and floodFill8 algorithms,
this one is recursive, but now each recursion will fill a whole vertical line
instead of a single pixel, so much less recursions and stack depth are needed.
The implementation given below first draws the current vertical line, and then
tests for vertical lines left and right and plants the new seeds by recursively
calling itself again.
This algorithm gives the same result as the floodFill4 algorithm, not as the
floodFill8 one. If you want, you can modify it to work like the floodFill8 one
by making it test for spans left and right one pixel up and down too.
//stack friendly and fast floodfill algorithm
void floodFillScanline(int x, int y, int newColor, int oldColor)
{
if(oldColor == newColor) return;
if(screenBuffer[x][y] != oldColor) return;
int y1;
//draw current scanline from start position to the top
y1 = y;
while(y1 < h && screenBuffer[x][y1] == oldColor)
{
screenBuffer[x][y1] = newColor;
y1++;
}
//draw current scanline from start position to the bottom
y1 = y - 1;
while(y1 >= 0 && screenBuffer[x][y1] == oldColor)
{
screenBuffer[x][y1] = newColor;
y1--;
}
//test for new scanlines to the left
y1 = y;
while(y1 < h && screenBuffer[x][y1] == newColor)
{
if(x > 0 && screenBuffer[x - 1][y1] == oldColor)
{
floodFillScanline(x - 1, y1, newColor, oldColor);
}
y1++;
}
y1 = y - 1;
while(y1 >= 0 && screenBuffer[x][y1] == newColor)
{
if(x > 0 && screenBuffer[x - 1][y1] == oldColor)
{
floodFillScanline(x - 1, y1, newColor, oldColor);
}
y1--;
}
//test for new scanlines to the right
y1 = y;
while(y1 < h && screenBuffer[x][y1] == newColor)
{
if(x < w - 1 && screenBuffer[x + 1][y1] == oldColor)
{
floodFillScanline(x + 1, y1, newColor, oldColor);
}
y1++;
}
y1 = y - 1;
while(y1 >= 0 && screenBuffer[x][y1] == newColor)
{
if(x < w - 1 && screenBuffer[x + 1][y1] == oldColor)
{
floodFillScanline(x + 1, y1, newColor, oldColor);
}
y1--;
}
}
This screenshot shows the vertical scanline floodfill algorithm while it's busy:
Normally, Scanline floodfill algorithms actually work with horizontal scanlines
instead of vertical ones. However, I found with the benchmark that it works much
faster with vertical ones, and the reason appeared to be the following: the CPU
caches parts of the 2D screenBuffer array, and when working with vertical lines
you're only changing the y-coordinate of that array, and the data it's working
with is then much more closely packed to each other in the memory structure,
than when you're changing it in the x-direction. When the data is further apart,
the chance is higher that not everything needed is cached, making it slower.
This might depend on what platform is used though. It's easy to convert the
function to work with horizontal lines instead, use x1 instead of y1 and swap
the coordinates in the rest of the code, for example "y1 = y - 1" becomes "x1 =
x - 1", and "screenBuffer[x - 1][y1]" becomes "screenBuffer[x1][y - 1]". The
difference in speed is especially visible when filling large shapes at high
resolutions.
Scanline Floodfill Algorithm With Stack (floodFillScanlineStack)
This is very similar to the previous algorithm, except again our own stack
routines are used instead of recursion. This implementation also uses two
boolean variables, "spanLeft" and "spanRight" to remember if pixels tested on
the left or right are part of a new span, or one already pushed to the stack. In
the implementation with recursion this wasn't needed, because there the spans to
the left and right were drawn first, causing all it's pixels to get the newColor
already so that other pixels of it couldn't be detected anymore.
Here's the result of a benchmark between the floodFill4Stack and the
floodFillScanlineStack function: it took floodFill4Stack 239 milliseconds to
fill the shape 50 times, while it took floodFillScanlineStack only 34
milliseconds.
