ata*_*air 3 c# recursion rhino
尽可能清理代码以显示我的问题。基本上它是一个八叉树搜索+相交。intersect 函数来自一个 SDK（整个项目是一个犀牛插件）。如果我使用交叉调用进行循环，它比通过八叉树进行递归搜索快 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);
}
}
谢谢！
现在我在家我终于可以回答你的问题了，那么让我们开始吧……
首先：如果您使用结构化编程语言，递归总是比迭代慢。你不能概括这一点，因为函数式编程语言中的函数调用速度更快（函数在那里定义不同）。有关更多信息，维基百科是一个很好的来源。
详细地说，递归调用将函数（或方法）分配的所有局部变量压入堆栈，等待内部调用返回（这包括相同的过程），最后从调用中弹出值 -堆栈并继续与他们合作。这不仅是沉重的内存负载，这也是垃圾收集器的痛苦：您的函数必须等待的时间越长，您的对象在内存中的持续时间就越长，老化并最终到达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！）等等......
如果我们正在搜索一个特定的框，我们的最大检查数量永远不会超过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在最好的情况下，我们在一个完全平衡的树中寻找一个特定的叶子。
| 归档时间： |
|
| 查看次数： |
3333 次 |
| 最近记录： |