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

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

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

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