焦良葆， 陳 瑞， 張 健

（南京工程學(xué)院通信工程學(xué)院，江蘇 南京 211167）

作為在光線跟蹤廣泛使用的一種層次樹結(jié)構(gòu)，KD樹(K-Dimensional Tree)得到了諸多研究者的關(guān)注[1]。作為一種基于空間剖分的加速結(jié)構(gòu)，它采用軸對齊的分割面對場景空間進行剖分，遞歸地生成空間單元間的組織結(jié)構(gòu)。光線跟蹤算法中，當(dāng)光線穿越空間單元時，就借助空間單元間的這種組織關(guān)系，跨越空單元來直接找到包含物體的單元，并進行光線與物體的求交測試，然后計算光強進行場景渲染。算法中計算量最大的部分就是光線與物體的求交運算。為提高光線和物體的求交速度，除了KD樹外，常用的加速結(jié)構(gòu)還有 Grids（網(wǎng)格）和 BVH（Bounding Volume Hierarchies，層次包圍體）等[2-3]。文獻[4]對基于CPU的光線跟蹤算法的加速結(jié)構(gòu)進行比較，認為對于不同類型的測試場景平均而言，KD樹是最快的。同時由于光線跟蹤有著天然的并行性，為了利用基于 SIMD（Single Instruction Multiple Data，單指令多數(shù)據(jù)）計算平臺的GPU（Graphic Process Unit，圖形處理單元）協(xié)處理器在并行計算上的優(yōu)勢，將KD樹算法移植到GPU上已成為目前的研究熱點[5-6]。

KD樹算法包括創(chuàng)建和遍歷兩個過程。好的KD樹構(gòu)建方法能夠生成優(yōu)化的樹結(jié)構(gòu)，從而提高遍歷速度。傳統(tǒng)上KD樹的實現(xiàn)一般基于遞歸過程或者棧數(shù)據(jù)結(jié)構(gòu)，但 GPU缺少對遞歸過程的支持且堆棧存取效率低下。因此，F(xiàn)oley等人[5]提出了基于GPU的無棧遍歷算法KD-restart。算法中為省去堆棧結(jié)構(gòu)，每次遍歷都退回到根節(jié)點處重新開始，因此遍歷效率低下。斯坦福大學(xué)Daniel Reiter Horn等人[6]在此基礎(chǔ)上提出了short-stack遍歷算法，采用push-down結(jié)構(gòu)降低額外的節(jié)點訪問次數(shù)，效率高于 KD-restart，但仍然需要使用少量堆棧。

本文提出一種新的線索KD樹算法，在創(chuàng)建KD樹時加以線索化，保存葉節(jié)點的六個方向的后繼節(jié)點索引。在GPU上實現(xiàn)KD樹遍歷時，根據(jù)光線在當(dāng)前葉節(jié)點的穿出平面沿著線索直接得到后繼節(jié)點，避免了從根節(jié)點（或中間節(jié)點）到葉節(jié)點過程中的“遠”子節(jié)點壓棧操作；計算中利用高效紋理內(nèi)存操作替代低效的遞歸堆棧操作，不僅避免了棧的使用，而且遍歷時根據(jù)索引值能快速找到后繼節(jié)點，無需退回到根節(jié)點處，從而減少無效遍歷的次數(shù)，顯著地提高遍歷效率。

1 相關(guān)工作

