24-04-2014, 12:48 PM
Lode's Computer Graphics Tutorial Flood Fill
Computer Graphics .pdf (Size: 285.03 KB / Downloads: 21)
Introduction
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.
You can download the full source code of this tutorial here.
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. The full source, including all these
functions, can be downloaded here: floodfill.cpp.
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.