6.2 基于Voxel的快速光线追踪的实现

本节首先介绍Voxel是什么，然后阐述如何进行Voxelization，最后详细介绍基于Voxel的快速光线追踪算法。

6.2.1 Voxel是什么

为了理解Voxel是什么，可以拿Pixel来进行对比。Voxel可以看作Pixel在3D空间中的概念延伸，即Voxel可以理解为3D空间的Pixel。Pixel的坐标用（x，y）表示，而Voxel的坐标需要用（x，y，z）来表示。同样地，Pixel占有一定的面积，而Voxel占有一定的体积。一图胜千言，图6.1和图6.2是对《王者荣耀》5V5场景局部区域进行Voxelization之后的对比图，按照Voxelization后的分辨率从低到高来进行排序，根据需求不同，可以选择使用不同分辨率的Voxelization。

需要说明的是，本文只需要进行Surface Voxelization（表面体素化）而不需要进行Solid Voxelization（体积体素化）。前者只需要对表面数据生成Voxel，而后者需要对物体内部也生成Voxel，可想而知，后者占用的存储空间比前者要大得多。本文所进行的光线追踪不需要内部Voxel数据，因此只需要实现Surface Voxelization即可，下面介绍如何快速进行Surface Voxelization。

6.2.2 Voxel的快速生成

Voxel处于3D空间中，3D空间中的数据结构有Octree、KD-Tree、R-Tree、Perfect Hash、GVDB。这些数据结构各自拥有不同的优缺点，有的节省内存、有的追踪更快。本文选取Octree作为存储Voxel的数据结构，因为它是各项比较平衡的数据结构。Octree的生成一般有自顶向下和自底向上两种方式，这里先介绍简单的自顶向下的算法，6.2.3节会使用一个更为快速的生成算法来优化生成时间。

6.2.2.1 Surface Voxels（表面体素）的生成

只需要在标准管线里进行一定的改造，即可完成Voxelization，步骤如下。首先确定Voxelization的分辨率，如1024voxel×1024voxel×1024voxel，然后将摄像机的Viewport设置为1024pixel×1024pixel。因为数据不需要写到Framebuffer中，所以所有的Framebuffer操作都应该禁掉，如Depth Test、Depth Write、Color Write。

根据论文[1]里面的研究，当进行Voxelization时，对于每一个三角形，要尽可能地提升生成的Fragment的数量，这样才不会漏掉Voxel。这很好理解，考虑一个极端的情况，有一个三角形正好和摄像机的方向平行，那么光栅化之后生成的Fragment数量就为0，那么这个三角形就不会生成任何一个Voxel，这当然是不对的。但是每个三角形的方向不一样，所以这里采用一个简单高效的方法，对于每一个三角形，在Geometry Shader中从3个主轴方向里选取一个方向，该方向可以最大化当前三角形的投影面积，即能最大化生成的Fragment数量。在Geometry Shader中，每个三角形的顶点坐标、法线信息都是已知的，所以是办得到的。具体来说，对于一个法线方向为n的三角形，选取主轴v来进行投影，v满足|n·v|是3个主轴里最大的。当v选好之后就可以在Geometry Shader中对三角形进行投影了。

当进行三角形光栅化时，必须采用Conservative Rasterization（保守光栅化）。对于普通的光栅化，只有每个Pixel的中心点被三角形覆盖时才会生成对应的Fragment，Conservative Rasterization可以保证更大的覆盖率，Pixel只要和三角形有一点重合就会生成对应的Fragment。

在三角形光栅化时，每个三角形会生成一系列的Fragment，并且能获得Fragment对应的世界空间坐标（x，y，z），如图6.3所示，（x，y，z）对应的小立方体即该Fragment对应的Voxel。在存储Voxel数据时，有若干选择，如color、normal，甚至各种PBR渲染所需要的粗糙度、金属度等参数。在本文的应用中，只需要存储color和normal即可。需要注意的是，在将Pixel Shader生成的Fragment转换成Voxel并放入Voxel列表中时，大量的线程会同时访问该列表，所以需要用到原子操作函数和Atomic Counter，它们支持高效率的整型数的原子增减操作。每个线程首先将Atomic Counter加1，然后把Voxel数据保存在列表的对应位置上，这样大量的线程就能高效地同时操作Voxel列表了。

