递归方法比交互方法慢10倍
尽可能清理代码以显示我的问题。 基本上它是八叉树搜索+相交。 交叉函数来自SDK（整个项目是rhino的插件）。 如果我使用交叉调用进行循环，它比通过八叉树的递归搜索快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(); // 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 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); } }
谢谢！
现在我在家，我终于可以回答你的问题了，让我们开始……
递归
首先： 如果您正在使用结构化编程语言 ， 则递归总是比迭代慢。 你不能概括这一点，因为函数式编程语言中的函数调用更快（函数在那里定义不同）。 有关更多信息， 维基百科是一个很好的来源。
详细地说，递归调用将所有局部变量推送到堆栈中的函数（或方法），等待直到内部调用返回（这包括相同的过程on on和on …），最后从调用中弹出值 – 堆栈并继续与他们合作。 这不仅是大量的内存负载，这对垃圾收集器来说也很痛苦：你的function必须等待的时间越长，你的对象在内存中的持续时间越长，老化并最终到达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维（例如列表或数组）中的条目。 要在二维构造中搜索信息，可以使用四叉树 。 现在我们需要添加另一个维度（因为我们现在是3D），所以我们使用八叉树 。
到目前为止一切都那么好，但是树木如何帮助我们“更好”地执行搜索操作？
那是因为分而治之的原则 。 如果我们在更大的信息集中搜索特定的东西，我们将集合分成小块。 我们这样做只要我们找到我们正在寻找的特定事物。
对于我们的八叉树，这意味着我们将一个立方体分成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深度元素。 因此我们将算法性能从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 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 (0; 8; i => { this.Children[i].Intersects(rayline, Nodes) });
好吧，我认为那是暂时的。 我希望这可以帮助你和周围的更多人。 🙂
注意：我对rhino3d不太熟悉。 也许有内置的function可以帮助您更好地解决您的问题！
注2：请原谅我，当我在所有方面都不是100％正确时，我暂时没有做过那些理论上的考虑......
1在最好的情况下，我们在完全平衡的树中搜索一个特定的叶子。