12,078,769 members (50,354 online)
alternative version

329.8K views
101 bookmarked
Posted

# QuickFill: An efficient flood fill algorithm.

, 12 Mar 2004
 Rate this:
Design and implimentation of efficient flood fill algorithms.

Original image:

Fill pattern:

## Introduction

In order to show the strengths of a good design, I must first: describe the basic types of flood filling and there individual strengths and weaknesses.

Note: By efficient, I mean creating an algorithm that reads as few pixels as possible and uses the least amount of memory allocations. Although we are now talking about flood filling a bitmap, historically speaking, flood fills read and wrote directly to the video, which was very slow. Therefore, it was a must to reduce the number of reads and writes; also the amount of memory was limited, so a reduction in memory usage was also a big plus.

### What is the QuickFill algorithm?

The QuickFill algorithm is a non-recursive (seed fill) method of filling a 2D graphics image using a scan line search method and doubly linked to lists of nodes to reduce the amount of memory required. The scan line method used in combination with the linked lists, greatly increases the speed at which an image can be filled and allows for multiple fill types to be implemented: background, border, and pattern fills.

Note: The original QuickFill algorithm was written, as part of my personal DOS graphics library, to fill images displayed on a video monitor.

## Basic 4 way recursive method

This is the most basic of all flood filling methods, as well as the simplest.

Its strength: simple to implement by even a beginner programmer.

Its weaknesses: repeated sampling of pixels and recursion (may overflow stack).

The diagram above shows how the flooding of a 3x3 image progresses. As you can see: each pixel was visited 2 or more times, and the depth of recursion was 10.

```// Fill background with given color
void SeedFill_1(int x, int y, COLORREF fill_color)
{
if( fill_color != GetPixel(x,y) ) { // sample pixel color
SeedFill_1(x,y,fill_color);
SeedFill_1(x-1,y,fill_color);
SeedFill_1(x+1,y,fill_color);
SeedFill_1(x,y-1,fill_color);
SeedFill_1(x,y+1,fill_color);
}
}```
```// Fill (over write) all pixels that are not the border color
void SeedFill_2(int x, int y, COLORREF fill_color, COLORREF border_color)
{
if( border_color != GetPixel(x,y) ) { // sample pixel color
SeedFill_2(x,y,fill_color,border_color);
SeedFill_2(x-1,y,fill_color,border_color);
SeedFill_2(x+1,y,fill_color,border_color);
SeedFill_2(x,y-1,fill_color,border_color);
SeedFill_2(x,y+1,fill_color,border_color);
}
}```

## Basic 8 way recursive method

This is similar to the 4 way method, except that it is even more inefficient.

Its strength: simple to implement by even a beginner programmer.

Its weaknesses: repeated sampling of pixels, recursion (may overflow stack), and it is designed to leak on the diagonals.

Note: This is what I call an abnormal flood fill method. Since it is designed to leak on the diagonals, it has very limited use.

The diagram above shows how the flooding of a 3x3 image progresses. As you can see: each pixel was visited 3 or more times, and the depth of recursion was 10.

```// Fill background with given color
void SeedFill_1(int x, int y, COLORREF fill_color)
{
if( fill_color != GetPixel(x,y) ) { // sample pixel color
SeedFill_1(x,y,fill_color);
SeedFill_1(x-1,y,fill_color);
SeedFill_1(x+1,y,fill_color);
SeedFill_1(x,y-1,fill_color);
SeedFill_1(x,y+1,fill_color);
SeedFill_1(x-1,y+1,fill_color);
SeedFill_1(x+1,y-1,fill_color);
SeedFill_1(x+1,y+1,fill_color);
SeedFill_1(x-1,y-1,fill_color);
}
}```
```// Fill (over write) all pixels that are not the border color
void SeedFill_2(int x, int y, COLORREF fill_color, COLORREF border_color)
{
if( border_color != GetPixel(x,y) ) { // sample pixel color
SeedFill_2(x,y,fill_color,border_color);
SeedFill_2(x-1,y,fill_color,border_color);
SeedFill_2(x+1,y,fill_color,border_color);
SeedFill_2(x,y-1,fill_color,border_color);
SeedFill_2(x,y+1,fill_color,border_color);
SeedFill_2(x-1,y+1,fill_color,border_color);
SeedFill_2(x+1,y-1,fill_color,border_color);
SeedFill_2(x+1,y+1,fill_color,border_color);
SeedFill_2(x-1,y-1,fill_color,border_color);
}
}```

## Recursive scan line method

The recursive scan line method is a type of 4 way method, but is more efficient than the 4 or 8 way single pixel recursive methods.

Its strength: complete lines are scanned.

Its weaknesses: repeated sampling of some lines and recursion (may overflow stack).

The diagram above shows how the flooding of a 3x3 image progresses. As you can see: each line was visited 1 to 3 times, and the depth of recursion was 2.

