[發明專利]一種基于動態任務調度的層次包圍盒構建方法

有效

• 申請號: 201710514892.0
• 申請日: 2017-06-29
• 公開（公告）號: CN107346527B
• 公開（公告）日: 2020-03-10
• 發明（設計）人: 何發智;張正昌;黎明麗;陳壹林
• 申請（專利權）人: 武漢大學
• 主分類號: G06T1/00
• 分類號: G06T1/00;G06F9/48;G06F9/54
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 魯力

本發明涉及一種層次包圍盒構建方法，屬于計算機圖形處理技術領域，具體是涉及一種基于動態任務調度的層次包圍盒構建方法。發明遍歷BVH時將一個線程對應葉子結點，在聚類幼樹重構時一個Warp對應2個內部結點，使得BVH構建算法在單個主機上的并行度進一步的提高，相比當前通用的方法BVH構建速度提升了大約25％。

技術領域

本發明涉及一種層次包圍盒構建方法，屬于計算機圖形處理技術領域，具體是涉及一種基于動態任務調度的層次包圍盒構建方法。

背景技術

光線跟蹤(Ray Tracing)是一種在平面圖像中通過跟蹤視點與像素平面上的像素連線形成的射線，并計算該射線與場景中物體的交點來設置像素屬性的技術，由Appe在1968年提出。該技術通常生成比典型的掃描線渲染方法質量更高的圖片，但需要更高的計算成本。這使得光線跟蹤更適用于如電影和電視視覺效果、靜止圖像等離線渲染方面而不適合在如游戲等實時渲染領域。此外，光線跟蹤還可用于模擬諸如反射、折射、閃射和色散等光學效果。

BVH是一種以幾何物體為對象的樹結構，該樹的葉子結點為與軸平行的可包圍幾何物體的最小立方體盒子。這些葉子結點被組合為一些集合并被更大的立方體盒子即內部結點所包圍，直到最后的根結點。BVH可以有效地支持幾何對象的一些操作如碰撞檢測、光線跟蹤加速等。

發明內容

本發明的目的是優化原有的基于GPU的計算方法，調整其并行架構使之并行效率更高，設計出一套改進的CUDA并行架構方式，利用GPU加速執行使得BVH構建速度在單個主機上的并行度進一步提高，相比當前通用方法BVH構建速度大約提升25％。

本發明的上述技術問題主要是通過下述技術方案得以解決的：

一種基于動態任務調度的層次包圍盒構建方法，包括以下步驟：

步驟1：初始化GPU中的全局變量g_optimizecounter，所述g_optimizecounter用于表示當前已處理任務數目；

步驟2：根據全局變量g_optimizecounter值和場景三角元片數目為線程分配任務；

步驟3：結合任務ID自頂向上遍歷BVH，并讀取幼樹重構所需數據到局部變量；

步驟4：當warp中有符合預定條件的線程時使用warp級編程用聚類方法進行幼樹重構；

步驟5：重復執行步驟2-4直到達到設定的結束條件，GPU輸出計算結果。

優選的，上述的基于動態任務調度的層次包圍盒構建方法，所述步驟4中所述的預定條件為warp中存在的至少一個線程的內部結點下有9個葉子結點。

優選的，上述的基于動態任務調度的層次包圍盒構建方法，所述步驟2具體包括：

步驟2.1：計算當前warp中空閑的線程數目；

步驟2.2：在warp第一個空閑線程中通過獲取g_optimizecounter值得到當前已處理的任務數，并放入共享變量中；若所有任務都已完成則結束循環；

步驟2.3：結合共享變量中的任務數目和當前線程在warp中空閑線程的序號，進行任務分配。

優選的，上述的基于動態任務調度的層次包圍盒構建方法，所述步驟3中，終止第一個到達父結點的線程以保證處理內部結點時該結點下的所有子結點都已經處理完畢。

優選的，上述的基于動態任務調度的層次包圍盒構建方法，所述步驟4中，具體包括以下子步驟：

步驟4.1：判斷當前warp中是否有9個及以上線程滿足條件，若沒有則跳轉到步驟2，若有則執行步驟4.2；

步驟4.2：從當前結點開始向下尋找9個葉子結點形成幼樹；