基于內(nèi)包圍盒的網(wǎng)格結(jié)構(gòu)光線跟蹤算法?

基于內(nèi)包圍盒的網(wǎng)格結(jié)構(gòu)光線跟蹤算法?

帖軍劉國鵬鄭祿

（中南民族大學(xué)武漢430000）

網(wǎng)格是加速光線跟蹤常用的場景劃分結(jié)構(gòu)，為減少光線與網(wǎng)格內(nèi)三角片面片的求交次數(shù)，提出了一種基于內(nèi)包圍盒的網(wǎng)格空間結(jié)構(gòu)，利用光線與網(wǎng)格的交點(diǎn)構(gòu)建一個(gè)內(nèi)包圍盒，將網(wǎng)格內(nèi)的三角片面片分為兩部分，一部分與內(nèi)包圍盒存在交集，另一部分與內(nèi)包圍盒不存在交集，穿過該網(wǎng)格的光線只需與第一部分三角片面做相交測試，從而剔除掉了網(wǎng)格內(nèi)的一部分三角片面，提高了光線跟蹤算法效率。相較于BVH及KD-Tree結(jié)構(gòu)，改進(jìn)算法在大場景上有顯著的優(yōu)越性。

光線跟蹤；空間網(wǎng)格；內(nèi)包圍盒；加速算法

Class NumberTP301.6

1 引言

經(jīng)典的光線跟蹤模型被Whitted［1］于1980年提出，給出了通用光線跟蹤算法描述。光線跟蹤算法原理如圖1所示，由視點(diǎn)與像素（x，y）發(fā)出一條射線，在與場景中第一個(gè)物體相交后繼續(xù)跟蹤其反射及折射光線，找出影響該點(diǎn)光強(qiáng)的所有光源，從而計(jì)算出該點(diǎn)上精確的光線強(qiáng)度。經(jīng)典的加速結(jié)構(gòu)有BVH［2～5］（包圍盒）、八叉樹［6～7］、KD-tree［8～11］、網(wǎng)格［12］等?？臻g網(wǎng)格結(jié)構(gòu)，對場景進(jìn)行均等的劃分，該方法結(jié)構(gòu)簡單，空間開銷小，但該算法在對于三角片面分布不均勻的場景效率較低。

圖1 光線跟蹤

傳統(tǒng)的網(wǎng)格加速結(jié)構(gòu)將場景的包圍盒用網(wǎng)格均等的方法進(jìn)行分割，利用三維DDA算法［13］從光線原點(diǎn)沿光線方向逐個(gè)遍歷網(wǎng)格，若與網(wǎng)格有交點(diǎn)則遍歷該網(wǎng)格中所有三角片面，直到找到交點(diǎn)完成光線跟蹤。本文算法將以網(wǎng)格結(jié)構(gòu)為基礎(chǔ)，構(gòu)建網(wǎng)格的內(nèi)包圍盒，優(yōu)化光線穿網(wǎng)格的效率，使求交次數(shù)大幅減少。

2 基于內(nèi)包圍盒的網(wǎng)格加速算法

傳統(tǒng)的網(wǎng)格算法步驟為：1）用文獻(xiàn)［14～15］所討論的方法，將場景分為三軸等分辨率的網(wǎng)格；2）遍歷所有場景中所有三角片面，將其劃分至相應(yīng)的網(wǎng)格；3）運(yùn)用三維DDA算法依次遍歷光線所穿過的網(wǎng)格，尋找光線與網(wǎng)格內(nèi)三角片面的交點(diǎn)。本文提出一種改進(jìn)的基于內(nèi)包圍盒的加速算法。

2.1基于內(nèi)包圍盒的網(wǎng)格加速

傳統(tǒng)的網(wǎng)格加速結(jié)構(gòu)光線跟蹤算法的光線如圖2所示，光線在通過一個(gè)場景時(shí)求得光線與場景包圍盒的相交交點(diǎn)p0，通過該點(diǎn)坐標(biāo)來確定光線第一個(gè)穿過的網(wǎng)格（0，0），采用DDA算法記錄光線穿過的網(wǎng)格，依次遍歷這些網(wǎng)格中的三角片面，直至光線射出或找到交點(diǎn)后返回。

圖2 光線穿越網(wǎng)格結(jié)構(gòu)

