八叉树优化raycasting

在之前的文章中，我们不得不等待 8 分钟来渲染一盏精灵灯和一个球体。总而言之，我们询问每个像素是否有多个三角形之一相交。这个场景包括：

4 个物体：1 个灯、2 个球体和 1 个平面
34,378 个三角形：1 个球体没有三角形，询问 OBJ 文件
640x480 = 307,200 像素

为我们提供了超过 105 亿次针对单个渲染场景的查询。通常，CPU 的单线程频率为 1-2 GHz。这意味着一个线程每秒可以计算大约 1-20 亿步。

现在一个 CPU 可以有多个内核 — 我的有 4 个内核。我可以使用多线程同时计算 8 个像素的颜色，但我建议避免这种复杂的架构，原因有 3 个：

当多个线程试图访问同一内存时需要正确锁定
你们中的一些人（初学者）可能不熟悉多线程和锁定
调试代码将变得非常困难，并使算法更难阅读和分析

教程代码可以在这里下载。

1、多线程之外的优化手段

这意味着我们需要另一种解决方案来加速光线投射（和光线追踪）。我找到了几种无需多线程和多进程处理即可加速渲染过程的可能方法，但只会将其中一种方法包含在我们的框架中（也许稍后我也会添加其他方法）。我们将从最复杂的方法开始，逐步介绍更简单的方法。

包围球

这是我的第一个解决方案：我们的对象将所有点存储在列表中。所有点都被球体包围。

我们已经讨论过光线/球体的交点，我们知道可以用一个公式完成计算。

只有当包围球被光线击中时，才会在存储的三角形列表中搜索最近的三角形。这样，如果光线甚至没有靠近物体，我们就可以避免很多查询。

包围球的一大缺点是中心和半径的正确放置。所有已开发的算法都是近似值，并提供误差系数。换句话说，要计算出覆盖所有相关点的最小半径的完美球体是完全不可能的。

包围盒

就像包围球一样，它包含所有要检查的点。一个包围盒有 8 个点和 6 个面，这意味着我们有更多的查询来确定光线是否与包围盒相交，特别是如果包围盒也被变换算法旋转和缩放。找到正确的尺寸也很困难。

二分空间 (BSP)

BSP 将一个空间分成两个子空间，这些子空间在另外两个子空间中，依此类推。因此，搜索对象的区域越来越小，将点和三角形划分为某些区域。

其中困难的部分是如何实现良好的分隔。

轴对齐包围盒 (AABB)

这是常规包围盒的简单版本。顾名思义，每个表面都与 3 轴 x、y 和 z 对齐。中心是每个轴的最小值和最大值的平均值，这些值的差值是边界大小。

有两种方法可以描述 AABB：

对最小值使用一个点，对最大值使用一个点
使用中心和描述从中心到表面的（最小）距离的向量

甚至射线/AABB 交集的计算也比包围盒的计算简单得多，它是我们将在框架中使用的数据结构的基础。

八叉树

想象一个 AABB。现在将所有 3 种尺寸（x、y 和 z）减半。你得到的立方体可以装进原来的立方体八次。

八叉树是一个内部有 8 个子立方体的立方体，每个子立方体还有另外 8 个子立方体（总共 64 个子立方体）。这样我们就有了一个节点层次结构来存储信息。如果我们击中大立方体，我们会搜索子立方体（如果光线会击中它们），然后更深入地搜索更小的立方体。可能的点/三角形的数量越来越小，这样我们就不必查看整个列表。

这种数据结构称为分区树。它将数据分成子部分，帮助我们比查看整个列表更快地找到正确的数据。

2、全能八叉树

轴对齐包围盒最重要的是它围绕着整个对象（即球体）。我们通过获取 x、y 和 z 的最小值和最大值来做到这一点。为确保所有点都在该包围盒内，我们给边界添加ε。

仅此一项就可以改善我们的光线投射。只有当光线与 AABB 相交时，我们才会遍历三角形列表并搜索最接近该光线的三角形。但是一个球体可以有成千上万个三角形，我们没有时间去研究所有的三角形。

这种AABB 的优点是我们可以将所有 x、y 和 z 的大小减半，并将其分成 8 个较小的子 AABB。如下图所示：

这些子AABB又可以分为另外8个子AABB，依此类推。这样做的好处是我们可以决定创建一个子 AABB（我们称它们为二叉树的节点）。如果有一个节点，那么至少有一个数据集可以预期。

不幸的是，内存存储会呈指数增长 (S(23n))。我们不能进入无限的深度。与其说一个子节点只能有一个三角形，我们可以让一个节点有有限数量的三角形。如果超过该限制，则将所有三角形拆分为适当的子节点。

有时一个三角形可以存在于几个子节点中（因为它的大小）。假设一个对象有 5000 个三角形：八叉树可能有 5010 个三角形甚至更多。这样我们就可以避免对同一级别的其他节点进行交叉查询。

