I have implemented realtime ray tracer with MetalFramework for iOS and it is implemented for following optical prisms like dodecahedron, icosahedron, octahedron, cube, etc. All my figures are composed from triangles, for example cube - 12 triangles, octahedron - 4 triangles. I trace rays and search intersection with figure, then I search how ray moves in prism. Then ray leaves figure and I search intersection with skybox. The problem is in complicated figures. When I test cube fps is 60, but when I test dodecahedron fps is 6. In my algorithm intersection with figure is the same as intersection with any triangle. It means that when I check intersection with ray and figure I have to check intersection with all triangles. I need some idea how to do not check intersections for all triangles. Thanks.
2 回答
假设你的世界被某个边界框包围
创建网格（将此框划分为立方体或其他）
每个体素/细胞
是相交或位于其中的三角形列表，因此在为每个单元格渲染之前处理所有三角形并存储内部或交叉的所有三角形的索引
重写光线跟踪器以跟踪此体素图
因此，只需通过相邻体素增加光线，它与像素上的线光栅化相同。这样你就完成了部分 Z 排序。因此，获取第一个被射线击中的体素并仅测试其中包含的三角形。如果发现任何体素命中，则停止（无需测试其他体素，因为它们更远）。
进一步优化
如果三角形已经过测试，您可以添加标志，因此只测试那些尚未测试的三角形，否则许多三角形将被多次测试
[笔记]
每个轴的体素数量会极大地影响性能，因此您需要稍微调整一下才能获得最佳性能。如果您有动态对象，则体素映射列表计算必须不时进行一次，甚至每帧进行一次。对于静态场景，只需执行一次即可。
为了有效地跟踪，您需要使用加速结构，例如 KD 树或包围体层次结构 (BVH)。这类似于使用二叉搜索树来查找匹配元素。
我建议使用 BVH，因为它比 KD 树更容易构建和遍历。我建议不要使用统一的体素网格结构。当三角形在场景中分布不均匀或高度集中在几个体素中时，体素网格的性能很容易变得很差。
BVH 只是一个包围体树，例如一个轴对齐包围盒 (AABB)，它包含其中的图元。这样，如果您的光线错过了包围体，您就知道它不会击中包含在其中的任何图元。
要构建 BVH：
将所有三角形放在一个包围盒中。这将是树的根。
将三角形分成两组，其中每组三角形的边界体积最小化。更准确地说，您希望遵循表面积启发式 (SAH)，您希望在其中创建一组三角形，在其中最小化两组三角形的（BVH 的表面积）/（# 个三角形）的总和。
递归地对每个节点重复步骤 2，直到剩下的三角形数量达到某个阈值（4 是一个很好的尝试数字）。
遍历
检查光线是否击中根边界框，如果是，则继续步骤 2，否则没有击中。
检查它是否击中子边界框。如果确实如此，则对其子边界框重复此步骤。否则没有命中。
当你得到一个只包含三角形的边界框时，你需要测试每个三角形，看看它是否像正常一样被击中。
这是 BVH 的基本概念。还有更多关于 BVH 的细节我没有深入探讨，您必须搜索它们，因为细节有很多变化。
简而言之，实现一个包围体层次结构来跟踪。