發(fā)布時(shí)間：2020-05-07 23:56

【摘要】：針對(duì)人機(jī)交互系統(tǒng)中碰撞檢測(cè)實(shí)時(shí)性、精確性的要求,本文提出了一種基于云計(jì)算模型的快速碰撞檢測(cè)算法。1提出一種新的分裂平面構(gòu)建OBB平衡包圍盒樹(shù)方法;2引入了標(biāo)記遍歷樹(shù)概念,對(duì)進(jìn)行碰撞檢測(cè)的OBB任務(wù)樹(shù)采用堆棧進(jìn)行深度或廣度遍歷標(biāo)記,減少相交檢測(cè)次數(shù);3采用Map-Reduce云模型對(duì)任務(wù)樹(shù)進(jìn)行劃分,劃分后子任務(wù)采用云模型并行執(zhí)行,減少了檢測(cè)時(shí)間;4對(duì)每個(gè)子任務(wù)結(jié)果進(jìn)行標(biāo)識(shí),將標(biāo)識(shí)后的子任務(wù)作邏輯運(yùn)算,通過(guò)運(yùn)算結(jié)果判斷是否發(fā)生了碰撞。對(duì)比實(shí)驗(yàn)結(jié)果表明:與經(jīng)典的I-COLLIDE、MPI及Pipelining等算法相比,該算法在效率、精確性方面具有明顯優(yōu)勢(shì),能夠滿足復(fù)雜虛擬空間人機(jī)交互的實(shí)時(shí)性和精確性的要求。
【圖文】：

是云計(jì)算的關(guān)鍵技術(shù)，工作的基本原理源于程序的函數(shù)式，它把要解決的復(fù)雜問(wèn)題分解、簡(jiǎn)化，即“Ｍａｐ（映射）”和“Ｒｅｄｕｃｅ（化簡(jiǎn)）”來(lái)完成。Ｍａｐ建立了函數(shù)與成員的關(guān)系，運(yùn)算結(jié)果保存在集合中。而Ｒｅｄｕｃｅ是把Ｍａｐ中處理的結(jié)果，通過(guò)多線程或多進(jìn)程并行執(zhí)行的結(jié)果進(jìn)行分類(lèi)和歸約。無(wú)論Ｍａｐ（）和Ｒｅｄｕｃｅ（）是否在同一系統(tǒng)，兩者均可以并行執(zhí)行。將Ｍａｐ－Ｒｅｄｕｃｅ運(yùn)行在集群上時(shí)，可以達(dá)到真正的并行，實(shí)現(xiàn)任務(wù)調(diào)度、結(jié)點(diǎn)通信等功能。如圖１所示。圖１Ｍａｐ－Ｒｅｄｕｃｅ執(zhí)行過(guò)程Ｆｉｇ．１ＴｈｅＭａｐ－Ｒｅｄｕｃｅｅｘｅｃｕｔｉｏｎｐｒｏｃｅｓｓ由圖１可以看出，Ｍａｐ－Ｒｅｄｕｃｅ工作流程是：從文件塊中讀取文件，Ｍａｐ將讀取的文件分割、執(zhí)行，將執(zhí)行結(jié)果寫(xiě)入文件，Ｒｅｄｕｃｅ將文件執(zhí)行結(jié)果劃分規(guī)約，輸出文件結(jié)果。其中，文件寫(xiě)入是在本地完成的，這主要是為了減少網(wǎng)絡(luò)傳輸?shù)膲毫�，同時(shí)也減少網(wǎng)絡(luò)讀寫(xiě)文件的時(shí)間。另外，Ｍａｐ－Ｒｅｄｕｃｅ還能使大型集群系統(tǒng)在海量數(shù)據(jù)集上并行執(zhí)行。如圖２所示，，在運(yùn)行系統(tǒng)的主程序時(shí)，系統(tǒng)協(xié)調(diào)Ｍａｐ－Ｒｅｄｕｃｅ，然后從每個(gè)ｒｅｄｕｃｅ操作中收集結(jié)果。２．３構(gòu)建基于ＯＢＢ的平衡包圍盒樹(shù)包圍盒間相交測(cè)試的精度和速度會(huì)直接影響到碰撞檢測(cè)的精度和速度。由于ＯＢＢ包圍盒間圖２主系統(tǒng)上的程序運(yùn)行過(guò)程Ｆｉｇ．２Ｔｈｅｍａｉｎｐｒｏｇｒａｍｒｕｎｎｉｎｇｏｎｔｈｅｓｙｓｔｅｍ的相交測(cè)試是所有包圍盒類(lèi)型中最精確的相交測(cè)試，所以本文采用的檢測(cè)包圍盒選擇了ＯＢＢ包圍盒，雖然在整體速度上較ＡＡＢＢ包圍盒稍慢了一點(diǎn)，但卻換

