光线跟踪的自适应多点迭代体素遍历算法

Self-adaptive voxel traversing algorithm based on multi-point iteration for ray tracing

光线跟踪算法是提高图形真实感的一种主要技术,为了提高光线跟踪算法的速度,提出了一种快速的三维直线均匀体素遍历算法.该算法借鉴光栅直线行程扫描转换的思想,依据直线斜率定义决策参数,利用迭代计算决策参数控制每一步的光线走向.与单点迭代算法不同的是,一条直线依据斜率被自适应地拆分成由多点组成的m-遍历,而决策参数仅需要针对m-遍历甚至由多个m-遍历组成的周期进行计算,从而有效地减少了运算量.理论分析和实验表明,该算法的运行速度比现存的最快单步算法提高约56%,大幅度提高了光线跟踪的效率,且仅使用简单的整数运算即可实现.

Ray tracing algorithm is a major technique for enhancing the realistic sense of graphs. In order to improve the speed of ray tracing algorithm, a fast uniform voxel traversing algorithm along 3D line was proposed. The basic idea for scanning conversion of raster line stroke was referenced in the proposed algorithm. The decision parameter was defined according to line slope, and the decision parameter obtained with iteration calculation was used to control the ray movement direction at each step. Different from the single-point iteration algorithm, a line was adaptively divided into serveral m-traversings composed of multiple points according to the slope. The decision parameter could be calculated only aiming at m-traversings and even periods composed of multiple m-traversings. And thus, the calculation amount gets effectively decreased. The theoretical and experimental results show that the running speed of the proposed algorithm increases nearly by 56% compared with the existing fastest single-point algorithm and the efficiency of ray tracing gets greatly enhanced, which can be realized only with simple integer calculation.