針對在復(fù)雜三維場景中傳統(tǒng)的碰撞檢測算法存在的檢測速率慢等問題,提出了一種基于量子蟻群的快速碰撞檢測算法。算法首先基于AABB層次包圍盒技術(shù)剔除不相交的模型部分,再應(yīng)用隨機碰撞檢測算法的思想將三維空間中的碰撞問題轉(zhuǎn)化為二維空間上的待檢測物體特征對距離的優(yōu)化問題,結(jié)合了量子計算和蟻群算法的尋優(yōu)策略,引入變異算子和一種新的自動旋轉(zhuǎn)角策略,設(shè)計了一種新的量子蟻群算法來解決碰撞檢測問題。實驗證明,在待檢測模型多邊形數(shù)量較多的情況下,可以提高碰撞檢測檢測速率。 

【文章來源】：計算機仿真. 2019,36(12)北大核心

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

【部分圖文】：

三角形相交測試結(jié)果顯示

把本文算法與單純基于層次包圍盒(HBV)的碰撞檢測算法進行檢測時間比較,比較兩種算法在達到不同檢測結(jié)果時所需時間,算法采樣特征對數(shù)量為2304,實驗結(jié)果如圖3所示。根據(jù)結(jié)果顯示,若完全檢測,HBV在達到100%檢測率時,時間消耗為33ms;QACO算法檢測率達到90%時,需要的時間為18.1ms。即在損失了10%的檢測率的情況下,QACO的算法時間效率比傳統(tǒng)的HBV算法提高了45%。

把本文算法、基于蟻群算法(ACO)的隨機碰撞檢測算法、單純基于粒子群(PSO)的隨機碰撞檢測算法進行碰撞檢測率比較,算法采樣特征對數(shù)量為2304,實驗結(jié)果如圖4所示。根據(jù)結(jié)果顯示,在檢測初期,幾種算法的檢測率基本相同。隨著檢測時間的增加,本文算法的檢測率明顯高于其它算法。QACO在16ms可以達到80%的檢測率,PSO所需時間則為18ms,與PSO算法相比,本文算法效率提高了11%;檢測率達到90%時QACO與PSO和ACO的差距達到了3ms,算法效率提高了13%。在相同碰撞檢測率的要求下,QACO具有更快的檢測效率。

【參考文獻】：
期刊論文
[1]基于八叉樹的柔性體切割仿真中并行化的碰撞算法[J]. 賈世宇,張維忠,于曉康,潘振寬.  計算機輔助設(shè)計與圖形學(xué)學(xué)報. 2017(12)
[2]融合智能算法的變形體碰撞檢測算法研究[J]. 靳雁霞,任超,李照,程思岳,王賀,韓慧妍.  計算機工程與應(yīng)用. 2017(19)
[3]基于量子蟻群算法的圖像分割[J]. 李積英,黨建武.  系統(tǒng)仿真學(xué)報. 2014(04)
[4]基于多智能體粒子群的快速碰撞檢測算法研究[J]. 付躍文,梁加紅,李猛,劉全平.  系統(tǒng)仿真學(xué)報. 2013(08)
[5]基于粒子群面向可變形物體的隨機碰撞檢測算法[J]. 李文輝,王天柱,王祎,秦忠.  系統(tǒng)仿真學(xué)報. 2006(08)



本文編號：3614215