6.2.2.2 Sparse Voxel Octree的生成

有了Voxel列表之后，就可以生成Voxel Octree了。Octree是一种层级树状结构，每一个节点拥有8个子节点，每一层节点的子节点的长宽高都是该层节点的1/2大小。算法按照自顶向下的顺序每次生成一层节点，第一层只有1个节点，依次往下分裂，当某个节点内部包含一个Voxel时，就把该节点拆分成8个子节点，对它的子节点采用一样的操作，逐步生成一棵Octree。到了最底下的层级的时候，Voxel的数据就写入子节点中。生成顺序是逐层的，即先生成第一层的所有节点，再生成第二层的所有节点，以此类推，直到生成最后的所有叶子节点。

虽然逻辑上使用了Octree，但实际上这棵树的数据是连续存放在内存里的，每一个节点的数据主要包括color、normal和坐标，不过为了节省显存，对它们进行了一定的压缩。

根据后续的烘焙结果分析，其实有无normal的关系不大，所以最后的结构可以进一步简化为

完整的的Octree生成一共包含3个步骤。下面详细描述每个步骤。对于每层节点的生成，前2个步骤都是需要运行的，第3个步骤在生成最后的叶子节点时才需要运行。

节点的数据用一个uint就可以表示了，对于中间的节点来说，nodeData里面保存的是它的8个子节点所在位置的相对位置，由于8个子节点是连续分配的，所以nodeData里只需要保存第1个子节点的相对位置，其他7个子节点位置加偏移即可。

对于叶子节点来说，nodeData里保存的是color数据，其中最高位保存的是该节点是否有效，后7位保存的是Alpha，最后24位保存的是rgb数据。另外，虽然albedo数据在0～1的范围里，但是有些美术需求需要调整albedo数据范围，所以需要对color数据进行一定的压缩。

假设已经处理到了第N层，第一步，需要确定当前层级的哪些节点需要进行拆分。Voxel列表里的每一个Voxel都生成一个线程，每个线程独立地自顶向下从根节点开始按照空间位置找到第N层对应的节点，并对这个节点进行标记，表明它需要被拆分，要注意这一步并不真正对这个节点进行拆分，因为Voxel数量巨大，如果同时进行节点拆分，线程之间就需要同步，耗时会非常长。如果只进行标记的话，大量线程的并行度就会很好。标记其实很简单，只要把子节点的最高位置1即可。

第二步，对第N层的每个节点生成一个线程，如果该节点在第一步中已经被标记为拆分，那么就先申请新的2×2×2个节点，再将父子关系连接好。这里需要注意的是，因为同时有大量线程在申请节点，所以需要用一个Atomic Counter来增加总的Voxel节点个数，以便大量的线程可以并行操作Voxel Pool。

最后一步，注入Voxel的数据到叶子节点中。要注意的是，不同的Voxel可能对应同一个叶子节点，那么到底该保存哪一个Voxel的数据到叶子节点中呢？简单可行的方式是选取Alpha最大的Voxel，当Alpha一样时，随机选取一个Voxel。另一个方式是取所有Voxel的平均值，但是有两个问题：如下面的代码段所示，一个问题是需要占用原来存储Alpha的位置来存储一个Voxel的计数值从而计算平均值，但这样无法保留Alpha。当然也可以既保留Alpha又计算平均值，方法是对于每个叶子节点，再申请一个uint专门用来存储计数值，不过作者在后面的烘焙测试中发现是否存储平均值对烘焙影响不大，所以此处选择存储Alpha最大的Voxel数据的方案；另一个问题是会降低Octree生成的速度。另外，每个Voxel数据注入的线程都不一样，这会产生大量的竞争问题，所以需要使用原子操作。

