## Introduction

While I was playing with a Mandelbrot set in VB6 I faced the problem of filling the set quickly. I looked into Floodfill algorithms and stumbled upon a Boundary Trace by Michael R. Ganss. Because the FloodFill algorithms I encountered all used a stack or recursion, I decided to benchmark the Boundary Trace algorithm against some of them. I rewrote it so the code is more transparent. It proved faster, with little load on resources.

## Background

I usually program in Visual Basic but decided on VC10 for the benchmark. I used an application (*floodfill.cpp*) by Lode VandeVenne that benchmarked some FloodFill algorithms, and added my versions of the Boundary Trace.

The author of the original is Michael R. Ganss. This is his explanation:

*Boundary Tracing Generation Method, traces the outline of areas of a single color and fills them in. We start from pixel (x,y) going right and keeping the "wall" to our left until we get back to the starting point. For each pixel, the next pixel visited will be computed thus: *

*check pixel to left (looking in the current direction, i.e. if the current direction is right, the pixel to the left is the one above it). If it's part of the wall (i.e. offscreen or a different color than the one we're tracking), go to b). If it's not, it is the next pixel. *
*do same for pixel straight ahead. Go there if it's not part of the wall. *
*ditto for pixel to the right. If this pixel is also part of the wall, go back one pixel. When we're back at the starting point we trace the boundary once more. Now, whenever we move up, we plot pixels to the right of the current one until we hit the wall. *

Source: Michael R. Ganss

An algorithm based on the same principle, but visiting every pixel is described here http://www.davdata.nl/math/floodfill.html (completely nonrecursive, but slow). I rewrote the original algorithm (used on a Mandelbrot set) to perform floodfill.

## Using the Code

The source code contains several Floodfill algorithms, including four versions of Boundary Trace, the algorithm that performed best. The idea of `BoundaryTrace`

is to trace the outlines of the area to be filled by going left as much as possible, keeping a 'wall' of pixels that should not be filled to the (relative) left side. The same algorithm is used to trace a maze. After tracing the complete boundary, filling all the boundary pixels with the fill color, and reaching the start spot again, a second tracing is done while filling the area between the boundaries.

The function `BoundaryTrace`

shows the basic algorithm, however it has limitations : if the fill area is 1 pixel wide on the edge it gives an incomplete fill, and if there are 'islands' in the fill area it gives an incomplete fill as well. `BoundaryTrace2`

adresses those problems, and in case there are 'islands' it calls `BoundaryTrace2a`

(recursive if needed : if several 'islands' are on top of each other), where the wall is kept to the right, thus going around the edges of the island.

`BoundaryTrace3`

does the same as BoundaryTrace2, however the code is optimized for performance - this gives a slight improvement but the code becomes much less transparent.

`BoundaryTrace4`

is like `BoundaryTrace2`

but uses a stack, collecting all the boundary points that are used to fill the area by going down untill we hit a pixel that is not the fillcolor nor the original color - in other words, we hit the opposite boundary. So we don't need a second tracing. And then of course I had to test the stack option with `BoundaryTrace3`

code. It is faster sometimes, but not always. All this code is in the source download. On this page I give the basic algorithm as code snippet.

Feel free to use this code if you are looking for a faster FloodFill.

## Initializing

