3

私の問題を示すために、コードは可能な限りクリーンアップされています。基本的には octree search+intersect です。intersect 関数は SDK から取得されます (プロジェクト全体が rhino のプラグインです)。交差呼び出しでループを作成すると、octree を介した再帰的検索よりも 10 倍高速になります。見知らぬ人でさえ-インターセクト呼び出しのタイミングを分離しました-そして再帰内では、ループよりも8倍遅くなりました。このように動作する理由はおそらく 1000 あるかもしれませんが、コードを調べて誰かが見つけられる明らかな間違いを犯したことを願っています。

遅い再帰的な部分があります：

public void NewRayCast()
{            
    int runs = 500000;                          //how many rays we cast
    Point3d raypos = new Point3d(0, 0, 0);      //raystart
    Ray3d ray = new Ray3d();                

    Random r = new Random();                    //here we create targets to scatter the ray directions
    Vector3d[] targets = new Vector3d[runs];
    for (int i = 0; i < runs; i++)
    {
        targets[i] = new Vector3d(r.NextDouble() * 200 - 100, 500, r.NextDouble() * 200 - 100);
    }

    for (int i = 0; i < runs; i++)
    {
        boxes = new List<int>();            // this collects the octree leaves the rays hits
        rayline.From = ray.Position;
        rayline.To = ray.Position + ray.Direction;                
        LineBoxer(starter);                 // this starts the raycasting - starter is a array with 1 value (the scene bounding box)
    }            
}

public void LineBoxer(int[] check)    // Cast a ray against boxes
{            
    for (int i = 0; i < check.Length; i++)  // check only because the first call is with the scene box (1 index)
    {
        if (octmanB.node[check[i]].closed == false) // if node is a dead end > empty we skip it
        {                                       
            isect = Rhino.Geometry.Intersect.Intersection.LineBox(rayline, octmanB.node[check[i]].bbox, 0, out ival); // intersection function, changing to an arbitrary bounding box doesnt speed it up either                    
            if (isect == true)
            {                        
                if (octmanB.node[check[i]].leaf == false)   // continue with recursion
                {
                    LineBoxer(octmanB.node[check[i]].child);
                }
                else
                {
                    boxes.Add(check[i]);    // here we have a leaf
                }
            }
        }
    }
}

そしてここで速いもの：

public void FasterTestRun()
{
    int runs = 500000;                       
    Line line = new Line(new Point3d(1, 1, 1), new Point3d(0, 1000, 0));
    BoundingBox box = new BoundingBox(new Point3d(-50, 50, -50), new Point3d(50, 150, 50));

    bool isect;
    Interval v = new Interval();

    Random r = new Random();
    Point3d[] targets = new Point3d[runs];
    for (int i = 0; i < runs; i++)
    {
        targets[i] = new Point3d(r.NextDouble() * 20 - 10, 1000, r.NextDouble() * 20 - 10);
    }

    for (int i = 0; i < runs; i++)
    {
        line.To = targets[i];                
        isect = Rhino.Geometry.Intersect.Intersection.LineBox(line, box, 0, out v);                
    }            
}

ありがとう！

4

1 に答える 1

5

家に帰ってきたので、ようやくあなたの質問に答えることができます。では始めましょう...

再帰

まず第一に、構造化プログラミング言語を使用している場合、再帰は常に反復よりも遅くなります。関数型プログラミング言語での関数呼び出しは高速であるため、これを一般化することはできません (関数の定義が異なります)。詳細については、ウィキペディアが良い情報源です。

詳細には、再帰呼び出しは、関数 (またはメソッド) が割り当てたすべてのローカル変数をスタックにプッシュし、内部呼び出しが返されるまで待ちます (これには、何度も何度も同じ手順が含まれます...)。最後に、呼び出しから値をポップします。スタックし、それらを使用して作業を続けます。これはメモリ負荷が大きいだけでなく、ガベージ コレクタにとっても苦痛です。関数が待機する時間が長くなればなるほど、オブジェクトがメモリ内に長く残り、老化して最終的にgen1またはgen2に到達します。つまり、リリースされるまでには実際には長い時間がかかります。

私が見ることができる別の問題は次のとおりです。

public void LineBoxer(int[] check)
{
    // ...
    LineBoxer(octmanB.node[check[i]].child);
    // ...
}

配列を再帰的に渡すということは、配列のすべての値がその長い間スタック上に存在することを意味します。ほとんどの要素が解放される準備ができていても！

同じことを繰り返し行っている場合、スタックにストレスはありません。割り当てられた変数は多くの場合、一時的な変数であり、すぐに解放されます。ここではメモリ割り当てがボトルネックです。これは、（そしてコメントであなたがそれを求めたので）、私がもう少し詳しく説明し続ける理由です.

パフォーマンスの向上 - 理論上

ただし、(コメントで) レイトレーシングをより効率的に処理する方法についても尋ねています。基本的に、オクツリーを使用することは正しいです。実行する基本的な操作は単純な検索です。そして、あなたの問題があります。私があなたのコードを理解している限り、ヒットしたかどうかにかかわらず、すべてのオクツリー リーフをテストしています。

