董哲++蔡瓊++胡潔

摘 要：傳統(tǒng)動(dòng)畫(huà)制作軟件大多采用關(guān)鍵幀技術(shù)進(jìn)行創(chuàng)作，所創(chuàng)作的群體動(dòng)畫(huà)在真實(shí)性和智能性上存在一定不足。為使群體動(dòng)畫(huà)產(chǎn)生逼真的運(yùn)動(dòng)路徑，采用碰撞檢測(cè)和碰撞避免的方法模擬群體運(yùn)動(dòng)，并基于微粒群算法提出一種群體動(dòng)畫(huà)路徑自動(dòng)規(guī)劃方法。仿真實(shí)驗(yàn)結(jié)果表明，該方法能夠改變?nèi)后w動(dòng)畫(huà)運(yùn)動(dòng)路徑，快速有效地生成群體動(dòng)畫(huà)。

關(guān)鍵詞：群體動(dòng)畫(huà)；微粒群算法；路徑規(guī)劃

DOIDOI：10.11907/rjdk.151601

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）009003004

0 引言

人們經(jīng)常觀察到自然界的群體運(yùn)動(dòng)現(xiàn)象，比如螞蟻搬家、一群蜜蜂來(lái)到花叢中采蜜、候鳥(niǎo)遷徙、羊群遭遇危險(xiǎn)集體竄逃等。這些群體運(yùn)動(dòng)中的單個(gè)個(gè)體看上去行為自由、表現(xiàn)隨機(jī)且不受周圍環(huán)境干擾；但反觀由單個(gè)個(gè)體組成的整體，它們卻能夠朝著共同的目標(biāo)方向前進(jìn)，而且在前進(jìn)過(guò)程中維持相對(duì)的距離，個(gè)體與個(gè)體之間有很好的交互性。群體動(dòng)畫(huà)[1]是群體行為動(dòng)畫(huà)的簡(jiǎn)稱，是群體智能的一種應(yīng)用表現(xiàn)，主要用來(lái)研究和模擬群體與環(huán)境之間以及群體中個(gè)體之間的互動(dòng)行為。多媒體數(shù)字處理技術(shù)和計(jì)算機(jī)圖形學(xué)技術(shù)的飛速發(fā)展，以及計(jì)算機(jī)硬件成本的不斷降低，推動(dòng)了群體動(dòng)畫(huà)技術(shù)的發(fā)展和應(yīng)用。

群體動(dòng)畫(huà)是動(dòng)漫產(chǎn)業(yè)中的一個(gè)特殊成員，它具有大規(guī)模的群體數(shù)量、逼真的群體仿真效果，以及創(chuàng)作難度大且成本相對(duì)較高等特點(diǎn)。群體動(dòng)畫(huà)在游戲、娛樂(lè)、教育、軍事模擬、虛擬現(xiàn)實(shí)等多個(gè)領(lǐng)域發(fā)揮著重要作用。Chenney借助于勢(shì)場(chǎng)和能量場(chǎng)提出了一種稱作流動(dòng)條目的技術(shù)，用來(lái)代表和設(shè)計(jì)流動(dòng)場(chǎng)，并且提供了大城市街道上人群模擬的應(yīng)用實(shí)例。而WeiShao等在深入研究自主人體行為控制后，提出了一種新的模擬人群運(yùn)動(dòng)的控制方法，將自主行

人的感知模塊分為靜態(tài)感知序列圖和動(dòng)態(tài)感知序列圖兩個(gè)部分，并通過(guò)發(fā)放射線的方法感知外界環(huán)境，最后對(duì)車站人群運(yùn)動(dòng)進(jìn)行模擬實(shí)驗(yàn)，驗(yàn)證了該方法的有效性。

群智能算法起初針對(duì)群體運(yùn)動(dòng)，為了能夠更好地模擬群體運(yùn)動(dòng)，使得在群體動(dòng)畫(huà)中產(chǎn)生出更加逼真的運(yùn)動(dòng)路徑。本文對(duì)微粒群算法進(jìn)行研究和改進(jìn)，并將其應(yīng)用于群體動(dòng)畫(huà)的路徑規(guī)劃中。

