统一3D -注满/油漆桶算法使引擎不断崩溃。

Question

我一直在尝试写一种洪水填充算法，这将在团结中起作用。这个想法是根据用户选择的颜色对黑白线的部分进行着色。我已经尝试过几个洪水填充算法的实现，但是当调用它们时，它们都会导致统一挂起。

在这方面的任何帮助都是非常感谢的，这是一个重要项目的一部分。如果对代码、算法设计或任何其他方法的修改提出建议，我们将不胜感激:)

代码：

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

    }

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

}

Answer 1

您的算法一次又一次地添加相同的像素。它还有很多其他的问题，但是这就是让它永远运行并消耗掉你所有记忆的原因。我认为您正在尝试在这里实现第三个算法：http://en.wikipedia.org/wiki/Flood_fill

您有一个明显的区别，维基百科算法有：

1. If n以北的节点的颜色是目标颜色，如果n以南的节点的颜色是目标颜色，则将该节点添加到Q.
2. ，然后将该节点添加到Q.

。

...however，您测试的是边界颜色，而不是目标颜色。您的算法会一次又一次地检测相同的像素，每次都会注意到它们与边界颜色不同。

你还有其他一些问题：

1. --您正试图将列表作为队列使用，方法是在最后追加。这意味着它会一直生长，并且会毫无理由地消耗大量的记忆。Wikipedia中的算法假设您使用一个队列，并且循环每次排出一个项。这不应该阻止您的算法工作，但您可能希望在大量使用之前修复它。
2. 您有大量的代码重复，这使得您的算法不必要地难以阅读，并且当您以后在一个地方进行更改而忘记在其他地方复制它时会引起麻烦。