public void LineBoxer(int[] check)    // Cast a ray against boxes
{            
    for (int i = 0; i < check.Length; i++)
    {
        // ...
    }
}

これは、光線と交差するすべてのボックスをすべて検索するだけです。しかし、それは木を導入する動機ではありません。八分木は、 3 次元に拡張された二分探索木のようなものだと想像できます。二分探索木は、1 次元 (リストや配列など) のエントリを検索できます。2 次元構造で情報を検索するには、quadtreesを使用できます。次に、別の次元を追加する必要があるため (現在は 3D であるため)、octreesを使用します。

ここまでは順調ですが、検索操作を「より適切に」実行するために、ツリーはどのように役立つのでしょうか?

それは、分割統治の原則によるものです。より大きな情報セットの中で特定のものを検索する場合、セットを小さな断片に分割します。探している特定のものが見つかるまで、これを行います。

八分木の場合、これは立方体を8 つの小さな立方体に分割することを意味します。次に、レイがボックスと交差するかどうかを各ボックスでテストします。最良の場合、ちょうど 1 つのボックスと交差します。それはさらにチェックするものです。しかし、各ボックスに1000個のボックスが含まれている場合、チェックを 1 回追加するだけで7000個のチェックをなくすことができます。

1 つまたは複数の葉が見つかるまで、これを何度も繰り返します。これを再帰的に行うことは、これを繰り返し行うことよりも遅くはありません。100.000 ノードの octree を想像してみてください。最初のキューブは 8 個のキューブを格納でき、それらの 8 個のキューブは 64 個のキューブ (深さ: 2!) を格納できます。

  • 深さ = 3 : 512 キューブ
  • 深さ = 4 : 4.096 キューブ
  • 深さ = 5 : 32.768 キューブ
  • 深さ = 6 : 262.144 キューブ
  • 深さ = 7 : 2.097.152 キューブ
  • ...

また、特定の 1 つのボックスを検索する場合、チェックの最大数は深さ要素の 8 倍を超えることはありません。そのため、アルゴリズムのパフォーマンスをO(n)からO(log(n))に向上させました。1

結構ですが、これをあなたの問題にどのように適用しますか?

まず第一に、オブジェクト指向言語である C# を使用しています。だから、オブジェクトを使用してください！オブジェクト構造内にすべてをカプセル化している場合、分割統治の原則をツリー構造に適用するのは非常に簡単です。

あなたの特定のケースでは、これは次のことを意味します：

public class OctreeNode
{
    public bool IsLeaf { get; private set; }
    public OctreeNode[8] Children { get; private set; }

    public OctreeNode()
    {
        this.IsLeaf = true;
        this.Children = null;
    }

    // Don't forget to implement methods to build up the tree and split the node when required.
    // Splitting results in a tree structure. Inside the split-method 
    // you need to allocate the Children-Array and set the IsLeaf-Property to false.

    public bool Intersects(Line rayline, ref ICollection<OctreeNodes> Nodes)
    {
        Interval interval;

        // If the current node does not intersect the ray, then we do not need to
        // investigate further on from here.
        if (!Rhino.Geometry.Intersect.Intersection.LineBox(rayline, this.GetBoundingBox(), 0, out interval))
        {
            return false;
        }

        // If this is a leaf (in which we are interested in) we add it to 
        // the nodes-collection.
        if (this.IsLeaf)
        {
            Nodes.Add(this);
            return true;
        }

        // Not a leaf, but our box intersects with the ray, so we need to investigate further.

        for (int i = 0; i < 8; ++i)
        {
            // Recursive call here, but the result doesn't actually matter.
            this.Children[i].Intersects(rayline, Nodes)
        }

        // The ray intersects with our current node.
        return true;
    }
}

これはあなたのためにすべての魔法を行います! テストが失敗する深さまでのみツリーをテストし、光線が交差するすべての葉が得られるまで続行します。また、「最も長い交差間隔を取得した人」で並べ替えて、ストリーミング時に内部のオブジェクトをより高い優先度にすることもできますが、トピックに完全に失敗しているため、続行します。

並列処理を適用することで、このアルゴリズムをさらに高速化できます。これは、 TPLを使用すると非常に簡単です。これは、ここでは非常に単純です。

Parallel.For<int> (0; 8; i =>
{
    this.Children[i].Intersects(rayline, Nodes)
});

わかりました、今のところは十分だと思います。これがあなたと周りの何人かの人々に役立つことを願っています. :)

注: rhino3dにはあまり詳しくありません。問題をさらに解決するのに役立つ機能が組み込まれている可能性があります。

注 2:申し訳ありませんが、すべての点で 100% 正しいとは限りません。しばらくの間、これらの理論的な考察を行っていません...

1最良のケースでは、完全にバランスの取れたツリーで 1 つの特定の葉を検索しています。

于 2013-02-28T18:23:10.220 に答える