1 基本特征和基本規(guī)則

目前，關(guān)于群體行為還沒(méi)有一個(gè)嚴(yán)格的定義，但人們對(duì)群體行為的特點(diǎn)已達(dá)成共識(shí)：①簡(jiǎn)單性。單個(gè)個(gè)體的智能程度相對(duì)簡(jiǎn)單；②自組織性。通過(guò)每個(gè)個(gè)體的獨(dú)立行為表現(xiàn)出群體行為的整體特性，群體中的單個(gè)個(gè)體運(yùn)動(dòng)看起來(lái)是隨機(jī)的，但就整個(gè)群體而言，卻是整體一致的；③魯棒性。單個(gè)個(gè)體的行為變化對(duì)整個(gè)群體的行為不會(huì)產(chǎn)生特別大的影響。

由于追求的是整個(gè)群體效應(yīng)，如果要對(duì)整個(gè)群體動(dòng)畫(huà)進(jìn)行模擬實(shí)驗(yàn)，單一個(gè)體運(yùn)動(dòng)時(shí)，會(huì)受到自身群體中其它單個(gè)個(gè)體運(yùn)動(dòng)路線的干擾，所以制作群體動(dòng)畫(huà)時(shí)應(yīng)該充分考慮如下規(guī)則：①群體中的單一個(gè)體應(yīng)該有屬于自己的運(yùn)動(dòng)區(qū)域，一旦剩余的單獨(dú)個(gè)體進(jìn)入此運(yùn)動(dòng)區(qū)域，那么單一個(gè)體本能地會(huì)保持固有距離，以保持單一個(gè)體的運(yùn)動(dòng)區(qū)域不被其他個(gè)體侵占，從而避免個(gè)體之間相互干擾帶來(lái)的碰撞；②從整體性來(lái)看，整個(gè)群體中的個(gè)體與其它個(gè)體應(yīng)該朝同一個(gè)方向、同一個(gè)目標(biāo)運(yùn)動(dòng)，具有統(tǒng)一性；③比較大的群體而言，應(yīng)當(dāng)細(xì)分成幾個(gè)比較小的群體，而且每一個(gè)小的群體通過(guò)自身?xiàng)l件判斷應(yīng)該與相鄰的比較小的群體重新組建成一個(gè)比較大的群體。

2 群體動(dòng)畫(huà)中的關(guān)鍵問(wèn)題

對(duì)群體動(dòng)畫(huà)的模擬需要注意以下兩個(gè)關(guān)鍵問(wèn)題：

（1）加大運(yùn)動(dòng)路徑逼真程度。在群體動(dòng)畫(huà)中使個(gè)體運(yùn)動(dòng)軌跡既符合各自運(yùn)動(dòng)的獨(dú)立性又能合乎群體運(yùn)動(dòng)規(guī)律，進(jìn)而能夠產(chǎn)生逼真的運(yùn)動(dòng)路徑，這是檢測(cè)判斷群體運(yùn)動(dòng)真實(shí)性的標(biāo)準(zhǔn)[2]，在產(chǎn)生運(yùn)動(dòng)路徑時(shí)，如何避免個(gè)體間的相互碰撞至關(guān)重要。

（2）提高群體運(yùn)動(dòng)速度。不能因?yàn)槟骋粋€(gè)體的速度而限制整體的運(yùn)動(dòng)速度，為更加強(qiáng)調(diào)群體的智能性，很大程度上增加了計(jì)算量，進(jìn)而影響了動(dòng)畫(huà)創(chuàng)作的實(shí)時(shí)性，影響了動(dòng)畫(huà)的生成速度。

3 微粒群算法