傳統(tǒng)的KD樹的構(gòu)建和遍歷過程是對節(jié)點空間進行自上而下劃分和操作的遞歸過程。其中，在構(gòu)建KD樹時的初始輸入是整個場景的圖元集合T（通常采用三角片圖元）及空間V（通常采用AABB軸對稱綁定盒）；最佳分割平面P一般通過SAH(Surface Area Heuristic，表面積啟發(fā))[6]的方法計算得到。在光線跟蹤應(yīng)用中，通過 KD樹的遍歷進行光線與圖元的求交測試，輸出第一個與光線相交的圖元及交點。遍歷KD樹的初始輸入是光線ray、場景空間節(jié)點（即KD樹的根節(jié)點root）和光線在節(jié)點中的起止參數(shù)（tmin和tmax）。進行節(jié)點遍歷時，如果光線橫跨分割平面的兩側(cè)，說明該光線同時穿過該節(jié)點的兩個孩子節(jié)點 lchild/rchild，則先與第一個子節(jié)點求交（這個節(jié)點記為“近”節(jié)點 nearNode），并將第二個子節(jié)點壓入堆棧（這個以后可能會訪問到的節(jié)點記為“遠”節(jié)點farNode）；否則直接遍歷光線經(jīng)過的孩子節(jié)點。因此，光線遍歷KD樹時需從根節(jié)點開始，直到葉節(jié)點然后求交，是一個遞歸過程。

由于 GPU不支持遞歸操作，只有使用棧數(shù)據(jù)結(jié)構(gòu)來替代。在SIMD計算架構(gòu)的GPU中?？臻g必須使用全局存儲空間，訪問效率非常低，訪問時間接近于高效寄存器內(nèi)存的100倍，因此標準的KD樹遍歷算法不適合在SIMD計算架構(gòu)上運行?；诖?，研究人員提出了基于SIMD的KD樹遍歷改進算法。Foley[5]提出了一種無棧的遍歷算法kd-restart。在該算法中，光線總是訪問“近”節(jié)點而舍棄“遠”節(jié)點；當(dāng)光線在葉節(jié)點中沒有找到相交的圖元，則把光線的起點前移到葉節(jié)點的出口處（即tmax處），重新從根節(jié)點開始遍歷，直到找到與之相交的三角片或遍歷完整棵樹。算法的輸入是光線、根節(jié)點及光線在場景中的起止點參數(shù) sceneMin和 sceneMax。在kd-restart遍歷算法中，雖然避免了使用堆棧結(jié)構(gòu)，但算法中的每次遍歷，光線都是從根節(jié)點開始，直至找到葉子節(jié)點，大量重復(fù)查詢導(dǎo)致該算法的效率不高。Daniel Reiter Horn[6]等人在kd-restart算法和標準遍歷算法的基礎(chǔ)上，提出了short-stack算法；引入了push-down結(jié)構(gòu)，用于記錄從根節(jié)點下溯到葉子的過程中的分叉狀態(tài)，如未發(fā)生分叉（即光線未與分割平面相交），則根節(jié)點可以下壓。通過采用根節(jié)點下壓和固定大小的棧結(jié)構(gòu)，該算法相對于kd-restart顯著減少了無效回溯，相對于傳統(tǒng)的全棧遍歷顯著減小了棧結(jié)構(gòu)。

綜上所述，基于SIMD架構(gòu)的GPU實現(xiàn)KD樹的遍歷時，算法效率的關(guān)鍵在于減少堆棧結(jié)構(gòu)的使用，同時減少無效回溯。而之所以需使用棧結(jié)構(gòu)就在于需要保存并獲取光線穿越節(jié)點后所要到達的后繼空間節(jié)點，類似于二叉樹遍歷中的線索樹中的線索。

而在 KD樹的創(chuàng)建和遍歷算法的實現(xiàn)過程中，可以發(fā)現(xiàn)光線從某個葉節(jié)點穿過后，一定與相鄰的節(jié)點相交。由于KD樹中的分割面都是軸對齊的，每個子節(jié)點都是一個軸對齊的包圍盒，因此每個節(jié)點共有上、下、左、右、前、后六個面。在KD樹建立完成后，從任意一個面穿出后的后繼空間節(jié)點是確定的。這樣，就可以建立一個三維空間的線索KD樹，用來保存并獲取光線穿越節(jié)點后所要到達的后繼空間節(jié)點?；谶@樣的考慮，作者提出了一個新的線索KD樹算法。

2 線索KD樹

