用于光線跟蹤的高并行度表面積啟發(fā)式（SAH）KD樹構建

李建鋒 譚耀華 廖勝輝

摘 要：提出一種用于光線跟蹤的SAHKD樹構建方法，解決當前KD樹并行算法并行度不高且效率低的問題.算法首先對所有圖元包圍盒在三個維度按坐標軸左值排序，得到三維上有序的包圍盒索引.然后使用層次遍歷構建KD樹，根據(jù)每個節(jié)點包圍盒選擇要劃分的維度，并在當前層生成所有節(jié)點在該維度下的候選劃分點序列.最后計算每個節(jié)點的空間樹，在GPU中計算每個候選點的SAH值，選擇每個節(jié)點的最小SAH值點進行劃分.實驗中采用4個常用場景進行測試算法性能，并同時比較了當前高效串行與并行算法，結(jié)果證明本文提出的算法在生成同等質(zhì)量KD樹的情況下達到對比串行方法4～6倍以及對比并行方法的1.3～1.5倍的計算速度，并且能在線程數(shù)成倍增加時達到相近倍數(shù)的加速比.

關鍵詞：SAHKD樹；空間樹；并行計算

中圖分類號：TP309.7 文獻標志碼：A

Abstract：This paper proposed a SAHKD tree construction method for ray tracing to solve the problem of low parallel degree and low efficiency in the existing algorithms. The algorithm first obtains the ordered index on the three latitudes by sorting the primitive bounding boxes according to the left value. Then， according to the node bounding box， we choose the dimension to be divided and generate the candidate partition points of each node under this dimension. Finally， the SAH value of each candidate point was calculated based on the spatial tree in GPU， and the minimum SAH value of each node was selected for partitioning. Four common scenarios were used for testing performance of the algorithm， and compared the efficient serial and parallel GPU algorithm. The results show that the proposed algorithm can achieve 4～6 and 1.3～1.5 times faster than the contrast method when generating the same quality KD tree. When the number of GPU cores fold increases， the speedup ratio reaches a near multiple.

Key words：SAHKDtree； space tree； parallel computing

K維樹（KD樹）是一類二進制分割樹，作為加速結(jié)構廣泛地應用于圖形與查詢領域，如光線跟蹤中圖元與光線的相交檢測[1-2]和最近鄰查詢等.為了高效遍歷KD樹，通常在構建時使用表面積啟發(fā)式劃分法（SAH），通過最小化每個節(jié)點的期望遍歷成本選擇劃分點.如何快速高效地構造SAHKD樹一直是研究重點，主要研究方向集中在兩種方法上.

一是串行構造方法，最簡單的思路是通過全遍歷計算SAHKD樹所有劃分點的SAH值，其計算復雜度為O（N2），由于計算復雜度較高，使得該方法無法應用于大場景.針對該問題，文獻[3]和[4]提出將劃分點進行預排序，通過迭代的方法依次求出每個劃分點的SAH值，把每個節(jié)點的時間復雜度降低到O（NlogN），從而使得整棵樹的構建復雜度降低至O（Nlog2N）.Wald和HaVRan在文獻[3]和文獻[5]的基礎上，提出只在根節(jié)點排序，非根節(jié)點通過遍歷其父節(jié)點序列得到有序序列，使得整棵樹的構建復雜度降低至O（NlogN）[5]，此時已經(jīng)達到了SAHKD樹串行構建的理論下限.文獻[6]提出一種自調(diào)整參數(shù)的通用方法，通過隨機搜索來得到滿足條件的劃分點.該方法雖然可以提高構造速度，但無法得到穩(wěn)定的結(jié)果.

