基于内包围盒的网格结构光线跟踪算法∗

基于内包围盒的网格结构光线跟踪算法∗

帖军刘国鹏郑禄

（中南民族大学武汉430000）

网格是加速光线跟踪常用的场景划分结构，为减少光线与网格内三角片面片的求交次数，提出了一种基于内包围盒的网格空间结构，利用光线与网格的交点构建一个内包围盒，将网格内的三角片面片分为两部分，一部分与内包围盒存在交集，另一部分与内包围盒不存在交集，穿过该网格的光线只需与第一部分三角片面做相交测试，从而剔除掉了网格内的一部分三角片面，提高了光线跟踪算法效率。相较于BVH及KD-Tree结构，改进算法在大场景上有显著的优越性。

光线跟踪；空间网格；内包围盒；加速算法

Class NumberTP301.6

1 引言

经典的光线跟踪模型被Whitted［1］于1980年提出，给出了通用光线跟踪算法描述。光线跟踪算法原理如图1所示，由视点与像素（x，y）发出一条射线，在与场景中第一个物体相交后继续跟踪其反射及折射光线，找出影响该点光强的所有光源，从而计算出该点上精确的光线强度。经典的加速结构有BVH［2～5］（包围盒）、八叉树［6～7］、KD-tree［8～11］、网格［12］等。空间网格结构，对场景进行均等的划分，该方法结构简单，空间开销小，但该算法在对于三角片面分布不均匀的场景效率较低。

图1 光线跟踪

传统的网格加速结构将场景的包围盒用网格均等的方法进行分割，利用三维DDA算法［13］从光线原点沿光线方向逐个遍历网格，若与网格有交点则遍历该网格中所有三角片面，直到找到交点完成光线跟踪。本文算法将以网格结构为基础，构建网格的内包围盒，优化光线穿网格的效率，使求交次数大幅减少。

2 基于内包围盒的网格加速算法

传统的网格算法步骤为：1）用文献［14～15］所讨论的方法，将场景分为三轴等分辨率的网格；2）遍历所有场景中所有三角片面，将其划分至相应的网格；3）运用三维DDA算法依次遍历光线所穿过的网格，寻找光线与网格内三角片面的交点。本文提出一种改进的基于内包围盒的加速算法。

2.1基于内包围盒的网格加速

传统的网格加速结构光线跟踪算法的光线如图2所示，光线在通过一个场景时求得光线与场景包围盒的相交交点p0，通过该点坐标来确定光线第一个穿过的网格（0，0），采用DDA算法记录光线穿过的网格，依次遍历这些网格中的三角片面，直至光线射出或找到交点后返回。

图2 光线穿越网格结构

在传统的网格加速算法中，当光线穿过一系列网格时可能出现光线只穿过网格极小一部分情况，如图3所示。当光线R0穿过场景包围盒时，与网格（0，1）、（2，1）、（3，3）等产生的交点t0、t1间距过短，光线与这些网格内三角片面相交的概率比较低，但仍要对网格内的所有三角片面做求交测试。为提高光线的求交效率，在此提出一种改进的网格加速结构——基于内包围盒的网格加速。如图4所示，该算法将网格空间内的三角形片面分为两部分，一部分如三角形片1与内包围没有交集，一部分如三角形片2，与包围盒存在交集。光线只需与包围盒有交集的三角形片面做相交测试，若遇到如网格（3，3）的比较极端情况，则可大量剔除类似三角片面1的片面，减少网格内光线与三角片面片的求交次数，提高光线的求交效率。

图3 光线穿过网格时的截距

2.2内包围盒的建立

为避免光线与网格中所有的三角片面做求交测试，在网格内动态建立一个更小的内包围盒，内包围盒建立的过程如下：1）求出光线与网格相交于两点t1，t2的坐标，以t1，t2为顶点构建一个AABB包围盒，如图4所示；2）遍历所有三角片面，求其是否与内包围盒相交，若相交则将其放入列表L。3）遍历列表L中的三角片面，判断其是否与光线相交，若相交则求出最近交点，若不相交则寻找下一网格重复1～4步，直至光线射出场景包围盒。

对于图5的情况，光线基本沿网格的对角线射进及射出，在此情况下建立内包围盒则包围盒所包围的三角形片面与网格所包围的三角形片面数量基本相同。因此内包围盒的构建并不适用所有网格，而是对一些满足要求的网格建立内包围盒。

