Unity 3D - flood fill / paint bucket algorithm keeps crashing engine

Question

I've been trying to write a flood-fill algorithm that will work in Unity. The idea is to colour sections of a black-on-white line drawing based on a colour selected by the user. I've tried several implementations of the flood-fill algorithm, but all of them cause unity to hang when they are called.

Any help on this is much appreciated, this is needed as part of an important project. Any suggestions for revisions to the code, algorithm design, or any alternate ways to get this to work would be much appreciated :)

Code:

// 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);
            }
        }

    }

    // ----------

}

Weeble Weeble · Accepted Answer · 2012-03-03T13:54:34

Your algorithm keeps adding the same pixels over and over again. It has various other issues, but this is what is making it run forever and eat up all of your memory. I think you're trying to implement the third algorithm here: http://en.wikipedia.org/wiki/Flood_fill

The obvious difference you have is that the Wikipedia algorithm has:

11. If the color of the node to the north of n is target-color, add that node to Q.
12. If the color of the node to the south of n is target-color, add that node to Q.

...however, you are testing against the boundary colour, not the target colour. Your algorithm will keep detecting the same pixels over and over again, every time noting that they're different from the boundary colour.

You have some other issues too:

You're trying to use a list as a queue, by appending on the end. This means it grows the whole time, and will eat up lots of memory for no good reason. The algorithm in Wikipedia assumes you use a queue and that the loop dequeues one item each time. This shouldn't stop your algorithm from working, but you probably want to fix it before you put it into much use.
You have a lot of code duplication, which makes your algorithm unnecessarily hard to read, and invites trouble when you later make a change in one place and forget to duplicate it everywhere else.

Unity 3D - flood fill / paint bucket algorithm keeps crashing engine

1 Answers