3

尽可能地清理代码以显示我的问题。基本上它是一个八叉树搜索+相交。intersect 函数来自一个 SDK（整个项目是一个 rhino 的插件）。如果我用交叉调用进行循环，它比通过八叉树的递归搜索快 10 倍。甚至更奇怪 - 我隔离了 intersect 调用的时间 - 在递归内部它比循环慢 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 维的二叉搜索树。二叉搜索树可以在一维中搜索条目（例如列表或数组）。要在二维结构中搜索信息，您可以使用四叉树。现在我们需要添加另一个维度（因为我们现在是 3D 的），所以我们使用octrees。

到目前为止一切都很好，但是树如何帮助我们“更好地”执行搜索操作呢？

那是因为分而治之的原则。如果我们在更大的信息集中搜索特定的东西，我们会将信息集分成小块。我们一直这样做，直到我们找到我们正在寻找的特定事物。

对于我们的八叉树，这意味着我们将一个立方体分成8个较小的立方体。现在我们测试每个盒子，如果我们的光线与它相交。在最好的情况下，它正好与一个盒子相交。那是要进一步检查的。但是，如果每个盒子包含1000 个盒子，我们只需通过一张额外的支票就可以摆脱7000张支票！

现在我们一次又一次地这样做，直到我们找到一个或多个叶子。递归执行此操作不应该比迭代执行此操作慢很多。想象一个有 100.000 个节点的八叉树。第一个立方体可以存储 8 个立方体，那 8 个立方体可以存储 64 个立方体（深度：2！）等等......

  • 深度 = 3：512 个立方体
  • 深度 = 4：4.096 个立方体
  • 深度 = 5：32.768 个立方体
  • 深度 = 6：262.144 个立方体
  • 深度 = 7：2.097.152 个立方体
  • ...

如果我们正在搜索一个特定的盒子，我们的最大检查数量永远不会超过8 x Depth元素。所以我们将算法性能从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在最好的情况下，我们在完全平衡的树中搜索一个特定的叶子。

于 2013-02-28T18:23:10.220 回答