微粒群算法是一種群智能優(yōu)化算法，通過(guò)對(duì)環(huán)境的適應(yīng)性進(jìn)行評(píng)估，將群體中的一些個(gè)體移動(dòng)到較好區(qū)域，強(qiáng)調(diào)群體效果模型。在人工生命模型開(kāi)發(fā)和應(yīng)用中，群體智能很多優(yōu)點(diǎn)的實(shí)現(xiàn)都需要借助粒子群算法的思想。在研究過(guò)程中，如果需要將整個(gè)群體中的某些成員描述為沒(méi)有重量、沒(méi)有體積，而且還要描述這些成員的運(yùn)動(dòng)方向及運(yùn)動(dòng)速度等，就需要引入“粒子”概念代替這些描述。針對(duì)上述問(wèn)題，使用微粒來(lái)表示某一個(gè)隱含的解，這意味著每一個(gè)微粒存在一個(gè)通過(guò)優(yōu)化函數(shù)決定的適應(yīng)值，并且可以自定義速度，通過(guò)計(jì)算速度差值選擇偏離的路線。設(shè)置pbest為單個(gè)個(gè)體的極限值，表示微粒剛剛經(jīng)過(guò)的最優(yōu)化解；使用gbest為全局極限值，表示所有種群當(dāng)前的最優(yōu)解，通過(guò)這兩個(gè)極值來(lái)更新其位置和速度，使實(shí)驗(yàn)的微?？梢愿櫘?dāng)前的最優(yōu)微粒，找到自己的區(qū)域，并且落在最優(yōu)位置上。不斷循環(huán)這一過(guò)程，最終達(dá)到預(yù)期目的，找到最優(yōu)解。

在整個(gè)求解過(guò)程中，應(yīng)該首先明確局部和全局在整個(gè)搜索過(guò)程中所占比例，提出一種帶有權(quán)重的改進(jìn)微粒群算法，其方程如下：

vij（t+1）=wvij（t）+c1r1j（t）[pij（t）-xij（t）]+c2r2j（t）[pgj（t）-xij（t）]（1）

xij（t+1）=xij（t）+vij（t+1）（2）

其中，j=1，2，...，n； i=1，2，.....s； t表示迭代次數(shù)，w為慣性權(quán)重，如果w的值比較小，則局部的收斂能力會(huì)比較強(qiáng)，收斂速度可能會(huì)慢些，一旦w值逐漸增大，則會(huì)導(dǎo)致全局收斂能力比較強(qiáng)，而且收斂的速度也會(huì)變得很快。式（1）中，定義兩個(gè)加速常數(shù)C1和C2，微粒能夠通過(guò)自身?xiàng)l件判斷尋找更合適的位置；為了使群體多樣化，可以設(shè)定兩個(gè)隨機(jī)函數(shù)a1、a2；微粒根據(jù)自身的環(huán)境適應(yīng)性以及與其它鄰近微粒之間的信息交流動(dòng)態(tài)地調(diào)整自身速度，最終全部在最優(yōu)點(diǎn)上降落。由于粒子的速度沒(méi)有可控性，Vij設(shè)置在固定值內(nèi)。

4 路徑規(guī)劃

本文改變算法中的步驟和參數(shù)，并將修改的參數(shù)應(yīng)用到路徑規(guī)劃中，使其生成效果更加真實(shí)的路徑，為群體動(dòng)畫(huà)中的角色找到一條最好的運(yùn)動(dòng)路徑，是群體動(dòng)畫(huà)模擬研究中的關(guān)鍵。

4.1 碰撞檢測(cè)

關(guān)于碰撞的例子生活中較常見(jiàn)，比如汽車發(fā)生正面碰撞，發(fā)動(dòng)機(jī)能夠吸收沖擊力下沉脫出發(fā)動(dòng)機(jī)艙，提升車輛應(yīng)對(duì)沖擊時(shí)的安全性能。針對(duì)碰撞情況，采用相應(yīng)的防范措施必不可少。

碰撞檢測(cè)算法的種類很多，主要有如下幾類：基于空間剖分的碰撞檢測(cè)法、基于特征的碰撞檢測(cè)法和基于包圍盒碰撞檢測(cè)法[3]。

