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

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

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

【相似文獻】

相關期刊論文 前10條

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

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

3 金鉞;侯文君;;基于虛擬手簡化面法向距離的抓取碰撞檢測算法[J];中國機械工程;2008年09期

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

5 鄒承明;湯智勇;;結合二維算法的三維快速碰撞檢測算法[J];軟件導刊;2009年04期

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

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

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

9 馬登武;葉文;李瑛;呂曉峰;;適用于復雜場景的碰撞檢測算法研究[J];計算機仿真;2006年12期

10 韓文君;趙偉;;基于空間數(shù)據(jù)結構的快速碰撞檢測算法[J];長春工業(yè)大學學報(自然科學版);2007年04期

相關會議論文 前10條

1 陳二雷;;加速碰撞檢測算法的研究[A];2008通信理論與技術新進展——第十三屆全國青年通信學術會議論文集（上）[C];2008年

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

3 紀傳舜;劉卉;;基于質點的快速可變形體自碰撞檢測算法[A];中國計算機圖形學進展2008--第七屆中國計算機圖形學大會論文集[C];2008年

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

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

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

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

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

9 曹力;鄭利平;劉曉平;;并行八叉樹碰撞檢測算法[A];計算機技術與應用進展——全國第17屆計算機科學與技術應用（CACIS）學術會議論文集（下冊）[C];2006年

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

相關博士學位論文 前4條

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

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

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

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

相關碩士學位論文 前10條

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

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

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

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

5 張紀鎖;虛擬現(xiàn)實中混合碰撞檢測算法的應用研究[D];遼寧工程技術大學;2011年

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

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

8 張鋒;移動平臺游戲中3D碰撞檢測算法的研究與應用[D];上海交通大學;2010年

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

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

本文編號：2653757