图4 网格内包围盒（小）

图5 网格内包围盒（大）

本文以下将对比改进前和改进后的算法时间复杂度来分析构建内包围盒的条件。定义trigT为单个三角片面与单条光线相交测试时间。boxT为单个三角片面与内包围盒相交所花费的时间。设当Vbox＜ratioT*Vgrid时才需要构建内包围盒，其中ratioT为［0，1］间的系数。在本文中假设CPU计算基本运算所需时间均为t。光线-三角面的求交采用To⁃mas Moller［16］等提出的求交算法trigT=45t；对于三角片面片与内包围盒的求交，在求交前先求得三角形的AABB包围盒，用此包围盒与内包围做相交检测，若两包围盒相交，则认为三角形在此内包围盒中。AABB包围盒的相交测试采用文献［17］中给出的算法boxT=15t。最后可估算当ratio=2/3时构建内包围盒的效率最高，在bunny场景测试结果如表1。

表1 渲染总时间在不同ratioT值下的实验结果（bunny）

3 实验及分析

3.1实验环境

本文采用VS2010及PBRT框架作为编程环境，在一台配置为ADM 2.8GHz的处理器，4GB内存，显卡为AMD Radeon HD6700 Win7（32）系统下进行实验，场景采用标准的PBRT实验场景：bunny、room-igi、yeahright。

3.2基于网格的内包围盒算法与其他算法的比较分析

基于上述讨论，本算法与传统的包围盒算法、网格算法、kd-tree算法进行比较分析，表2展示在相同内存使用率的情况下，分别对bunny、room-igi、yeahright三场景做光线跟踪渲染处理。

表2 四种算法在不同场景下的实验结果

由表2可见在bunny场景中，当场景中某一区域片面数较多，片面数分布极不均匀时，该算法结构相对于kdtree算法结构效果不是非常明显，这是由于当三角片面数分布不均匀时，对场景均分时导致每个网格内所含的三角片面数较多，在构建内包围盒时，会对过多的三角片面进行遍历，影响构建内包围盒效率。对于片面数较小的场景如room-igi场景，bvh算法渲染起来更快，而新的改进算法依旧会对整个场景做分割，因此新的改进算法在渲染小场景的时候没有bvh算法结构效率高。对于场景yeahright，改进的网格算法相较于传统网格算法的求交次数少了近90%，但改进的网格算法需要以网格内的三角片面与内包围盒的求交测试为代价，因此时间只相较于传统的网格算法减少10%左右。综上所述，当场景越复杂，所含三角片面越多时，改进网格算法所体现出的性能就越优越。

4 结语

本文通过构建内包围盒来减少三角片面与光线的求交次数，改进了传统的网格算法，从而提高效率。通过实验可看出该算法能显著提高大场景中的光线计算速度。目前随着GPU成本的降低以及在家用计算机的普及，该领域内大量研究已将光线跟踪算法转向GPU并行运算，在今后的工作重点将放在上述算法向GPU并行运算的移植，并在移植过程中解决GPU与CPU通信代价问题。

［1］Turner Whitted.An Improved Illumination Model for Shad⁃ed Display［C］//CACM，June 1980，23（6）：343-349.

［2］Hank Weghorst，Gary Hooper.Improves Computational Methods for Ray Tracing［J］.ACM Transactions on Graph⁃ics，1984，3：52-69.

［3］P.Hanrahan.Models of Light Reflection for Computer Syn⁃thesized Pictures［J］.Computer Graphics，1977，11（2）：23-25.

［4］Ingo Wald，Solomon Boulos.Ray Tracing DeformableScenes using Bounding Volume Hierarchies［C］//In Pro⁃ceedings of the ACM SIGGRAPH Conference，2007，26（1）：1-18.

［5］周鹏.基于光线跟踪的真实感全局光照问题研究［D］.济南：山东大学，2012：26-40.

ZHOU Peng.Research On Ray Tracing Baseed Photoreal⁃istic Global Illumination［D］.Jinan：Shandong University，2012：26-40.

［6］A.S.Glassner.Space subdivision for fast ray tracing［J］. IEEE Computer Graphics and Applications，1984，4（10）：15-22.

