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

無效

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

技術(shù)領(lǐng)域

本發(fā)明關(guān)于一種并行碰撞檢測(cè)系統(tǒng)及方法，特別是涉及一種基于粒子群優(yōu)化的并行碰撞檢測(cè)系統(tǒng)及方法。

背景技術(shù)

碰撞問題多年來一直受到較多的關(guān)注，碰撞檢測(cè)方法在計(jì)算幾何、計(jì)算機(jī)動(dòng)畫、CAD/CAM，仿真機(jī)器人和虛擬現(xiàn)實(shí)等領(lǐng)域中都有較好的應(yīng)用前景。

近二十多年來，研究人員在碰撞檢測(cè)領(lǐng)域中做了相當(dāng)多有意義的工作。提出一些較為成熟的方法。從總體上將這些方法分為兩大類：幾何分解法和分層包圍盒法。前者是將整個(gè)虛擬空間劃分為相等體積的小的單元格，只對(duì)占居了同一單元格或相鄰單元格的幾何對(duì)象進(jìn)行相交計(jì)算。比較典型的例子有：八叉樹、k-d樹、BSP樹等。這類方法的特點(diǎn)為：方法復(fù)雜、精度高。分層包圍盒的核心思想是用體積略大而幾何特性簡(jiǎn)單的包圍盒來近似地描述復(fù)雜的幾何對(duì)象，從而通過判斷包圍盒是否重疊來粗略估計(jì)兩檢測(cè)對(duì)象是否碰撞，此外可以通過構(gòu)造樹狀分層結(jié)構(gòu)一步步逼近幾何模型，提高檢測(cè)精度。分層包圍盒由于其方法簡(jiǎn)單、效率相對(duì)高，也是一種廣泛應(yīng)用的碰撞檢測(cè)方法。但其檢測(cè)精度較低。

另外，現(xiàn)有的動(dòng)態(tài)碰撞檢測(cè)方法自身還存在一些問題：如檢測(cè)中刺穿現(xiàn)象和遺漏情況等。傳統(tǒng)的多物體間的碰撞檢測(cè)方法一般時(shí)間復(fù)雜度為O(n2)，不能滿足實(shí)時(shí)性的要求，不利于碰撞檢測(cè)快速實(shí)現(xiàn)。基于空間分割技術(shù)的幾何分解方法，影響該方法效率的一個(gè)重要因素是分區(qū)的多少，而分區(qū)的數(shù)目又較難把握。八叉樹和其它幾何模型在解決碰撞檢測(cè)的框架之間的幾何干涉問題時(shí)，不會(huì)大幅度提高方法效率。采用分層包圍盒技術(shù)來加速多面體場(chǎng)景的碰撞檢測(cè)，但一般的包圍盒方法作為一個(gè)整體的方法，檢測(cè)精度低，效率提高并不明顯。

發(fā)明內(nèi)容

為克服上述現(xiàn)有技術(shù)存在的不足，本發(fā)明之一目的在于提供一種基于粒子群優(yōu)化的并行碰撞檢測(cè)系統(tǒng)及方法，其可以在提高碰撞檢測(cè)速度的同時(shí)保證較高的精度，而且適用于大規(guī)模復(fù)雜場(chǎng)景的實(shí)時(shí)動(dòng)態(tài)碰撞檢測(cè)。

為達(dá)上述及其它目的，本發(fā)明提出一種基于粒子群優(yōu)化的并性碰撞檢測(cè)系統(tǒng)，至少包括：

構(gòu)建搜索空間模組，用于構(gòu)建三維空間內(nèi)兩個(gè)物體之間存在的特征對(duì)構(gòu)成的二維離散空間，以將碰撞檢測(cè)問題轉(zhuǎn)化成在一個(gè)由兩物體特征對(duì)序號(hào)構(gòu)成的離散空間中的復(fù)雜組合優(yōu)化問題；

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

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

進(jìn)一步地，該多面體剖分模組以包圍盒的中心點(diǎn)作為特征對(duì)象進(jìn)行采樣。

進(jìn)一步地，如權(quán)利要求2所述的一種基于粒子群優(yōu)化的并性碰撞檢測(cè)系統(tǒng)，其特征在于，該并行碰撞檢測(cè)模組還包括：

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

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

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

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

更新模組，根據(jù)位置更新公式及速度更新公式更新粒子的和速度，并啟動(dòng)該適應(yīng)度計(jì)算模組重新計(jì)算粒子的適應(yīng)度值；以及

輸出模組，用于輸出結(jié)果及碰撞元素。

進(jìn)一步地，該適應(yīng)度計(jì)算模組采用如下公式計(jì)算適應(yīng)度值：

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

其中{a，b}為一個(gè)特征對(duì)，(x，y，z)是真實(shí)的物體空間中點(diǎn)的坐標(biāo)。

進(jìn)一步地，若p_i＜pBest則pBest＝p_i，若p_i＜gBest，則gBest＝p_i，其中p_i為粒子的適應(yīng)度值，pBest為個(gè)體極值，gBest為全局極值。

進(jìn)一步地，該終止條件包括如下兩種：

一、如果要找出幾何模型之間所有的碰撞點(diǎn)，終止條件可以設(shè)為達(dá)到最大次數(shù)停止；

二、找到第一個(gè)干涉點(diǎn)以后則終止粒子的演化進(jìn)程，但是若在演化進(jìn)程中，一直沒有找到干涉點(diǎn)，則當(dāng)粒子的演化代數(shù)達(dá)到最大數(shù)時(shí)停止運(yùn)行。

進(jìn)一步地，該速度更新公式與位置更新公式分別為：