基于八叉树自适应体归并的光线跟踪加速结构

Ray Tracing Acceleration Structure Based on Octree Adaptive Volume Merging

针对光线跟踪算法计算量大和运行效率低的问题,提出了一种采用八叉树自适应体归并(OAVM)的光线跟踪加速结构。该结构将八叉树模型的空节点自适应地聚集为包围体,尽可能地减小了光线与空白节点的求交次数。基于OAVM的一种多级八叉树结构的特点,提出了采用Morton码对各层级的所有节点分别进行编码的算法,该结构所采用的存储方式和邻域查询算法有效减小了指针数量,避免了递归搜索。同时,该算法可以有效处理大规模动态场景的局部更新问题。基于Liang-Barsky算法,光线相交测试的计算速度得到提升。实验结果表明,和传统结构算法相比,所提出算法的指针总数平均减少了54.45%,光线相交测试时间平均缩短了52.37%,大幅加快了相交测试速度,提升了场景的渲染效率。

In order to overcome the problems of large amounts of calculation and low operating efficiency of ray tracing algorithm,a ray tracing acceleration structure based on the octree adaptive volume merging（OAVM）is proposed.Through gathering blank nodes of an octree model as a bounding volume adaptively,this structure can reduce the intersection number between ray and blank nodes as much as possible.Based on the characteristic that OAVM is a multi-level octree structure,an algorithm with the Morton code to encode all the nodes at different levels is proposed.The storage method and neighborhood search algorithm used in this structure can reduce the amount of pointers and avoid the recursive search effectively.In the meanwhile,the algorithm deals with the problem of partial update a in large scale dynamic scene effectively.Based on the idea of Liang-Barsky algorithm,the calculation speed of intersection test for rays is improved.The experiment results indicate that,compared with traditional algorithms,the proposed algorithm can reduce the total number of pointers by 54.45% averagely.The time of ray intersection test is reduced by 52.37%averagely.The ray intersection test time is decreased and the scene rendering efficiency is improved.