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

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

6.2.1 Voxel是什么

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

图6.1 《王者荣耀》5V5低、中分辨率Voxelization

图6.2 《王者荣耀》5V5高、超高分辨率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对应的世界空间坐标(xyz),如图6.3所示,(xyz)对应的小立方体即该Fragment对应的Voxel。在存储Voxel数据时,有若干选择,如color、normal,甚至各种PBR渲染所需要的粗糙度、金属度等参数。在本文的应用中,只需要存储color和normal即可。需要注意的是,在将Pixel Shader生成的Fragment转换成Voxel并放入Voxel列表中时,大量的线程会同时访问该列表,所以需要用到原子操作函数和Atomic Counter,它们支持高效率的整型数的原子增减操作。每个线程首先将Atomic Counter加1,然后把Voxel数据保存在列表的对应位置上,这样大量的线程就能高效地同时操作Voxel列表了。

图6.3 Voxelization算法流程

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平面相交时可以求得:

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

下面会详细阐述整个算法,该算法参考了论文[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后结束,因为此时射线已经离开了根节点。

图6.4 射线遍历Octree的例子

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

第1~7行初始化一系列的状态变量。射线当前的有效区域的上下限分别保存在tmin和tmax中,并且初始化为射线和根节点相交的区域值。h是tmax的一个阈值,用来防止对堆栈的不必要写入。parent指向当前考察的Octree Voxel节点,idx表示正在考察的parent的子节点序号,通过比较tmin及由Octree中心点计算出来的txtytz之间的关系可以得到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的高效支持还在开发中。