［7］Armin H，Kal M W，Maren B，et al.OctoMap：an efficient probabilistic 3D mapping framework based on octrees［J］. Auton Robot，2013，34（3）：189-206.

［8］Wald I，Friedrich H，Marmitt G.Fast isosurface ray trac⁃ing using implicit KD-Tree［J］.IEEE Transactions on Vi⁃sualization and Computer Graphics，2005，25（12）：562-572.

［9］Alexander Reshetov.Omnidirectional ray tracing traversal algorithm for kd-trees［C］//In Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing，2006：57-60.

［10］Sugerman F T J.KD-tree acceleration structures for a GPU ray tracer［C］//Proceedings of the Graphics Hard⁃ware.Los Angeles，California，2005：15-22.

［11］李勇.光线跟踪加速算法在异构多核平台上的设计与

［13］胡长华.基于海量准实时数据的电网负载分析应用研究［J］.电力信息与通信技术，2014，12（10）：42-45.

HU Changhua.Research on Application of Grid Load Analysis Based on Quantitative Quasi-real-time Data［J］.Electric Power Information and Communication Technology，2014，12（10）：42-45.

［14］易先海.一种基于SCA的ETL架构的设计和实现［J］.计算机应用与软件，2015（4）：24-29.

YI Xianhai.Design and Implementation of an ETL Archi⁃tecture Based on SCA［J］.Computer Applications and Software，2015（4）：24-29.

［15］王岩，王纯.一种基于Kafka的可靠的Consumer的设计方案［J］.软件，2016，37（1）：61-66.

WANG Yan，WANG Chun.A Design Based on Kafka's Reliable Consumer［J］.software，2016，37（1）：61-66.实现［D］.南京：南京邮电大学，2011：18-38.

LI Yong.A Research and Implementation of System Ar⁃chitecture for Heterogeneous Multi-core Platform［D］. Nanjing：Nanjing University of Posts and Telecommunica⁃tions，2011：18-38.

［12］Ingo，Thiago.Ray Tracing Animated Scenes using Coher⁃ent Grid Traversal［J］.ACM Transactions on Graphics，2006，25（3）：485-493.

［13］J.Goldsmith，J.Salmon.Auto matic creation of object hi⁃erachies for ray tracing［J］.IEEE Computer Graphics and Application，1987，7（5）：14-20.

［14］Havran V，Prikry I J，Purgathoffer W.Statistical compari⁃son of ray-shooting eddiciency schemes［R］.Vienna Uni⁃versityofTechnology，Austria：TechnicalReport TR-186-2-00-14，2000.

［15］Muller G，Fellner D W.Hybrid scene structuring with ap⁃plication to ray tracing［C］//Proceedings of the Interna⁃tional Conference on Visual Computing 1999.Goa，India，1999：19-26.

［16］Tomas Moller，Ben Trumbore.Fast，Minimum Storage Ray-Triangle Intersection［J］.Journal of Graphics Tools，2005，2（1）：21-28.

［17］C.F.Li，Y.T.Feng，D.R.J.Owen.SMB：Collision detection based on temporal coherence［J］.Computer methods in appliedmechanicsandengineering，2006（195）：2252-2269.

Grid Structure Ray Tracing Algorithm Based on Inner-Box

TIE JunLIU GuopengZHEN Lu
（South-Central University for Nationalities，Wuhan430000）

Grid is a common means for dividing scenes of acceleration ray，In order to reduce the intersection number of ray with triangle，then an improved grid structure is presented based on Inner-box.An inner-box is built by using of the point where the ray intersects the triangle.The inner-box divides the triangle in the grid into two parts，the one part has a intersection with the in⁃ner-box，the other part hasn't.So the ray needs to do intersection testing with the first part，thus pushing the second part out of inter⁃section testing，improving the efficiency of ray tracing.Compared to BVH and KD-Tree structure，improved algorithm has a signifi⁃cant advantage in large scenes.

ray tracing，grid，inner-box，accelerated methods

TP301.6

10.3969/j.issn.1672-9722.2017.05.006

2016年11月20日，

2016年12月27日

国家自然科学基金（编号：61302192）资助。

帖军，男，博士，副教授，研究方向：图像处理、计算机图形等。刘国鹏，男，硕士研究生，研究方向：数字图像处理。郑禄，男，硕士，助理实验师，研究方向：物联网、数字图像处理等。