由于本文探討的是單一粒子運(yùn)動(dòng)情形，不需要外部干擾，采用基于包圍盒碰撞檢測(cè)方法，使用圓柱體的包圍盒，使得碰撞檢測(cè)過(guò)程更加簡(jiǎn)便。檢測(cè)過(guò)程中主要對(duì)距離進(jìn)行計(jì)算。包圍障礙物圓柱體的圓心位置用position[k]表示，粒子新變化后的新位置用y[k]表示，其中y為k維向量，粒子的運(yùn)動(dòng)過(guò)程是隨機(jī)的，粒子與障礙物之間設(shè)置一個(gè)距離值為d，如式（3）所示：

d=∑ki=1（x[i]-position[i]）2（3）

受實(shí)驗(yàn)條件限制，本文實(shí)驗(yàn)系統(tǒng)設(shè)置為3維，所以令k值為3，針對(duì)碰撞設(shè)定一個(gè)碰撞條件：粒子與障礙物之間的距離小于粒子半徑與障礙物半徑之和。很明顯，當(dāng)粒子半徑或者障礙物半徑足夠大時(shí)，粒子飛不過(guò)去，必然會(huì)發(fā)生碰撞。相應(yīng)地，粒子相互之間的碰撞檢測(cè)條件：兩個(gè)粒子的半徑之和大于飛躍障礙物的空間，公式如下：

d=∑ki=1（x1[i]-x2[i]）2（4）

個(gè)體在運(yùn)動(dòng)過(guò)程中難免會(huì)發(fā)生穿透現(xiàn)象，針對(duì)個(gè)體的運(yùn)動(dòng)步長(zhǎng)進(jìn)行調(diào)整，則不會(huì)看到穿透現(xiàn)象。由圖1可知，根據(jù)粒子群算法得到下一個(gè)粒子將要落入的位置A′，粒子一開(kāi)始在點(diǎn)A處，連接A到A′的距離，可以看到在點(diǎn)A′的位置上，A′O的距離已經(jīng)大于圓的半徑，也即粒子和障礙物之間的距離相對(duì)大一些，不滿足碰撞條件，則不會(huì)發(fā)生碰撞；但是通過(guò)AA′的虛線連線可以明顯地看到發(fā)生碰撞，那么僅僅對(duì)步長(zhǎng)作出調(diào)整在某些階段可以使粒子不會(huì)發(fā)生穿透。然而，在大多情況下如果步長(zhǎng)限制過(guò)小是不科學(xué)的，甚至?xí)l(fā)生某些異常情況。本文通過(guò)對(duì)兩個(gè)夾角大小的檢測(cè)來(lái)避免發(fā)生穿透。

從圖1可以看出，當(dāng)β>α?xí)r，粒子可以穿透到障礙物的另一側(cè)，當(dāng)β<α?xí)r，粒子不能穿透到障礙物的另一側(cè)。實(shí)驗(yàn)中，為看到明顯的檢測(cè)變化，可以設(shè)置另外一個(gè)點(diǎn)A″，如果按照之前設(shè)定的檢測(cè)方法和條件來(lái)判斷，粒子會(huì)穿透過(guò)去，不會(huì)產(chǎn)生規(guī)避，如此進(jìn)行下去會(huì)增大失誤率，不能帶來(lái)高效的探測(cè)效果。對(duì)本實(shí)驗(yàn)的碰撞方法性能進(jìn)行分析，設(shè)算法時(shí)間復(fù)雜度為O（n2）。實(shí)驗(yàn)?zāi)M中，為了達(dá)到更好的效果將粒子數(shù)目設(shè)定在55左右，當(dāng)障礙物的數(shù)量小于35時(shí)，可以看到非常真實(shí)的仿真效果，基本上能夠達(dá)到理想實(shí)驗(yàn)效果。

圖1 夾角大小比較

f（x）=沒(méi)有發(fā)生穿透，AA″

發(fā)生穿透，AA″≥AB（5）

4.2 碰撞避免

