基于加速結構和CUDA的光線追蹤算法和技術研究

王 平,李益文，喬 磊,姚立民,陳立海

(1．河北石油職業技術大學 1a.儀器儀表中心;1b.熱能工程系，河北 承德 067000；2.空軍工程大學 等離子體動力學重點實驗室，陜西 西安 710038；3．承德摩隱信息科技有限公司 應用開發部，河北 承德 067000)

自然界萬事萬物都是并發的，按照其內在時間序列運行著。真實世界是高度并行的，和串行計算相比，并行計算更適用于對現實世界中的復雜現象進行建模、模擬和理解。

目前，并行計算特別是基于GPU的并行計算在很多效率問題的解決上起到了重要的作用，特別是涉及浮點運算的算法上[1-2]。另一方面，加速結構對減少射線追蹤過程中相交判斷有著非常好的效果[3-5]。在進行射線追蹤相關仿真計算時，由于所產生的射線數量巨大，導致計算量非常龐大。開展基于GPU的射線追蹤并行算法的研究，并對多種加速結構在GPU下數據傳遞方法和應用場景進行研究具有重要價值！

1 并行計算及CUDA技術

并行計算是相對串行計算的，簡單來說就是同時使用多個計算資源來解決一個計算問題。并行計算的問題或算法具有離散化、可并行執行、需進行集中調度等特點。

并行計算模型是作為硬件和內存架構之上的一種抽象存在，這些模型并不和特定的機器和內存架構有關。常見的并行編程模型[6]包括：共享內存模型、線程模型、分布式內存/消息傳遞模型、數據并行模型、混合模型、單程序多數據模型、多程序多數據模型。

常見編程模型[7-12]包括OpenMP、MPI、CUDA、OpenCL、C++ AMP等。這些編程模型在程序邏輯方面相似，也有一定區別。因為CUDA與OpenCL更接近硬件底層，所以前兩者的性能更好，然而C++ AMP的易編程性卻要優于CUDA和OpenCL。

在 CUDA 的架構下，一個程序分為兩個部份：Host端和 Device 端。Host 端是指在 CPU 上執行的部份，而 Device端則是在顯示芯片上執行的部份。Device 端的程序又稱為 “Kernel”核函數。通常Host端程序會將數據準備好后，復制到顯卡的內存中，再由顯示芯片執行 Device端程序，完成后再由 Host端程序將結果由顯存中取回。為了讓GPU有可用的編程環境，從而能通過程序控制底層的硬件進行計算,CUDA提供Host-Device的編程模式以及非常多的接口函數和科學計算庫，通過同時執行大量的線程而達到并行的目的。

2 常用加速結構

光線追蹤涉及到大量計算，通過空間劃分數據結構來實現加速是一種比較常用的手段。

1)四叉樹索引的基本思想是將地理空間遞歸劃分為不同層次的樹結構。它將已知范圍的空間等分成四個相等的子空間，如此遞歸下去，直至樹的層次達到一定深度或者滿足某種要求后停止分割。四叉樹的結構在空間數據對象分布比較均勻時，具有比較高的空間數據插入和查詢效率(復雜度O(logN))。八叉樹的結構和四叉樹基本類似，其擁有8個節點。

2)KD-Tree是一棵二叉樹，其每個節點都代表一個k維坐標點；樹的每層都是對應一個劃分維度；樹的每個節點代表一個超平面，該超平面垂直于當前劃分維度的坐標軸，并在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹;即若當前節點的劃分維度為i，其左子樹上所有點在i維的值均小于當前值，右子樹上所有點在i維的值均大于等于當前值，本定義對其任意子節點均成立。

3)層次包圍盒(BVH)與前幾種方法最顯著的區別就是，不再以空間作為劃分依據，而是從對象的角度考慮，過程如下：第一步同樣找出場景的整體包圍盒作為根節點；第二步找到合適的劃分點，將最大包圍盒內的三角形面分為兩部分，再分別重新計算新的包圍盒；包圍盒會重疊，但一個三角形面只會被存儲在唯一的包圍盒內，而這也就解決了KD-Tree的缺點。接下來與KD-Tree的建立類似，遞歸對所有子空間重復該步驟。