The line fill method below may be inefficient, but it reduces the number of times that a pixel is revisited and reduces the number of recursive calls made. It also has the advantage of being optimizable, that is it can be improved through optimization techniques.

Some techniques that can be applied are:

1. write scan and search line functions that read and write the image data directly,
2. rewrite the function to remove recursion.
```// Fill background with given color
extern int nMinX, nMaxX, nMinY, nMaxY;
void LineFill_3(int x1, int x2, int y,
COLORREF fill_color, COLORREF seed_color)
{
int xL,xR;
if( y < nMinY || nMaxY < y )
return;
for( xL = x1; xL >= nMinX; --xL ) { // scan left
if( GetPixel(xL,y) != seed_color )
break;
SetPixel(xL,y,fill_color);
}
if( xL < x1 ) {
LineFill_3(xL, x1, y-1, fill_color, seed_color); // fill child
LineFill_3(xL, x1, y+1, fill_color, seed_color); // fill child
++x1;
}
for( xR = x2;  xR <= nMaxX; ++xR ) { // scan right
if( GetPixel(xR,y) !=  seed_color )
break;
SetPixel(xR,y,fill_color);
}
if(  xR > x2 ) {
LineFill_3(x2, xR, y-1, fill_color, seed_color); // fill child
LineFill_3(x2, xR, y+1, fill_color, seed_color); // fill child
--x2;
}
for( xR = x1; xR <= x2 && xR <= nMaxX; ++xR ) {  // scan betweens
if( GetPixel(xR,y) == seed_color )
SetPixel(xR,y,fill_color);
else {
if( x1 < xR ) {
// fill child
LineFill_3(x1, xR-1, y-1, fill_color, seed_color);
// fill child
LineFill_3(x1, xR-1, y+1, fill_color, seed_color);
x1 = xR;
}
// Note: This function still works if this step is removed.
for( ; xR <= x2 && xR <= nMaxX; ++xR) { // skip over border
if( GetPixel(xR,y) == seed_color ) {
x1 = xR--;
break;
}
}
}
}
}

void SeedFill_3(int x, int y, COLORREF fill_color)
{
COLORREF seed_color = GetPixel(x,y);
if( fill_color != seed_color )
LineFill_3(x,x,y,fill_color,seed_color);
}```

## A simple non-recursive scan line method

The non-recursive scan line method is a type of 4 way method, but is more efficient than the recursive method.

Its strengths: complete lines are scanned, and no recursion.

Its weaknesses: repeated sampling of some lines, and limited stack size.

The line fill method below is more inefficient, than the recursive method. It also has the advantage of being optimizable, that is it can be improved through optimization techniques.

Some techniques that can be applied are:

1. write scan and search line functions that, read the image data directly,
2. rewrite the code so that it uses a linked list for stack.

The second, so called, optimization technique, appears as if it would slow down the filling process. If it was used in the same way as the stack array in the following code, then you would be correct. The fact is, a linked list allows us to apply other optimization techniques that more than compensate for the slight loss in efficiency. For example: we could pop items off the stack based on there line number, which reduces the number of items on the stack.

Note: Since most programmers now work with bitmaps, instead of reading and writing directly to video, the first optimization above may be all that is required to make this a truly fast solid flood fill algorithm.

```// The following is a rewrite of the seed fill algorithm by Paul Heckbert.
// The original was published in "Graphics Gems", Academic Press, 1990.
//
// I have rewitten it here, so that it matches the other examples
// of seed fill algorithms presented.

extern int nMinX, nMaxX, nMinY, nMaxY;
typedef struct { int x1, x2, y, dy; } LINESEGMENT;

#define MAXDEPTH 10000

#define PUSH(XL, XR, Y, DY) \
if( sp < stack+MAXDEPTH && Y+(DY) >= nMinX && Y+(DY) <= nMaxY ) \
{ sp->xl = XL; sp->xr = XR; sp->y = Y; sp->dy = DY; ++sp; }

#define POP(XL, XR, Y, DY) \
{ --sp; XL = sp->xl; XR = sp->xr; Y = sp->y+(DY = sp->dy); }

// Fill background with given color
void SeedFill_4(int x, int y, COLORREF new_color)
{
int left, x1, x2, dy;
COLORREF old_color;
LINESEGMENT stack[MAXDEPTH], *sp = stack;

old_color = GetPixel(x, y);
if( old_color == new_color )
return;

if( x < nMinX || x > nMaxX || y < nMinX || y > nMaxY )
return;

PUSH(x, x, y, 1);        /* needed in some cases */
PUSH(x, x, y+1, -1);    /* seed segment (popped 1st) */

while( sp > stack ) {
POP(x1, x2, y, dy);

for( x = x1; x >= nMinX && GetPixel(x, y) == old_color; --x )
SetPixel(x, y, new_color);

if( x >= x1 )
goto SKIP;

left = x+1;
if( left < x1 )
PUSH(y, left, x1-1, -dy);    /* leak on left? */

x = x1+1;

do {
for( ; x<=nMaxX && GetPixel(x, y) == old_color; ++x )
SetPixel(x, y, new_color);

PUSH(left, x-1, y, dy);

if( x > x2+1 )
PUSH(x2+1, x-1, y, -dy);    /* leak on right? */

SKIP:        for( ++x; x <= x2 && GetPixel(x, y) != old_color; ++x ) {;}

left = x;
} while( x<=x2 );
}
}```