通信等功能。如圖１所示。圖１Ｍａｐ－Ｒｅｄｕｃｅ執(zhí)行過(guò)程Ｆｉｇ．１ＴｈｅＭａｐ－Ｒｅｄｕｃｅｅｘｅｃｕｔｉｏｎｐｒｏｃｅｓｓ由圖１可以看出，Ｍａｐ－Ｒｅｄｕｃｅ工作流程是：從文件塊中讀取文件，Ｍａｐ將讀取的文件分割、執(zhí)行，將執(zhí)行結(jié)果寫(xiě)入文件，Ｒｅｄｕｃｅ將文件執(zhí)行結(jié)果劃分規(guī)約，輸出文件結(jié)果。其中，文件寫(xiě)入是在本地完成的，這主要是為了減少網(wǎng)絡(luò)傳輸?shù)膲毫�，同時(shí)也減少網(wǎng)絡(luò)讀寫(xiě)文件的時(shí)間。另外，Ｍａｐ－Ｒｅｄｕｃｅ還能使大型集群系統(tǒng)在海量數(shù)據(jù)集上并行執(zhí)行。如圖２所示，在運(yùn)行系統(tǒng)的主程序時(shí)，系統(tǒng)協(xié)調(diào)Ｍａｐ－Ｒｅｄｕｃｅ，然后從每個(gè)ｒｅｄｕｃｅ操作中收集結(jié)果。２．３構(gòu)建基于ＯＢＢ的平衡包圍盒樹(shù)包圍盒間相交測(cè)試的精度和速度會(huì)直接影響到碰撞檢測(cè)的精度和速度。由于ＯＢＢ包圍盒間圖２主系統(tǒng)上的程序運(yùn)行過(guò)程Ｆｉｇ．２Ｔｈｅｍａｉｎｐｒｏｇｒａｍｒｕｎｎｉｎｇｏｎｔｈｅｓｙｓｔｅｍ的相交測(cè)試是所有包圍盒類(lèi)型中最精確的相交測(cè)試，所以本文采用的檢測(cè)包圍盒選擇了ＯＢＢ包圍盒，雖然在整體速度上較ＡＡＢＢ包圍盒稍慢了一點(diǎn)，但卻換回了更高的精度，減少了相交檢測(cè)次數(shù)，總的檢測(cè)效率會(huì)更高。鑒于此，本文提出了一種新的構(gòu)建ＯＢＢ平衡包圍盒樹(shù)的方法。（１）任取空間解集Ｍ＝｛Ｍ１，Ｍ２，…，Ｍｎ｝的任意兩個(gè)物體Ｍｉ∈Ｍ，Ｍｊ∈Ｍ，分別以Ｍｉ，Ｍｊ為根節(jié)點(diǎn)構(gòu)建其整體ＯＢＢ包圍盒樹(shù)，Ｍｉ，Ｍｊ包含組成物體所有多邊形。（２）本文采用文獻(xiàn)［１１］分裂平面的方法劃分Ｍｉ，Ｍｊ的左右子樹(shù)。（３）使用最長(zhǎng)軸方法確

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王浩,張航義;一種適合多機(jī)空戰(zhàn)仿真的碰撞檢測(cè)算法及應(yīng)用[J];系統(tǒng)仿真學(xué)報(bào);2004年09期

2 林鴻;常學(xué)宏;;計(jì)算機(jī)碰撞檢測(cè)算法的研究[J];吉林省經(jīng)濟(jì)管理干部學(xué)院學(xué)報(bào);2008年06期

3 金鉞;侯文君;;基于虛擬手簡(jiǎn)化面法向距離的抓取碰撞檢測(cè)算法[J];中國(guó)機(jī)械工程;2008年09期

4 熊玉梅;曾憲文;陳一民;;基于并行的快速碰撞檢測(cè)算法的研究[J];計(jì)算機(jī)應(yīng)用與軟件;2008年04期

5 鄒承明;湯智勇;;結(jié)合二維算法的三維快速碰撞檢測(cè)算法[J];軟件導(dǎo)刊;2009年04期

6 戴高樂(lè);吳貴芳;李艷;;一種快速混合碰撞檢測(cè)算法研究[J];通信技術(shù);2010年05期

7 梁鵬帥;;碰撞檢測(cè)算法的探討[J];黑龍江科技信息;2010年14期

8 齊曉松;胡青泥;劉晶;;基于多視角的動(dòng)態(tài)八叉樹(shù)碰撞檢測(cè)算法[J];東華大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年05期

