- Home /
Flood fill algorithm for colour fill / paint bucket tool
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);
}
}
}
// ----------
}
Hey @dchen05 you can share your solution again ?
The op wasn't online for over a year and dchen05 wasn't on for four months. His git hub account doesn't exist anymore. So it's very unlikely to get a response any time soon.
Answer by Bunny83 · Mar 04, 2012 at 05:09 AM
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.
Note that Get/SetPixel inherently check boundaries, depending on whether the texture is set to repeat or clamp.
Thanks, this is an excellent answer :) I'll have a go at making the recommended changes.
Oh and you're exactly right, this is the floodfill from wikipedia
Hey @Bunny83, thanks for your work on this algorithm. I needed to add a tolerance factor for the color comparison for a project I'm working on. I created a Gist here incase anyone else wants to use it. https://gist.github.com/dchen05/5298031