群體動(dòng)畫中碰撞檢測(cè)及避免方法研究.pdf

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

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

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

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

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

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

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

8、O算法應(yīng)用于碰撞檢測(cè)算法,生成的動(dòng)畫顯示:基于RMPSO碰撞檢測(cè)算法具有良好的性能.本文將其與基于PSO碰撞檢測(cè)算法進(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)提出了一種新的快速的碰撞檢測(cè)算法——基于RMPSO的碰撞檢測(cè)算法,并與基于PSO的碰撞檢測(cè)算法進(jìn)行比較,證明了基于RMPSO的碰撞檢測(cè)算法的高效性以及多樣性。
　　(3)提出了一種簡(jiǎn)單、智能的碰撞避免算法,解決了個(gè)體因避免碰撞障礙物而繞遠(yuǎn)的情況.使用此算法后,個(gè)體可以繞離目標(biāo)進(jìn)的一側(cè)移動(dòng),使個(gè)體更加的智能.
　　(4)基于.NET+HOOPS+ACIS平臺(tái)開發(fā)了一碰撞檢測(cè)算法系統(tǒng),將基于RMPSO碰撞檢測(cè)