有成千上万的射线和三角形。我们需要得到所有的交点。如果我们使用正常的两级循环，我们需要 O( mn) 时间复杂度。有没有办法将时间复杂度从 O( mn) 降低到 O(m* logn) 或 O(logm*n)？
此致，
问问题
381 次
6 回答
8
您可能想看的是某种空间分区技术。这使您可以快速排除三角形的集合。
我可能会考虑使用球形Bounding Volume Hierarchies的一些方法。但是您可能还想研究的其他技术是BSP（二进制空间分区）树/ KD 树或使用八叉树
于 2009-12-23T09:45:51.280 回答
2
不，原因很简单：实际上可能有 O(m * n) 个交叉点。仅创建它们的列表就是 O(n * m)。
于 2009-12-23T09:35:29.893 回答
2
这个问题的经典解决方案是基于三角形构建一个 KD 树，并为每条射线查询它。您可以针对您期望的查询类型优化树；如果您的光线是随机分布的，则命中的概率与所讨论的表面积成正比。
即使您实际上并没有进行光线追踪，这个问题也是目前光线追踪的主要性能瓶颈，因此您可能应该查看有关它的文献。
于 2009-12-25T02:14:53.830 回答
0
在 2D 中有SweepLine算法。在我看来，它可以概括为 3D。
于 2009-12-23T09:34:18.867 回答
0
您可以将彼此靠近的三角形组合成立方体。然后对于每条射线：如果它没有击中立方体，您确定它没有击中立方体内的其中一个三角形，因此您可以跳过与该特定射线的这些三角形的所有相交计算。
于 2009-12-23T09:44:34.380 回答
0
显然，如果您必须迭代并计算射线和每个三角形之间的交点，那么复杂度就是 O(mn)。但是，如果您只对可能与特定光线相交的三角形感兴趣，您可以尝试空间划分网格的变体，例如分层四叉树网格 ( http://graphics.stanford.edu/courses/cs468- 06-fall/Slides/steve.pdf）。
于 2014-02-07T20:40:43.570 回答