動態柵格劃分的光線追蹤場景繪制

陳濱，虞鴻，吳哲夫

(1.浙江工業大學 藝術學院，浙江 杭州 310023;2.浙江工業大學 信息工程學院，浙江 杭州 310023)

在光線追蹤繪制真實場景過程中，加速結構是用來減少光線-圖元相交檢測所需要的時間［1］.早期提出的加速結構包括Bentley提出的kd樹［2］，Rubin和Whited提出的 BVH［3-4］，以及 Fujimoto提出的均勻柵格法［5-6］，Sachidhar等人已經把這種算法在GPU上實現［7］.對于均勻柵格法的加速結構，它是將空間細分為具有相同大小的長方體形式的三維柵格.這種空間組織方式創建簡單，主要就是把空間中的圖元分配到關聯的網格當中，因此它的建立速度要快于kd樹和BVH，但是它的光線遍歷并求交的速度要慢于kd樹和BVH.對于動態真實場景的繪制，每種加速結構的效率是由兩部分組成:加速結構建立時間和光線-圖元求交時間.在真實復雜場景繪制的時候，由于場景中的圖元分布未知，Wald等人認識到很難選擇一種較為平衡的方法，最終提出了采用建立速度較快的相對比較平衡的grids方法來替代建立速度較慢的kd樹和BVH等方法［8］.Shirley提出只對每個擁有圖元的柵格構造對象［9］，擁有圖元的柵格只存一個圖元指針，該優化方法大大降低了該方法所需要的內存.然而，均勻柵格法在光線遍歷的過程中還沒有很好的提升，主要因為在類似由一個較小的物體和較大的房間組成的場景中，有許多沒有涉及到實體的空間也會進行同樣數量的柵格劃分［10］.因此，這種方法就增加了許多冗余的光線與加速結構求交計算.

本文描述了一種改進后的均勻柵格方法，它根據每個柵格所包含的圖元數量動態分割柵格，在那些比較空曠的空間就不進行柵格劃分了，除去了因為沒有必要的柵格劃分而帶來的多余計算量.最后，在CPU上實現動態柵格加速結構的光線追蹤方法.

1 柵格數據結構

建立柵格數據結構過程包括把整個空間中所有物體的包圍盒分割成大小相同的柵格(本文把空間中的一個長方體體元當作一個柵格)，并把組成物體的圖元(一般為三角形)放入這些柵格中.在均勻柵格法當中，柵格的數量是根據整個空間中圖元的個數決定的，每個維度的柵格數量nx、ny、nz可進行如下計算［11］:

式中:wx、wy、wz為空間中所有物體包圍盒 x、y、z方向的跨度，m用來改變柵格數量的系數，通常取2，s為每個柵格的邊長.由于它均勻地分割成相同大小的柵格，可將這些柵格根據對應的坐標序號放入一個一維數組當中，如圖1.柵格數組中的每個柵格對象保存著指向與該柵格關聯的三角形圖元指針，若柵格沒有關聯的三角形圖元，那么可以把這個柵格對象設置為空.

圖1 均勻柵格法的空間劃分和數據結構表示Fig.1 Uniform grids space partition and data struct presentation

動態柵格法的空間劃分也是基于均勻柵格劃分策略，但是動態柵格劃分并不是一下子均勻地劃分成相等大小的柵格，如圖2.柵格樹的根部代表整個空間所有物體的包圍盒，每個子節點表示父節點進行一次均勻劃分4個部分的子柵格.和均勻柵格的數據表示一樣，每個柵格對象保存著指向與該柵格關聯的三角形圖元指針，若沒有關聯圖元對象可以設置為空.柵格樹有2個重要的性質:1)涉及多個柵格圖元，它的指針可能會保存在多個柵格節點;2)樹左側節點中圖元離視點距離一定小于樹右側節點中圖元離視點的距離，并且隨著樹的深度變化，節點中的圖元離視點的距離也越遠.這樣在光線遍歷的過程中，如發現與某個圖元相交，那么就結束該光線的遍歷.

圖2 動態柵格法的空間劃分和數據結構表示Fig.2 Dynamic grids space partition and data struct presentation

2 基于視點距離的柵格建立