## The QuickFill algorithm

Finally, we get to the QuickFill method of flood filling, which is a type of 4 way method, but is more efficient than the simple non-recursive method (believe it or not).

Note: For the purposes of this article, I will be describing (mostly) the original QuickFill algorithm, since the included code does not use optimized scan, search, and line drawing functions (remember, the original code directly accessed the video).

Its strengths are:

1. supports 3 types of fills: background, border and pattern,
2. optimized scan, search and drawing functions,
3. no recursion,
4. use of doubly linked list, to allow for efficiently removing items from list based on line number,
5. efficient use of list for reverse line splitting, when pattern filling is required.

Its weakness: repeated sampling of some lines, during solid fills.

As you can see from the code below, this is the most complicate method of flood filling. It was derived, indirectly, from the ideas presented in the simple non-recursive method.

The steps taken to create the original code where as follows:

1. Wrote `QuickFill` function based on what I could remember about scan line filling.
2. Replaced stack array with two singly linked lists.
3. Modified `PopLine` function, so that lines would be removed based on line number.
4. Added `SearchLeft`, `SearchRight`, `ScanLeft`, `ScanRight` functions; in order to allow for optimization of searching and scanning.
5. Added the `PushOpposite` function, which reverse splits lines, in order to reduce the number of lines revisited. This required that the list be changed to a doubly linked list and that the list be x-sorted. The reason behind this function was to eliminate all line revisits, but instead it just reduced the number of visits (at a cost).
6. Optimization of all of the above.

Note: While testing the port of the code to Windows, I discovered a gapping hole in the single visit code, patterns and masks could not be empty or the code would get stuck looping for ever (hence the following).

In order to make this function more useful to Windows programmers, I added code to support flooding of image with a bitmap pattern. Since `PushOpposite` only reduces the number of lines revisited and does not prevent revisits, I had to add another linked list to keep track of which lines had already been visited. The `PushOpposite` function is still required as it still reduces the number of line revisits and, as a bonus, it reduces the number of items placed in the visited list. To optimize the visited list, I decided to use visited blocks (rectangles) instead of visited lines, this serves to reduce the number of items needed in the list, which means less memory allocations.

Note: The following is the QuickFill function taken from version 1.0 of the code.

