基于动态任务调度的层次包围盒构建算法  

Bounding Volume Hierarchy Construction Algorithm Based on Dynamic Task Scheduling

作　　者：张正昌 何发智[1] 周毅[1] Zhang Zhengchang;He Fazhi;Zhou Yi(School of Compute Science,Wuhan University,Wuhan 430072)

机构地区：[1]武汉大学计算机学院,武汉430072

出　　处：《计算机辅助设计与图形学学报》2018年第3期491-498,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61472289);国家重点研究发展计划(2016YFC0106305)

摘　　要：交点计算是光线跟踪算法中开销最大的部分,层次包围盒(BVH)则是主流加速结构.为了提高BVH的构建速度,提出一种基于动态任务调度和warp线程优化的BVH构建算法,并针对目前主流GPU架构特点进行优化.该算法根据表面积启发式(SAH)值对BVH进行自底向上多轮优化;在每次循环的开始阶段判断当前线程是否空闲,若空闲,则根据记录任务进度的全局变量进行任务分配,否则,继续遍历BVH;当遍历到符合条件的节点时以该节点为幼树根节点进行幼树重构,这一阶段使用同一warp中的32个线程协同进行幼树重构,并且可以依据幼树叶子节点数调整同时处理的幼树个数.对经典的三维场景进行实验的结果表明,在BVH构建质量相同的情况下,当场景中三角元片数超过10万时,BVH构建速度会得到提升;当三角元片数大于100万时,该算法比聚类幼树重构层次包围盒(Atr BVH)算法在BVH优化阶段速度提升47%,从而使整个构建速度提高25%.Intersection computation is the most expensive part of the ray-tracing while BVH is the main acceleration structure.To improve the construction speed of BVH,a new BVH construction method based on dynamic task scheduling and threads optimization of warp is presented and it is optimized according to some main GPU architectures.The algorithm performed multiple rounds of bottom-up traversal over the BVH based on the SAH value.At the beginning of each cycle,we assigned the task according to the global variables that recorded the progress of the task if the current thread was idle,otherwise we continued to traverse the BVH.We reconstructed the treelet that used the node as treelet root when the node met the conditions during the traversal.At this stage,we leveraged 32 threads in the same warp to reconstruct the treelet collaboratively and we could adjust the number of parallel tasks according to the number of treelet leaves.According to the experiments on some classical scenes,our solution can be faster while the number of triangles is greater than one hundred thousand and can be about 47%faster when the number of triangles is above one million in the optimization stage of AtrBVH,thus increasing the overall speed by 25%,in the case of BVH construction quality being the same.

关 键 词：GPU加速 动态任务调度 光线跟踪 层次包围盒 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]