為了提高光線追蹤中光線與柵格遍歷速度，許多方法在建立加速數據結構的時候都進行了排序［12-13］.根據從頂層到底層的順序建立柵格樹，這個從頂層到底層的順序對應著柵格節點中的圖元距離從近到遠.先把根節點初始化，對空間中所有物體的包圍盒做一次均勻柵格劃分，此次劃分在x、y、z方向一分為二，即在三維空間中把物體包圍盒分成8個柵格.然后根據離視點的距離，從左到右依次作為根節點的子節點.在本文的實現當中，視點放在z軸的負半軸上，因此柵格的z軸序列號較小的就是離視點較近的.最后判斷這些子節點中的圖元是否到達柵格的飽和狀態，若沒有到達柵格的飽和狀態，那么用相同的方法繼續劃分子柵格，反之則停止.圖3描述了一個柵格的飽和狀態，左圖中的柵格中有2個三角形圖元a和b，如果對這個柵格再進行每個維度二分的柵格劃分，那么它的每個子柵格還是關聯著2個圖元三角形，這樣的重復操作將會消耗很大的遞歸?？臻g，因此在實現當中，針對遇到這種情況就停止柵格劃分.

圖3 柵格的飽和狀態Fig.3 Saturation state of the grid

如上所述的柵格數據結構構造方法，顯然比較適合一些非規則分布的模型，例如當視點對著廣闊的天空，天空中排布這零星的物體，這些物體相對天空就比較小.因此在天空這部分做柵格劃分的時候，很快就到達了柵格飽和狀態，而劃分物體的時候會劃分地比較密，算法1給出了本文的動態柵格劃分方法.

算法1 動態柵格建立

輸入:空間中三角形圖元數組objects，這些圖元的包圍盒bbox，柵格根節點recursivecells

1)if recursivecells equal null then

2)初始化根節點的子柵格數，numcells=2×2×2，并把根節點recursivecells的8個子柵格都設置為null;

3)for each objectsi，do

4)objbbox=objectsi-＞bbox;

5)根據單個圖元包圍盒objbbox的位置，把它分配到父節點包圍盒bbox其中8個子柵格當中，得到這個圖元在父節點當中的3個維度最大最小序列號 cellminx，cellminy，cellminz，cellmaxx，cellmaxy，cellmaxz

6)for iz from cellminz to cellmaxz

for iy from cellminy to cellmaxy

for ix from cellminx to cellmaxx

7)獲得子柵格序列號cellindex=ix+iy×2+iz×2;

8)if recursivecells［cellindex］equal null then

9)構造一個類型和根節點一樣的柵格對象recursivecell，把 objectsi分配到 recursivecell

10)else then

直接把objectsi分配到recursivecell

11)for each recursivecelli

if recursivecelli has reached saturate state then break;

else then繼續調用該函數;

3 動態柵格建立算法分析

算法1在實現動態柵格建立的過程當中采用函數遞歸的方法，必須考慮到算法效率和調用?？臻g開銷中尋求平衡.首先有以下假設:整個空間中圖形元組成的包圍盒是一個正方體，這個包圍盒中有N(8的冪次數)個三角形圖元;每個柵格的飽和狀態為容納一個三角形圖形元.

算法1消耗的時間主要由均勻柵格劃分時間、分配圖元時間組成.無論柵格大小、均勻柵格劃分時間Tgrid都是一樣的.分配圖元的時間與圖元的數量成正比，Tprimitive為分配單位圖元的時間.算法1中，最壞的情況就是每次柵格都分割為8個子柵格，用圖4中的遞歸樹分析可得，算法1在最壞情況下的消耗時間T為

式中:i表示在遞歸樹中的深度，根節點的深度為0.深度為i的子節點個數為8i，每個子節點中的圖元數目為n/8i-1.進一步可得到化簡式:

從式(3)可得算法1的時間復雜度為O(n)，與均勻柵格劃分方法的時間復雜度是一個數量級別的［14］.

圖4 算法1的遞歸樹Fig.4 Recursive tree of algorithm 1