void BoundaryTrace(int x, int y, Uint32 fillcolor, Uint32 oldcolor)
{
if(fillcolor == oldcolor) return;
int PtX[4];
int PtY[4];
int t = h-1;
int q = w-1;
while(screenBuffer[x][y]==oldcolor)
{
y++;
if (y > t)
break;
}
y--;
bool IsTraced = FALSE;
int iDir =2;
int Y3;
int sX = x;
int sY = y;
bool onEdge;

## The First Loop

The first loop terminates if we are back at our starting point (`sX`

, `sY`

) We do 2 things in the first loop

- check of we are on an edge of the screen, if so, move along the edge.
- if we are not on the edge, calculate the 4 neighbour points of the current position.

So, first check the edges:

while (!IsTraced)
{ onEdge = FALSE;
if (x==0) {
while ((screenBuffer[x][y-1]==oldcolor || screenBuffer[x][y-1]==fillcolor) && y>0)
{
y--;
screenBuffer[x][y] = fillcolor;
}
iDir = 0;
}
if (y==0) {
while ((screenBuffer[x+1][y]==oldcolor || screenBuffer[x+1][y]==fillcolor) && x<q)
{
x++;
screenBuffer[x][y] = fillcolor;
}
iDir = 1;
}
if (x==q) {
while ((screenBuffer[x][y+1]==oldcolor || screenBuffer[x][y+1]==fillcolor) && y<t)
{
y++;
screenBuffer[x][y] = fillcolor;
}
iDir = 2;
}
if (y==t) {
while ((screenBuffer[x-1][y]==oldcolor || screenBuffer[x-1][y]==fillcolor) && x>0)
{
x--;
screenBuffer[x][y] = fillcolor;
if (sX==x && sY==y)
{
IsTraced = TRUE;
onEdge = TRUE;
break;
}
}
iDir = 3;
if (!IsTraced && x==0) onEdge = TRUE;
}

If we are not on an edge, we calculate 4 neighbour points, it depends on the Direction (iDir) in what order they are checked (always the left one relative to the direction first, then straigt ahead, then right, finally going back.

if (!onEdge) {
switch (iDir)
{
case 0: PtX[0] = x;
PtY[0] = y - 1;
PtX[1] = x + 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y + 1;
PtX[3] = x - 1;
PtY[3] = y;
break;
case 1: PtX[0] = x + 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y + 1;
PtX[2] = x - 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y - 1;
break;
case 2: PtX[0] = x;
PtY[0] = y + 1;
PtX[1] = x - 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y - 1;
PtX[3] = x + 1;
PtY[3] = y;
break;
case 3: PtX[0] = x - 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y - 1;
PtX[2] = x + 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y + 1;
break;
}
if (screenBuffer[PtX[0]][PtY[0]]==oldcolor || screenBuffer[PtX[0]][PtY[0]]==fillcolor)
{
x = PtX[0];
y = PtY[0];
iDir = (iDir + 3)%4;
}
else
{
if (screenBuffer[PtX[1]][PtY[1]]==oldcolor || screenBuffer[PtX[1]][PtY[1]]==fillcolor)
{
x = PtX[1];
y = PtY[1];
}
else
{
if (screenBuffer[PtX[2]][PtY[2]]==oldcolor || screenBuffer[PtX[2]][PtY[2]]==fillcolor)
{
x = PtX[2];
y = PtY[2];
iDir = (iDir + 1)%4;
}
else
{
x = PtX[3];
y = PtY[3];
iDir = (iDir + 2)%4;
}
}
}
screenBuffer[x][y] = fillcolor;
if (sX==x && sY==y)
IsTraced = TRUE;
}
}

So in the first loop we have traced the complete boundary of the area to be filled, and we gave the boundary pixels we encountered the value of fillcolor.

Now we are going to trace the boundary once again, this time we will fill the area : each time we have direction Right (so we are at the top of the fill area) we go down from the current pixel untill we hit the opposite border at the bottom of the fill area, filling the pixels on the way with fillcolor. We fill in case `y = 0`

(if we are on the top edge) or in case iDir = 0 (=Right)

IsTraced = FALSE;
iDir = 2;
while (!IsTraced)
{
onEdge = FALSE;
if (x==0)
{
while (screenBuffer[x][y-1]==fillcolor && y>0) y--;
iDir = 0;
}
if (y==0)
{
while ( screenBuffer[x+1][y]==fillcolor && x<q)
{
Y3 = y ;
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
x++;
}
Y3 = y ;
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
iDir = 1;
}
if (x==q)
{
while (screenBuffer[x][y+1]==fillcolor && y<t) y++;
iDir = 2;
}
if (y==t)
{
while (screenBuffer[x-1][y]==fillcolor && x>0)
{
x--;
if (sX==x && sY==y)
{
IsTraced = TRUE;
onEdge = TRUE;
break;
}
}
iDir = 3;
if (!IsTraced && x==0) onEdge = TRUE;
}
if (!onEdge)
{
switch (iDir)
{
case 0:
PtX[0] = x;
PtY[0] = y - 1;
PtX[1] = x + 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y + 1;
PtX[3] = x - 1;
PtY[3] = y;
Y3 = y ;
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
break;
case 1:
PtX[0] = x + 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y + 1;
PtX[2] = x - 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y - 1;
break;
case 2:
PtX[0] = x;
PtY[0] = y + 1;
PtX[1] = x - 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y - 1;
PtX[3] = x + 1;
PtY[3] = y;
break;
case 3:
PtX[0] = x - 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y - 1;
PtX[2] = x + 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y + 1;
break;
}
if (screenBuffer[PtX[0]][PtY[0]]==fillcolor)
{
x = PtX[0];
y = PtY[0];
iDir = (iDir + 3)%4;
}
else
{
if (screenBuffer[PtX[1]][PtY[1]]==fillcolor)
{
x = PtX[1];
y = PtY[1];
}
else
{
if (screenBuffer[PtX[2]][PtY[2]]==fillcolor)
{
x = PtX[2];
y = PtY[2];
iDir = (iDir + 1)%4;
}
else
{
x = PtX[3];
y = PtY[3];
iDir = (iDir + 2)%4;
}
}
}
if (sX==x && sY==y) IsTraced = TRUE;
}
}
}

This code has some limitations :

- If the fill area is 1 pixel wide at the edge it finds its starting point too early
- If there are 'islands' in the fill area it gives an incomplete fill

Hence `BoundaryTrace2`

and `BoundaryTrace3`

(using recursion for 'islands'). `BoundaryTrace2`

is a compact code, while `BoundaryTrace3`

is written to optimize performance, giving up on code transparency.

In `BoundaryTrace4`

and `BoundaryTrace5`

we use a stack to speed things up (put the pixels on the top of the fill area on stack, so the second trace is not needed). Actually, the stack does not always perform better. Despite the differences the basic algorithm is the same for all functions, as explained above These functions are given in the source download.

## Points of Interest

I enjoyed (re)writing this code a lot, sometimes however I had to get used to VC10 again after working in VB for a long time. Though the algorithm is not mine, I have never seen it used for FloodFill before.

How to use the demo : use left mouse button to draw a shape (make sure its boundaries are uninterrupted). Then click inside the area to be filled with the right mouse button. To perform a benchmark test, press SPACE thereafter. The time is in milliseconds (for 600 iterations).