This article assumes that you have a basic understanding of:
- Direct pixel access in GDI+
- I highly recommend reading all of the articles in Christian Graus's image processing series, but if you don't read them all, at least you should read the first one - it gives you the basic knowledge necessary for pixel manipulation in GDI+.
GDI+ does not have built-in flood fill capabilities. This example shows you how to create three different flood-fill algorithms for GDI+. It expands on the typical flood fill implementation by allowing adjustable color tolerance, and optional 8-way (diagonal) branching.
The flood fill algorithms will not be as fast as they would be if they were written in assembler, but you most likely won't notice this in ordinary use, because they are still quite fast.
There are two main types of flood fills. The most common is 4-direction flood fill. This type of flood fill starts from a single point and branches up, down, and to the right and left. The 8-direction flood fill is similar to the 4-direction, except that it also branches diagonally.
Figure 1: The 4-direction flood fill branches in 4 directions from each pixel, whereas the 8-direction flood fill branches in 8 directions from each pixel.
We will look at 3 different flood fill algorithms - linear, recursive, and queue.
This is the most common algortihm, and simplest to implement. The recursive algorithm branches in all directions at once. This can (read: often will) lead to stack overflows in a managed environment.
The queue algorithm is similar to the recursive algorithm, except that it adds the points to be checked to a queue rather than calling them directly. The loop returns immediately to the main fill method, rather than calling itself recursively. It requires extra heap space for a queue, but it uses hardly any stack space.
The queue algorithm is by far the slowest algorithm, taking about twice as long as the others. This may be partly because of lack of optimizations in the .NET
Queue class, but the queue method would be slower regardless of whether the
Queue class was optimized.
The linear algorithm first finds the horizontal extent of the color on a given level, then it moves horizontally from left to right, initializing the fill loop upwards and downwards for each point along the way.
By handling vertical and horizontal checking separately, this algorithm consumes only half the stack space that the recursive algorithm uses, while avoiding the extra heap space needed for a queue. It is also just as fast as the recursive algorithm.
Needless to say, the linear algorithm is the best algorithm of the three covered here. I decided to cover the others because they would inevitably be brought up anyway if I didn't do it in the article. Anyway, it's nice to see some other kinds of techniques that could be used.
The demonstration program
The demo program allows you to open and save bitmap files, and flood-fill them. It allows you to change the fill color and color tolerance for the fill operation, and has a brief explanation of each algorithm. You can watch the fill operation in slow motion (helpful for understanding how the different algorithms work). You can also see how long the flood fill operation took.
So as not to take up too much space, I am only showing a small part of the code - the method that starts the fill, the 4-way version of the linear algorithm, and the function that checks the pixels.
public override void FloodFill(Bitmap bmp, Point pt)
System.IntPtr Scan0 = bmpData.Scan0;
byte * scan0=(byte *)(void *)Scan0;
int color= *((int*)(scan0+loc));
case FloodFillStyle.Linear :
case FloodFillStyle.Queue :
case FloodFillStyle.Recursive :
unsafe void LinearFloodFill4( byte* scan0, int x, int y,Size bmpsize,
int stride, byte* startcolor)
int* p=(int*) (scan0+(CoordsToIndex(x,y, stride)));
unsafe bool CheckPixel(byte* px, byte* startcolor)
ret&= (px[i]>= (startcolor[i]-m_Tolerance[i])) &&
px[i] <= (startcolor[i]+m_Tolerance[i]);
Undoubtedly there will be optimizations that I did not think of, and you are more than welcome to mention any that you find.
- 10/05/03 - Posted the article