[發(fā)明專利]基于GPU的構建BVH樹并行光線追蹤方法

有效

• 申請?zhí)枺?/td>: 201210441051.9
• 申請日: 2012-11-07
• 公開（公告）號: CN103021018A
• 公開（公告）日: 2013-04-03
• 發(fā)明（設計）人: 吳哲夫;虞鴻;何熊熊;陳濱
• 申請（專利權）人: 浙江工業(yè)大學
• 主分類號: G06T15/06
• 分類號: G06T15/06
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

技術領域

本發(fā)明屬于計算機圖形學領域，具體涉及一種利用GPU構建BVH樹進行并行光線追蹤方法的方法，該技術能夠大大降低傳統CPU光線追蹤的計算時間。

背景技術

光線追蹤算法是真實感圖形學領域中的重要算法，它通過模擬光線在傳播過程中的反射、折射現象，將光線的顏色與物體的材質屬性結合建模，能對復雜的三維物體做出較好的仿真，適合繪制表面光潔度高或具有透明表面和鏡面的場景。在整個算法中，計算量最大的就是光線與場景圖形元的求交過程。若考慮動態(tài)光線追蹤，還需要加上整個場景空間結構的建立。隨著GPU性能正以每年翻倍的速度發(fā)展，動態(tài)光線追蹤生成動畫越來越成為工業(yè)界的趨勢。

在對場景進行空間劃分的方法中，最常用的就是KD-tree和BVH-tree。這兩種方法都可以完成光線追蹤，但是在動態(tài)場景當中，BVH-tree性能更加優(yōu)于KD-tree。同時，實驗研究已經表明表面積啟發(fā)SAH方法可以生成高質量的生成樹，但卻需要極大的時間開銷，這阻礙了BVH-tree的快速構建，且即使通過優(yōu)化SAH機制還是無法達到動態(tài)光線追蹤的效果。但是如果利用GPU完成BVH-tree的建立，并用GPU計算SAH函數，就可以大大加快光線追蹤前期準備速度，而且利用GPU并行處理求交還可以很好彌補CPU串行計算求交的低效性。

發(fā)明內容

本發(fā)明要克服先有光線跟蹤方法效率較低的缺點，提出一種在GPU上快速高效建立BVH-tree進行并行光線追蹤的方法。該方法通過在GPU上高效地建立BVH-tree來加快光線追蹤速度，并利用GPU并行計算光射線與圖形元相交處的信息，從而提高光線追蹤效率。

本發(fā)明的技術方案為：

基于GPU的構建BVH樹并行光線追蹤方法，其步驟為：

1）讀取3D場景模型，設置三角形的模型圖形元，將這些數據存儲在GPU顯存中。

2)?創(chuàng)建一個動態(tài)增長存儲BVH節(jié)點的空間。

3)?根據模型圖形元，分別求X軸、Y軸和Z軸的跨度，并計算出最大值，以這個最大值的坐標軸使用SAH機制劃分空間。

4)?判斷由步驟3)分割的子節(jié)點當中的三角形數目是否大于1，若大于1則返回到3)。

5)?BVH-tree構造完畢，輸出線性結構BVHlist數組。

6）根據視點和投影面構造射線。

7）構造一個BVH元素的堆棧，聲明變量stackoffset=0。

8）取當前射線與當前所指BVHlist節(jié)點做相交測試。

9）如果當前射線與這個BVH節(jié)點不相交，而且如果stackoffset為0，表明當前光線與場景無相交，則結束當前射線的光線追蹤；反之stackoffset大于0，那么stackoffset減1，并且把當前節(jié)點設置為堆棧中偏移量為stackoffset的節(jié)點，返回步驟8)；如果當前射線與這個BVH節(jié)點相交轉移到步驟10）。

10）判斷該BVH節(jié)點中是否有圖形元三角形，如果有，說明當前射線與一個BVH樹的葉子節(jié)點正方體有相交，并繼續(xù)測試該射線與節(jié)點內的三角形是否相交，如果相交就把當前的節(jié)點和三角形序號交給該射線。若stackoffset大于0就減1,?并且把當前節(jié)點設置為堆棧中偏移量為stackoffset的節(jié)點，返回步驟8)。如果BVH節(jié)點沒有圖形元三角形就轉移到步驟11)。

11）根據當前節(jié)點的右節(jié)點標記變量，把右節(jié)點序號放入堆棧中，然后stackoffset加1，把當前節(jié)點設置為之前節(jié)點的左節(jié)點，返回步驟8)。

本發(fā)明的效果如下：首次在GPU上對3D模型實現了高質量的BVH-Tree的并行構建方法，每次劃分空間采用SAH劃分機制，這極大提高了BVH-Tree的平衡性。并且通過對光線與模型做并行相交運算，大大減少了原先串行計算的復雜度。

附圖說明

圖1為本發(fā)明的算法流程圖

圖2為本發(fā)明的BVH空間劃分圖

圖3為本發(fā)明的射線與正方體求交方法圖

圖4?為本發(fā)明的BHV-tree保存結構圖

具體實施方式

以下實施方式結合附圖對本發(fā)明進行詳細的描述，參照附圖，本發(fā)明包括以下步驟：

1)?讀取3D場景模型，并設置三角形的模型圖形元，這些數據存儲在GPU顯存中。這些數據是以DirectX規(guī)定的SRV格式保存的，一共有兩個SRV。第一個SRV中保存用于遍歷的圖形元三角形序號數組。第二個SRV中保存圖形元三角形的頂點數組。