APP下载

用于光线跟踪的高并行度表面积启发式(SAH)KD树构建

2018-12-26李建锋谭耀华廖胜辉

湖南大学学报·自然科学版 2018年10期

李建锋 谭耀华 廖胜辉

摘 要:提出一种用于光线跟踪的SAHKD树构建方法,解决当前KD树并行算法并行度不高且效率低的问题.算法首先对所有图元包围盒在三个维度按坐标轴左值排序,得到三维上有序的包围盒索引.然后使用层次遍历构建KD树,根据每个节点包围盒选择要划分的维度,并在当前层生成所有节点在该维度下的候选划分点序列.最后计算每个节点的空间树,在GPU中计算每个候选点的SAH值,选择每个节点的最小SAH值点进行划分.实验中采用4个常用场景进行测试算法性能,并同时比较了当前高效串行与并行算法,结果证明本文提出的算法在生成同等质量KD树的情况下达到对比串行方法4~6倍以及对比并行方法的1.3~1.5倍的计算速度,并且能在线程数成倍增加时达到相近倍数的加速比.

关键词:SAHKD树;空间树;并行计算

中图分类号:TP309.7 文献标志码:A

Abstract:This paper proposed a SAHKD tree construction method for ray tracing to solve the problem of low parallel degree and low efficiency in the existing algorithms. The algorithm first obtains the ordered index on the three latitudes by sorting the primitive bounding boxes according to the left value. Then, according to the node bounding box, we choose the dimension to be divided and generate the candidate partition points of each node under this dimension. Finally, the SAH value of each candidate point was calculated based on the spatial tree in GPU, and the minimum SAH value of each node was selected for partitioning. Four common scenarios were used for testing performance of the algorithm, and compared the efficient serial and parallel GPU algorithm. The results show that the proposed algorithm can achieve 4~6 and 1.3~1.5 times faster than the contrast method when generating the same quality KD tree. When the number of GPU cores fold increases, the speedup ratio reaches a near multiple.

Key words:SAHKDtree; space tree; parallel computing

K维树(KD树)是一类二进制分割树,作为加速结构广泛地应用于图形与查询领域,如光线跟踪中图元与光线的相交检测[1-2]和最近邻查询等.为了高效遍历KD树,通常在构建时使用表面积启发式划分法(SAH),通过最小化每个节点的期望遍历成本选择划分点.如何快速高效地构造SAHKD树一直是研究重點,主要研究方向集中在两种方法上.

一是串行构造方法,最简单的思路是通过全遍历计算SAHKD树所有划分点的SAH值,其计算复杂度为O(N2),由于计算复杂度较高,使得该方法无法应用于大场景.针对该问题,文献[3]和[4]提出……

登录APP查看全文