可以选择将八叉树制作成尺寸为 a 的完美立方体，但我建议制作尺寸为宽度、高度和深度的八叉树，而不是单一尺寸。 a 将是最大宽度、高度、深度。

2.1 将三角形添加到八叉树

我的建议是以下算法：

如果未达到限制或节点达到最大深度：
	将三角形添加到列表
	如果该三角形超出限制并且未达到最大深度
		查询所有存储的三角形与子节点的交集
		如果该位置没有节点，则创建子节点
	告诉节点已达到限制
否则将三角形添加到子节点（可能有更多合适的节点）
如果该位置没有节点，则创建子节点

三角形/AABB相交测试

最大的问题是三角形何时与 AABB 相交？ Tomas Möller 提出了一种非常快速的算法可以解决我们的问题（论文）。他实现了分离轴 Therom (SAT)，在 13 个测试中提出了 3 个问题：

AABB 内部是否至少有一个三角点？（如果有则为真）
平面是否与 AABB 重叠？（如果有则为真）
三角形边和平面法线之间是否有分离平面（如果有则为 False）

我修改了算法，以便查询是否存在与 AABB 相交的三角形边，而不是重叠测试（测试 2）。

2.2 Ray/AABB相交测试

如果你还记得射线/平面相交测试，这个测试就非常简单。为此，我们需要用 2 个点进行 6 次计算：只有最小值的点和只有最大值的点。

再一次，这里是射线/平面相交的公式：

其中 t 是根据射线的起点 S 和方向 v 的标量距离，P0 是 AABB 平面的角点之一（Pmin 或 Pmax），n 是 AABB 平面的法线。考虑到所讨论的平面，该法线是 (1,0,0)、(0,1,0) 或 (0,0,1)。

假设我们想要采用前平面，那么 n 将为 (0,0,1)，我们需要 Pmin。我们的公式可以简化为：

对于前、左和下平面，我们可以使用 Pmin，对于后、右和上平面，我们可以使用 Pmax。这样进行六次计算。很简单，不是吗？

这样我们就得到了六个不同的 t 值。我们将其放入射线方程中以获得一个恰好在平面上的点，但它也在边界内吗？如果使用前平面的计算，如果它在 AABB 平面内，则需要查询 x 和 y 值。你可以从 Pmin 和 Pmax 获得边界值。

如果两个查询都为真，则射线与平面相交，因此与整个 AABB 相交。

3、框架

我解释说我不会更改 Scene3D 中的对象设置来比较渲染时间。但我利用这段时间做了一些结构改进：

场景 3D：

提供为每个对象构建八叉树的选项
所有列表现在都是 std::maps，用于 Object3D、Light、Material 和 Texture
使用“键”获取对象，但仍可转换为 std::vector
这样，从 OBJLoader 创建的对象可以很容易地转换

对象 3D：

包含链接到该对象的新实现的 Octree 对象
射线相交查询是否有八叉树（不为空）
如果没有，像以前一样遍历每个 Surface3D（使八叉树可选）
现在有一个 ID 可以更好地识别对象（即更新 Octree 时）

八叉树：

从 Object3D 实例计算 AABB 的中心和大小
使用准备好的信息创建 OctreeNode 作为根节点

八叉树节点：

有 8 个 OctreeNode 类型的子节点
将中心、大小和 8 个子中心存储为 Vector3D
如果未达到限制或最大深度，则包含存储的 Surface3D 列表
最大级别和限制的静态值对所有节点和子节点有效。

对象加载器：

现在可以从不同的文件夹中读取 .obj 和 .mtl 文件
保存文件路径，以便它可以找到 MTL 文件

main.cpp：

添加了计时器以查看以秒为单位的渲染时间

再次总结一下之前渲染的场景：

4 个物体（1 个灯、2 个球体和 1 个平面）
34,378 个三角形（1 个球体没有三角形，询问 OBJ 文件）
640x480 = 307,200 像素

没有八叉树的时间：约8分钟

有八叉树的时间：7-8秒

这里回答你的问题：我仍然不使用图形库，因此没有图形卡。但是我的CPU是 Intel i7（4 核/8 线程，每个 2.4 GHz）。因此，结果可能因计算机而异。

4、结束语

我们在框架中添加了一个数据结构来限制每个像素的查询数量，并且能够将时间减少大约五十分之一 (1:50)。而且我们仍然没有（也永远不会）将多线程添加到框架中。

在下一期中，我们将使用外部 OBJ 文件（可能是您的创作）制作一些更好的渲染场景，并实现等待已久的 RAYTRACING，我们将在其中模拟反射（镜子）和折射（玻璃）。我们还将对阴影做一个简短的介绍，以使一切更加真实。

原文链接：Speed-up raycasting with Octrees

BimAnt翻译整理，转载请标明出处