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

無效

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

1.一種基于GPU的八叉樹并行構建方法，其特征在于，在需要進行渲染的模型空間的三個坐標軸上分別選取若干個采樣分割點，計算每個采樣分割點的SAH花費，然后選取每個坐標軸上SAH花費最小的分割點，將選取的這三個分割點作為分割平面，對模型空間中的場景數據逐級進行劃分，直至劃分到每個節(jié)點所含面片數不多于10個；

其中劃分場景數據的具體步驟如下：

a)在存儲區(qū)域中建立兩個隊列，分別用來存放等待進行劃分的場景節(jié)點；

b)從第一隊列中依次取等待進行劃分的場景節(jié)點進行劃分，并將產生的新的場景節(jié)點放入第二隊列；

其中對第一隊列中編號為k的場景節(jié)點進行劃分所產生的新的場景節(jié)點在第二隊列中的編號分別為8×k+t(t＝0，1，...7)；場景節(jié)點在隊列中的編號也對應了該場景節(jié)點在存儲區(qū)域中的位置；

c)當第一隊列中等待進行劃分的場景節(jié)點處理完畢后，清空第一隊列中所有的場景節(jié)點數據，從第二隊列中依次取等待進行劃分的場景節(jié)點進行劃分，并將產生的新的場景節(jié)點放入第一隊列，直至第二隊列中等待進行劃分的場景節(jié)點都處理完畢；

其中對第二隊列中編號為j的場景節(jié)點進行劃分所產生的新的場景節(jié)點在第一隊列中的編號分別為8×j+t(t＝0，1，...7)；場景節(jié)點在隊列中的編號也對應了該場景節(jié)點在存儲區(qū)域中的位置；

d)循環(huán)步驟b)、步驟c)，直至完成所有場景節(jié)點的劃分；

所述的步驟b)、步驟c)中當每個隊列中等待進行劃分的場景節(jié)點劃分完畢后，通過硬件支持的緊湊操作清除對該隊列中的空場景節(jié)點；對每一個場景節(jié)點進行劃分時，GPU的每一個線程塊分別處理不同的場景節(jié)點，在相互對應的線程塊和場景節(jié)點中，線程塊中的每一線程分別計算不同采樣分割點的SAH花費，最后通過硬件支持的歸約操作，選取每個坐標軸上SAH花費最小的分割點。

2.如權利要求1所述的八叉樹并行構建方法，其特征在于，采樣分割點的SAH花費

n₁和n_r分別代表與當前采樣分割點相鄰的左、右子節(jié)點所含的面片數量；

SA(N₁)、SA(N_r)分別表示與當前采樣分割點相鄰的左、右子節(jié)點的表面積；

SA(N)表示當前采樣分割點的父節(jié)點的表面積；

K_T表示對當前采樣分割點的父節(jié)點進行遍歷所產生的花費；

K_I表示對當前采樣分割點進行相交操作所產生的花費。