Boundary Trace FloodFill

• Download source code - 12.1 KB

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:

1. 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.
2. do the same for pixel straight ahead. Go there if it's not part of the wall.
3. 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 in this link (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 addresses 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 until 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)
{  
//we start at screen position x, y where a MouseClick event happened
// no need to fill if fillcolor is oldcolor
	if(fillcolor == oldcolor) return; 
// storage for 4 points
	int PtX[4];
	int PtY[4];
//h = height, w = width
	int t = h-1;
	int q = w-1;
//find a starting point (boundary spot) by going down until we hit a different color
	while(screenBuffer[x][y]==oldcolor)
	{
		y++;
		if (y > t)
			break;
	}
	y--;
	bool IsTraced = FALSE;
// The direction we are going (0 = Right, 1 = Down, 2 = Left, 3 = Up), select one to start
	int iDir =2;
	int Y3;
//save the starting point
	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 two things in the first loop:

1. Check if we are on an edge of the screen, if so, move along the edge.
2. If we are not on the edge, calculate the 4 neighbour points of the current position.

So, first check the edges:

while (!IsTraced)
{               // in case we are at the edge of the screen, trace the edge
    onEdge = FALSE;
    if (x==0) //edge
    {
        while ((screenBuffer[x][y-1]==oldcolor || screenBuffer[x][y-1]==fillcolor) && y>0)
        {
            y--;
            screenBuffer[x][y] = fillcolor;
        }
        iDir = 0;
    }
    if (y==0) //edge
    {

        while ((screenBuffer[x+1][y]==oldcolor || screenBuffer[x+1][y]==fillcolor) && x<q)
        {
            x++;
            screenBuffer[x][y] = fillcolor;
        }
        iDir = 1;
    }
    if (x==q) //edge
    {
        while ((screenBuffer[x][y+1]==oldcolor || screenBuffer[x][y+1]==fillcolor) && y<t)
        {
            y++;
            screenBuffer[x][y] = fillcolor;
        }
        iDir = 2;
    }
    if (y==t) //edge
    {
        while ((screenBuffer[x-1][y]==oldcolor || screenBuffer[x-1][y]==fillcolor) && x>0)
        {
            x--;
            screenBuffer[x][y] = fillcolor;
            //we might encounter the starting point here,
            //because we defined the starting point sX, sY at the bottom of the fill area
            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 straight ahead, then right, finally going back.

if (!onEdge) //trace boundary
		{
			switch (iDir)
			{
			case 0: //going Right
			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: //going Down
			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: //going Left
			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: //going Up
			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;
			}
			//proceed to next pixel on the left (relative to Direction) and change Direction
			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 we did hit the wall proceed straight ahead (relative to direction)
				if (screenBuffer[PtX[1]][PtY[1]]==oldcolor || 
                    screenBuffer[PtX[1]][PtY[1]]==fillcolor)
				{
				x = PtX[1];
				y = PtY[1];
				}
				else
				{
					// if we did hit the wall go right (relative to Direction) 
                    // and change Direction
					if (screenBuffer[PtX[2]][PtY[2]]==oldcolor || 
                        screenBuffer[PtX[2]][PtY[2]]==fillcolor)
					{
					x = PtX[2];
					y = PtY[2];
					iDir = (iDir + 1)%4;
					}
					else
					// we hit the wall in all directions so we go back to the previous pixel
					{
					x = PtX[3];
					y = PtY[3];
					iDir = (iDir + 2)%4;
					}
				}
			}
			screenBuffer[x][y] = fillcolor;
	
			if (sX==x && sY==y)
				// we are back at the starting point
				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 until 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).

	// trace the boundary once again, this time filling
	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 ;
			//fill 1 line going down until we hit the opposite wall
				while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
				{
					screenBuffer[x][Y3]=fillcolor;
					Y3++;
					if (Y3 == t)
						break;
				}
				x++;
			}
			Y3 = y ;
			//fill last line going down 
			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 ;
			//fill 1 line going down until we hit the opposite wall
			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).

History

• 18^th September, 2012: Initial version