基于AABB包圍盒的文化粒子群碰撞檢測(cè)算法的研究與實(shí)現(xiàn).pdf

1、隨著虛擬現(xiàn)實(shí)技術(shù)和仿真技術(shù)的興起，快速、健壯的碰撞檢測(cè)檢測(cè)算法在虛擬現(xiàn)實(shí)、計(jì)算機(jī)游戲、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域扮演著重要角色。 在剛體對(duì)象的碰撞處理中，由于模型不會(huì)發(fā)生形變，所以其包圍盒等關(guān)鍵數(shù)據(jù)都可以在預(yù)處理階段處理完畢。對(duì)于軟體對(duì)象即變形體對(duì)象，由于在移動(dòng)時(shí)其對(duì)象頂點(diǎn)之間的相對(duì)位置要發(fā)生變化，導(dǎo)致包圍盒不斷發(fā)生改變，必須更新大量的數(shù)據(jù)以重構(gòu)包圍盒，而這種龐大的運(yùn)算量在虛擬現(xiàn)實(shí)系統(tǒng)中會(huì)嚴(yán)重影響到系統(tǒng)的實(shí)時(shí)性。因此，優(yōu)化碰撞檢測(cè)算法

2、的研究已成為虛擬現(xiàn)實(shí)領(lǐng)域的熱點(diǎn)。 粒子群優(yōu)化算法是一種新型的群體智能算法，系統(tǒng)初始化為一組隨機(jī)解，通過(guò)疊代搜尋最優(yōu)值。文化粒子群算法則將粒子群算法融合到文化算法框架中，它在群體空間的基礎(chǔ)上增加了一個(gè)知識(shí)空間，兩個(gè)空間交互通信，以指導(dǎo)粒子的優(yōu)化飛行，同時(shí)提高算法的收斂速度。 為了提高碰撞檢測(cè)的實(shí)時(shí)效率，本文提出了基于AABB包圍盒的文化粒子群優(yōu)化算法AABB-CAPSO。該算法首先利用AABB包圍盒做粗略檢測(cè)，如果變形體模型

3、碰撞后發(fā)生形變，則利用文化粒子群算法進(jìn)行精確的碰撞信息計(jì)算。本文將粒子群算法與文化算法相結(jié)合，組成基于粒子群算法的主群體空間和知識(shí)空間,兩空間獨(dú)立并行演化，下層主群體空間定期貢獻(xiàn)優(yōu)選個(gè)體給上層知識(shí)空間,上層知識(shí)空間經(jīng)演化后,也定期貢獻(xiàn)優(yōu)選個(gè)體給下層主群體空間,這種“雙演化雙促進(jìn)”機(jī)制避免了PSO可能因?yàn)椤霸缡臁爆F(xiàn)象而陷入局部最優(yōu)解，提高了AABB包圍盒尋優(yōu)更新數(shù)據(jù)的運(yùn)算效率。 本文的創(chuàng)新點(diǎn)在于將文化算法框架同粒子群算法相結(jié)合，基