```/* Arguments:
*        Pointer to bitmap to fill, (x,y) coordinates of seed point,
*        color used for solid or masked fills, border color used if area to
*        be filled is outlined (or CLR_INVALID).
*
* Returns:
*         0 = Success.
*        -1 = Invalid seed point.
*        -2 = Memory allocation error.
*        -3 = Invalid bitmap or unknown error.
*/
int CQuickFill::QuickFill(
CBitmap* pBitmap,int x,int y,
COLORREF fill_color,COLORREF border_color/*=CLR_INVALID*/)
{
COLORREF ThisColor;
int MaxY,MaxX,dy;
int ChildLeft,ChildRight;
int ParentLeft,ParentRight;

#ifdef QUICKFILL_SLOW
HWND hWnd;
if( m_bSlowMode )
hWnd = ::GetActiveWindow();
#endif

// Create dib data object
if( !m_DibData.CreateDIB(pBitmap) )
return -3;

/* Initialize global variables */
#ifdef QUICKFILL_TEST
SHORT nKeyState;
m_CurStackSize = m_MaxStackSize = m_VisitSize = 0U;
m_CurrentLine = 0;
#endif
m_bXSortOn = m_bMemError = FALSE;
m_LastY = -1;

/* Initialize internal info based on fill type */
if( CLR_INVALID != border_color ) {
/* Check color at x,y position */
ThisColor = GetPixel(x,y);
if( ThisColor == border_color )
return -1;

ThisColor = border_color;
m_bXSortOn = TRUE;
}
else {
/* Check color at x,y position */
ThisColor = GetPixel(x,y);
if( ThisColor == fill_color && !m_DibPattern.GetDibPtr() )
return -1;

m_bXSortOn = TRUE;
}

/* Using macros because we can not uses pointer to member functions.
* This makes the code less efficient, but solves the problem.
*/
#define FindLeft(x,y,xmin,color) \
((CLR_INVALID != border_color) \
? SearchLeft(x,y,xmin,color) : ScanLeft(x,y,xmin,color))
#define FindRight(x,y,xmax,color) \
((CLR_INVALID != border_color) \
? SearchRight(x,y,xmax,color) : ScanRight(x,y,xmax,color))
#define SkipRight(x,y,xmax,color) \
((CLR_INVALID != border_color) \
? ScanRight(x,y,xmax,color) : SearchRight(x,y,xmax,color))

/* Initialize Line list */
if( MakeList() )
return -2;

/* Initialize maximum coords */
MaxX = m_DibData.GetWidth()-1;
MaxY = m_DibData.GetHeight()-1;

/* Push starting point on stack */
PushLine(x,x,y,+1);        /* Needed in one special case */
PushLine(x,x,y+1,-1);

/* Now start flooding */
while( m_pLineList ) {
PopLine(&ParentLeft,&ParentRight,&y,&dy);
y += dy;
if( y < 0 || MaxY < y )
continue;
if( m_bMemError )
continue;
if( m_bXSortOn && IsRevisit(ParentLeft,ParentRight,y) )
continue;

#ifdef QUICKFILL_SLOW
if( m_bSlowMode ) {
nKeyState = ::GetAsyncKeyState(VK_ESCAPE);
if( nKeyState < 0 )
break;
}
m_CurrentLine = y;
#endif

/* Find ChildLeft end ( ChildLeft>ParentLeft on failure ) */
ChildLeft = FindLeft(ParentLeft,y,0,ThisColor)+1;
if( ChildLeft<=ParentLeft ) {
/* Find ChildRight end ( this should not fail here ) */
ChildRight = FindRight(ParentLeft,y,MaxX,ThisColor)-1;
/* Fill line */
if( ChildLeft == ChildRight )
SetPixel(ChildRight,y,fill_color);
else
DrawHorizontalLine(ChildLeft,ChildRight,y,fill_color);

#ifdef QUICKFILL_SLOW
if( m_bSlowMode && hWnd ) {
m_DibData.SetDIBits(pBitmap);
::InvalidateRect(hWnd,NULL,FALSE);
::UpdateWindow(hWnd);
}
#endif

/* Push unvisited lines */
if( ParentLeft-1<=ChildLeft && ChildRight<=ParentRight+1 ) {
PushLine(ChildLeft,ChildRight,y,dy);
}
else {
if( m_bXSortOn )
PushOpposite(ParentLeft,ParentRight,
ChildLeft,ChildRight,y,dy);
else
PushLine(ChildLeft,ChildRight,y,-dy);
PushLine(ChildLeft,ChildRight,y,dy);
}
/* Addvance ChildRight end on to border */
++ChildRight;
}
else ChildRight = ParentLeft;

/* Fill betweens */
while( ChildRight < ParentRight ) {
( ChildRight>ParentRight on failure ) */
ChildRight = SkipRight(ChildRight,y,ParentRight,ThisColor);
/* If new ChildLeft end found */
if( ChildRight<=ParentRight ) {
ChildLeft = ChildRight;
/* Find ChildRight end ( this should not fail here ) */
ChildRight = FindRight(ChildLeft,y,MaxX,ThisColor)-1;
/* Fill line */
if( ChildLeft == ChildRight )
SetPixel(ChildRight,y,fill_color);
else
DrawHorizontalLine(ChildLeft,ChildRight,y,fill_color);

#ifdef QUICKFILL_SLOW
if( m_bSlowMode && hWnd ) {
m_DibData.SetDIBits(pBitmap);
::InvalidateRect(hWnd,NULL,FALSE);
::UpdateWindow(hWnd);
}
#endif

/* Push unvisited lines */
if( ChildRight <= ParentRight+1 )
PushLine(ChildLeft,ChildRight,y,dy);
else {
if( m_bXSortOn )
PushOpposite(ParentLeft,ParentRight,
ChildLeft,ChildRight,y,dy);
else
PushLine(ChildLeft,ChildRight,y,-dy);
PushLine(ChildLeft,ChildRight,y,dy);
}
/* Addvance ChildRight end onto border */
++ChildRight;
}
}

/* Push visited line onto visited stack */
if( m_bXSortOn )
PushVisitedLine(ParentLeft,ParentRight,y);
}
FreeList();
m_DibData.SetDIBits(pBitmap);
m_DibData.DeleteObject();
return( m_bMemError?-2:0 );
}```

Parent/Child line relationship:

Basic line pushing:

Note: In the following diagram "Scanned" impiles next line to be scanned, when line being pushed is popped off the stack.

Reverse line splitting:

Note: In the following diagram the scanning/pushing starts at the top.

Note: In the following diagram the blue (arrowed) lines represent the lines being pushed.

## Background

At the time that the QuickFill algorithm was created, I had seen only two types of flood fills used and wanted an algorithm that could handle both types. The first type used a border-color approach, which meant that the area that needed to be filled first had to be outlined with a border of a given color; this approach is the least desirable of the flood fills. The second type used the color at the seed-point, which meant that only pixels of that color where filled; this approach is much more versatile, since it allows for multiple image objects of varying color to be contained in the area being filled. Both of these flood fill types used a horizontal scan-line approach to solve the problem of flood filling an image.

