高级检索
张正昌, 何发智, 周毅. 基于动态任务调度的层次包围盒构建算法[J]. 计算机辅助设计与图形学学报, 2018, 30(3): 491-498. DOI: 10.3724/SP.J.1089.2018.16388
引用本文: 张正昌, 何发智, 周毅. 基于动态任务调度的层次包围盒构建算法[J]. 计算机辅助设计与图形学学报, 2018, 30(3): 491-498. DOI: 10.3724/SP.J.1089.2018.16388
Zhang Zhengchang, He Fazhi, . Bounding Volume Hierarchy Construction Algorithm Based on Dynamic Task Scheduling[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(3): 491-498. DOI: 10.3724/SP.J.1089.2018.16388
Citation: Zhang Zhengchang, He Fazhi, . Bounding Volume Hierarchy Construction Algorithm Based on Dynamic Task Scheduling[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(3): 491-498. DOI: 10.3724/SP.J.1089.2018.16388

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

Bounding Volume Hierarchy Construction Algorithm Based on Dynamic Task Scheduling

  • 摘要: 交点计算是光线跟踪算法中开销最大的部分,层次包围盒(BVH)则是主流加速结构.为了提高BVH的构建速度,提出一种基于动态任务调度和warp线程优化的BVH构建算法,并针对目前主流GPU架构特点进行优化.该算法根据表面积启发式(SAH)值对BVH进行自底向上多轮优化;在每次循环的开始阶段判断当前线程是否空闲,若空闲,则根据记录任务进度的全局变量进行任务分配,否则,继续遍历BVH;当遍历到符合条件的节点时以该节点为幼树根节点进行幼树重构,这一阶段使用同一warp中的32个线程协同进行幼树重构,并且可以依据幼树叶子节点数调整同时处理的幼树个数.对经典的三维场景进行实验的结果表明,在BVH构建质量相同的情况下,当场景中三角元片数超过10万时,BVH构建速度会得到提升;当三角元片数大于100万时,该算法比聚类幼树重构层次包围盒(Atr BVH)算法在BVH优化阶段速度提升47%,从而使整个构建速度提高25%.

     

    Abstract: 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.

     

/

返回文章
返回