[發明專利]一種基于GPU的八叉樹并行構建方法

無效

• 申請號: 201010150547.1
• 申請日: 2010-04-19
• 公開（公告）號: CN101840565A
• 公開（公告）日: 2010-09-22
• 發明（設計）人: 許端清;楊鑫;趙磊
• 申請（專利權）人: 浙江大學
• 主分類號: G06T1/20
• 分類號: G06T1/20;G06T1/60
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

技術領域

本發明涉及圖形實時渲染技術領域，尤其涉及一種基于GPU的八叉樹并行構建方法。

背景技術

在過去的二十年時間里，顯卡性能的巨大提高，尤其是其可編程性的出現，大大促進了圖形學研究領域的進步。光線跟蹤技術是一種在圖形繪制領域廣泛應用的技術。相比光柵化技術，光線跟蹤技術有很多優勢，包括物體可見性的自動計算，時間復雜度與場景中圖元數量呈次線性關系，更適合并行架構處理等。但是，由于光線跟蹤技術模擬的是真實世界中光的物理路徑，因此它最大的優勢是產生高質量的圖像，繪制出高真實感的平滑的反射、折射、軟影(soft?shadow)等全局光照效果。Whitted最早使用光線跟蹤技術來模擬全局光照效果。由于光線跟蹤技術需要花費很高的計算量，因此以往這種技術只能應用在非實時繪制領域中。

當前，計算機硬件的計算能力呈指數形式的增長速度已經使交互式的實時光線跟蹤成為可能。越來越多的研究開始關注光線跟蹤的實時計算，已經出現了一些優秀的研究成果。然而，盡管這些研究很多都是基于GPU架構設計的，但這些實現仍然未能充分利用當前GPU強大的并行計算能力。

近年來已經出現了一些基于GPU實現的編程方法，例如NVIDIA公司的CUDA(Compute?Unified?Device?Architecture)編程模型、蘋果公司的OpenCL，以及一些底層的框架結構。這些模型允許程序員自己定義合適的數據結構，為編程提供很大的靈活性和可操作性，包括創建、調度、同步等線程管理操作可以完全由硬件來完成。例如在CUDA編程模型里，我們可以根據程序的并行特征將程序劃分成幾個順序執行的被稱為kernel的代碼段，使其在GPU中執行。為了有效地管理大量的線程，kernel使用標量形式的SIMT(Single?Instruction，Multiple?Thread)操作，線程以一種被稱作warps的分組形式根據kernel中的指令來執行。程序員將線程組織成線程塊(block)，這些線程塊本質上可以看成是虛擬的SM多處理器，擁有獨立的寄存器和共享內存(shared?memory)，各線程塊間相對獨立的亂序執行。

為了獲得GPU的最大計算性能，有兩個問題需要考慮：第一，每個線程應該使用盡量少的硬件寄存器和存儲資源，以保證GPU內部同一時刻運行更多的活動線程，Popov等的光線跟蹤實現消耗了過多的寄存器，導致GPU利用率還不到33％；第二，線程的SIMD(Single?Instruction，Multiple?Data)操作對程序員來說是透明的，而SIMD的操作方式對程序的分支執行非常敏感，同一warp的線程只有執行程序的同一分支才能獲得最大效益。

最近，一些研究開始關注動態場景下的光線跟蹤方法。在光線跟蹤算法中，構造加速結構是其中重要的一步，通過將面片重新進行組織，可以大大減少無效的光線遍歷操作和相交操作。由于動態場景下物體間的拓撲結構會發生改變，甚至物體本身都會發生形變，因此，每一幀都需要重新對加速結構進行重構。然而，加速結構的構造是一個比較耗時的操作，通常無法在繪制一幀的時間內完成，這也是導致當前基于動態場景的實時光線跟蹤研究進展較慢的主要原因。

設計出一種高質量的快速的加速結構構造方法，使其可以充分利用多核處理器強大的并行處理能力，從而使加速結構建造速度進一步加快，滿足實時性的要求，是一個光線跟蹤算法能否有效執行的關鍵。層次結構的構造并不能很好的利用多個核的并行處理能力。其中存在的主要問題是，層次結構自上而下的遞歸構造方式通常會產生一個二叉樹結構，在構造階段初期只能生成少量節點，很難充分的利用硬件的并行計算能力，從而造成硬件的低效使用，而且訪存的延遲也給構造造成了困難。

傳統的八叉樹構造根據三個垂直坐標軸x、y、z方向上對象的中間位置對場景進行劃分，這種劃分方式盡管簡單快速，但其粗糙的質量造成了大量無效的遍歷和相交操作，也造成了大量的空節點而浪費存儲空間，使得八叉樹逐漸被構建質量更高的kd樹所取代。kd樹通常使用SAH策略來確定最優的分割點，然而大量的計算使得kd樹的構建需要一些時間，難以滿足動態場景的實時光線跟蹤計算要求。另一方面，當前的GPU架構包含多個多核處理器，需要同時運行上萬個線程才能充分利用這些處理器的計算能力，而kd樹等加速結構在其構建之初只有少量的節點供處理核使用，大大浪費了GPU的計算資源，進而影響構造速度。

發明內容

本發明提供一種基于GPU的八叉樹并行構建方法，可有效利用硬件的并行計算能力，提高加速結構的構造速度和質量。