[發(fā)明專利]基于粒子群優(yōu)化的并行碰撞檢測系統(tǒng)及方法

無效

• 申請?zhí)枺?/td>: 201210465702.8
• 申請日: 2012-11-16
• 公開（公告）號: CN102999661A
• 公開（公告）日: 2013-03-27
• 發(fā)明（設計）人: 熊玉梅;寧建紅;閆俊英
• 申請（專利權）人: 上海電機學院
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06N3/00
• 代理公司: 上海思微知識產權代理事務所(普通合伙) 31237
• 代理人: 鄭瑋

1.一種基于粒子群優(yōu)化的并性碰撞檢測系統(tǒng)，至少包括：

構建搜索空間模組，用于構建三維空間內兩個物體之間存在的特征對構成的二維離散空間，以將碰撞檢測問題轉化成在一個由兩物體特征對序號構成的離散空間中的復雜組合優(yōu)化問題；

多面體剖分模組，用于將三維空間的多面體剖分得到四面體的包圍盒，并行取多個四面體的包圍盒特征對；以及

并行碰撞檢測模組，利用粒子群優(yōu)化方法對提取的多個四面體包圍盒特征對并行求解，輸出結果及碰撞元素。

2.如權利要求1所述的一種基于粒子群優(yōu)化的并性碰撞檢測系統(tǒng)，其特征在于：該多面體剖分模組以包圍盒的中心點作為特征對象進行采樣。

3.如權利要求2所述的一種基于粒子群優(yōu)化的并性碰撞檢測系統(tǒng)，其特征在于，該并行碰撞檢測模組還包括：

初始化模組，用于隨機初始化粒子的位置與速度；

適應度計算模組，利用輔助進程并行計算所有粒子的適應度值，并發(fā)送給主控進程；

比較模組，利用主控進程接收到粒子的適應度值，將其與個體極值、全局極值比較，若該適應度值優(yōu)于此時粒子的個體極值或全局極值，則更新粒子的個體極值或全局極值，否則不進行更新；

判斷模組，用于判斷是否滿足終止條件，若滿足終止條件，則啟動輸出模組輸出結果及碰撞元素，否則啟動更新模組；

更新模組，根據位置更新公式及速度更新公式更新粒子的和速度，并啟動該適應度計算模組重新計算粒子的適應度值；以及

輸出模組，用于輸出結果及碰撞元素。

4.如權利要求3所述的一種基于粒子群優(yōu)化的并性碰撞檢測系統(tǒng)，其特征在于，該適應度計算模組采用如下公式計算適應度值：

F＝(a·x-b·x)²+(a·y-b·y)²+(a·z-b·z)²

其中{a，b}為一個特征對，(x，y，z)是真實的物體空間中點的坐標。

5.如權利要求4所述的一種基于粒子群優(yōu)化的并性碰撞檢測系統(tǒng)，其特征在于：若p_i＜pBest則pBest＝p_i，若p_i＜gBest，則gBest＝p_i，其中p_i為粒子的適應度值，pBest為個體極值，gBest為全局極值。

6.如權利要求5所述的一種基于粒子群優(yōu)化的并性碰撞檢測系統(tǒng)，其特征在于，該終止條件包括如下兩種：

一、如果要找出幾何模型之間所有的碰撞點，終止條件可以設為達到最大次數停止；

二、找到第一個干涉點以后則終止粒子的演化進程，但是若在演化進程中，一直沒有找到干涉點，則當粒子的演化代數達到最大數時停止運行。

7.如權利要求6所述的一種基于粒子群優(yōu)化的并性碰撞檢測系統(tǒng)，其特征在于，該速度更新公式與位置更新公式分別為：

v^k+1＝ω*v^k+c1*rand()*(pBest^k-x^k)+c2*rand()*(gBest^k-x^k)；

x^k+1＝x^k+v^k+1，

其中，v^k是粒子的速度，ω是慣性權重，x^k是當前粒子的位置，pBest^k，gBest^k分別是個體最優(yōu)解和全局最優(yōu)解，rand()是介于(0，1)之間的隨機數。c1，c2是學習因子。

8.如權利要求7所述的一種基于粒子群優(yōu)化的并性碰撞檢測系統(tǒng)，其特征在于：c1＝c2＝2。

9.一種基于粒子群優(yōu)化的并行碰撞檢測方法，包括如下步驟：

步驟一，構建三維空間內兩個物體之間存在的特征對構成的二維離散空間，以將碰撞檢測問題轉化成在一個由兩物體特征對序號構成的離散空間中的復雜組合優(yōu)化問題；

步驟二，將三維空間的多面體剖分得到四面體的包圍盒，并行取多個四面體的包圍盒特征對；以及

步驟三，利用粒子群優(yōu)化方法對提取的多個四面體包圍盒特征對并行求解，輸出結果及碰撞元素。