Flood fill algorithm for colour fill / paint bucket tool

Questions & Answers
1

Hi,

I need to write a flood fill algorithm using C# in Unity, in order to make a simple colour-fill tool similar to the one in MS paint. The user will be presented with a white texture with black line-drawings to be filled. They will pick a colour from a pallet, and click to fill sections of the line-drawing with colour. Black will always represent the boundary colour.

Here is the flood-fill method I have written. The code surrounding the sample is checked and works, but the algorithm seems to only fill one line to the left of the clicked pixel.

It would be great to get some advice on this, either to find out what is wrong with the existing code, or find another method of doing colour-fills. I think it’s overflowing the stack.

EDIT: New version of code below, still with same problem:

/ FloodFill function

void FloodFill() {

// TEST - colour the clicked pixel
//_tex.SetPixel( (int)_pixelUV.x, (int)_pixelUV.y, m_fillColour );
//_tex.SetPixel( _pixelX, _pixelY, m_fillColour );

	
// FLOOD FILL 
// ----------

// Create WestEast
List<Point> m_WestEast;

//get the pixel's colour
Color PC = new Color(_tex.GetPixel(m_StartNode.X, m_StartNode.Y).r, _tex.GetPixel(m_StartNode.X, m_StartNode.Y).g, _tex.GetPixel(m_StartNode.X, m_StartNode.Y).b);
	
//Record clicked pixel as point
Point node = new Point(m_StartNode.X, m_StartNode.Y);
	
//if the pixel's colour is boundary colour (black), return.
if(PC == Color.black)
{
	return;
}
	
//else continue
	
// Create a list Q[]
m_List = new List<Point>();
	
//add clicked pixel to Q[]
m_List.Add(node);

//for each element in Q[]
for(int i=0; i<m_List.Count; i++)
{
	//create new WE[] and add Q[n] to it
	m_WestEast = new List<Point>();
	m_WestEast.Add(node);
		
	//get pixel 1 to left (w) of Q[n]
	Point w = new Point(node.X + 1, node.Y);
	//get colour of w
	Color wCol = new Color(_tex.GetPixel(w.X, w.Y).r, _tex.GetPixel(w.X, w.Y).g, _tex.GetPixel(w.X, w.Y).b);	
		
	while(wCol != Color.black)
	{		
		//add pixel to WE[] and repeat
		m_WestEast.Add(w);
			
		//get new w
		w = new Point(w.X + 1, w.Y);
			
		//get colour of w
		wCol = new Color(_tex.GetPixel(w.X, w.Y).r, _tex.GetPixel(w.X, w.Y).g, _tex.GetPixel(w.X, w.Y).b);	
			
		//else if colour is boundary colour
			//go to next step
	}

	//get pixel 1 to right (e) of Q[n]
	Point e = new Point(node.X - 1, node.Y);
	//get colour of w
	Color eCol = new Color(_tex.GetPixel(e.X, e.Y).r, _tex.GetPixel(e.X, e.Y).g, _tex.GetPixel(e.X, e.Y).b);	
		
	while(eCol != Color.black)
	{		
		//add pixel to WE[] and repeat
		m_WestEast.Add(e);
			
		//get new e
		e = new Point(e.X - 1, e.Y);
			
		//get colour of e
		eCol = new Color(_tex.GetPixel(e.X, e.Y).r, _tex.GetPixel(e.X, e.Y).g, _tex.GetPixel(e.X, e.Y).b);	
			
		//else if colour is boundary colour
			//go to next step
	}

	//for each pixel in WE[]
	for(int j=0; j<m_WestEast.Count; j++)
	{
		//set the pixel to replacement colour
		_tex.SetPixel(m_WestEast[j].X, m_WestEast[j].Y, m_fillColour);
			
		//get pixel 1 to north (n) of Q[n]
		Point n = new Point(m_WestEast[j].X, m_WestEast[j].Y - 1);	
		
		//get colour of n
		Color nCol = new Color(_tex.GetPixel(n.X, n.Y).r, _tex.GetPixel(n.X, n.Y).g, _tex.GetPixel(n.X, n.Y).b);
		
		//if colour is not boundary colour
		if(nCol != Color.black)
		{
			//add pixel to Q[]
			m_List.Add(n);
		}
			
		//get pixel 1 to south (s) of Q[n]
		Point s = new Point(m_WestEast[j].X, m_WestEast[j].Y + 1);	
		
		//get colour of s
		Color sCol = new Color(_tex.GetPixel(s.X, s.Y).r, _tex.GetPixel(s.X, s.Y).g, _tex.GetPixel(s.X, s.Y).b);
			
		//if colour is not boundary colour
		if(sCol != Color.black)
		{
			//add pixel to Q[]
			m_List.Add(s);
		}
	}

}
	
// ----------

}

2

Ok, it seems you’re trying to implement the second alternative floodfill algorithm on wikipedia but there are some things wrong or a bit messy:

  • First, GetPixel returns already a Color, why do you call it 3 times, take only one component at a time and then re-assemble them to a Color?
  • I’m not sure what “Point” you’re using. If it’s a struct (which it should be) you don’t have to use new Point all the time you want to change a component of it. Since it’s a value type every variable holds it’s own copy of it.
  • Watch your texture boundary. First i thought you never check your coordinates, but GetPixel and SetPixel seems to be safe, thanks to Eric’s comment.
  • SetPixel and GetPixel are quite slow functions. It’s usually better to copy the texture into an array, do your operations and copy it back.
  • It seems you never read any of your stored nodes back. I guess you want a “node = m_List[i];” at the start of your main loop.
  • Don’t forget to call texture.Apply() after you’re done with your changes.

I’ve had some time and implemented the algorithm myself and created two extension methods FloodFillArea and FloodFillBorder if someone is interested. (github mirror)