為了保存線索信息，在建立KD樹時，在節(jié)點信息中增加一個數(shù)據(jù)結(jié)構(gòu) nodebox，用來保存與每個葉子節(jié)點六個面相鄰的節(jié)點（此節(jié)點可能是葉節(jié)點，也有可能是中間節(jié)點），即為每個葉節(jié)點保存六個線索?？梢韵葘⒏赣H節(jié)點的線索值繼承給孩子節(jié)點，然后根據(jù)父親節(jié)點的分割方式修正孩子節(jié)點的兩個線索，即左孩子的右線索就是右孩子，如此類推。線索的繼承和更新過程可采用二維圖解，如圖1所示。

圖1 節(jié)點二維結(jié)構(gòu)和層次關(guān)系

圖1中，以節(jié)點8為例來說明子節(jié)點如何繼承父節(jié)點的nodebox并進行更新的。根節(jié)點1的nodebox={-1，-1，-1，-1}，其分割平面垂直于X軸，子節(jié)點2和3首先繼承了根節(jié)點1的nodebox，然后在X軸方向上更新子節(jié)點2和3的nodebox。節(jié)點2的nodebox更新為{-1，3，-1，-1}，節(jié)點3的nodebox更新為{2，-1，-1，-1}。此時，將節(jié)點3壓入棧中。繼續(xù)對節(jié)點2進行分割，其分割平面垂直于Y軸，分為4和5兩個子節(jié)點。節(jié)點4繼承節(jié)點2的nodebox，并更新為{-1，3，-1，5}；節(jié)點5也繼承了節(jié)點2的nodebox，并更新為{-1，3，4，-1}。然后，將節(jié)點 5壓棧，繼續(xù)對節(jié)點4進行分割，其分割平面垂直于Y軸，得到子節(jié)點8和9。節(jié)點8的nodebox先繼承節(jié)點4的nodebox{-1，3，-1，5}，然后更新為{-1，3，-1，9}，節(jié)點 9的 nodebox也繼承節(jié)點 4的nodebox，并更新為{-1，3，8，5}。

光線跟蹤中，遍歷時如果光線經(jīng)過了某個葉節(jié)點且和此葉節(jié)點中的圖元無交點，可根據(jù)光線的穿出平面及該面的線索值得到下一個需遍歷的節(jié)點。由于建樹時線索的獲得采用了繼承的方式，因此此節(jié)點與KD樹標準遍歷算法中的棧頂節(jié)點完全相同。

現(xiàn)在的關(guān)鍵就是需得到穿出平面，而穿出平面的實質(zhì)就是最近一次導(dǎo)致分叉狀態(tài)的分割平面。由于每個節(jié)點有六個穿出平面，可用一個三比特的索引值來表示。因此，作者定義了一個長整型變量SplitStack來保存每次分叉狀態(tài)所導(dǎo)致的分割平面，最低三個比特就是最近一次分割平面。這樣當(dāng)光線在KD樹中遍歷時，如光線橫跨當(dāng)前節(jié)點的分割面，就不再需要將“遠”子節(jié)點和 t_split，t_max壓入堆棧，只需要將分割平面更新存入SplitStack變量即可。

下面詳細介紹索引 KD樹的創(chuàng)建和遍歷算法。

2.1 線索KD樹的建立

線索KD樹與普通KD樹相比，為葉節(jié)點增加了一個用于記錄與該葉節(jié)點的六個穿出平面線索的數(shù)組 nodebox。nodebox中的元素類型為int clue[6]。線索KD樹的創(chuàng)建過程也是一個自頂向下的遞歸的過程，在 CPU上實現(xiàn)的具體算法見圖2左。

2.2 線索KD樹的遍歷

標準遍歷算法中的棧操作不適合在 GPU上運行，因為棧操作會大幅度地降低 GPU的并行效率，作者線索操作代替棧操作，從而提高GPU的并行效率。在剔除了標準遍歷算法中大幅降低GPU并行效率的棧操作，使用線索操作來替代的基礎(chǔ)上，作者得到了基于GPU的線索KD樹的遍歷算法，具體遍歷算法參見圖2右。