When trying to find information on how to implement a fast flood fill algorithm, I discovered that there was almost no information on the subject. The only algorithms that I found were:

1. the basic recursive 4 way flood fill that has been mentioned in many publications (and still is), this is the worst (and slowest) method for filling an image,
2. a non-recursive scan-line version (ref. 1), that was faster than the 4 way version (still too slow for my purposes), and
3. a non-recursive scan-line version (ref. 2) that used two linked lists to implement a flood fill algorithm, faster (but still too slow).

The first two methods had the advantage of being very compact, and very slow. The third method on the other hand, had the potential of being very fast and complicated.

After placing the idea on the back burners for a while, since it was for my own personal graphics library and was not a priority, I had an epiphany. I was having a cup of coffee at the local coffee shop and thinking about how I could solve the problem, when it all came together in my head. I started with the ideas used in the simple scan-line algorithm (ref. 1) and proceeded to expand on the idea using a singly linked list (ref. 2) of nodes, representing a LIFO stack. Over the next nine days, I made incremental changes to the algorithm, each designed to increase the over all speed. When I was finished, I had an algorithm that was not only fast, but faster than every implementation that I could find, except for the one implemented in the Fastgraph library by Ted Gruber (written in assembly). Five months after the completion of the code, I finally went back and added the code necessary for single line visits so that the `QuickFill` function could also handle pattern fills.

## References:

1. A Seed Fill Algorithm by Paul Heckbert from "Graphics Gems", Academic Press, 1990
2. An Efficient Flood Visit Algorithm by Anton Treuenfels, C/C++ Users Journal Volume 12, Number 8, August, 1994

## Using the code

Note: When running the demo program in slow mode, you can press the ESC key to stop it.

#### CDibData specific:

If you have not installed the Windows SDK from Microsoft, you will get some compilation errors when compiling in debug mode. The reason for this is that `BITMAPV5HEADER` was not defined in the SDK that came with Visual C++ 6.0. Since `BITMAPV5HEADER` is only used for displaying debugging information, it should be easy to comment out the code.

