0

Unity で動作するフラッド フィル アルゴリズムを作成しようとしています。アイデアは、ユーザーが選択した色に基づいて、白地に黒の線画のセクションに色を付けることです。フラッド フィル アルゴリズムのいくつかの実装を試しましたが、それらはすべて呼び出されたときに Unity をハングさせます。

これに関するヘルプは大歓迎です。これは重要なプロジェクトの一部として必要です。コード、アルゴリズム設計、またはこれを機能させるための代替方法の改訂に関する提案は大歓迎です:)

コード：

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

    }

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

}
4

1 に答える 1

1

アルゴリズムは、同じピクセルを何度も追加し続けます。他にもさまざまな問題がありますが、これが永遠に実行され、すべてのメモリを消費する原因です. ここで 3 番目のアルゴリズムを実装しようとしていると思います: http://en.wikipedia.org/wiki/Flood_fill

明らかな違いは、ウィキペディアのアルゴリズムには次のものがあることです。

11. n の北にあるノードの色がターゲット カラーの場合、そのノードを Q に追加します。
12. n の南にあるノードの色がターゲット カラーの場合、そのノードを Q に追加します。

...ただし、ターゲットの色ではなく、境界の色に対してテストしています。アルゴリズムは同じピクセルを何度も検出し続け、そのたびに境界色とは異なることに注意します。

他にもいくつかの問題があります。

  1. 最後に追加して、リストをキューとして使用しようとしています。これは、常に成長し、正当な理由もなく大量のメモリを消費することを意味します。ウィキペディアのアルゴリズムは、キューを使用し、ループが毎回 1 つのアイテムをデキューすることを前提としています。これによりアルゴリズムが機能しなくなることはありませんが、実際に使用する前に修正する必要があります。
  2. コードの重複が多いため、アルゴリズムが不必要に読みにくくなり、後である場所に変更を加えて他の場所にコピーするのを忘れると、問題が発生します。
于 2012-03-03T13:54:34.730 に答える