在傳統(tǒng)的網(wǎng)格加速算法中，當(dāng)光線穿過一系列網(wǎng)格時(shí)可能出現(xiàn)光線只穿過網(wǎng)格極小一部分情況，如圖3所示。當(dāng)光線R0穿過場景包圍盒時(shí)，與網(wǎng)格（0，1）、（2，1）、（3，3）等產(chǎn)生的交點(diǎn)t0、t1間距過短，光線與這些網(wǎng)格內(nèi)三角片面相交的概率比較低，但仍要對網(wǎng)格內(nèi)的所有三角片面做求交測試。為提高光線的求交效率，在此提出一種改進(jìn)的網(wǎng)格加速結(jié)構(gòu)——基于內(nèi)包圍盒的網(wǎng)格加速。如圖4所示，該算法將網(wǎng)格空間內(nèi)的三角形片面分為兩部分，一部分如三角形片1與內(nèi)包圍沒有交集，一部分如三角形片2，與包圍盒存在交集。光線只需與包圍盒有交集的三角形片面做相交測試，若遇到如網(wǎng)格（3，3）的比較極端情況，則可大量剔除類似三角片面1的片面，減少網(wǎng)格內(nèi)光線與三角片面片的求交次數(shù)，提高光線的求交效率。

圖3 光線穿過網(wǎng)格時(shí)的截距

2.2內(nèi)包圍盒的建立

為避免光線與網(wǎng)格中所有的三角片面做求交測試，在網(wǎng)格內(nèi)動態(tài)建立一個(gè)更小的內(nèi)包圍盒，內(nèi)包圍盒建立的過程如下：1）求出光線與網(wǎng)格相交于兩點(diǎn)t1，t2的坐標(biāo)，以t1，t2為頂點(diǎn)構(gòu)建一個(gè)AABB包圍盒，如圖4所示；2）遍歷所有三角片面，求其是否與內(nèi)包圍盒相交，若相交則將其放入列表L。3）遍歷列表L中的三角片面，判斷其是否與光線相交，若相交則求出最近交點(diǎn)，若不相交則尋找下一網(wǎng)格重復(fù)1～4步，直至光線射出場景包圍盒。

對于圖5的情況，光線基本沿網(wǎng)格的對角線射進(jìn)及射出，在此情況下建立內(nèi)包圍盒則包圍盒所包圍的三角形片面與網(wǎng)格所包圍的三角形片面數(shù)量基本相同。因此內(nèi)包圍盒的構(gòu)建并不適用所有網(wǎng)格，而是對一些滿足要求的網(wǎng)格建立內(nèi)包圍盒。

圖4 網(wǎng)格內(nèi)包圍盒（?。?/p>

圖5 網(wǎng)格內(nèi)包圍盒（大）

本文以下將對比改進(jìn)前和改進(jìn)后的算法時(shí)間復(fù)雜度來分析構(gòu)建內(nèi)包圍盒的條件。定義trigT為單個(gè)三角片面與單條光線相交測試時(shí)間。boxT為單個(gè)三角片面與內(nèi)包圍盒相交所花費(fèi)的時(shí)間。設(shè)當(dāng)Vbox＜ratioT*Vgrid時(shí)才需要構(gòu)建內(nèi)包圍盒，其中ratioT為［0，1］間的系數(shù)。在本文中假設(shè)CPU計(jì)算基本運(yùn)算所需時(shí)間均為t。光線-三角面的求交采用To?mas Moller［16］等提出的求交算法trigT=45t；對于三角片面片與內(nèi)包圍盒的求交，在求交前先求得三角形的AABB包圍盒，用此包圍盒與內(nèi)包圍做相交檢測，若兩包圍盒相交，則認(rèn)為三角形在此內(nèi)包圍盒中。AABB包圍盒的相交測試采用文獻(xiàn)［17］中給出的算法boxT=15t。最后可估算當(dāng)ratio=2/3時(shí)構(gòu)建內(nèi)包圍盒的效率最高，在bunny場景測試結(jié)果如表1。

表1 渲染總時(shí)間在不同ratioT值下的實(shí)驗(yàn)結(jié)果（bunny）

3 實(shí)驗(yàn)及分析

3.1實(shí)驗(yàn)環(huán)境