二是并行化構建方法， 文獻[7]和[8]提出在上層大節(jié)點通過一個高性能線程計算，直到每個節(jié)點計算量足夠小，才將它們分配到多核系統(tǒng)中的構造.具體實踐中，在4核CPU系統(tǒng)中能達到單核構造2.5倍的速度[9].Shevtsov等[10]通過并行方法計算中位圖元取代SAH的計算來尋找上層的大節(jié)點的劃分點，雖然在遍歷性能較SAH方法有15%的退化，但該方法應用在Larrabee[11]的4路并行光線追蹤器時達到3.9倍的構造與遍歷的總性能.文獻[12]先把圖元進行層次分組，之后按組并行構建SAHKD樹，在層次分明的場景中，12線程下性能最好時達到文獻[4]中算法的130倍.該方法雖然平分了各個線程的計算量，但對于層次不明確的場景無法達到理想效果.自從CUDA與OPENCL等并行架構提出來后，GPU上SAHKD樹的構建得到了更多的研究與改進，Kun Zhou[13]提出在大節(jié)點直接使用圖元的中點劃分，對于小節(jié)點則進行多路GPU構建.該方法在128線程上達到了單核構建的6～15倍性能，在252K個三角形的場景下達到了16線程的3～6倍.該方法雖然通過頂層退化提高了SAHKD樹的構建效率，但在超大型場景遍歷時有不同程度的性能損失.文獻[14]在前者的基礎上加入了CUDA自帶的reduction和原子操作，在實際應用中構建效率得到了部分提升，但依然存在頂層退化的問題.

2 并行SAHKD樹構造

并行化SAHKD樹的構造，現(xiàn)有的并行方式都是基于單個節(jié)點，每個線程串行處理一個節(jié)點，并單獨使用一個線程進行同步.由于上層節(jié)點的巨大計算量，通常會使用大小節(jié)點的方式分別計算：對于大節(jié)點，使用一種退化的方式劃分，比如空間中點劃分以及圖元中點劃分等，對于小結(jié)點，則通過上述高效的串行方法.理想的并行方法需要基于候選劃分點，這樣可以實現(xiàn)較高的并行度和每個線程極低的負載.

為了設計一棵基于候選劃分點并行的SAHKD樹，必須解決兩個問題.第一是合理的同步機制.由于SAH值和空間樹的計算分別位于GPU和CPU中，因此計算前后的同步工作變得尤為重要.高效的同步方案應該減少空間分配以及內(nèi)存與顯存間互相拷貝的次數(shù).第二是每個線程使用高效的線面相交檢測的方法，由于GPU單核性能并不突出，如果直接使用暴力算法，在大場景中效率會十分低下，從而影響整體的構造性能.

本文提出的方法大致思想如下：首先生成一層每個節(jié)點在三個維度上圖元包圍盒的有序索引，然后根據(jù)每個節(jié)點包圍盒選擇一個維度進行劃分，生成每個節(jié)點在該維度下候選劃分點序列，最后一次性在GPU中并行計算一層每個劃分點的SAH值，并選擇每個節(jié)點最優(yōu)的SAH值的點進行劃分.

2.1 算法步驟

本文方法的算法步驟如下.

1）預處理：在SAHKD樹的構建之前，對根節(jié)點圖元進行預處理，其中包括在CPU中計算圖元和根節(jié)點的AABB包圍盒，之后在三個維度按包圍盒左值的升序排列所有圖元包圍盒.

2）按層次遞歸構建KD樹，對于該層的每個節(jié)點：

（a）數(shù)據(jù)準備：在CPU中根據(jù)節(jié)點包圍盒選擇劃分的維度，生成該維度下的候選劃分點序列和空間樹，并傳入GPU.

（b）計算SAH值：在GPU中利用空間樹并行計算出每個劃分點的SAH值并傳回內(nèi)存.

（c）圖元指派：在CPU中選出最小SAH值對應的劃分點，生成兩個新節(jié)點，在三個維度將圖元劃入對應的節(jié)點中，得到新節(jié)點的有序圖元包圍盒.

2.2 計算候選劃分點的SAH值

計算候選劃分點的SAH值主要是為每個節(jié)點選出最優(yōu)劃分點.由于KD樹每次只選擇一個維度進行劃分，所以第一步是找出要進行劃分的維度.為了簡便計算，通常對當前節(jié)點包圍盒進行分析，選擇包圍盒最長的維度作為要劃分的維度.