```// Normal solid filling
#include "QuickFill.h"

// Declare a quickfill variable
QuickFill qf;

// Call quickfill to flood fill image background starting at given point
qf.QuickFill(&bitmap, x, y, fill_color);

// Or call quickfill to flood fill outlined image starting at given point
qf.QuickFill(&bitmap, x, y, fill_color, border_color);```
```// Pattern filling
#include "QuickFill.h"

// Declare a quickfill variable
QuickFill qf;

// Set bitmap used as pattern
qf.SetPatternBitmap(&patternBitmap);

// If you want to make a color transparent (only applies to patterns)
qf.SetPatternClearColor(transparentColor);

// Call quickfill to flood fill image background starting at given point
qf.QuickFill(&bitmap, x, y, fill_color);

// If pattern bitmap no longer needed
// Frees pattern bitmap and invalidates pattern clear color.
qf.SetPatternBitmap();```
```// Masked filling
#include "QuickFill.h"

// Declare a quickfill variable
QuickFill qf;

0x80, 0x80>>1, 0x80>>2, 0x80>>3,
0x80>>4, 0x80>>5, 0x80>>6, 0x80>>6,
};

// Call quickfill to flood fill image background starting at given point
qf.QuickFill(&bitmap, x, y, fill_color);

// If mask to longer needed

## Points of Interest

I see no barrier to rewriting the code for use with GDI+, the only reason I did not do that, is that, I do not know enough about GDI+ usage at this time. Besides, I have a personal paint program written using GDI and would like to add this code to it.

For those who want to compare the various flood fill algorithms, I suggest the following:

1. add some tracking variables and code (like the ones in the QuickFill code),
2. make the test function or functions private members of the `QuickFill` class,
3. after the `QuickFill` initialization, but before the first push, add a call to the test function. Then clean up after the test function call and return without entering the main QuickFill loop.

Note: The above is how I tested the recursive scan line code. Since it was written off the top of my head, I needed to be sure it would work.

If any one knows how to completely eliminate the need for the visited list, I would be very interested. When I discovered that the original method used to reduce revisits did not eliminate them, I felt insulted by my own code. At the time I wrote the QuickFill algorithm, I may have known of this problem and just forgot about it (doubt that).

Question: How would you optimize the QuickFill algorithm for bitmaps?

Answer: Modify the `CDibData` class so that it has optimized functions for `ScanLeft`, `ScanRight`, `SearchLeft`, `SearchRight` and horizontal line drawing. Of course, horizontal line drawing would be the hardest, since it would have to work the same as the `DrawHorizontalLine` member function.

## History

#### Version 1.0

• Jan. ??, 2004 : Converted from C (direct video access) to C++ for use with MS Windows bitmaps and added support for: pattern bitmaps to be used as fill and visit-block-list to eliminate revisiting durring pattern & mask fills.

Note: Since the origanal code had direct video access it could take advantage (with the correct write mode) of byte block copping and color-bit-mask reading (read mode 1). Both of which where hardware supported (VGA/EGA monitors) and much more efficeint than reading/writing single pixels directly from/to a bitmap.

#### Version 1.1

• Feb. 6, 2004 : Added left optimization, eliminates some revisits.
• Feb. 8, 2004 : Added reverse clip optimization, eliminates some revisits.
• Feb. 15, 2004 : Found `PushOpposite` special case and corrected it.
• Feb. 19, 2004 : Changed internal scan, search and line drawing routines to use pixel color values, in order to increase overall speed while working with palettized bitmaps (modified `CDibData`).
• Mar. 5, 2004 : (1) Moved `PushVisitedLine` from `QuickFill` to `PushOpposite`, this increases the number of revisits and reduces the size of the visit list (8:1). (2) Changed visit list to use `HLINE_NODE`, since block checking is no longer required and the number of allocations are reduce because the free list can now be used by all. (Of course `HLINE_NODE` is larger than we need, since it is not a visit list specific node type)
• Mar. 9, 2004 : (1) Added argument to `QuickFill` so that user can specify the rectangular area to be filled. (2) Added the `GetInvalidRect` function and associated code so that user can retrieve the rectangular coordinates of the bitmap area that has been modified, since lack of this information forces user to redraw whole bitmap.

Changes to demo program:

• "Show Revisits" option. This is used to show which lines were placed in the visit list, when pattern bitmaps or masks are used. Line types: Cyan->line in visit list, Yellow->revisited line direction = -1, Blue->revisited line direction = +1.
• Fill area selection via mouse (left-click and drag to select area). To fill: left-click in selected area and release to fill.
• Added elapsed fill time and revisit count to information displayed to right of bitmap.

## Credits

• Andrew J. McCauley for modifying `CDibData` debug code so that header type checking occurs based on `WINVER` rather than on header type only. This stopped compilation errors which occurred if the user did not have the new Windows SDK installed.

A list of licenses authors might use can be found here

## Share

 Software Developer United States
I am a senior software engineer who has been designing and developing software for many years, mostly in C/C++. You might say that I think in code; which is why I am passionate about my first rule of coding: “First do no harm”. So if I get carried away in my explanations, please realize that it is just part of my personality. I enjoy learning new things and, when I have the time, passing that knowledge onto others.

## You may also be interested in...

 First PrevNext
 QuickFill AlexL822-Apr-15 2:03 AlexL82 2-Apr-15 2:03
 Compiles but crashes on Win 7 VS 2010 Michael B Pliam16-Feb-15 18:28 Michael B Pliam 16-Feb-15 18:28
 Re: Compiles but crashes on Win 7 VS 2010 Michael B Pliam20-Feb-15 8:15 Michael B Pliam 20-Feb-15 8:15
 Re: Compiles but crashes on Win 7 VS 2010 John R. Shaw24-Feb-15 14:48 John R. Shaw 24-Feb-15 14:48
 License jkronk28-Mar-12 17:48 jkronk 28-Mar-12 17:48
 Single visit of each pixel Member 155606918-Mar-11 6:51 Member 1556069 18-Mar-11 6:51
 Re: Single visit of each pixel Member 155606922-Mar-11 20:19 Member 1556069 22-Mar-11 20:19
 Re: Single visit of each pixel John R. Shaw14-Apr-11 13:55 John R. Shaw 14-Apr-11 13:55
 Re: Single visit of each pixel Member 155606914-Apr-11 17:02 Member 1556069 14-Apr-11 17:02
 Re: Single visit of each pixel [modified] Think-A-Tron5-Jun-11 22:17 Think-A-Tron 5-Jun-11 22:17
 Re: Single visit of each pixel Member 15560696-Jun-11 5:04 Member 1556069 6-Jun-11 5:04
 Re: Single visit of each pixel John R. Shaw6-Jun-11 12:48 John R. Shaw 6-Jun-11 12:48
 Re: Single visit of each pixel Member 15560696-Jun-11 14:38 Member 1556069 6-Jun-11 14:38
 Re: Single visit of each pixel Think-A-Tron6-Jun-11 20:33 Think-A-Tron 6-Jun-11 20:33
 Re: Single visit of each pixel John R. Shaw6-Jun-11 10:59 John R. Shaw 6-Jun-11 10:59
 Re: Single visit of each pixel Think-A-Tron6-Jun-11 21:26 Think-A-Tron 6-Jun-11 21:26
 Re: Single visit of each pixel John R. Shaw8-Jun-11 7:27 John R. Shaw 8-Jun-11 7:27
 Re: Single visit of each pixel Think-A-Tron8-Jun-11 21:10 Think-A-Tron 8-Jun-11 21:10
 Re: Single visit of each pixel Member 155606926-Jul-11 10:29 Member 1556069 26-Jul-11 10:29
 Re: Single visit of each pixel [modified] Think-A-Tron28-Jul-11 22:04 Think-A-Tron 28-Jul-11 22:04
 I have a caution: The stack can actually get fairly large, and checking it for overlaps can add substantial overhead. I'm pretty sure that for regions without holes, neither your algorithm without the stack check nor a well-written implementation of the standard scanline fill algorithm revisits already filled pixels. That means for such regions, any overhead to test for overlaps slows down the fill relative to the standard fill. Let me give an example. Consider the following 10 pixel long, two-line pattern, where Xs represent nonfillable pixels and Os represent fillable pixels: ```oooooooxxxoooooooxxxoooooooxxxoooooooxxx ooxxxoooooooxxxoooooooxxxoooooooxxxooooo oooooooxxxoooooooxxxoooooooxxxoooooooxxx ooxxxoooooooxxxoooooooxxxoooooooxxxooooo oooooooxxxoooooooxxxoooooooxxxoooooooxxx ooxxxoooooooxxxoooooooxxxoooooooxxxooooo ``` It turns out that for your method of filling, the maximum combined stack depth when filling this pattern is about equal to one-seventh the number of pixels. For instance: 50 x 50: 352 100 x 100: 1405 400 x 500: 28823 Obviously checking over 28 thousand intervals for intersection with a filled span will have a negative effect on performance. While this example may seem rather contrived, something like it could occur, and even relatively tame examples can produce a stack depth of over a hundred. BTW, I think there's a small error in your description. I believe the line, 7) if rnew < R-1 push_up(rnew, R, y-1) should be, 7) if rnew < R-1 push_up(rnew+2, R, y-1). The pixels at rnew and rnew+1 have already been tested, so they needn't be tested again. For anyone who wishes to experiment with the algorithm (minus the stack overlap tests), I'll provide my implementation in C#. Please forgive any weakness in the coding style; I wrote it rather quickly, with no great effort at elegance or efficiency. My version is structured slightly differently than the description, but I believe it's functionally the same. The Fill4 routine is passed a delegate function that tests the pixel to see if it needs to be filled, fills it if it does, and returns a boolean that's true if the pixel was filled, and false otherwise. Obviously this sacrifices efficiency for generality. ```class FloodFill { private int xMin, yMin, xMax, yMax; TestAndModifyPixel testAndModifyPixel;   // A routine that does the following: // Test the pixel at (x, y) to see if it hasn't already been // modified, and if not, whether it fits the criteria to // need modification. If so, modify the pixel and return // true; otherwise, return false. public delegate bool TestAndModifyPixel(int x, int y); public delegate bool TestPixel(int x, int y); public delegate void ModifyPixel(int x, int y);   public FloodFill() { DeallocateMemory(); }   private struct Statistics { public int ShadowCount;   public void Clear() { ShadowCount = 0; }   public void IncrementShadowCount() { ShadowCount++; } } Statistics Stats = new Statistics();   private bool inUse = false; public bool InUse { get { return inUse; } private set { inUse = value; } }   // Set the x and y range. public void SetRange(int XMin, int YMin, int XMax, int YMax) { xMin = XMin; yMin = YMin; xMax = XMax; yMax = YMax; int ySize = yMax - yMin + 1; }   private class Shadow { public int left, right; public int y; public Shadow next, previous;   public Shadow(int myLeft, int myRight, int myY) { left = myLeft; right = myRight; y = myY; next = previous = null; }   public Shadow(int myLeft, int myRight, int myY, Shadow myNext) { left = myLeft; right = myRight; y = myY; next = myNext; previous = null; } }   Shadow upShadowsHead; Shadow upShadows; Shadow downShadowsHead; Shadow downShadows;   public void DeallocateMemory() { upShadowsHead = new Shadow(0, 0, 0, null); upShadows = upShadowsHead; downShadowsHead = new Shadow(0, 0, 0, null); downShadows = downShadowsHead; Stats.Clear(); }   public int GetAllocationCount(int which) { switch (which) { case 0: return Stats.ShadowCount; default: return 0; } }   public int ShadowCount { get { return Stats.ShadowCount; } }   int upStackSize = 0; int downStackSize = 0;   // The stack is stored as a double-linked list, with a dummy node on the end the // list as the top of the stack. New nodes are added as needed, but not removed // except by calling DeallocateMemory(). Normally, pushing a shadow consists // moving to the previous node. Popping a shadow consists of moving to the next node. void PushUpShadow(int left, int right, int y) { if ((upShadows = upShadows.previous) == null) { Stats.IncrementShadowCount(); upShadows = new Shadow(left, right, y, upShadowsHead); upShadowsHead.previous = upShadows; upShadowsHead = upShadows; } else { upShadows.left = left; upShadows.right = right; upShadows.y = y; } upStackSize++; }   void PopUpShadow(out int left, out int right, out int y) { left = upShadows.left; right = upShadows.right; y = upShadows.y; upShadows = upShadows.next; upStackSize--; }   void PushDownShadow(int left, int right, int y) { if ((downShadows = downShadows.previous) == null) { Stats.IncrementShadowCount(); downShadows = new Shadow(left, right, y, downShadowsHead); downShadowsHead.previous = downShadows; downShadowsHead = downShadows; } else { downShadows.left = left; downShadows.right = right; downShadows.y = y; } downStackSize++; }   void PopDownShadow(out int left, out int right, out int y) { left = downShadows.left; right = downShadows.right; y = downShadows.y; downShadows = downShadows.next; downStackSize--; }   // Fill4: set the pixel at (x ,y) and all of its 4-connected neighbors // with the same pixel value to the new pixel value. // A 4-connected neighbor is a pixel above, below, left, or right of a pixel. public void Fill4(int seedX, int seedY, TestAndModifyPixel argTestAndModifyPixel) { // Exit if the position is out of range. if ((seedX < xMin) || (seedY < yMin) || (seedX > xMax) || (seedY > yMax)) return;   InUse = true; testAndModifyPixel = argTestAndModifyPixel;   // Scan the seed span, wich consists of the seed pixel. // Exit if the pixel isn't filled. if (!LineFill(seedX, seedX, seedY)) { inUse = false; return; }   // Save the shadow for the previous and next lines. PushUpShadow(leftNew, rightNew, seedY + 1); PushDownShadow(leftNew, rightNew, seedY - 1);   // Pop the stack with the most shadows, then move up or down until a shadow // contains no fillable pixels. Return when both stacks are empty. while (true) { if (upStackSize <= downStackSize) { if (downStackSize == 0) break;   ScanDown(); } else { ScanUp(); } }   InUse = false; }   // Pop the next shadow from the up stack. Fill the first fillable span within the // shadow, then move to the shadow the span cast on the next line. Fill the first // fillable span on that line, and continue to the next line until encountering // a shadow with no fillable pixels. If a fillable span extends more than one pixel // outside the shadow, additional pixels need to be checked on the parent line. If // the fillable span ends more than one pixel before the end of the shadow, the // remaining pixels will need to be checked later. void ScanUp() { int left, right, y;   PopUpShadow(out left, out right, out y); while ((y <= yMax) && LineFill(left, right, y)) { // If the span extends more than one pixel left of the the shadow that generated // it, push a left parent shadow. If it extends more than one pixel right, push a // right parent shadow. If it's more than one pixel from the right of the parent // shadow, push the remanider of the parent shadow for later processing. if (leftNew < left - 1) PushDownShadow(leftNew, left - 2, y - 1); if (rightNew > right + 1) PushDownShadow(right + 2, rightNew, y - 1); else if (rightNew < right - 1) PushUpShadow(rightNew + 2, right, y);   left = leftNew; right = rightNew; y++; } }   // Same as ScanUp, but pop the down stack, and move to the previous lines. void ScanDown() { int left, right, y;   PopDownShadow(out left, out right, out y); while ((y >= yMin) && LineFill(left, right, y)) { if (leftNew < left - 1) PushUpShadow(leftNew, left - 2, y + 1); if (rightNew > right + 1) PushUpShadow(right + 2, rightNew, y + 1); else if (rightNew < right - 1) PushDownShadow(rightNew + 2, right, y);   left = leftNew; right = rightNew; y--; } }   // Fill the leftmost fillable span within the interval. The span may extend // to the left and right of the interval. int leftNew, rightNew; bool LineFill(int left, int right, int y) { // Find the first interior pixel. int x = left; while (!testAndModifyPixel(x, y)) { if (++x > right) return false; }   // If the first pixel was filled, scan left. if (x == left) { while ((--x >= yMin) && testAndModifyPixel(x, y)) ; leftNew = x + 1; x = left; } else { leftNew = x; }   // Find the end of the fillable span. while ((++x <= xMax) && testAndModifyPixel(x, y)) ;   rightNew = x - 1; return true; } } ``` modified on Friday, July 29, 2011 3:20 AM
 Re: Single visit of each pixel Member 155606929-Jul-11 7:58 Member 1556069 29-Jul-11 7:58
 Re: Single visit of each pixel John R. Shaw30-Jul-11 6:08 John R. Shaw 30-Jul-11 6:08
 minor error matthias.fauconneau7-Apr-09 7:54 matthias.fauconneau 7-Apr-09 7:54
 Re: minor error Neil Roy18-Mar-11 8:29 Neil Roy 18-Mar-11 8:29
 help with debug error message: Loaded 'C:\WINDOWS\system32\kernel32.dll', no matching symbolic information found. [modified] jin_ming12-Nov-08 12:54 jin_ming 12-Nov-08 12:54
 Last Visit: 31-Dec-99 19:00     Last Update: 13-Feb-16 19:30 Refresh 123 Next »