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

摘要

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