9 馬登武;葉文;李瑛;呂曉峰;;適用于復(fù)雜場(chǎng)景的碰撞檢測(cè)算法研究[J];計(jì)算機(jī)仿真;2006年12期

10 韓文君;趙偉;;基于空間數(shù)據(jù)結(jié)構(gòu)的快速碰撞檢測(cè)算法[J];長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

相關(guān)會(huì)議論文 前10條

1 陳二雷;;加速碰撞檢測(cè)算法的研究[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（上）[C];2008年

2 邵引平;李瑞鵬;;WTK環(huán)境下的碰撞檢測(cè)算法的應(yīng)用[A];信號(hào)與信息處理技術(shù)——第一屆信號(hào)與信息處理聯(lián)合學(xué)術(shù)會(huì)議論文集[C];2002年

3 紀(jì)傳舜;劉卉;;基于質(zhì)點(diǎn)的快速可變形體自碰撞檢測(cè)算法[A];中國(guó)計(jì)算機(jī)圖形學(xué)進(jìn)展2008--第七屆中國(guó)計(jì)算機(jī)圖形學(xué)大會(huì)論文集[C];2008年

4 趙偉;陳承收;李立軍;;基于MapReduce云計(jì)算模型的碰撞檢測(cè)算法[A];'2010系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2010年

5 張安真;孫長(zhǎng)嵩;徐俊杰;;一種基于圖像的凸多面體碰撞檢測(cè)算法研究[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)——通信與信息技術(shù)會(huì)議論文集（下）[C];2006年

6 金漢軍;劉直良;吳天真;;虛擬教學(xué)中碰撞檢測(cè)算法的研究[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（上）[C];2008年

7 邢一思;劉小平;徐少平;;虛擬焊接仿真系統(tǒng)中碰撞檢測(cè)算法的改進(jìn)[A];探索 創(chuàng)新 交流——第五屆中國(guó)航空學(xué)會(huì)青年科技論壇文集(第5集)[C];2012年

8 李學(xué)慶;孟祥旭;汪嘉業(yè);;基于Minkowski差構(gòu)造技術(shù)的凸體碰撞檢測(cè)算法[A];第一屆全國(guó)幾何設(shè)計(jì)與計(jì)算學(xué)術(shù)會(huì)議論文集[C];2002年

9 曹力;鄭利平;劉曉平;;并行八叉樹(shù)碰撞檢測(cè)算法[A];計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展——全國(guó)第17屆計(jì)算機(jī)科學(xué)與技術(shù)應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];2006年

10 趙偉;李立軍;陳承收;;基于粒子群優(yōu)化的隨機(jī)碰撞檢測(cè)算法研究[A];'2010系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2010年

相關(guān)博士學(xué)位論文 前4條

1 趙偉;基于并行的快速碰撞檢測(cè)算法研究[D];吉林大學(xué);2009年

2 鄒益勝;虛擬樣機(jī)環(huán)境下實(shí)時(shí)碰撞檢測(cè)算法研究[D];西南交通大學(xué);2009年

3 水泳;虛擬現(xiàn)實(shí)中連續(xù)碰撞檢測(cè)算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2013年

4 金漢均;虛擬環(huán)境中物體碰撞檢測(cè)算法研究[D];華中科技大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

1 李山;變形物體碰撞檢測(cè)算法研究[D];吉林農(nóng)業(yè)大學(xué);2012年

2 王龍濤;基于云計(jì)算的碰撞檢測(cè)算法研究[D];吉林農(nóng)業(yè)大學(xué);2013年

3 李立軍;基于粒子群蟻群的快速碰撞檢測(cè)算法研究[D];長(zhǎng)春工業(yè)大學(xué);2011年

4 游靈聰;分布式多層次粒子碰撞檢測(cè)算法[D];華南理工大學(xué);2015年

5 張紀(jì)鎖;虛擬現(xiàn)實(shí)中混合碰撞檢測(cè)算法的應(yīng)用研究[D];遼寧工程技術(shù)大學(xué);2011年

6 程天翔;大規(guī)模柔體的連續(xù)碰撞檢測(cè)算法研究[D];天津大學(xué);2014年

7 黎珍;基于空間域的碰撞檢測(cè)算法的研究[D];湖南師范大學(xué);2013年

8 張鋒;移動(dòng)平臺(tái)游戲中3D碰撞檢測(cè)算法的研究與應(yīng)用[D];上海交通大學(xué);2010年

9 于奎超;柔性織物碰撞檢測(cè)算法的研究[D];吉林農(nóng)業(yè)大學(xué);2013年

10 李建波;變形體的碰撞檢測(cè)算法研究[D];青島大學(xué);2005年

本文編號(hào)：2653757