計算SAH值時需要統(tǒng)計劃分點左右兩側(cè)圖元數(shù)量，本文算法通過空間樹來加速這一過程.空間樹通過有序圖元包圍盒構造：有序序列可以看成一棵平衡二叉樹，而空間樹是對平衡二叉樹加入一個副值來二次判斷.以劃分X軸為例，包圍盒有兩個坐標值Xleft和Xright，用來代表包圍盒左右兩端，此時加入一個輔助值T，其定義為：

1）如果該節(jié)點是葉節(jié)點，T定義為Xright；

2）如果該節(jié)點是非葉節(jié)點，T定義為兩個子節(jié)點的T值與自己Xright的最大值.

很顯然T值需要后序自底向上遍歷，使用有序序列轉(zhuǎn)換為平衡二叉樹的算法實現(xiàn)T值的計算.為了節(jié)省函數(shù)調(diào)用的開銷，本文使用非遞歸的方式實現(xiàn).計算出空間樹后，每個候選劃分點都需要遍歷相應節(jié)點的空間樹求出其SAH值，主要復雜度在計算NL、NR和NP上，其中NL，NR，NP分別為位于候選劃分點左，右以及被候選劃分點穿過的圖元數(shù).過程中對于坐標為pos的候選劃分點有：

1）如果當前節(jié)點的T值小于pos，則從left到當前節(jié)點都在劃分點的左邊，將NL加上當前區(qū)間圖元的個數(shù)，并計算其右子節(jié)點.

2）如果當前節(jié)點的Xleft大于pos，則位于該節(jié)點右邊的節(jié)點都在劃分點的右邊，將NR置為當前節(jié)點序號，并計算其左子節(jié)點.

3）否則，判斷當前節(jié)點的圖元包圍盒與pos的位置關系，相應地修改NL和NP，并遍歷其左右子節(jié)點.

4）得到NL，NR，NP后計算出SAH值.

上述空間樹的遍歷方法需要使用輔助棧，然而如果每個線程都使用輔助內(nèi)存，在大場景下無法正常進行計算.在實際操作中可以使用二叉搜索樹的思想進行改造，在構造空間樹時得到節(jié)點遍歷的順序并設立一個狀態(tài)標識，不但可以節(jié)省顯存開銷，同時使各個線程計算更加高效.

2.3 圖元指派

2.4 復雜度分析

本文方法的特點一是按層級同時計算每一層節(jié)點的最優(yōu)劃分點.按層級計算可以使分配內(nèi)存的次數(shù)以及GPU與CPU的交互次數(shù)只與層數(shù)有關，并且可以使用連續(xù)內(nèi)存空間保存全部需要計算的圖元，而不需要使用隊列的輔助.在進行同步操作時，只需要在每個維度遍歷一次上層節(jié)點就能得到下層節(jié)點的有序候選序列，避免了多次遍歷.二是使用基于空間樹的快速計數(shù)方法，使每個線程可以根據(jù)快速計算出劃分點對應的NL、NR和NP，其計算復雜度和劃分點穿過的圖元數(shù)有關，考慮實際場景這個值總是遠遠小于總的圖元數(shù)，使得計算速度大大提高.

本節(jié)對本文提出方法的復雜度從三個方面進行分析：

1）KD樹構造前，需要先對圖元包圍盒在三個維度進行排序，其復雜度是O（NlogN）.

2）在KD樹構造期間，對于每一個非根節(jié)點，CPU端首先需要構造出三個維度的有序圖元包圍盒和節(jié)點包圍盒.節(jié)點包圍盒可以根據(jù)最優(yōu)劃分點在O（1）的時間得出，將圖元順序指派至新的節(jié)點中，需要在三個維度上遍歷所有圖元包圍盒序列一次，復雜度為O（N）.得出有序的圖元包圍盒后，層次遞歸每個節(jié)點的圖元包圍盒序列構造該節(jié)點的空間樹，每一層總的復雜度為O（N）.在GPU端，根據(jù)空間樹的特性，它需要搜索每個區(qū)間，如果區(qū)間內(nèi)所有圖元都在劃分點的同一側(cè)，則停止搜索這個區(qū)間.所以只有該區(qū)間包括了被劃分點穿過的圖元包圍盒時，空間樹才會在該區(qū)間的二分子區(qū)間中去搜索.又因為樹的層高不會超過（logN），于是每次計算SAH值的復雜度最壞情況下不會超過O（NP+logN）.其中NP是該劃分點穿過的圖元數(shù)，正常場景中無論NP還是logN都是遠遠小于N的值.

