询问有关快速光线追踪算法的资源
首先，我对这个粗略的问题感到抱歉，但我不想介绍太多细节，所以我只是要求相关资源，例如文章，库或 >提示。
我的程序需要对射线与三角形相交进行密集计算（有数百万条射线和三角形），我的目标是使其尽可能快。
我所做的是：
使用最快的射线三角形 我知道的算法。
使用八叉树。（摘自游戏编程珍宝 1, 4.10. 4.11）
使用 一种高效、鲁棒的射线盒相交算法，用于八叉树算法。
它比我应用那些更好的算法之前更快，但我相信它可以更快，您能否阐明任何可能使其更快的地方？
First, I am sorry for this rough question, but I don't want to introduce too much details, so I just ask for related resource like articles, libraries or tips.
My program need to do intensive computation of ray-triangle intersection (there are millions of rays and triangles), and my goal is to make it as fast as I can.
What I have done is:
Use the fastest ray-triangle algorithm that I know.
Use Octree.(From Game Programming Gem 1, 4.10. 4.11)
Use An Efficient and Robust Ray–Box Intersection Algorithm which is used in octree algorithm.
It is faster than before I applied those better algorithms, but I believe it could be faster, Could you please shed lights on any possible places that could make it faster?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
提出这些问题的地方是 ompf2.com。一个有关实时（尽管也是非实时）光线追踪主题的论坛
The place to ask these questions is ompf2.com. A forum with topics about realtime (although also non-realtime) raytracing
OMPF 论坛是解决这个问题的正确位置，但既然我今天在这里...
不要使用光线/盒子交集进行 OctTree 遍历。您可以将它用作树的根节点，但仅此而已。一旦知道了根盒子入口和出口的距离，就可以计算到 x、y 和 z 分割平面（细分盒子的平面）的距离。如果到前面和后面的距离分别是f和b，那么你可以通过分析f、b、x、y、z距离来确定盒子的哪些子节点被击中。您还可以确定遍历子节点的顺序并完全拒绝其中的许多子节点。
最多可以击中 4 个子级，因为射线从一个八分圆开始，并且仅在穿过 3 个分区平面之一时才更改八分圆。
此外，由于它变得递归，您将需要子节点的进入和退出距离。这些距离是从您已经计算的集合 (f,b,x,y,z) 中选择的。
我已经对此进行了很长一段时间的优化，并且可以有把握地说，对于许多深度的树来说，您仍然可以获得大约一个数量级的性能。我从你现在所在的地方开始。
OMPF forum is the right place for this question, but since I'm here today...
Don't use a ray/box intersection for OctTree traversal. You may use it for the root node of the tree, but that's it. Once you know the distance to the entry and exit of the root box, you can calculate the distances to the x,y, and z partition planes - the planes that subdivide the box. If the distance to front and back are f and b respectively then you can determine which child nodes of the box are hit by analyzing f,b,x,y,z distances. You can also determine the order to traverse the child nodes and completely reject many of them.
At most 4 of the children can be hit since the ray starts in one octant and only changes octants when it crosses one of the 3 partition planes.
Also, since it becomes recursive you'll be needing the entry and exit distances for the child nodes. These distances are chosen from the set (f,b,x,y,z) which you've already computed.
I have been optimizing this for a very long time, and can safely say you have about an order of magnitude performance still on the table for trees many levels deep. I started right where you are now.
您可以进行多种优化，但所有优化都取决于问题的具体领域。就通用算法而言，您走在正确的轨道上。根据领域的不同，您可以：
There are several optimizations you can do, but all of them depend on the exact domain of your problem. As far as general algorithms go, you are on the right track. Depending on the domain, you could:
使用空间排序和快速交集算法，您已经有了一个良好的开端。为了一次追踪单条光线，最好的结构之一（对于静态场景）是使用表面积启发式构建的 Kd 树。
然而，对于真正的高速光线追踪，您需要利用：
我建议您从“使用连贯网格遍历的光线追踪动画场景”。它提供了这种现代方法的一个易于理解的示例。您还可以按照参考文献了解如何将这些想法应用于 Kd 树和 BVH。
在同一页面上，还可以查看“光线追踪动画场景的最新技术”。
另一组很棒的资源是多年来的所有 SIGGRAPH 出版物。这是一个竞争非常激烈的会议，因此这些论文往往都是一流的。
最后，如果您愿意使用现有代码，请查看 OpenRT 的项目页面。
You've already gotten a good start using a spatial sort coupled with fast intersection algorithms. For tracing single rays at a time, one of the best structures out there (for static scenes) is a K-d tree built using the Surface Area Heuristic.
However, for truly high-speed ray tracing you need to take advantage of:
I would suggest you start with "Ray Tracing Animated Scenes using Coherent Grid Traversal". It gives an easy-to-follow example of such a modern approach. You can also follow the references to see how these ideas are applied to K-d trees and BVHs.
On the same page, also check out "State of the Art in Ray Tracing Animated Scenes".
Another great set of resources are all the SIGGRAPH publications over the years. This is a very competitive conference, so these papers tend to be top-notch.
Finally, if you're willing to use existing code, check out the project page for OpenRT.
我见过的一个有用的资源是图形工具杂志。根据您的场景，另一个 BVH 可能比八叉树更合适。
另外，如果您还没有使用分析器查看您的性能，那么您应该这样做。 Shark 在 OSX 上表现出色，而我在 Windows 上使用 Very Sleepy 也获得了很好的结果。
A useful resource I've seen is the journal of graphics tools. Depending on your scenes, another BVH might be more appropriate than an octree.
Also, if you haven't looked at your performance with a profiler then you should. Shark is great on OSX, and I've gotten good results with Very Sleepy on windows.