為了驗證算法1的時間復雜度和均勻柵格劃分的時間復雜度一致，在Intel i5 CPU，2 GB內存的PC機上進行實驗，取4個不同大小的Stanford大學網站上的模型Bunny，其圖元數量大約為4k、10k、16k、69k，分別測量柵格結構的建立時間.測量結果如表1所示.從表1中可以看出，本文方法的運行時間略慢于均勻柵格法，由前文分析可得，該方法需要對每個柵格判斷是否處于飽和狀態，然而均勻柵格法是不需要這些判斷的.本文方法和均勻柵格法的運行時間增長趨勢是一致的，說明該方法在建立柵格結構的運行時間是合理的.

表1 不同模型下均勻柵格法和本文方法的建立時間Table 1 Building time of uniform grid and our method by different models

4 基于動態柵格法的光線遍歷

和均勻柵格光線遍歷方法一樣，每根光線只與它穿過的柵格內部圖元做相交運算［15］.這比沒有加速結構的時候能節省許多時間，特別是當場景中有大量物體的時候，光線只與其中一部分物體做相交運算.本文的光線遍歷方法也繼承了以上的優點，并對場景中存在較大空曠區域的情況進行了優化.

圖5 一條光線的動態柵格結構遍歷Fig.5 Dynamic grids struct traversal of a ray

圖5所表示的就是一條光線穿越本文提出的動態柵格結構的情景.斜杠標記的柵格即光線穿越的柵格，光線將根據柵格與視點距離進行求交運算，順序依次為(c，0)- ＞ (d，3)- ＞ (g，0)- ＞(h，2)- ＞(f，0).括號中的第1項為柵格編號，第2項為該柵格中的圖元編號.第2章節中已經提到，本文的柵格劃分方法就是基于柵格與視點的距離建立的.把這個順序對應到圖2中去，這個操作順序是非常方便的，柵格樹同一深度的子樹，操作順序一定是從左往右，不同深度的子樹，操作順序一定是從上往下，這在一定程度上增強了算法性能.

本文動態柵格結構光線遍歷方法關鍵在于如何沿著光線方向依次遍歷柵格，如圖5，即如何沿著(c，0)- ＞ (d，3)- ＞ (g，0)- ＞ (h，2)- ＞ (f，0)該路徑遍歷柵格.觀察到圖5的動態柵格結構是把根節點均勻劃分為a、b、c、d 4個柵格，然后再把b節點劃分為e、f、g、h 4個柵格.因此可以對根節點采用均勻柵格的光線遍歷方法，當檢測到節點b時，再一次采用均勻柵格的光線遍歷方法，即動態柵格結構光線遍歷方法就是一種均勻柵格結構光線遍歷方法的遞歸模式.

均勻柵格結構中為了沿著光線方向計算遍歷步進，采用以下比較巧妙的方法.即使光線和柵格邊的交點不是均勻的，如圖6(a)，但是在x方向和y方向上的交點是均勻的，如圖6(b)和圖6(c).這樣允許分別從x、y方向計算光線參數t，每個方向的光線參數t的步進為

圖6 每條光線的動態柵格結構遍歷Fig.6 Dynamic grids struct traversal of every ray

針對每個柵格，必須算出下一個光線經過的柵格，在二維柵格的情況下，通過x方向步進和通過y方向的步進得到的下一個柵格是不一樣的，圖7說明了這2種不同情況，黑色的正方形就是應該選擇的下一個柵格.在圖7中，假設光線剛進入初始柵格時，在x方向最小的光線參數為tminx，在y方向最小的光線參數為tminy，橫斜杠標記的柵格為當前進入的柵格，豎斜杠標記的柵格為下一個進入的柵格，計算txnext和tynext，它們分別為x方向和y方向的下一個光線經過柵格的光線參數.如果txnext＜tynext，就把x方向的下一個柵格作為光線下一個經過的柵格，反之把y方向的下一個柵格作為光線下一個經過的柵格.

圖7 決定下一個光線經過的柵格過程Fig.7 Process of next grid a ray pass through

本文的動態柵格光線遍歷方法也是基于以上方法，它決定下一個光線經過的柵格之后，必須還要判斷這柵格是否還有子柵格，如果有子柵格的話還需要重復上述過程，反之則檢測這個柵格和圖元的求交情況.算法2給出了本文光線遍歷算法，為了簡化算法描述，假設光線的起點位于空間所有物體的外面.

