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 [You must be registered and logged in to see this link.].
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: [You must be registered and logged in to see this link.].

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.

int main(int argc, char *argv[]) { screen(screenW, screenH, 0, "Flood Fill"); clearScreenBuffer(RGB_White); int mouseX, mouseY; int oldMouseX, oldMouseY; bool LMB, RMB; while(!done()) { oldMouseX = mouseX; oldMouseY = mouseY; getMouseState(mouseX, mouseY, LMB, RMB); //3 different mouse input actions if(LMB) paint_drawLine(oldMouseX, oldMouseY, mouseX, mouseY, RGB_Black); if(RMB) { int color = RGBtoINT(ColorRGB((mouseX % 3 + 1) * 64, (mouseY % 8) * 32, (mouseX + mouseY) % 256)); floodFillScanlineStack(mouseX, mouseY, color, screenBuffer[mouseX][mouseY]); } if(RMB && LMB) clearScreenBuffer(RGB_White); //benchmark readKeys(); if(inkeys[SDLK_SPACE]) { float startTime = getTime(); for(int i = 1; i < 50; i++) floodFill4Stack(mouseX, mouseY, RGBtoINT(ColorRGB(i,255,i)), screenBuffer[mouseX][mouseY]); float endTime = getTime(); float startTime2 = getTime(); for(int i = 1; i < 50; i++) floodFillScanlineStack(mouseX, mouseY, RGBtoINT(ColorRGB(i,255,i)), screenBuffer[mouseX][mouseY]); float endTime2 = getTime(); drawBuffer(screenBuffer[0]); print(endTime - startTime, 0, 0, 0, RGB_Black, 1, RGB_White); print(endTime2 - startTime2, 0, 0, 8, RGB_Black, 1, RGB_White); redraw(); sleep(); } //redraw the screen each frame drawBuffer(screenBuffer[0]); redraw(); } return 0; }

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.

//4-way floodfill using our own stack routines void floodFill4Stack(int x, int y, int newColor, int oldColor) { if(newColor == oldColor) return; //avoid infinite loop emptyStack(); if(!push(x, y)) return; while(pop(x, y)) { screenBuffer[x][y] = newColor; if(x + 1 < w && screenBuffer[x + 1][y] == oldColor) { if(!push(x + 1, y)) return; } if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor) { if(!push(x - 1, y)) return; } if(y + 1 < h && screenBuffer[x][y + 1] == oldColor) { if(!push(x, y + 1)) return; } if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor) { if(!push(x, y - 1)) return; } } }

This algorithm goes a bit faster than the recursive version.
8-Way Method With Stack
(floodFill8Stack)


This is the 8-way version of the previous function, and only
differs because it has 4 extra neighbor test conditions:

//4-way floodfill using our own stack routines void floodFill4Stack(int x, int y, int newColor, int oldColor) { if(newColor == oldColor) return; //avoid infinite loop emptyStack(); if(!push(x, y)) return; while(pop(x, y)) { screenBuffer[x][y] = newColor; if(x + 1 < w && screenBuffer[x + 1][y] == oldColor) { if(!push(x + 1, y)) return; } if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor) { if(!push(x - 1, y)) return; } if(y + 1 < h && screenBuffer[x][y + 1] == oldColor) { if(!push(x, y + 1)) return; } if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor) { if(!push(x, y - 1)) return; } if(x + 1 < w && y + 1 < h && screenBuffer[x + 1][y + 1] == oldColor) { if(!push(x + 1, y + 1)) return; } if(x + 1 < w && y - 1 >= 0 && screenBuffer[x + 1][y - 1] == oldColor) { if(!push(x + 1, y - 1)) return; } if(x - 1 >= 0 && y + 1 < h && screenBuffer[x - 1][y + 1] == oldColor) { if(!push(x - 1, y + 1)) return; } if(x - 1 >= 0 && y - 1 >= 0 && screenBuffer[x - 1][y - 1] == oldColor) { if(!push(x - 1, y - 1)) return; } } }

Recursive Scanline
Floodfill Algorithm (floodFillScanline)


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.

//The scanline floodfill algorithm using our own stack routines, faster void floodFillScanlineStack(int x, int y, int newColor, int oldColor) { if(oldColor == newColor) return; emptyStack(); int y1; bool spanLeft, spanRight; if(!push(x, y)) return; while(pop(x, y)) { y1 = y; while(y1 >= 0 && screenBuffer[x][y1] == oldColor) y1--; y1++; spanLeft = spanRight = 0; while(y1 < h && screenBuffer[x][y1] == oldColor ) { screenBuffer[x][y1] = newColor; if(!spanLeft && x > 0 && screenBuffer[x - 1][y1] == oldColor) { if(!push(x - 1, y1)) return; spanLeft = 1; } else if(spanLeft && x > 0 && screenBuffer[x - 1][y1] != oldColor) { spanLeft = 0; } if(!spanRight && x < w - 1 && screenBuffer[x + 1][y1] == oldColor) { if(!push(x + 1, y1)) return; spanRight = 1; } else if(spanRight && x < w - 1 && screenBuffer[x + 1][y1] != oldColor) { spanRight = 0; } y1++; } } }

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.

Nguồn [You must be registered and logged in to see this link.]

toàn tiếng anh, đọc mãi ko hiểu, có ai hiểu thì bảo mình với, dùng thuật toán nào trong chỗ trên kia để làm bt lớn là OK nhất ???