6.2.3 更快的Voxel Octree生成

6.2.2节的Octree生成算法的最大缺点是按照顺序一层一层地自顶向下创建整棵树，每一层的创建都必须等待它的所有上层创建完毕之后才能开始，而且越靠近根节点的层所拥有的节点数越少，这样就会造成算力的极大浪费。例如，在创建第2层节点时，只能使用8个线程，但是现代GPU需要成千上万个线程才能满载运行，那当前算法对GPU算力的利用率就非常低，并且随着GPU的进一步提升，该算法的算力利用率会越来越低。

这里采用论文[2]中构建LBVH的思想，同时构建整棵树的所有节点，充分利用GPU的所有核心。限于篇幅，本文只粗略介绍算法的核心部分，感兴趣的读者可以参考原始论文，算法的大致步骤如下。

（1）为每一个Fragment计算Morton Code。

（2）使用Radix Sort对所有第（1）步得到的Morton Code进行排序。

（3）找到所有相同的Morton Code，即落在了同一个叶子节点中的Morton Code，只需要简单对比相邻的Morton Code就可以找出来。

（4）使用Parallel Compaction算法移除多余的相同Morton Code。

（5）生成Binary Radix Tree。

（6）使用Parallel Prefix Sum算法分配所有Octree节点。

（7）对每一个节点找到它的parent，并建立关联。

以上每一步在GPU上都可以并行。对于第（2）步，如果使用的是Cuda，则可以直接使用Thrust库的Sort函数；如果使用的是Compute（本文即如此），则可以参考论文[3]，该论文详细阐述了如何高并发地快速对大量数据进行Radix Sort。

该算法的核心在于第（5）～（7）步不需要逐层建立Octree，每一个节点对应一个线程，所有节点可以并发计算，大大提高了对GPU核心的利用率。

6.2.4 Voxel的快速光线追踪

有了Octree之后，就可以进行射线和Voxel的相交测试了，主要算法和射线与BVH的相交测试类似，从根节点开始逐层进行节点和射线的相交测试，并用堆栈记录整条路径中的所有节点，逐渐寻找可能相交的子节点直到叶子节点。当某条路径继续往下不可能相交时，就回退到该条路径中的上层分叉点建立新的路径进行相交测试。

在描述具体算法前，先对射线进行基本的定义：

pt(t)=p+td

当射线与yz平面相交时可以求得：

射线与xz和xy平面相交可以类似地计算得到。

下面会详细阐述整个算法，该算法参考了论文[4]中的实现方法，该实现方法进行了很多的优化，下面先对算法进行大致说明。

算法按照深度优先的顺序遍历Octree里的Voxel，在每一次循环时根据当前状态，有3种不同的操作来选择下一个需要处理的Voxel。

● PUSH：接着处理射线第一个进入的子节点Voxel。

● ADVANCE：接着处理当前Voxel的兄弟Voxel。

● POP：找到射线出射的最高层祖先节点的兄弟节点Voxel。

图6.4所示为射线遍历Octree的例子。首先从Voxel 2开始，Voxel 2是根节点Voxel 1的子节点。运行两次PUSH操作进入Voxel 3，然后进入叶子节点Voxel 4。执行两次ADVANCE操作后，进入兄弟节点Voxel 5和Voxel 6，接着算法发现射线从它们两个的共同parent Voxel 3出射，于是执行POP操作进入Voxel 7。算法最终在访问完叶子节点Voxel 22后结束，因为此时射线已经离开了根节点。

下面列出了伪代码，包括一个初始化步骤及一个大的循环，处理各个Voxel和射线之间的相交测试。