3）整體分析：整體結(jié)合來看，每一層復雜度為O（N+NP+logN），而樹的高度為（logN），因此該構造方法復雜度仍為O（NlogN）.由于CPU端的任務主要是指派圖元與空間樹構建，而不涉及任何浮點數(shù)計算，所以計算效率很高.處理中排序?qū)λ惴ㄐ阅苡绊懞艽螅紤]到真實場景中一般都會有一個初始狀態(tài)，我們可以基于該狀態(tài)下提前離線進行預排序，從而節(jié)省初始的排序計算量.

3 實驗結(jié)果及討論

為了驗證方法的有效性，我們使用統(tǒng)一計算設備架構（Compute Unified Device Architecture：CUDA）框架實現(xiàn)本文提出的算法.算法運行平臺為：四核八線程INTEL酷睿E3處理器，GPU型號為GTX750Ti.測試數(shù)據(jù)為Toys、 Bunny 、Dragon 、buddha四個常用的場景，這些場景包含的圖元的數(shù)從11 k到1 M不等.在最多64線程下本文算法與3種算法進行比較，分別是Wald提出的串行算法[2]、文獻[14]算法，以及不使用空間樹的本文算法（樸素GPU算法）做對比，算法時間（并行算法64線程）比較如表1所示.

表1結(jié)果表明，本文算法的構造時間在各個場景都優(yōu)于其他算法，其主要原因是：本文算法是對圖元包圍盒進行排序，而不是候選點，使得需要排序的序列長度從2N減少到了N，在計算上又通過圖元級并行處理，雖然算法均攤下來不如 Wald方法中O（1）簡單，但從每個計算核心來看本文算法復雜度為O（NP+logN）優(yōu)于Wald方法的O（N）.樸素GPU算法雖然不需要進行預排序，但每個線程都需要對當前所有圖元進行相交測試，時間復雜度為O（N），復雜度也遠高于本文算法，對比于Wald方法，二者復雜度雖然相近，但由于GPU單核心計算能力較低，所以速度較慢.文獻[14]中算法雖然是退化的SAHKD樹，但在實際場景中依然慢于本文算法，這歸根于單節(jié)點運算的低并行度.此外，每次劃分求出的SAH值是KD樹性能的重要指標，但由于后三種方法都是通過尋找最優(yōu)候選劃分點，所以求出來的SAH值都差不多，并不存在遍歷性能上的差別.

在具體的場景中，場景Toys的處理結(jié)果表明，在小場景下，本文算法與高效的串行算法差距并不大，主要原因是本文算法中指派圖元是在CPU中完成，而少量的浮點數(shù)計算不會明顯影響串行算法的計算時間.樸素GPU算法不需要最開始的預排序，且在小場景下空間樹的效果并不明顯，最終兩者的結(jié)果相近.

其他三個場景中隨著圖元數(shù)量的增加，本文算法達到4～6倍于串行算法的時間效率，且隨著圖元數(shù)變大穩(wěn)步增加.串行算法在每層構建時通常需要O（N）級別的浮點數(shù)計算，當數(shù)據(jù)量大時計算量遠超過條件判斷并且越來越明顯.空間樹的效果也在大場景中體現(xiàn)出來，對比于樸素GPU算法，由于條件判斷較多消耗了大量線程的計算能力，而空間樹可以大大降低這一過程，代價僅需在CPU端對有序的圖元進行一次遍歷.