本文采用VS2010及PBRT框架作為編程環(huán)境，在一臺配置為ADM 2.8GHz的處理器，4GB內(nèi)存，顯卡為AMD Radeon HD6700 Win7（32）系統(tǒng)下進(jìn)行實(shí)驗(yàn)，場景采用標(biāo)準(zhǔn)的PBRT實(shí)驗(yàn)場景：bunny、room-igi、yeahright。

3.2基于網(wǎng)格的內(nèi)包圍盒算法與其他算法的比較分析

基于上述討論，本算法與傳統(tǒng)的包圍盒算法、網(wǎng)格算法、kd-tree算法進(jìn)行比較分析，表2展示在相同內(nèi)存使用率的情況下，分別對bunny、room-igi、yeahright三場景做光線跟蹤渲染處理。

表2 四種算法在不同場景下的實(shí)驗(yàn)結(jié)果

由表2可見在bunny場景中，當(dāng)場景中某一區(qū)域片面數(shù)較多，片面數(shù)分布極不均勻時(shí)，該算法結(jié)構(gòu)相對于kdtree算法結(jié)構(gòu)效果不是非常明顯，這是由于當(dāng)三角片面數(shù)分布不均勻時(shí)，對場景均分時(shí)導(dǎo)致每個(gè)網(wǎng)格內(nèi)所含的三角片面數(shù)較多，在構(gòu)建內(nèi)包圍盒時(shí)，會對過多的三角片面進(jìn)行遍歷，影響構(gòu)建內(nèi)包圍盒效率。對于片面數(shù)較小的場景如room-igi場景，bvh算法渲染起來更快，而新的改進(jìn)算法依舊會對整個(gè)場景做分割，因此新的改進(jìn)算法在渲染小場景的時(shí)候沒有bvh算法結(jié)構(gòu)效率高。對于場景yeahright，改進(jìn)的網(wǎng)格算法相較于傳統(tǒng)網(wǎng)格算法的求交次數(shù)少了近90%，但改進(jìn)的網(wǎng)格算法需要以網(wǎng)格內(nèi)的三角片面與內(nèi)包圍盒的求交測試為代價(jià)，因此時(shí)間只相較于傳統(tǒng)的網(wǎng)格算法減少10%左右。綜上所述，當(dāng)場景越復(fù)雜，所含三角片面越多時(shí)，改進(jìn)網(wǎng)格算法所體現(xiàn)出的性能就越優(yōu)越。

4 結(jié)語

本文通過構(gòu)建內(nèi)包圍盒來減少三角片面與光線的求交次數(shù)，改進(jìn)了傳統(tǒng)的網(wǎng)格算法，從而提高效率。通過實(shí)驗(yàn)可看出該算法能顯著提高大場景中的光線計(jì)算速度。目前隨著GPU成本的降低以及在家用計(jì)算機(jī)的普及，該領(lǐng)域內(nèi)大量研究已將光線跟蹤算法轉(zhuǎn)向GPU并行運(yùn)算，在今后的工作重點(diǎn)將放在上述算法向GPU并行運(yùn)算的移植，并在移植過程中解決GPU與CPU通信代價(jià)問題。

［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］周鵬.基于光線跟蹤的真實(shí)感全局光照問題研究［D］.濟(jì)南：山東大學(xué)，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，F(xiàn)riedrich 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］李勇.光線跟蹤加速算法在異構(gòu)多核平臺上的設(shè)計(jì)與

［13］胡長華.基于海量準(zhǔn)實(shí)時(shí)數(shù)據(jù)的電網(wǎng)負(fù)載分析應(yīng)用研究［J］.電力信息與通信技術(shù)，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架構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)［J］.計(jì)算機(jī)應(yīng)用與軟件，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的設(shè)計(jì)方案［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.實(shí)現(xiàn)［D］.南京：南京郵電大學(xué)，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，F(xiàn)ellner 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日

國家自然科學(xué)基金（編號：61302192）資助。

帖軍，男，博士，副教授，研究方向：圖像處理、計(jì)算機(jī)圖形等。劉國鵬，男，碩士研究生，研究方向：數(shù)字圖像處理。鄭祿，男，碩士，助理實(shí)驗(yàn)師，研究方向：物聯(lián)網(wǎng)、數(shù)字圖像處理等。