第1～7行初始化一系列的状态变量。射线当前的有效区域的上下限分别保存在tmin和tmax中，并且初始化为射线和根节点相交的区域值。h是tmax的一个阈值，用来防止对堆栈的不必要写入。parent指向当前考察的Octree Voxel节点，idx表示正在考察的parent的子节点序号，通过比较tmin及由Octree中心点计算出来的tx、ty、tz之间的关系可以得到idx的初始值，pos和scale分别表示当前Voxel对应的Cube位置和大小。

第8～34行的循环一直持续到要么找到和射线相交的节点，要么发现射线离开了Octree的范围。循环每次尝试在区间（tmin，tmax）内对射线和当前Voxel进行相交测试。如果相交，则在第13～20行选取对应的子节点进行下一轮的相交测试；如果当前节点没有和射线相交，则执行第23～25行的ADVANCE操作，之后可能在第27～32行执行POP操作。

第9行通过当前Voxel节点对应的立方体大小计算出射线区域大小tc，tc后续会被INTERSECT和ADVANCE操作用到。第10行决定是否继续处理当前Voxel节点。如果（tmin，tmax）区间为空，则当前Voxel不可能和射线相交，直接跳转到ADVANCE操作即可；否则当前Voxel可能和射线相交，需要进一步考察才能判断。

第11行通过计算当前Voxel和射线的有效区域（tmin，tmax）的相交得到区域tv，它精确地表示了射线和当前Voxel相交的区域。第12行检查tv区域是否为空，如果不为空，则执行PUSH操作；否则跳过当前Voxel并执行ADVANCE操作。

如果当前Voxel是叶子节点，则在第13行终止整个Octree的遍历。第14行把parent和tmax压栈，是否压栈需要分情况来考虑。

● 通常h代表了射线离开parent时对应的t。当tcmax=h时表示射线会同时离开当前Voxel及它的parent，这种情况下不需要保存parent到堆栈上，因为它不会再被访问了。

● 如果parent已经被保存到了堆栈上，就将h置为0。因为tcmax不小于0，这个操作意味着同样的parent不会被重复压栈。

当自顶向下遍历Octree时，第15～19行将parent替换为当前的Voxel，并且相应地设置idx、pos、scale的值去匹配射线进入的第一个子节点。第20行重新进入下一次循环去处理子节点。

第23～25行执行ADVANCE操作。当前Voxel的位置首先保存在一个临时变量里。将pos和idx设置为沿着射线行进所碰到的下一个相同大小的Voxel对应的值。同时更新射线的有效区域的下限值tmin为射线进入新的Voxel的t。第26行检查子节点的index bit的翻转是否和射线行进的方向一致，即射线是否仍处于同一个parent节点里面。如果是，则进入下一次循环；否则执行POP操作。

第27～31行执行POP操作。如果新的scale超过了smax，则第28行可以得出射线已经射出了整棵Octree，于是返回miss。第32行将h置为0，以防止parent被再次压栈检查。

上面的伪代码和算法描述比较粗略，更多的细节和优化可以参考原始论文中的描述。

为了支持半透明的追踪，在叶子Voxel中加入Alpha数据。如果当前子节点是叶子节点，就根据叶子节点数据算出color，当color的Alpha超过translucentNoise时，可以随机判定是否和该叶子节点相交，其中translucentNoise是一个Blue Noise。这里对Alpha进行处理的算法类似论文[5]中的Stochastic Transparency，是一种随机算法，能比较高效地处理半透明物体的追踪。其中，NextGoldenRandom（translucentNoise）对translucentNoise使用Golden Ratio生成随机数，因为输入的translucentNoise是一个2维的Blue Noise，但是需要的是3维的随机数，所以使用Golden Ratio来低代价地生成3维的随机数。

实现了射线和Voxel的相交测试之后，路径追踪就能实现了，实现内容读者可以参考Physically Based Rendering[6]，这里就不再赘述了，只大概阐述下过程。类似论文[7]，作者采用的是单向的路径追踪，光源目前支持点光、平行光、聚光灯、高效的环境光，对Mesh Light的高效支持还在开发中。