構建SAHKD樹過程中，隨著層次的加深，每個節(jié)點所包含的圖元數(shù)越少，但遍歷時需要更多的相交測試才能達到葉節(jié)點，為了平衡這一現(xiàn)象，在實際應用中都會制定相應的早停策略.圖1列出buddha場景下SAHKD樹計算1～7層時，通過公式（7）計算得到的算法時間效率（文獻[14]的算法在上層使用中位圖元劃分，不適用于這類分析）.

4 總 結(jié)

本文提出了一種使用CPU和GPU并行構造一棵基于層次的SAHKD樹，解決了當前SAHKD樹并行度較低和需要區(qū)分大小節(jié)點的問題.由于KD樹的構建是一個靜態(tài)過程，本文所有測試都是在靜態(tài)場景中進行.但是真實場景許多是動態(tài)的，以往研究者通常是對靜態(tài)場景進行重復計算來模擬動態(tài)場景.我們接下來的研究方向是如何在動態(tài)場景中快速生成SAHKD樹，基于本文算法在預排序階段進行相關的優(yōu)化，期望達到實時光線跟蹤的效果.

參考文獻

[1] HUSSAIN S， GRAHN H. Fast kdtree construction for 3Drendering algorithms like ray tracing[C]//Lecture Notes in Computer Science. Berlin： Springer， 2004，4842：681-690.

[2] WALD I. Realtime ray tracing and interactive global illumination[J]. Information Technology，2004，48 （4）：242-245.

[3] MACDONALD J D， BOOTH K S. Heuristics for raytracing using space subdivision[J]. Visual Computer， 1990，6 （3）：153-165.

[4] SZECSI L. An effective implementation of the kdtree[M]. Rockland： Charles River Media Inc，2003：315-326.

[5] WALD I， HAVRAN V. On building fast kdtrees for ray tracing and ondoing that in O（NlogN）[C]//Symposium on Interactive Ray Tracing 2006（RT）.Salt Lake City：IEEE，2006 ：61-69.

[6] TILLMANN M， PFAFFE P， CKAAG W F.Onlineauto tuning of parallel SAH kdtrees[C]//International Parallel and Distributed Processing Symposium（2016）.Chicago：IEEE，2016：628-637.

[7] LEE J， SHIN Y.Realtime ray tracing on coarsegrained reconfigurable processor[J].International Conference on Fieldprogrammable Technology，2014， 149 （3）：192-197.

[8] POPOV S， GUNTHER J. HP seidel.experiences with streaming construction of SAH kdtrees[C]//Symposium on Interactive Ray Tracing （2006）.Salt Lake City：IEEE，2006：89-94.

[9] HUNT W，MARK W R，STOLL G.Fast kdtree construction with an adaptive errorbounded heuristic[C]//Symposium on Interactive Ray Tracing （2006）.Salt Lake City：IEEE，2006：81-88.

[10]SHEVTSOV M， SOUPIKOV A， KAPUSTIAN A. Highly parallel fast kdtree construction for interactive ray tracing of dynamic scenes[J].Computer Graphics Forum， 2007，26 （3）：395-404.

[11]SPJUT J， BOULOS S， KOPTA D. A multithreaded architecture for realtime ray tracing[J].Symposium on Application Specific Processors，2008，28 （12） ：108-114.

[12]KANG Y S， NAH J H， PARK W C. gkDtree： A groupbased parallel update kdtree for interactive ray tracing[J].Journal of Systems Architecture the Euromicro Journal ， 2013，59 （3）：166-175.

[13]ZHOU K， HOU Q， WANG R.Realtime kdtree construction on graphics hardware[J].Acm Transactions on Graphics，2008，27 （5）：1-11.

[14]CHANGH B，SEOH W，IHM I. On the efficient Implementation of a realtime kdtree construction algorithm[M].Singapore： Springer，2015：207-219.

[15]MACDONALD J D， BOOTH K S.Heuristics for raytracing using space subdivision[J].Visual Computer，1990，6 （3）：153-166.

[16]SANTAL L A.Integral geometry and geometric probability[M]. London： AddisonWesley Pub Co，1976 ：91-113.