并行化的雙輪廓算法
發(fā)布時(shí)間：2021-01-07 18:19
提出一種新穎的適用于GPU且支持化簡(jiǎn)的并行化的雙輪廓方法。通過(guò)使用新的GPU八叉樹生成算法,克服了傳統(tǒng)的八叉樹數(shù)據(jù)結(jié)構(gòu)難以完全在GPU端并行生成與存儲(chǔ)的困難,適用于對(duì)三維離散點(diǎn)云、數(shù)據(jù)場(chǎng)及三角網(wǎng)格模型構(gòu)建（包含等值面或原模型的）八叉樹。上述方法逐層并行生成八叉樹結(jié)點(diǎn),線性存儲(chǔ)每層結(jié)點(diǎn)信息同時(shí)避免存儲(chǔ)空結(jié)點(diǎn)信息,有效節(jié)約了存儲(chǔ)空間并且便于后續(xù)對(duì)各層結(jié)點(diǎn)并行處理。以并行八叉樹生成方法為基礎(chǔ),提出了對(duì)原始雙輪廓算法的GPU加速實(shí)現(xiàn)。與在CPU上單線程執(zhí)行的算法相比,速度可以提高1個(gè)數(shù)量級(jí)。
【文章來(lái)源】：計(jì)算機(jī)仿真. 2020,37(06)北大核心
【文章頁(yè)數(shù)】：6 頁(yè)
【部分圖文】：
頂點(diǎn)樹數(shù)據(jù)結(jié)構(gòu)示意圖
對(duì)于從符號(hào)距離場(chǎng)[19-21]構(gòu)造等值面的情況,通過(guò)離散差分計(jì)算出的交點(diǎn)法向量并不精確。如圖2所示,若重構(gòu)出的輪廓面不在采樣網(wǎng)格正中心,則在采樣點(diǎn)o處由差分計(jì)算所得的梯度不等于0,導(dǎo)致解得的特征點(diǎn)位置不準(zhǔn)確。對(duì)此,本文對(duì)于一個(gè)立方體內(nèi)每條具有符號(hào)變化的邊,用符號(hào)為正的端點(diǎn)在輪廓面上對(duì)應(yīng)的距離最近的點(diǎn)(不一定是邊與輪廓面的交點(diǎn))來(lái)構(gòu)造QEF。4.3 化簡(jiǎn)八叉樹
在執(zhí)行第二步前,要為surf_indices數(shù)組分配存儲(chǔ)空間,數(shù)組元素的數(shù)量取邊數(shù)組元素?cái)?shù)量的6倍。因?yàn)槊恳粭l最小邊最多產(chǎn)生兩個(gè)三角形。對(duì)于邊數(shù)組的每個(gè)元素(邊),4個(gè)相鄰結(jié)點(diǎn)的存儲(chǔ)順序應(yīng)如圖3所示。當(dāng)邊的首端點(diǎn)符號(hào)為“負(fù)”時(shí),箭頭方向指向生成表面的外側(cè)。按照右手定則,所構(gòu)造的三角形在鄰結(jié)點(diǎn)數(shù)組中的索引為0,1,2和(或)0,2,3。當(dāng)首端點(diǎn)標(biāo)識(shí)符為1時(shí),三角形繞向取反。第二步:并行處理邊數(shù)組中的每個(gè)元素。按照邊的鄰結(jié)點(diǎn)數(shù)組中的索引值依次找到每個(gè)結(jié)點(diǎn)所關(guān)聯(lián)的頂點(diǎn)樹結(jié)點(diǎn)。若頂點(diǎn)樹結(jié)點(diǎn)被標(biāo)記為“被合并” (即is_collapsed為true),則遞推跟蹤parent索引值直到遇到第一個(gè)沒(méi)有被標(biāo)記為“被合并”的父結(jié)點(diǎn),取出該頂點(diǎn)樹結(jié)點(diǎn)的x_id構(gòu)建三角形。經(jīng)化簡(jiǎn)后,4個(gè)結(jié)點(diǎn)的x_id可能重復(fù),并不一定能組成兩個(gè)三角面片,這里只存儲(chǔ)有效的三角面片索引。
【參考文獻(xiàn)】：
期刊論文
[1]基于GPU的并行八叉樹生成算法[J]. 王吉強(qiáng),賈世宇. 青島大學(xué)學(xué)報(bào)(自然科學(xué)版). 2018(04)
[2]基于八叉樹的柔性體切割仿真中并行化的碰撞算法[J]. 賈世宇,張維忠,于曉康,潘振寬. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào). 2017(12)
[3]基于八叉樹鄰域分析的光線跟蹤加速算法[J]. 張文勝,解騫,鐘瑾,劉俊平,郝青,郭廣利. 圖學(xué)學(xué)報(bào). 2015(03)
[4]大規(guī)模三維云實(shí)時(shí)模擬方法[J]. 任威,梁曉輝,馬上,沈旭昆. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào). 2010(04)
本文編號(hào)：2963019
【文章來(lái)源】：計(jì)算機(jī)仿真. 2020,37(06)北大核心
【文章頁(yè)數(shù)】：6 頁(yè)
【部分圖文】：
頂點(diǎn)樹數(shù)據(jù)結(jié)構(gòu)示意圖
對(duì)于從符號(hào)距離場(chǎng)[19-21]構(gòu)造等值面的情況,通過(guò)離散差分計(jì)算出的交點(diǎn)法向量并不精確。如圖2所示,若重構(gòu)出的輪廓面不在采樣網(wǎng)格正中心,則在采樣點(diǎn)o處由差分計(jì)算所得的梯度不等于0,導(dǎo)致解得的特征點(diǎn)位置不準(zhǔn)確。對(duì)此,本文對(duì)于一個(gè)立方體內(nèi)每條具有符號(hào)變化的邊,用符號(hào)為正的端點(diǎn)在輪廓面上對(duì)應(yīng)的距離最近的點(diǎn)(不一定是邊與輪廓面的交點(diǎn))來(lái)構(gòu)造QEF。4.3 化簡(jiǎn)八叉樹
在執(zhí)行第二步前,要為surf_indices數(shù)組分配存儲(chǔ)空間,數(shù)組元素的數(shù)量取邊數(shù)組元素?cái)?shù)量的6倍。因?yàn)槊恳粭l最小邊最多產(chǎn)生兩個(gè)三角形。對(duì)于邊數(shù)組的每個(gè)元素(邊),4個(gè)相鄰結(jié)點(diǎn)的存儲(chǔ)順序應(yīng)如圖3所示。當(dāng)邊的首端點(diǎn)符號(hào)為“負(fù)”時(shí),箭頭方向指向生成表面的外側(cè)。按照右手定則,所構(gòu)造的三角形在鄰結(jié)點(diǎn)數(shù)組中的索引為0,1,2和(或)0,2,3。當(dāng)首端點(diǎn)標(biāo)識(shí)符為1時(shí),三角形繞向取反。第二步:并行處理邊數(shù)組中的每個(gè)元素。按照邊的鄰結(jié)點(diǎn)數(shù)組中的索引值依次找到每個(gè)結(jié)點(diǎn)所關(guān)聯(lián)的頂點(diǎn)樹結(jié)點(diǎn)。若頂點(diǎn)樹結(jié)點(diǎn)被標(biāo)記為“被合并” (即is_collapsed為true),則遞推跟蹤parent索引值直到遇到第一個(gè)沒(méi)有被標(biāo)記為“被合并”的父結(jié)點(diǎn),取出該頂點(diǎn)樹結(jié)點(diǎn)的x_id構(gòu)建三角形。經(jīng)化簡(jiǎn)后,4個(gè)結(jié)點(diǎn)的x_id可能重復(fù),并不一定能組成兩個(gè)三角面片,這里只存儲(chǔ)有效的三角面片索引。
【參考文獻(xiàn)】：
期刊論文
[1]基于GPU的并行八叉樹生成算法[J]. 王吉強(qiáng),賈世宇. 青島大學(xué)學(xué)報(bào)(自然科學(xué)版). 2018(04)
[2]基于八叉樹的柔性體切割仿真中并行化的碰撞算法[J]. 賈世宇,張維忠,于曉康,潘振寬. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào). 2017(12)
[3]基于八叉樹鄰域分析的光線跟蹤加速算法[J]. 張文勝,解騫,鐘瑾,劉俊平,郝青,郭廣利. 圖學(xué)學(xué)報(bào). 2015(03)
[4]大規(guī)模三維云實(shí)時(shí)模擬方法[J]. 任威,梁曉輝,馬上,沈旭昆. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào). 2010(04)
本文編號(hào)：2963019
本文鏈接：http://www.wukwdryxk.cn/kejilunwen/jisuanjikexuelunwen/2963019.html
最近更新
教材專著
