+高级检索
用于光线跟踪的高并行度表面积启发式(SAH)KD树构建
DOI:
作者:
作者单位:

作者简介:

通讯作者:

基金项目:


Highly Parallel SAH-KD-tree Construction for Raytracing
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

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

    Abstract:

    This paper proposed a SAH-KD 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.

    参考文献
    相似文献
    引证文献
文章指标
  • PDF下载次数:
  • HTML阅读次数:
  • 摘要点击次数:
  • 引用次数:
引用本文

李建锋,谭耀华,廖胜辉.用于光线跟踪的高并行度表面积启发式(SAH)KD树构建[J].湖南大学学报:自然科学版,2018,45(10):148~154

复制
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2018-10-23
  • 出版日期:
作者稿件一经被我刊录用,如无特别声明,即视作同意授予我刊论文整体的全部复制传播的权利,包括但不限于复制权、发行权、信息网络传播权、广播权、表演权、翻译权、汇编权、改编权等著作使用权转让给我刊,我刊有权根据工作需要,允许合作的数据库、新媒体平台及其他数字平台进行数字传播和国际传播等。特此声明。
关闭