复杂图形的光线追踪器

Question

我使用Metal Framework开发了iOS的实时光线追踪器，它适用于以下类型的光学棱镜，如十二面体、二十面体、八面体、立方体等。我的所有图形都由三角形组成，例如立方体-12个三角形，八面体-4个三角形。我跟踪光线并搜索与图形的交点，然后搜索光线在棱镜中的移动方式。然后射线离开图形，我再搜索其与天空盒子的交点。问题在于复杂的图形上。当我测试立方体时fps为60，但当我测试十二面体时fps为6。在我的算法中，与图形相交与任何三角形相交是相同的。这意味着当我检查光线和图形之间的交点时，我必须检查所有三角形之间的交点。我需要一些思路，如何不检查所有三角形的交点。谢谢。

- Serhii Londar

---

你需要将场景分成不同的区域，并且只测试与光线相交的区域内的物体/三角形...有很多基于树的方法可以实现这一点，但我更喜欢从场景中创建一个像素化的网格，将三角形分组到“像素立方体”中，然后只需通过这些立方体跟踪光线并测试仅列出为命中像素立方体的三角形。这应该会显著提高速度。 - Spektre

谢谢。我不明白如何分割场景。你能给一些例子吗？ - Serhii Londar

添加了回答，试图澄清我的意思... - Spektre

Answer 1

假设你有一个由某个包围盒限定的世界

1. 创建网格（将此盒子分成立方体或其他形状）

   

2. 每个体素/单元格

   是与之相交或在其中的三角形列表，因此在处理每个单元格之前，需要处理所有三角形并存储所有内部或穿过的三角形的索引。

3. 重写射线追踪器以通过此体素地图进行跟踪

   所以只需增加射线穿过相邻的体素，这与像素行栅格化相同。这样就部分完成了Z排序。因此只需考虑射线击中的第一个体素，并测试其中包含的三角形。如果发现任何体素的击中，则停止（不需要测试其他体素，因为它们更远）。

4. 进一步优化

   您可以添加标志来表示三角形是否已经被测试过，因此只需测试那些尚未被测试过的三角形，否则将测试许多次的三角形。

[注]

每个轴上的体素数量极大地影响性能，因此您需要稍微调整它以实现最佳性能。如果有动态对象，则需要定期执行体素地图列表计算，甚至针对每个帧进行计算。对于静态场景，只需执行一次即可。

- Spektre

Answer 2

为了高效追踪，您需要使用加速结构，例如KD树或边界体层次结构（BVH）。这类似于使用二叉搜索树查找匹配元素。

我建议使用BVH，因为它比KD树更容易构建和遍历。而且我建议不要使用均匀的体素网格结构。如果场景中的三角形分布不均匀或在几个体素中密集分布，体素网格很容易表现非常差。

BVH只是一组包围其内原语的边界体的树，例如轴对齐边界框（AABB）。这样，如果射线未击中边界体，则可以知道它不会击中其中包含的任何原语。

要构建BVH：

1. 将所有三角形放入一个边界体积中。这将成为树的根。

2. 将三角形分为两组，使每组三角形的边界体积最小。更准确地说，您需要遵循表面积启发式（SAH），其中您希望创建一组三角形，其中您最小化两组三角形的（BVH的表面积）/（#三角形）之和。

3. 递归地对每个节点重复步骤2，直到剩余的三角形数量达到某个阈值（4是一个不错的尝试数字）。

遍历时：

1. 检查光线是否击中了根边界框，如果是，则继续进行步骤2，否则没有击中。

2. 检查它是否击中子边界框。如果是，则重复此步骤以获取其子边界框。否则没有击中。

3. 当您获得仅包含三角形的边界框时，您需要像正常情况下一样测试每个三角形是否被击中。

这是BVH的基本概念。关于BVH的细节还有很多内容需要您查询，因为细节上有很多变化。

简而言之，实现一个包围体层次结构进行追踪。

- illeyezur

---

谢谢您的回复。但我不确定它是否有帮助。据我所知，它仅适用于静态场景。如果我旋转我的场景，它将无效。我只有一个由三角形组成的图形。如果我创建BVH并旋转我的图形，它将无效。 - Serhii Londar

旋转场景是什么意思？你是指将物体移动到场景中还是移动相机？因为如果你移动相机，那么如果你已经在世界空间坐标系中定义了BVH，则它仍然有效。如果你实际上是在世界中移动物体，那么即使使用体素网格也没有帮助，因为你每帧都要重新处理它们。如果场景中只有一个物体，那么你只需在物体坐标空间中创建BVH，然后无论你如何移动该物体都没有关系。 - illeyezur