基于八叉树自适应体归并的光线跟踪加速结构
|
摘要
针对光线跟踪算法计算量大和运行效率低的问题,提出了一种采用八叉树自适应体归并(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.
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.
引文
[1]Cai Xun,Zeng Liang,Liu Guangguo.Survey of ray tracing in volume rendering[J].Computer Engineering and Design,2009,30(21):4956-4959.蔡勋,曾亮,刘光国.光线跟踪方法在体绘制中的应用与发展[J].计算机工程与设计,2009,30(21):4956-4959.
[2]Luo Han,Yuan Changying.Retroreflective performance analysis of cube corner membrane structure[J].Acta Optica Sinica,2015,35(3):0323001.罗汉,袁长迎.立方角锥型膜结构的逆反射特性计算[J].光学学报,2015,35(3):0323001.
[3]Wu Shuangqing,Zhang Yin,Zhang Sanyuan,et al.Analysis of three-dimensional measurement system and the coordinates calibration in Fourier transform profilometry[J].Acta Optica Sinica,2009,29(10):2780-2785.吴双卿,张引,张三元,等.傅里叶变换轮廓术物体三维形貌测量的系统分析及其坐标校准方法[J].光学学报,2009,29(10):2780-2785.
[4]Walter B,Drettakis G,Greenberg D P.Enhancing and optimizing the render cache[C].Proceedings of the 13th Eurographics Workshop on Rendering,2002:37-42.
[5]Maria M,Horna S,Aveneau L.Constrained convex space partition for ray tracing in architectural environments[J].Computer Graphics Forum,2016,DOI:10.1111/cgf.12801.
[6]Li Jing,Wang Wencheng,Wu Enhua.Ray tracing of dynamic scenes by managing empty regions in adaptive boxes[J].Chinese Journal of Computers,2009,32(6):1172-1182.李静,王文成,吴恩华.基于空盒自适应生成的动态场景光线跟踪计算[J].计算机学报,2009,32(6):1172-1182.
[7]Navrátil P A,Fussell D S,Lin C,et al.Dynamic scheduling for large-scale distributed-memory ray tracing[C].Eurographics Symposium on Parallel Graphics and Visualization,2012:61-70.
[8]Hu W,Huang Y,Zhang F,et al.Ray tracing via GPU rasterization[J].Visual Computer,2014,30(6-8):697-706.
[9]Zhou P,Meng X.SIMD friendly ray tracing on GPU[C].International Conference on Computer-Aided Design and Computer Graphics,2011:87-92.
[10]Nery A S,Nedjah N,Fran9a F M G.Efficient hardware implementation of ray tracing based on an embedded software for intersection computation[J].Journal of Systems Architecture,2013,59(3):176-185.
[11]Yoder R,Bloniarz P A.A practical algorithm for computing neighbors in quadtrees,octrees,and hyperoctrees[C].Proceedings of the 2006International Conference on Modeling,Simulation&Visualization Methods,2006:249-255.
[12]Tian J,Jiang W F,Luo T,et al.Adaptive coding of generic 3Dtriangular meshes based on octree decomposition[J].The Visual Computer,2012,28(6):819-827.
[13]Namdari M H,Hejazi S R,Palhang M.MCPN,octree neighbor finding during tree model construction using parental neighboring rule[J].3DResearch,2015,6:29.
[14]Liu B Q,Clapworthy G J,Dong F,et al.Octree rasterization:Accelerating high-quality out-of-core GPU volume rendering[J].IEEE Transactions on Visualization&Computer Graphics,2013,19(10):1732-1745.
[15]Wang Wenxi,Xiao Shide,Meng Wen,et al.Ray tracing algorithm based on octree space partition method[J].Journal of Computer Applications,2008,28(3):656-658.王文玺,肖世德,孟文,等.一种基于八叉树空间剖分技术的光线跟踪算法[J].计算机应用,2008,28(3):656-658.
[16]Zhang Wensheng,Xie Qian,Zhong Jin,et al.Acceleration algorithm in ray tracing by the octree neighbor finding[J].Journal of Graphics,2015,36(3):339-344.张文胜,解骞,钟瑾,等.基于八叉树邻域分析的光线跟踪加速算法[J].图学学报,2015,36(3):339-344.
[17]Fu Huan,Liang Li,Wang Fei,et al.A point cloud segmentation algorithm using local convexity and octree[J].Journal of Xi’an Jiaotong University,2012,46(10):60-65.傅欢,梁力,王飞,等.采用局部凸性和八叉树的点云分割算法[J].西安交通大学学报,2012,46(10):60-65.
[18]Yan Jian,Peng Youduo,Cheng Ziran,et al.Moving accumulative computation method for flux distribution of heat absorber in symmetry concentrating solar collector system[J].Acta Optica Sinica,2016,36(5):0508001.颜健,彭佑多,程自然,等.对称型太阳能聚光集热系统吸热器能流分布的运动累加计算方法[J].光学学报,2016,36(5):0508001.
[19]Hornung A,Wurm K M,Bennewitz M,et al.OctoMap:An efficient probabilistic 3D mapping framework based on octrees[J].Autonomous Robot,2013,34(3):189-206.
[20]LüGuangxian,Pan Mao,Wu Huanping,et al.Research on large virtual octree model for true three dimensional geoscience modeling[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2007,43(4):496-501.吕广宪,潘懋,吴焕萍,等.面向真三维地学建模的海量虚拟八叉树模型研究[J].北京大学学报(自然科学版),2007,43(4):496-501.
[21]Hapala M,Havran V.Review:Kd-tree traversal algorithms for ray tracing[J].Computer Graphics Forum,2011,30(1):199-213.
[2]Luo Han,Yuan Changying.Retroreflective performance analysis of cube corner membrane structure[J].Acta Optica Sinica,2015,35(3):0323001.罗汉,袁长迎.立方角锥型膜结构的逆反射特性计算[J].光学学报,2015,35(3):0323001.
[3]Wu Shuangqing,Zhang Yin,Zhang Sanyuan,et al.Analysis of three-dimensional measurement system and the coordinates calibration in Fourier transform profilometry[J].Acta Optica Sinica,2009,29(10):2780-2785.吴双卿,张引,张三元,等.傅里叶变换轮廓术物体三维形貌测量的系统分析及其坐标校准方法[J].光学学报,2009,29(10):2780-2785.
[4]Walter B,Drettakis G,Greenberg D P.Enhancing and optimizing the render cache[C].Proceedings of the 13th Eurographics Workshop on Rendering,2002:37-42.
[5]Maria M,Horna S,Aveneau L.Constrained convex space partition for ray tracing in architectural environments[J].Computer Graphics Forum,2016,DOI:10.1111/cgf.12801.
[6]Li Jing,Wang Wencheng,Wu Enhua.Ray tracing of dynamic scenes by managing empty regions in adaptive boxes[J].Chinese Journal of Computers,2009,32(6):1172-1182.李静,王文成,吴恩华.基于空盒自适应生成的动态场景光线跟踪计算[J].计算机学报,2009,32(6):1172-1182.
[7]Navrátil P A,Fussell D S,Lin C,et al.Dynamic scheduling for large-scale distributed-memory ray tracing[C].Eurographics Symposium on Parallel Graphics and Visualization,2012:61-70.
[8]Hu W,Huang Y,Zhang F,et al.Ray tracing via GPU rasterization[J].Visual Computer,2014,30(6-8):697-706.
[9]Zhou P,Meng X.SIMD friendly ray tracing on GPU[C].International Conference on Computer-Aided Design and Computer Graphics,2011:87-92.
[10]Nery A S,Nedjah N,Fran9a F M G.Efficient hardware implementation of ray tracing based on an embedded software for intersection computation[J].Journal of Systems Architecture,2013,59(3):176-185.
[11]Yoder R,Bloniarz P A.A practical algorithm for computing neighbors in quadtrees,octrees,and hyperoctrees[C].Proceedings of the 2006International Conference on Modeling,Simulation&Visualization Methods,2006:249-255.
[12]Tian J,Jiang W F,Luo T,et al.Adaptive coding of generic 3Dtriangular meshes based on octree decomposition[J].The Visual Computer,2012,28(6):819-827.
[13]Namdari M H,Hejazi S R,Palhang M.MCPN,octree neighbor finding during tree model construction using parental neighboring rule[J].3DResearch,2015,6:29.
[14]Liu B Q,Clapworthy G J,Dong F,et al.Octree rasterization:Accelerating high-quality out-of-core GPU volume rendering[J].IEEE Transactions on Visualization&Computer Graphics,2013,19(10):1732-1745.
[15]Wang Wenxi,Xiao Shide,Meng Wen,et al.Ray tracing algorithm based on octree space partition method[J].Journal of Computer Applications,2008,28(3):656-658.王文玺,肖世德,孟文,等.一种基于八叉树空间剖分技术的光线跟踪算法[J].计算机应用,2008,28(3):656-658.
[16]Zhang Wensheng,Xie Qian,Zhong Jin,et al.Acceleration algorithm in ray tracing by the octree neighbor finding[J].Journal of Graphics,2015,36(3):339-344.张文胜,解骞,钟瑾,等.基于八叉树邻域分析的光线跟踪加速算法[J].图学学报,2015,36(3):339-344.
[17]Fu Huan,Liang Li,Wang Fei,et al.A point cloud segmentation algorithm using local convexity and octree[J].Journal of Xi’an Jiaotong University,2012,46(10):60-65.傅欢,梁力,王飞,等.采用局部凸性和八叉树的点云分割算法[J].西安交通大学学报,2012,46(10):60-65.
[18]Yan Jian,Peng Youduo,Cheng Ziran,et al.Moving accumulative computation method for flux distribution of heat absorber in symmetry concentrating solar collector system[J].Acta Optica Sinica,2016,36(5):0508001.颜健,彭佑多,程自然,等.对称型太阳能聚光集热系统吸热器能流分布的运动累加计算方法[J].光学学报,2016,36(5):0508001.
[19]Hornung A,Wurm K M,Bennewitz M,et al.OctoMap:An efficient probabilistic 3D mapping framework based on octrees[J].Autonomous Robot,2013,34(3):189-206.
[20]LüGuangxian,Pan Mao,Wu Huanping,et al.Research on large virtual octree model for true three dimensional geoscience modeling[J].Acta Scientiarum Naturalium Universitatis Pekinensis,2007,43(4):496-501.吕广宪,潘懋,吴焕萍,等.面向真三维地学建模的海量虚拟八叉树模型研究[J].北京大学学报(自然科学版),2007,43(4):496-501.
[21]Hapala M,Havran V.Review:Kd-tree traversal algorithms for ray tracing[J].Computer Graphics Forum,2011,30(1):199-213.