群體動畫中碰撞檢測及避免方法研究.pdf

1、動漫產(chǎn)業(yè)是一個新興的產(chǎn)業(yè),它被視為是創(chuàng)意產(chǎn)業(yè)的一種,并被越來越多的國家和城市所重視和大力扶持,尤其是群體動畫.例如現(xiàn)在比較受人們關(guān)注的《變形金剛》、《熊貓功夫》等大型、經(jīng)典的群體動畫.然而群體動畫中除了復(fù)雜場景的設(shè)計(jì)、吸引人們眼球的角色造型等方面的研究外,角色之間的碰撞避免也成為制作群體動畫的核心技術(shù)之一;又由于現(xiàn)在計(jì)算機(jī)技術(shù)的迅速發(fā)展,人們對群體動畫的喜愛,使得碰撞檢測問題再一次成為研究的熱點(diǎn).現(xiàn)在碰撞檢測問題已經(jīng)成為計(jì)算機(jī)圖形學(xué)、群

2、體動畫、機(jī)器人路徑規(guī)劃、虛擬模擬等領(lǐng)域的研究熱點(diǎn).
　　現(xiàn)在自然界中動物群體運(yùn)動越來越多的受到人們的關(guān)注,很多人想利用計(jì)算機(jī)技術(shù)模擬這種群體運(yùn)動.首先是使用關(guān)鍵幀技術(shù)來生成動畫,這種技術(shù)無疑是對傳動手繪動畫技術(shù)的一種提高,但使用這種方法不但消耗動畫制作者大量的時間,制作出的動畫也比較機(jī)械簡單,缺乏自主性。隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展,群體動畫技術(shù)將計(jì)算機(jī)動畫提高到了一個更高的高度.群智能算法與群體動畫技術(shù)結(jié)合再一次提高了計(jì)算機(jī)動畫制作

3、技術(shù).現(xiàn)在較為流行的群智能算法主要有微粒群算法、蟻群算法、蜂群算法等.而微粒群算法(PSO算法)應(yīng)用最為廣泛.
　　PSO算法是模擬鳥群的捕食行為的一種優(yōu)化算法.PSO算法把優(yōu)化問題的解比喻為搜索空間中的一只只正在覓食的鳥,并稱之為“粒子”.用適應(yīng)值來評價“粒子”的優(yōu)劣,每個粒子除了具有速度大小屬性之外還有速度方向等屬性,并且每個“粒子”除了自己能夠得知當(dāng)前的適應(yīng)值之外還對上一步的適應(yīng)值有所記憶,并在得知自己當(dāng)前的適應(yīng)值之后,與記

4、錄的適應(yīng)值進(jìn)行比較,如果比上記錄的適應(yīng)值性能更好,則放棄所記錄的適應(yīng)值而保存當(dāng)前適應(yīng)值,否則,保持記錄不變,在每一步中每個“粒子”所保存的最優(yōu)值被稱為“個體極值 pBest”.同時對于整個鳥群來說還有一個引領(lǐng)者,此引領(lǐng)者是所有“粒子”中適應(yīng)值最好的那一個“粒子”即當(dāng)前代中最優(yōu)解,其它“粒子”會在它的帶領(lǐng)下一步一步的向食物靠近,當(dāng)前代整個鳥群所保存的最優(yōu)解成為“全局極值 gBest”.所以“粒子”都是通過跟蹤這兩個“極值”來更新自己的速度

5、大小、方向等屬性。
　　群體動畫與虛擬場景等對碰撞檢測精確度要求很高的技術(shù)有所不同,群體動畫對設(shè)備要求不是很高,這就要求檢測群體之間是否發(fā)生碰撞的算法簡單高效.一般簡單的碰撞檢測算法會出現(xiàn)角色穿透角色、角色穿透障礙物現(xiàn)象.
　　本文針對以上問題及一般的碰撞檢測算法速度慢問題提出了一種新的碰撞檢測算法——基于RMPSO的碰撞檢測算法,本算法分為兩個階段完成:粗魯階段、精確階段.由于標(biāo)準(zhǔn)的PSO算法具有容易陷入早熟、群體多樣性差

6、等缺點(diǎn),本文提出了一種改進(jìn)的RMPSO算法.RMPSO算法增加了群體的多樣性、提高了算法的準(zhǔn)確性,使PSO算法更加智能.為了避免角色之間出現(xiàn)穿透問題,本文將障礙物分為靜態(tài)障礙物(場景)與動態(tài)障礙物(群體角色)兩大類.對靜態(tài)障礙物采取以下策略:將角色看為一粒子,過粒子做障礙物的兩條切線,將粒子沿切線移動.為使制作出的動畫更加真實(shí),粒子應(yīng)選擇離自己目標(biāo)位置比較近的一邊移動,本文將采取一定的算法使其能夠沿靠近目標(biāo)點(diǎn)的一側(cè)移動.對動態(tài)障礙物的碰

7、撞避免策略為:減小步長的方法,如仍將發(fā)生碰撞,則采用暫停運(yùn)動的方式進(jìn)行碰撞避免.此方法既體現(xiàn)了角色之間相互禮讓的社會形態(tài),也解決了碰撞穿透問題.
　　本文基于HOOPS和ACIS平臺用C++編程實(shí)現(xiàn)對本算法的模擬,并將模擬中的場景和群體角色路徑數(shù)據(jù)進(jìn)行保存,最終用Maya軟件生成動畫.實(shí)驗(yàn)表明,改進(jìn)后的RMPSO算法比標(biāo)準(zhǔn)的PSO算法以及MPSO算法都具有更好的性能,尤其是在避免早熟現(xiàn)象以及提高群體的多樣性方面.同時將基于RMPS

8、O算法應(yīng)用于碰撞檢測算法,生成的動畫顯示:基于RMPSO碰撞檢測算法具有良好的性能.本文將其與基于PSO碰撞檢測算法進(jìn)行了比較,實(shí)驗(yàn)表明本算法不但能夠很好地避免群體之間的碰撞,在運(yùn)算速度方面也有一定的提高.
　　概括來說,本文的主要工作和創(chuàng)新點(diǎn)有以下三點(diǎn):
　　(1)分析了幾種主要的群智能算法的優(yōu)缺點(diǎn),尤其是標(biāo)準(zhǔn)的PSO算法的優(yōu)缺點(diǎn),并提出了一種多樣性更好,速度更快的RMPSO算法,最后通過實(shí)驗(yàn)證明RMPSO的有效性與高效性

9、。
　　(2)提出了一種新的快速的碰撞檢測算法——基于RMPSO的碰撞檢測算法,并與基于PSO的碰撞檢測算法進(jìn)行比較,證明了基于RMPSO的碰撞檢測算法的高效性以及多樣性。
　　(3)提出了一種簡單、智能的碰撞避免算法,解決了個體因避免碰撞障礙物而繞遠(yuǎn)的情況.使用此算法后,個體可以繞離目標(biāo)進(jìn)的一側(cè)移動,使個體更加的智能.
　　(4)基于.NET+HOOPS+ACIS平臺開發(fā)了一碰撞檢測算法系統(tǒng),將基于RMPSO碰撞檢測