圖2 線索KD樹的構(gòu)建(左)和遍歷(右)算法

3 算法的實現(xiàn)及實驗結(jié)果分析

實驗的硬件環(huán)境是：CPU為Intel CoreTM2，1.86GHz；GPU為NVIDIA Geforce 260 GTX。實驗場景包括Cornel box、Robots和Kitchen三個典型場景。原始的場景數(shù)據(jù)來源于BART項目，主要由AFF格式的場景描述文件和ppm格式的紋理圖片文件組成。這些文件，由主文件kitchen.aff通過i(include)命令，逐級包含，形成對于場景的整體描述[10]。渲染結(jié)果如圖3所示。

作者將線索KD樹算法與Foley和Horn等人提出的算法進行了比較，各算法的效率比較如表1，push-down、kd-restart和short-stack算法的效率來自文獻[6]。從表1中可以看出，為節(jié)點增加了索引后，能大幅度提高算法的效率。例如，kitchen場景中，采用push-down算法、kd-restart算法及short-stack算法，每秒計算的光線數(shù)為分別為 21.4×106、17.1×106和 27.3×106，而索引 KD樹算法每秒計算的光線數(shù)為 139.8×106，分別提高了6.5、8.1和5.1倍；對于Robots場景，索引KD樹算法的效率比這三種算法又分別提高了3.1、4.2和2.5倍。

圖3 線索KD樹重建和光線跟蹤的實驗場景

表1 算法效率比較

4 結(jié)束語

本文在Foley，Daniel Reiter Horn等人提出的KD樹算法的基礎(chǔ)上，通過對各種KD樹遍歷算法的分析，提出了基于索引值的KD樹算法，不僅省去了堆棧的使用，而且遍歷算法更高效。通過對Kitchen和Robots兩個場景的渲染結(jié)果比較，作者的算法每秒計算的光線數(shù)比 push-down算法提高了3～6倍，比kd-restart算法提高了4～8倍，比short-stack算法提高了3～5倍。

目前，KD樹的創(chuàng)建工作還是在 CPU上完成，然后將數(shù)據(jù)結(jié)構(gòu)導(dǎo)入 GPU中。為了能將實現(xiàn)動態(tài)場景的光線跟蹤，需要將KD樹的創(chuàng)建速度和遍歷速度進一步提高。作者下一步的工作是將KD樹的創(chuàng)建移植到GPU上執(zhí)行，進而實現(xiàn)動態(tài)場景的光線跟蹤算法。

[1]Artur L dos Santos, et al. KD-Tree traversal implementations for ray tracing on massive multiprocessors: a comparative Study [C]//21st International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2009,2009: 41-48.

[2]Wald I, Boulos S, Shirley P. Ray tracing deformable scenes using dynamic bounding volume hierarchies [J].ACM Transactions on Graphics, 2007, 26(1): 1-18.

[3]李 靜, 吳恩華. 基于空盒自適應(yīng)生成的動態(tài)場景光線跟蹤計算[J]. 計算機學(xué)報, 2009, (6):1172-1182.

[4]Wald I, Ize T, Kensler A, et al. Ray tracing animated scenes using coherent grid traversal [J]. ACM Transactions on Graphics, 2006, 25(3): 485-493.

[5]Foley T, Sugerman J. KD-tree acceleration structures,for a GPU ray tracer [C]//SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hardware:Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware. New York: ACM Press, 2005: 15-22.

[6]Daniel Reiter Horn, Jeremy Sugerman, Mike Houston,et al. Interactive k-d tree GPU raytracing [C]//Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games. 2007, Seattle, Washington, 2007:167-174.

[7]BART: A benchmark for animated ray tracing [EB/OL].http://www.ce.chalmers.se/research/group/graphics/BART/