欢迎访问《图学学报》 分享到：
图学学报

图学学报

• 专论：第18届中国虚拟现实大会暨第8届国际虚拟现实与可视化会议(ChinaVR & ICVRV 2018 青岛 ) • 上一篇    下一篇

基于多索引树的阴影光线遍历算法

  

  1. (1. 西南石油大学计算机科学学院，四川 成都 610500； 
    2. 西南石油大学材料科学与工程学院，四川 成都 610500)
  • 出版日期:2019-06-30 发布日期:2019-08-02
  • 基金资助:
    西南石油大学启航计划项目(2015QHZ022)

A Shadow Ray Traversal Algorithm Based on Multiple-Index Tree

  1. (1. School of Computer Science, Southwest Petroleum University, Chengdu Sichuan 610500, China;
    2. School of Materials Science and Engineering, Southwest Petroleum University, Chengdu Sichuan 610500, China)
  • Online:2019-06-30 Published:2019-08-02

PDF (PC)

113

摘要： 阴影光线求交计算是光线跟踪的重要计算瓶颈。然而，构造一棵能有效剔除阴影 光线冗余求交计算的标准树结构仍然十分困难。为区分遮挡和非遮挡的阴影光线，提出一种基 于多索引树的遍历方法，在节点中增加提升遍历速度的索引。首先，针对遮挡光线为尽快与图 元相交的遍历特征，选择性的将位于叶节点上、对光线遮挡概率高的图元索引到中间节点，促 使光线提前在树中层停止搜索。其次，针对非遮挡光线为尽快搜索最邻近节点的遍历特征，为 底层节点建立邻接索引，减少节点搜索空间。利用帧间相关性预测遮挡类型，采用相应遍历方 法进行针对性的加速。相比专有树结构的遍历算法，该算法将遍历时效率提升 20%以上，具有 更好的遍历性能，且预计算时间更少。

关键词: 光线跟踪, 阴影光线遍历, 层次加速结构, 分支预测

Abstract: Shadow ray traversal is abig computation bottleneck in ray tracing. However, constructing an efficient tree to cull down redundant intersections is quite difficult. We propose a Multiple-index Tree based on shadow ray traversal algorithm, which adds indexes for nodes to accelerate traversal with acceptable pre-computation. First, since occluded rays try to intersect with primitive, we select primitives with high intersection probability from leaf nodes to store in inner nodes, which aims to stop traversal in upper tree. Second, since un-occluded rays try to find the nearest node, we create adjacency indexes between nodes in bottom tree, and use the indexes to access next node along ray direction directly. During traversal, by exploiting frame coherence, we estimate the occlusion type of rays and use corresponding method to reduce traversal cost. The experimental result suggest that the algorithm can improve traversal performance more than 20% for complex scenes. Even compared with tree reconstruction method, our method outperforms in reducing more intersections and only consumes 21% pre-computation time.

Key words: ray tracing, shadow ray traversal, hierarchy acceleration structure, branch decision