一個新的線索KD樹并行算法

焦良葆， 陳 瑞， 張 健

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 線索KD樹

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

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

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

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

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

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

2.1 線索KD樹的建立

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

2.2 線索KD樹的遍歷

標(biāo)準(zhǔn)遍歷算法中的棧操作不適合在 GPU上運(yùn)行，因?yàn)闂２僮鲿蠓鹊亟档?GPU的并行效率，作者線索操作代替棧操作，從而提高GPU的并行效率。在剔除了標(biāo)準(zhǔn)遍歷算法中大幅降低GPU并行效率的棧操作，使用線索操作來替代的基礎(chǔ)上，作者得到了基于GPU的線索KD樹的遍歷算法，具體遍歷算法參見圖2右。

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

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

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

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

圖3 線索KD樹重建和光線跟蹤的實(shí)驗(yàn)場景

表1 算法效率比較

4 結(jié)束語

本文在Foley，Daniel Reiter Horn等人提出的KD樹算法的基礎(chǔ)上，通過對各種KD樹遍歷算法的分析，提出了基于索引值的KD樹算法，不僅省去了堆棧的使用，而且遍歷算法更高效。通過對Kitchen和Robots兩個場景的渲染結(jié)果比較，作者的算法每秒計(jì)算的光線數(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中。為了能將實(shí)現(xiàn)動態(tài)場景的光線跟蹤，需要將KD樹的創(chuàng)建速度和遍歷速度進(jìn)一步提高。作者下一步的工作是將KD樹的創(chuàng)建移植到GPU上執(zhí)行，進(jìn)而實(shí)現(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ì)算[J]. 計(jì)算機(jī)學(xué)報(bào), 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/