4)基于表面積的啟發式評估劃分方法：在KD樹、BVH的構建過程中采用了中點劃分和等量劃分兩種方式對圖元進行劃分。當圖元分布不均勻的時候，劃分結果會變得很差。基于表面積的啟發式評估劃分方法(Surface Area Heuristic，SAH)[13]通過對求交代價和遍歷代價進行評估，給出了每一種劃分的代價，而KD樹等構建過程便是尋找代價最小的劃分。

3 算法程序設計與驗證

3.1 程序總體設計

程序設計分為兩個大的部分，其中第一部分是通過WinForm框架，結合C#語言開發的帶界面的前端程序；第二部分是使用C++語言結合CUDA開發的射線生成程序，以及光線與三角面片進行相交判斷的內核程序(見圖1)。兩者之間通過約定格式的文件來實現數據傳遞。

3.2 無加速結構CUDA設計關鍵點

CUDA程序設計有兩個核心點，一個是如何有效的將數據從CPU向GPU傳遞，并且能夠正常高效的供CPU的內核使用；另外就是如何將程序并行化分配到每一個內核上。

1)CPU數據向GPU數據的傳遞：由于GPU中無法使用map之類的泛型結構，因此需要以數組等方式來組織好數據，并通過cudaMemcpy將內存中的信息拷貝到CPU的內存中。

2)將相關算法修改為可在Device上調用的函數。

3)對算法程序進行并行改造：每一個GPU線程處理一個指定索引號對應的計算需求。

4)調用方法的適應性修改：設置相應的Block塊和每個Block中的Threads，然后通過指定的語法調用相應的函數和相應的參數。

5)GPU數據向CPU數據的傳遞：將GPU算法中計算完成的數據拷貝到主機內存中再進行下一步的處理和展示等操作。

3.3 加速結構的CUDA數據傳遞方式

采用加速結構的CUDA程序從總體上與無加速結構程序類似，區別之處在于在于進行射線相交時需要考慮先使用加速結構來縮小三角面片判斷的范圍，這樣帶來的問題就是如何將加速結構有效的進行組織，傳遞到GPU中并進行相應的計算判斷(見圖2)。

3.4 SAH算法帶來的調整

SAH算法可以有效的解決圖元分布不均勻的情況，但SAH算法會導致加速結構樹不是完全樹，因此在進行GPU編程開發時需要調整數據結構(見圖3)。完全二叉樹的父節點與子節點存在著明確的關系(j=(i-1)*K+1+1)，而非完全樹的父節點與子節點的關系是不確定的，因此對于加速結構包圍盒樹結構進行子節點相交測試時需要明確節點下的子節點編號關系。在使用SAH時需要調整數據傳遞及調用關系，由于要多傳遞一組數據，數據結構有所調整。

3.5 效率測試與評估

最后，在實現上述算法并進行相應細節上的優化操作之后，通過實驗對算法的整體性能進行了測試。實驗時所采用的PC平臺為64位Win10操作系統，處理器和內存為：Intel Core(TM)i7-7700HQ CPU @2.8 GHz，RAM 8.0 GB，所使用的顯卡GPU支持為GTX 1050。

表1 實驗測試數據及加速比

續表

從表1中可以看出將算法合理并行化后移植于GPU平臺得到了很大的速度提升。通過實驗可以看出：

1)加速結構的構建相對射線相交判斷來說耗時少很多，研究重點可以集中在對加速結構的合理構建上，圖元分布均勻性對加速結構的加速效果有著比較大的影響。總體來看，BVH和KD樹(SAH)加速效果普遍好一些，其次是八叉樹，最后是KD樹(中點分隔)。

2)在網格數量較少時，加速結構效果并不明顯，甚至耗時有所增加(增加了加速結構包圍盒層次結構與射線的判斷)；而隨著網格數量增加后，加速結構可以有效的減少射線與面片的相關判斷次數，從而減少時間。

4 結論

本文首先較為詳細闡述了并行計算在光線追蹤計算中的作用、常用加速結構；然后通過加速結構和基于CUDA的射線追蹤算法的并行化實現及效率測試。經測試可知：隨著網格數量增加后，加速結構可以有效的減少射線與面片的相關判斷次數，從而減少時間；BVH和KD樹(SAH)在加速效果比較明顯；GPU加速的效果整體上也比較明顯，但不同GPU的性能和參數都有不同，如何最大限度的利用好GPU性能需要進一步的細化分析和研究。