碰撞避免的策略雖有多種，但從根本上無(wú)非是等待和轉(zhuǎn)向兩種，其它碰撞避免策略都是在這兩種策略上進(jìn)行深化或者改進(jìn)得到。（1）等待法。顧名思義，就是等待另一運(yùn)動(dòng)個(gè)體先行通過(guò)，該方法適用于追尾碰撞和側(cè)面碰撞。在追尾碰撞時(shí)，后一障礙物可以先停止運(yùn)動(dòng)，等待前一障礙物運(yùn)動(dòng)到出口位置或者目標(biāo)點(diǎn)再繼續(xù)運(yùn)動(dòng)；在側(cè)面碰撞時(shí)，其中一個(gè)障礙物可以等待另一障礙物運(yùn)動(dòng)過(guò)碰撞點(diǎn)后再按照先前運(yùn)動(dòng)方向繼續(xù)運(yùn)動(dòng)。（2） 轉(zhuǎn)向法。正面碰撞時(shí)，在未來(lái)某一時(shí)點(diǎn)必然相撞，可以計(jì)算出一旦無(wú)碰撞，則向該方向運(yùn)動(dòng)；追尾碰撞時(shí)，如果前一障礙物運(yùn)動(dòng)速度過(guò)慢，而后面障礙物運(yùn)動(dòng)速度過(guò)快，使用等待法不切合實(shí)際，后一障礙物可以轉(zhuǎn)向另一無(wú)碰撞方向運(yùn)動(dòng)；側(cè)面碰撞時(shí)可以通過(guò)該方法轉(zhuǎn)向任一無(wú)碰撞方向來(lái)避免。

為了提升動(dòng)畫(huà)的真實(shí)美感，借鑒上述兩種碰撞避免方法?？煽吹綀D1中存在兩條邊界切線，試想粒子如果在邊界線外繞過(guò)則不會(huì)發(fā)生碰撞，為了不讓粒子發(fā)生穿透，則需要改變運(yùn)動(dòng)粒子的方向，可以設(shè)定為粒子連著邊界線移動(dòng)。

將點(diǎn)A定為起點(diǎn)， G定為終點(diǎn)，如果AA2與AG的夾角大于AA1與AG之間的夾角，通過(guò)在AA1上改變下一個(gè)定點(diǎn)位置，如果AA1與AG之間的夾角大于AA2與AG兩條線之間的夾角，則應(yīng)該在AA2上改變下一個(gè)定點(diǎn)位置?？赏ㄟ^(guò)縮小步長(zhǎng)的策略來(lái)解決粒子與粒子之間的碰撞，一旦啟動(dòng)停止模式，所有粒子都會(huì)靜止。通過(guò)對(duì)大規(guī)模粒子進(jìn)行路徑研究，具體示例變化如圖2所示，從左至右依次為初始化效果，中間為運(yùn)行多代后的效果，最右邊為自由運(yùn)動(dòng)路線，可以看出該方法的效果。

4.3 分散和聚集行為運(yùn)動(dòng)

群體的分散運(yùn)動(dòng)在大自然中隨處可見(jiàn)，比如當(dāng)羊群受到攻擊時(shí)四處逃竄。微粒群算法作為群體算法的一種，對(duì)群體分散運(yùn)動(dòng)路徑規(guī)劃的研究具有重要價(jià)值[4]，本文主要對(duì)算法中計(jì)算適應(yīng)度值（app）的方法作出修改。

圖2 粒子運(yùn)動(dòng)軌跡

app=（x-gx）2+（y-gy）2+（z-gz）2 （6）

其中，（x，y，z）表示離子的當(dāng)前位置，分散時(shí)的初始起點(diǎn)用坐標(biāo)點(diǎn)（gx，gy，gz）表示。根據(jù)公式可以計(jì)算出粒子的確切位置以及運(yùn)行速度，粒子可以定向移到很遠(yuǎn)。分散行為的算法應(yīng)用如下：

進(jìn)行初始化，首先設(shè)定起點(diǎn)位置，并設(shè)定粒子個(gè)數(shù)、群體的迭代次數(shù)，以及粒子最初軸線的范圍加速常數(shù)c1、c2等。

