GPU BVH Construction

对100000面的Dragon生成的BVH

最近需要在GPU上实现BVH的并行高速构建方法,于是就照着一篇NVidia的文章《Thinking Parallel, Part III: Tree Construction on the GPU》做了。

此遍历的算法是完全并行的,因为在建树时早早已经将所有的片元(譬如三角形或是Vec3)根据Morton Code来进行排序。神奇之处也就在于在如此排序之后,对于某个片元,即可直接通过Morton Code来得到它在最终的表示BVH的二叉树中的位置,而这样所以能成立的原因则是这里的Code与Z-Curve是等价的,按数值大小从小到大排列就会呈现出以递归的方式填满空间的规律。

NVidia的文章在讲解此算法时引用了其文章作者本人在2012年的文章《Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees》( http://devblogs.nvidia.com/parallelforall/wp-content/uploads/2012/11/karras2012hpg_paper.pdf )。此篇文相比起先前的工作最大的进步就在于通过这个Morton Code的方法使得在GPU中每个线程之间完全没有任何的依赖关系,从而达成非常高的执行效率;相比起先前需要从上到下一层层扩张,其进步尤为明显,可以达到100%的核心利用率。不过这只是整个计算BVH的过程当中的一步而非全部;整体的过程应该是:

  1. 给所有的片元赋上一个Morton Code。如果是三角形,可以取其几何中心。再把Morton Code进行排序。如果有重复的Morton Code,还要去除重复。这也就意味着一个Morton Code可能对应多个片元。
  2. 用Morton Code进行排序并生成BVH。
  3. 把片元填充进BVH,再从叶子结点到根结点进行Reduce,写入包围盒的值。

在以上的第3步中,利用率还仍是会因为层层Reduce时树的结点数变少而变低,所以性能的提升主要来自于第2步。

在第二步中,需要在两个地方用到二分搜索的模式;第一个是找「覆盖的结点的下标的范围」,第二个是在第一步的范围中找「分界点」。写起来时和刷题中经常遇到的二分搜索是一样的。

此篇文章的算法只在所有的Morton Code都没有重复的情况下才有用。如果有重复,则会出现一个叶子结点对应多个父结点的情况,会导致Reduce的过程无法进行。这也是因为如果有重复的Morton Code时,第二步中的找「范围」会在不同次迭代时找到同一个分界点,这就导致了这个问题。这个问题也可以在BVH生成以后做一个简单的一致性检查来确认:只要看每个结点的parent和left/right是否能匹配就可以知道了。

在Reduction时,对每个结点的更新需要用加锁来确保原子操作,而对每个结点的访问亦要用atomicAdd来统计次数,以避免重复计算,不然在有锁的情况下,几千个线程从叶子结点涌向极结点造成的锁竞争可是要让程序永远都完不成了。

既然用了锁,就要设法回避死锁的问题。一种方法是加上 -G 打开 debug模式;更好方式是在 if{} else{} 之后加上一个随便什么语句,譬如 __asm(“pmevent 0;”) 。不过即使是打开 debug模式,性能会都比 CPU上 用最朴素的方法做要高出许多,更不用说打开 -O3 模式了。其中两个Kernel的CPU与GPU的性能对比如下:

CPU: i5-3210M
GPU: NVidia NVS 5200M

Morton Code生成与排序时间
CPU上排序:19 ms

构建BVH的时间(100000面,98848个不重复的Morton Code)
CPU,层次法 = 30 ms
CPU,Karras文中的方法,单线程 = 59 ms
GPU,Karras文中的方法,<<<120, 128>>> = 1.3 ms !!!!

计算包围盒的时间
CPU,从下往上 = 196 ms
GPU,并行 reduction = 7 ms !!!

所以可见这个方法是相当之有效的,而且适应不同大小的GPU。论文中用的是GTX480,前述网页的文章中用的是 GTX690,横跨了Fermi与Kepler这两代,说明在不同代的GPU之间也是应当能够通用的。(可能就除了一些细微的可能死锁的情况、或者可能发生非法内存访问但勉强蒙混过头的情况下不通用外,其它情况都应当是通用的吧)

此条目发表在Programming分类目录。将固定链接加入收藏夹。