提出一種新穎的適用于GPU且支持化簡的并行化的雙輪廓方法。通過使用新的GPU八叉樹生成算法,克服了傳統(tǒng)的八叉樹數(shù)據(jù)結(jié)構(gòu)難以完全在GPU端并行生成與存儲的困難,適用于對三維離散點云、數(shù)據(jù)場及三角網(wǎng)格模型構(gòu)建（包含等值面或原模型的）八叉樹。上述方法逐層并行生成八叉樹結(jié)點,線性存儲每層結(jié)點信息同時避免存儲空結(jié)點信息,有效節(jié)約了存儲空間并且便于后續(xù)對各層結(jié)點并行處理。以并行八叉樹生成方法為基礎(chǔ),提出了對原始雙輪廓算法的GPU加速實現(xiàn)。與在CPU上單線程執(zhí)行的算法相比,速度可以提高1個數(shù)量級。 

【文章來源】：計算機仿真. 2020,37(06)北大核心

【文章頁數(shù)】：6 頁

【部分圖文】：

頂點樹數(shù)據(jù)結(jié)構(gòu)示意圖

對于從符號距離場[19-21]構(gòu)造等值面的情況,通過離散差分計算出的交點法向量并不精確。如圖2所示,若重構(gòu)出的輪廓面不在采樣網(wǎng)格正中心,則在采樣點o處由差分計算所得的梯度不等于0,導(dǎo)致解得的特征點位置不準確。對此,本文對于一個立方體內(nèi)每條具有符號變化的邊,用符號為正的端點在輪廓面上對應(yīng)的距離最近的點(不一定是邊與輪廓面的交點)來構(gòu)造QEF。4.3 化簡八叉樹

在執(zhí)行第二步前,要為surf_indices數(shù)組分配存儲空間,數(shù)組元素的數(shù)量取邊數(shù)組元素數(shù)量的6倍。因為每一條最小邊最多產(chǎn)生兩個三角形。對于邊數(shù)組的每個元素(邊),4個相鄰結(jié)點的存儲順序應(yīng)如圖3所示。當(dāng)邊的首端點符號為“負”時,箭頭方向指向生成表面的外側(cè)。按照右手定則,所構(gòu)造的三角形在鄰結(jié)點數(shù)組中的索引為0,1,2和(或)0,2,3。當(dāng)首端點標識符為1時,三角形繞向取反。第二步:并行處理邊數(shù)組中的每個元素。按照邊的鄰結(jié)點數(shù)組中的索引值依次找到每個結(jié)點所關(guān)聯(lián)的頂點樹結(jié)點。若頂點樹結(jié)點被標記為“被合并” (即is_collapsed為true),則遞推跟蹤parent索引值直到遇到第一個沒有被標記為“被合并”的父結(jié)點,取出該頂點樹結(jié)點的x_id構(gòu)建三角形。經(jīng)化簡后,4個結(jié)點的x_id可能重復(fù),并不一定能組成兩個三角面片,這里只存儲有效的三角面片索引。

【參考文獻】：
期刊論文
[1]基于GPU的并行八叉樹生成算法[J]. 王吉強,賈世宇.  青島大學(xué)學(xué)報(自然科學(xué)版). 2018(04)
[2]基于八叉樹的柔性體切割仿真中并行化的碰撞算法[J]. 賈世宇,張維忠,于曉康,潘振寬.  計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2017(12)
[3]基于八叉樹鄰域分析的光線跟蹤加速算法[J]. 張文勝,解騫,鐘瑾,劉俊平,郝青,郭廣利.  圖學(xué)學(xué)報. 2015(03)
[4]大規(guī)模三維云實時模擬方法[J]. 任威,梁曉輝,馬上,沈旭昆.  計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2010(04)



本文編號：2963019