算法2 動態柵格光線遍歷

輸入:當前光線對象ray，光線參數tmin，當前父柵格的包圍盒bbox，光線圖元求交之后的信息hitrecord，柵格樹 recursivecells.

1)初始化光線進入空間柵格區域每個方向的柵格序號ix，iy，iz;每個方向的柵格光線參數步進dtx=(txmax-txmin)/nx，dty=(tymax-tymin)/ny，dtz=(tzmax-tzmin)/nz;

2)計算出每個方向下一個柵格的光線參數，每次步進的柵格個數，已經遍歷的最后的柵格序號.

算法2遞歸次數由某個空間區域的圖元數量決定，數量少的區域很快完成遞歸，數量多的區域會進行多次遞歸.

5 動態柵格法光線遍歷算法分析

與第3節分析動態柵格建立算法一樣，采取相同的假設:整個空間中圖形元組成的包圍盒是一個正方體，這個包圍盒中有N(8的冪次數)個三角形圖元;每個柵格的飽和狀態為容納一個三角形圖形元.

由算法2可知，光線遍歷算法消耗時間由2部分組成:確定初始化柵格具體序號的時間、光線與它經過的柵格檢測相交的時間.每條光線只需進行一次初始化柵格具體序號的確定，把這段時間定為Tinit，第2部分消耗時間則與空間內部具體圖元分布有關，每個柵格求交時間為Tintersect.考慮最壞情況，即空間的圖元是分布均勻的，那么空間動態柵格建立的子柵格也是均勻分布的，光線在這種情況下沿著對角線經過子柵格，并且光線到達最后一個子柵格才檢測到與圖元相交.對角線上的柵格數量也是與N有關，如圖4空間中物體包圍盒每個方向可以分成8log8N個柵格，那么物體包圍盒最長對角線的數量Nray可以由式(5)得到.那么在最壞情況下，每條光線的遍歷時間Ttraversal如式(6)所示.因此，本文算法計算復雜度為O((log8N)2/3).這個數量級和均勻網格遍歷方法是一樣的，但是在實際場景中，特別是針對空曠的場景性能是有明顯提升的.式(6)只是給出了本文算法的估計的一個運行數量級時間，與實際往往有比較大的偏差，主要原因在于Tintersect這個變量在每個柵格中并不是都是一樣的，可能在某些柵格它的飽和圖元數量為c1，其他柵格的飽和圖元數量為c2.這會影響光線與當前柵格的求交時間.

6 實驗及結果分析

在Intel i5 CPU，2GB內存的PC機上進行了實驗.實驗以如下方式進行:選擇若干典型模型，它們都處于由三角形圖元組成的地面.分別對這些場景用均勻柵格法和本文提出的動態柵格法進行光線追蹤，最后把這2種方法進行比較.

實驗實用的模型包括多個不同大小的Bunny、Horse、Fish、Hand，為了體現空間的空曠性，在它們的下方放著由三角形圖元組成的地面，圖8為使用本文方法光線追蹤繪制的模型圖.實驗一共分為2組，第1組使用均勻柵格方法并記錄運行時間和劃分的柵格數目.第2組使用本文提出的動態柵格光線追蹤方法并記錄相同的數據項目.表2給出了這些模型具體圖元數目，采用2種方法的柵格劃分數目以及這2種方法的運行時間.為了突出本文算法在空曠場景的作用，本次實驗的模型包括三角形圖元的地面，這樣更加凸顯出場景的空曠性.

圖8 用本文方法光線追蹤繪制的場景Fig.8 Scenes drawn by ray tracing through our method

實驗結果如表2所示，采用本文提出的動態柵格光線追蹤方法繪制場景確實提高了繪制速度.注意到Horse、Fish、Bunny4k的圖元個數雖然遠遠小于其余的模型，但是繪制時間還是比較長，這是由于放大了渲染模型.可以看到，本文方法所需要的柵格遠遠小于均勻柵格所需要的柵格，這從算法的初衷就可以猜測到:采用均勻柵格結構光線追蹤算法沒有對模型進行任何判斷，直接對場景按照式(1)進行均勻柵格劃分，然后本文算法是根據場景的疏密程度動態地進行柵格劃分，因此所需要的柵格會大大減少.表2中還可以看到不同圖元的Bunny隨著圖元數量的增加本文方法的運行時間并沒有減少，這和柵格劃分數有關，在圖元集中的區域柵格數量的增加是可以加速場景繪制速度的，從另一個角度說明本文算法隨著場景圖元疏密程度增加性能就越高.