while（當(dāng)前迭代次數(shù)未達(dá)到提前設(shè)定的最大次數(shù)）{

Step1：選擇每個(gè)粒子的目標(biāo)位置，計(jì)算每個(gè)粒子新位置的app值，對(duì)每個(gè)粒子進(jìn)行計(jì)算，若粒子的app值優(yōu)于原來(lái)的個(gè)體極限值pbest，那么設(shè)置當(dāng)前app值為個(gè)體的極限值pbest；Step2：由粒子的個(gè)體極限值pbest的計(jì)算結(jié)果找出全局極值；Step3：更新微粒速度并將更新后的速度值限制在最大設(shè)定值內(nèi)；Step4：采取碰撞檢測(cè)方法，若發(fā)生碰撞情形，則實(shí)行相應(yīng)的避免策略；Step5：重新設(shè)定原來(lái)的位置和速度；}

聚集行為是一種普遍存在的生物運(yùn)動(dòng)行為，聚集算法同樣采用微粒群方法。由于聚集行為與分散行為是兩個(gè)相對(duì)層面，因此可以使用一種對(duì)立的計(jì)算公式，設(shè)定一個(gè)警示值h，讓最終的落點(diǎn)成為中心，以警示值h為半徑，所有落入該半徑內(nèi)的點(diǎn)都可為靜止?fàn)顟B(tài)，并且通過(guò)改變app值，使得粒子分散開(kāi)來(lái)，防止集中在某一點(diǎn)上，同樣，參數(shù)坐標(biāo)值設(shè)定如下：

app=（x-gx）2+（y-gy）2+（z-gz）-rand（h）（7）

4.4 仿真實(shí)驗(yàn)

借助于Visual Studio 2008和ACIS等平臺(tái)，同時(shí)采

用HOOPs框架模型，將路徑規(guī)劃產(chǎn)生的數(shù)據(jù)導(dǎo)入Maya 軟件中，根據(jù)變化的場(chǎng)景和不同的動(dòng)畫(huà)效果來(lái)完成仿真實(shí)驗(yàn)?zāi)M。實(shí)驗(yàn)結(jié)果如圖3所示，圖3（a）是通過(guò)讀取數(shù)據(jù)生成的路徑曲線圖，圖3（b）是動(dòng)畫(huà)與場(chǎng)景相互融合的圖形，圖3（c）是最終生成的動(dòng)畫(huà)效果。

圖3 仿真效果

5 結(jié)語(yǔ)

本文對(duì)群體動(dòng)畫(huà)路徑規(guī)劃方法進(jìn)行了研究，并對(duì)微粒群算法的系列參數(shù)作出了調(diào)整。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的方法相對(duì)于傳統(tǒng)的基于關(guān)鍵幀技術(shù)的方法而言，能夠更好地提高群體動(dòng)畫(huà)的生成效率，進(jìn)一步提高真實(shí)程度。后續(xù)研究中，將進(jìn)一步研究其它群體算法優(yōu)勢(shì)，以找出更有效的方法運(yùn)用于群體動(dòng)畫(huà)中。

參考文獻(xiàn)參考文獻(xiàn)：

[1] 涂曉媛.人工魚(yú)計(jì)算機(jī)動(dòng)畫(huà)的人工生命方法[M].北京：清華大學(xué)出版社，2001：610.

[2] 魏麗.群體動(dòng)畫(huà)中路徑自動(dòng)規(guī)劃方法研究[J].計(jì)算機(jī)工程與應(yīng)用，2012（25）：8387.

[3] 張淑軍，班曉娟，陳勇，等.基于記憶的人工魚(yú)認(rèn)知模型[J].計(jì)算機(jī)工程，2007（19）：56.

[4] 鄭慧杰，劉弘，鄭向偉.基于改進(jìn)群搜索優(yōu)化算法的群體路徑規(guī)劃方法[J].計(jì)算機(jī)應(yīng)用，2012（8）：1013.

責(zé)任編輯（責(zé)任編輯：陳福時(shí)）