6

首先，我很抱歉这个粗略的问题，但我不想介绍太多细节，所以我只是要求相关资源，如文章、库或提示。

我的程序需要对射线与三角形的交点进行密集计算（有数百万条射线和三角形），我的目标是尽可能快地完成。

我所做的是：

  1. 使用我知道的最快的射线三角形算法。

  2. 使用八叉树。（来自 Game Programming Gem 1, 4.10. 4.11）

  3. 使用八叉树算法中使用的高效且鲁棒的 Ray-Box 相交算法。

它比我应用那些更好的算法之前更快，但我相信它可能会更快，你能说明一下任何可能使它更快的地方吗？

谢谢。

4

5 回答 5

3

问这些问题的地方是ompf2.com。一个关于实时（虽然也是非实时）光线追踪主题的论坛

于 2010-01-06T11:37:18.577 回答
2

OMPF 论坛是解决这个问题的好地方，但是因为我今天在这里......

不要对 OctTree 遍历使用光线/盒子交叉点。您可以将它用于树的根节点，仅此而已。一旦你知道了到根盒子的入口和出口的距离，你就可以计算到 x、y 和 z 分区平面的距离 - 细分盒子的平面。如果前后距离分别为 f 和 b，那么您可以通过分析 f,b,x,y,z 距离来确定框的哪些子节点被命中。您还可以确定遍历子节点的顺序并完全拒绝其中的许多子节点。

最多可以击中 4 个孩子，因为光线从一个八分圆开始，并且只有在穿过 3 个分区平面之一时才会改变八分圆。

此外，由于它变得递归，您将需要子节点的进入和退出距离。这些距离是从您已经计算的集合 (f,b,x,y,z) 中选择的。

我已经对此进行了很长时间的优化，并且可以肯定地说，对于许多级别的树来说，你的性能仍然有一个数量级。我从你现在的位置开始。

于 2010-01-07T19:04:41.997 回答
1

您已经使用空间排序和快速交叉算法获得了良好的开端。对于一次追踪单条光线，最好的结构之一（用于静态场景）是使用表面积启发式构建的 Kd 树。

但是，对于真正的高速光线追踪，您需要利用：

  • 相干的射线包
  • 弗鲁斯塔
  • SIMD

我建议您从“使用相干网格遍历的光线追踪动画场景”开始。它为这种现代方法提供了一个易于理解的示例。您还可以按照参考资料了解这些想法如何应用于 Kd 树和 BVH。

在同一页面上，还可以查看“光线追踪动画场景中的最新技术”。

另一组很好的资源是这些年来所有的 SIGGRAPH 出版物。这是一个竞争非常激烈的会议，所以这些论文往往是一流的。

最后，如果您愿意使用现有代码，请查看OpenRT的项目页面。

于 2010-07-17T06:41:32.540 回答
1

您可以进行多种优化，但所有优化都取决于您的问题的确切领域。就一般算法而言，您走在正确的轨道上。根据域，您可以：

  1. 引入门户系统
  2. 将计算移至 GPU 并利用并行计算
  3. 最近光线追踪的一个非常流行的趋势是Bounding Volume Hierarchies
于 2010-01-06T11:38:58.173 回答
0

我看到的一个有用的资源是图形工具杂志。根据您的场景，另一个 BVH 可能比八叉树更合适。

此外，如果您没有使用分析器查看您的表现，那么您应该这样做。Shark 在 OSX 上很棒，而且我在 Windows 上使用 Very Sleepy 获得了不错的效果。

于 2010-01-08T17:33:08.287 回答