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

焦良葆， 陳 瑞， 張 健

（南京工程學院通信工程學院，江蘇 南京 211167）

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

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

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

1 相關工作

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

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

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

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

2 線索KD樹

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

圖1 節點二維結構和層次關系

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

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

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

下面詳細介紹索引 KD樹的創建和遍歷算法。

2.1 線索KD樹的建立

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

2.2 線索KD樹的遍歷

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

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

3 算法的實現及實驗結果分析

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

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

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

表1 算法效率比較

4 結束語

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

目前，KD樹的創建工作還是在 CPU上完成，然后將數據結構導入 GPU中。為了能將實現動態場景的光線跟蹤，需要將KD樹的創建速度和遍歷速度進一步提高。作者下一步的工作是將KD樹的創建移植到GPU上執行，進而實現動態場景的光線跟蹤算法。

[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]李 靜, 吳恩華. 基于空盒自適應生成的動態場景光線跟蹤計算[J]. 計算機學報, 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/