表2 不同模型下均勻柵格法和本文方法繪制場景運行時間Table 2 Scene drawing time of uniform grid and our method by different models

7 結束語

對于光線追蹤繪制場景的加速均勻柵格結構，本文提出了一種新的動態柵格加速結構.與已有的方法相比，本文的方法對需要繪制的場景根據不同分布特征進行按需柵格劃分.在建立動態柵格加速結構的時候，不同深度從根節點到葉子節點，同一深度從左邊節點到右邊節點，都是隨著離視點的距離逐漸增大，這有利于光線的遍歷.實驗結果表明，本文方法在處理空曠場景的時候，優于同類的已有工作，本文的方法還能推廣到基于GPU光線追蹤加速結構上，這也是未來將擴展的工作.

［1］ANDREW S.An introduction to ray tracing［M］.London:Academic Press，1989:201-204.

［2］BENTLEY J L.Multidimensional binary search trees used for associative searching［J］.Communications of the ACM，1975，18(9):509-517.

［3］RUBIN S M，WHITTED T.A 3-dimensional representation for fast rendering of complex scenes［C］//Proceedings of the 7th Annual Conference on Computer Graphics and Interactive Techniques.New York，USA，1980:509-517.

［4］KIRILL G，SIMON P，ALEXANDER B，et al.Grid-based SAH BVH construction on a GPU［J］.The Visual Computer，2011，27(6/7/8):697-706.

［5］TANAKA T，IWATA K.Arts:accelerated ray-tracing system［J］.IEEE Computer Graphics and Applications，1986，6(4):16-26.

［6］童星，袁道華.基于GPU和均勻柵格法的光線追蹤算法研究［J］.計算機工程與設計，2011，32(10):3499-3502.

TONG Xing，YUAN Daohua.Research of ray-tracing algorithm based on GPU and uniform grid method［J］.Computer Engineering and Design，2011，32(10):3499-3502.

［7］GUNTURY S，NARAYANAN P J.Raytracing dynamic scenes on the GPU using grids［J］.IEEE Transactions on Visualization and Computer Graphics，2012，18(1):5-16.

［8］WALD I，IZE T，ANDREW K，et al.Ray tracing animated scenes using coherent grid traversal［C］//Proceedings of ACM SIGGRAPH.New York，USA，2006，485-493.

［9］SHIRLEY P，ASIKHMIN M，GLEICHER M，et al.Fundamentals of computer graphics［M］.2nd ed.Wellesley:AK Peters，2005:224-226.

［10］KALOJANOV J，BILLETER M，SLUSALLEK P.Two-level grids for ray tracing on GPUs［J］.Computer Graphics Forum，2011，30(2):307-314.

［11］KALOJANOV J，SLUSALLEK P.A parallel algorithm for construction of uniform grids［C］//Proceedings of the Conference on High Performance Graphics.New York，USA，2009:23-28.

［12］GARANZHA K，LOOP K.Fast ray sorting and breadthfirst packet traversal for GPU ray tracing［J］.Computer Graphics Forum，2010，29(2):289-298.

［13］PANTALEONI J，LUEBKE D.HLBVH:hierarchical LBVH construction for real-time ray tracing of dynamic geometry［C］//Proceedings of the Conference on High Performance Graphics.Switzerland，2010:87-95.

［14］VACLAV S.An efficient space partitioning method using binary maps［C］//Proceedings of the 11th International Conference on Telecommunications and Informatics.Wisconsin，USA，2012:121-124.

［15］PERROTTE L，SAUPIN G.Fast GPU perspective grid construction and triangle tracing for exhaustive ray tracing of highly coherent rays［J］.International Journal of High Performance Computing Applications，2012，26(3):192-202.