黃東晉 段思文 雷雪 梁景坤

摘 要：影視作品中采用群體隊形控制技術(shù)來制作大量角色處于某種隊形運(yùn)動的場景，但許多群體隊形技術(shù)往往側(cè)重于對自由移動的個體角色進(jìn)行控制，而忽視了對隊形運(yùn)動的整體控制，導(dǎo)致場景畫面缺乏美感性、整體性和條理性。針對這些問題，提出了基于Voronoi圖的群體隊形控制方法。首先，將群體隊形進(jìn)行Voronoi圖空間劃分，建立一個包含所有智能體的隊形網(wǎng)格;然后，提出一種新的群體隊形形變算法，采用人工勢能場和相對速度障礙法進(jìn)行合理避障，再結(jié)合彈簧系統(tǒng)使群體隊形在形變過程中盡可能保持整體穩(wěn)定;最后，采用Lloyd算法快速恢復(fù)到目標(biāo)隊形。實(shí)驗(yàn)結(jié)果表明，該方法可以很好地模擬群體隊形變換運(yùn)動，適用各種復(fù)雜場景，具有美感、整體、條理的隊形變換效果。

關(guān)鍵詞：群體仿真;隊形控制;Voronoi圖;彈簧系統(tǒng);Lloyd算法

中圖分類號： TP391.9

文獻(xiàn)標(biāo)志碼：A

Abstract： Group formation control technologies are ofen used for the film formation scenes of a large number of characters in film and television works， but a lot of group formation technologies tend to focus on the free-moving individual characters without considering the overall control of the formation， which causes the scene picture a lack of beauty， integrity and organization. In order to solve these problems， a group formation control method based on Voronoi diagram was proposed. Firstly， the group formation was divided into Voronoi diagram spaces to create a formation grid containing all the agents. Then， a new group formation deformation algorithm was proposed， in which artificial potential energy field and relative speed obstacle method were used to reasonably avoid obstacles， and a spring system was combined to keep the formation as stable as possible in the deformation process. Finally， Lloyd algorithm was used to quickly restore the target formation. The experimental results show that， the proposed method can simulate the group formation transformation motion well， is suitable for various complex scenes， and has an aesthetic， overall and organized formation transformation effect.

Key words： group simulation; formation control; Voronoi diagram; spring system; Lloyd algorithm

0 引言

群體隊形控制是指多個移動智能體在運(yùn)動過程中，受環(huán)境約束或客觀條件限制，整體保持預(yù)定隊形或變換至新隊形的過程[1]，被廣泛運(yùn)用于影視動畫、軍事演練、藝術(shù)體育、游戲等領(lǐng)域，其中在影視動畫方面應(yīng)用較為突出。群體隊形控制技術(shù)在影視方面主要是輔助呈現(xiàn)大規(guī)模群集數(shù)字角色隊形運(yùn)動行為的特效鏡頭，主要體現(xiàn)在千軍萬馬、排兵布陣，對陣殺敵等宏偉壯觀的大場面，如《星河戰(zhàn)隊》的野獸大軍、《僵尸世界大戰(zhàn)》中的恐怖僵尸、《從秦始皇到漢武帝》的士兵隊伍等。采用傳統(tǒng)的實(shí)拍技術(shù)需要大量的群眾演員，花費(fèi)很多時間進(jìn)行多次拍攝才能完成，且難以達(dá)到理想的效果。通過借助計算機(jī)群體隊形控制技術(shù)，可以大大節(jié)省人力財力物力，并提高視覺效果。

隨著群體隊形控制技術(shù)被越來越多地應(yīng)用到影視作品中，人們對群體動畫隊形控制模擬的要求也日益提高。目前的仿真方法側(cè)重使單個智能體保持某種特定的位置，涉及群體隊形整體控制的方法較少，普遍存在隊伍角色之間協(xié)同能力差、整體性和穩(wěn)定性不太好等問題。因此，提高角色彼此間的耦合度、提高隊形變換的穩(wěn)定性和整體性是當(dāng)前的研究重點(diǎn)和難點(diǎn)。

針對上述問題，本文提出了基于Voronoi圖的群體隊形控制方法，該方法使用Voronoi圖進(jìn)行隊形網(wǎng)格的劃分，采用人工勢能場和相對速度障礙物（Reciprocal Velocity Obstacle， RVO）進(jìn)行避障，再結(jié)合彈簧系統(tǒng)使群體隊形在避障過程中盡可能保持隊形形變的整體穩(wěn)定，通過Lloyd算法實(shí)現(xiàn)群體隊形的快速恢復(fù)。實(shí)驗(yàn)結(jié)果表明，本文提出的方法可以使智能體在隊形變化時避免發(fā)生阻塞現(xiàn)象，維持隊形的整體形變;同時，在智能體避開障礙物后能盡快恢復(fù)目標(biāo)隊形，提高隊形的整體穩(wěn)定性。

1 相關(guān)工作

隨著計算機(jī)群體動畫技術(shù)的快速發(fā)展，群體隊形變換仿真技術(shù)被廣泛地應(yīng)用到各個領(lǐng)域，如何利用計算機(jī)仿真出形象逼真的群體隊形變換成為計算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)等技術(shù)領(lǐng)域的學(xué)者們一直以來研究的熱點(diǎn)。目前，群體隊形控制技術(shù)主要是從隊形劃分、隊形變形和隊形恢復(fù)三個方面進(jìn)行研究。

1）群體隊形劃分。Henry等[2]提出了一種單遍算法來控制復(fù)雜環(huán)境中的人群，將人群隊伍進(jìn)行可變形的網(wǎng)格劃分，該方法有效減少了阻塞現(xiàn)象并提高了智能體的全局移動效率;但同時也增加了算法的計算代價。李祖寧等[3]采用改進(jìn)的網(wǎng)格引導(dǎo)方法，對群體隊形進(jìn)行三角網(wǎng)格劃分，利用可變形網(wǎng)格的特征對具有特定隊形的群體運(yùn)動進(jìn)行控制，提高了算法效率;但群體隊形仿真的真實(shí)性有待提高。鄭利平等[4]提出一種基于幾何約束機(jī)制的受限異構(gòu)群體隊形控制方法，將基于質(zhì)心的容量限制Power圖（Centroidal Capacity Constrained Power Diagram， CCCPD）應(yīng)用到群體隊形的個體中，產(chǎn)生所需的異構(gòu)分布，使群體隊形的變化平滑流暢;但在高階非均勻密度場下不穩(wěn)定。

2）群體隊形變形。Anderson等[5] 為實(shí)現(xiàn)對群體動畫結(jié)果的約束或控制，提出一種生成受約束組動畫的新技術(shù)。在文獻(xiàn)[6]的Boids行為模型基礎(chǔ)上，提出了帶有約束的鳥群動畫;但是基于Boids模型的群體動畫技術(shù)在變形過程中群體成員大多排列雜亂，中間隊形過渡不夠光滑。紀(jì)慶革等[7]設(shè)計了一個團(tuán)體操編排和演練原型系統(tǒng)，運(yùn)用了實(shí)時繪制、運(yùn)動建模、路徑規(guī)劃和碰撞避免等技術(shù)，實(shí)現(xiàn)了在大規(guī)模場景中群體隊形有規(guī)則的變形模擬;但僅限于團(tuán)體操運(yùn)動，具有局限性。Xu等[8]提出了一種新的基于圖形約束的群動畫系統(tǒng)，通過采樣、對應(yīng)和應(yīng)用局部控制規(guī)則實(shí)現(xiàn)了群體在約束隊形間的變形， 得到了良好的三維變形和群組動畫效果;但是在變形過程中群體成員大多排列雜亂無章，中間隊形過渡不平滑，適合生成鳥群、昆蟲等非人物的群組動畫。Kwon等[9]提出了一種整體編輯群體運(yùn)動的方法，利用拉普拉斯網(wǎng)格變形方法對已有的群體隊形進(jìn)行變換和連接，從而形成大規(guī)模群體動畫;但需通過固定的拖動路徑完成群體隊形運(yùn)動變形，缺乏自主性。梁家海[10]利用人工勢場法、行為融合、領(lǐng)航者法，解決移動機(jī)器人編隊運(yùn)動中的避障、避碰、到達(dá)目標(biāo)的問題，實(shí)現(xiàn)移動機(jī)器人編隊的多樣性、穩(wěn)定性和隊形變換連續(xù)性;但缺乏整體性。

3）群體隊形恢復(fù)。柴運(yùn)等[11]提出基于多跳式網(wǎng)絡(luò)技術(shù)的編隊控制方法，通過引入絕對位置和相對速度以及二層鄰居信息來設(shè)計二階一致性協(xié)議，設(shè)計了多智能體的編隊控制方法，可以使多智能體更快地達(dá)到期望的編隊隊形;但缺乏多樣性。李健等[12]采用一種基于隊形約束的群體運(yùn)動編輯與控制方法，利用貪心算法構(gòu)建從初始隊形到目標(biāo)隊形中個體位置的配對關(guān)系，實(shí)現(xiàn)群體隊形運(yùn)動的恢復(fù)控制，提高群體隊形制作的效率;但不適宜具有嚴(yán)格變換規(guī)則的隊形。鄭利平等[13]提出基于幾何約束機(jī)制的團(tuán)體操隊形輔助設(shè)計平臺，從隊形約束、個體分布、個體配對、個體運(yùn)動路徑規(guī)劃、群體碰撞避免等方面，綜合提出一種群體隊形變換解決方案，該方法的隊形恢復(fù)平滑流暢;但未考慮避障，且效率不高。

綜合上述分析，群體隊形在運(yùn)動過程中，容易出現(xiàn)阻塞，隊形形變整體分散等現(xiàn)象，因而提高群體隊形運(yùn)動過程中的整體性和穩(wěn)定性是本文研究重點(diǎn)。

2 群體隊形網(wǎng)格生成

為了保證群體隊形的整體性，群體隊形在移動的過程中，智能體之間要保持相對位置不變的傾向，在進(jìn)行碰撞避免時應(yīng)當(dāng)盡可能使整體隊形的變化最小，并且當(dāng)群體隊形形變后，隊伍需要快速恢復(fù)到目標(biāo)隊形。由于Voronoi圖的形成只與其生成的相鄰站點(diǎn)有關(guān)，具有局部特征性，當(dāng)整體發(fā)生平移或者形變時，Voronoi圖的變化是輕微的、少量的，可以保持隊形的穩(wěn)定性。因此，采用Voronoi圖進(jìn)行隊形網(wǎng)格的生成，具體流程如圖1所示。

首先對場景中的個體進(jìn)行分組，分別將同一群組內(nèi)的所有個體位置存入隊列。然后根據(jù)Delaunay三角剖分算法對該隊列中的點(diǎn)進(jìn)行三角剖分，形成一個三角形鏈表，再找出三角網(wǎng)格每一個三角形的外接圓圓心，最后連接相鄰三角形的外接圓圓心，形成以每一個三角形頂點(diǎn)為生成元的Voronoi圖[14]，即隊形網(wǎng)格，其Voronoi圖生成過程圖如圖2所示，其中圖2（a）為智能體的分布位置，圖2（b）根據(jù)Delaunay三角網(wǎng)格生成Voronoi圖，圖2（c）為最終得到的Voronoi圖網(wǎng)格。

3 群體隊形變形

人工勢能場法[15]的基本思想是給環(huán)境中的目標(biāo)點(diǎn)引力勢場，障礙物斥力勢場，群體隊形中的每個智能體在人工勢能場的引力和斥力的合力作用下朝目標(biāo)點(diǎn)運(yùn)動，并規(guī)劃出一條平滑無碰撞的路徑。對于靜態(tài)障礙物，通過人工勢能場可以產(chǎn)生避免碰撞的平滑路徑，但是在影視制作過程中，三維場景必然存在動態(tài)障礙，比如兩支隊伍迎面相遇，本文采用相對速度障礙法（RVO）[16]可以使個體之間合理避讓。

群體隊形在避障過程中，每個個體因?yàn)樗幬恢貌煌瑫艿讲煌较虻牧?，促使它們各自有不同的運(yùn)動軌跡，特別是當(dāng)碰到較大障礙物時，會出現(xiàn)使隊形割裂分散現(xiàn)象，導(dǎo)致群體隊形形變的整體性被破壞。本文采用虛擬彈簧系統(tǒng)的思想來控制隊形的形變來解決上述問題，將隊伍進(jìn)行網(wǎng)格化，構(gòu)建一個覆蓋整個隊伍的平面三角形網(wǎng)格W（N，L），其中，N={Ni}為網(wǎng)格中的頂點(diǎn)集， L={Lij}為網(wǎng)格中的邊集。該三角形網(wǎng)格與初始隊形中的Voronoi網(wǎng)格的對偶Delaunay三角形一樣。將三角網(wǎng)格的每條邊看作一根彈簧，則整個三角網(wǎng)格構(gòu)成一個彈簧系統(tǒng)。進(jìn)入障礙范圍的智能體，其運(yùn)動方向和速度在吸引力和排斥力的合力作用下發(fā)生變換，彈簧系統(tǒng)發(fā)生動態(tài)伸縮形變，而沒有到達(dá)障礙勢能場范圍的智能體為了保持彈簧系統(tǒng)的新平衡，自發(fā)調(diào)整方向和位移，進(jìn)而形成變形網(wǎng)格。

如圖3所示，線段彈簧模型系統(tǒng)，將每一根彈簧的平衡長度設(shè)置為其變形前的長度。當(dāng)群體隊形中的某些智能體在障礙勢場的作用下，發(fā)生形變位移，其他智能體會調(diào)整自身位置，即通過運(yùn)用胡克定律來控制其自身位移，使彈簧系統(tǒng)達(dá)到平衡，所有彈簧頂點(diǎn)的合力都應(yīng)該為0，以此來調(diào)整智能體的方向。

4 群體隊形恢復(fù)

群體隊形通過障礙物發(fā)生形變后，虛擬彈簧系統(tǒng)消失，為了能夠平滑、流暢地恢復(fù)到目標(biāo)隊形，運(yùn)用Lloyd路徑規(guī)劃算法使群體隊形中的智能體向中間隊形移動直至達(dá)到目標(biāo)隊形。因?yàn)楫?dāng)群體隊形開始向目標(biāo)隊形移動變換時，隊形的網(wǎng)格由于處與形變階段，每個網(wǎng)格的站點(diǎn)并不處于該Voronoi圖的質(zhì)心處，并且個體之間的相對位置變化比較嚴(yán)重，在此過程中如果只是簡單地讓群體隊形從原始位置變化到目標(biāo)位置，很多情況下會出現(xiàn)交叉和碰撞甚至混亂現(xiàn)象，運(yùn)用Lloyd[17]完成從任意初始點(diǎn)到最終基于質(zhì)心的Voronoi圖（Centroidal Voronoi Tessellation， CVT）布局之間的移動，可以實(shí)現(xiàn)條理的恢復(fù)到目標(biāo)隊形的變換結(jié)果。Lloyd算法迭代過程中會重復(fù)計算子點(diǎn)集的中心，并以距離中心最近為原則重新劃分區(qū)域，使智能體移向質(zhì)心。每執(zhí)行一次迭代，站點(diǎn)分布便愈加均勻。在Voronoi圖中，使用Lloyd進(jìn)行智能體移動處理，用于優(yōu)化站點(diǎn)分布，可逐步逼近質(zhì)心，最終使所有站點(diǎn)都處于對應(yīng)Voronoi區(qū)域的質(zhì)心處，即CVT分布，恢復(fù)初始隊形。圖4為恢復(fù)過程的示意圖，恢復(fù)過程的具體步驟描述如下：

5 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文算法的有效性，設(shè)計四組實(shí)驗(yàn)分別在Unity 3D引擎上分別進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)的硬件配置為Intel Xeon CPU E5-2620 v4 @2.10GHz的處理器，64.0GB的內(nèi)存，NVIDIA TITAN Xp的顯卡。

實(shí)驗(yàn)一：設(shè)計群體隊形形變控制的對比實(shí)驗(yàn)，驗(yàn)證形變算法的有效性。

實(shí)驗(yàn)二：設(shè)計群體隊形恢復(fù)的對比實(shí)驗(yàn)，驗(yàn)證網(wǎng)格劃分和Lloyd算法在隊形恢復(fù)階段的高效性。

實(shí)驗(yàn)三：模擬不同群體相遇以及避讓的情景，驗(yàn)證群體隊形控制算法在動態(tài)避障方面的有效性

實(shí)驗(yàn)四：在不同的場景下從初始階段、變形階段和恢復(fù)階段三個方面進(jìn)行實(shí)驗(yàn)，驗(yàn)證本文提出的算法在群體隊形形變控制方面的有效性和穩(wěn)定性。

5.1 實(shí)驗(yàn)一

將加入彈簧系統(tǒng)的勢能場與未加入彈簧系統(tǒng)的勢能場的隊形變形情況進(jìn)行對比。圖5（a）為采用人工勢能場的路徑，圖5（b）為加入彈簧系統(tǒng)的人工勢能場路徑。從圖5（a）可以看出，群體隊形運(yùn)用人工勢場法躲避障礙物時，在力的作用下會使隊形分散;而從圖5（b）可以看出，加入彈簧系統(tǒng)后，準(zhǔn)備朝另一個方向避開障礙物的個體在彈力的作用下重新回到原始路徑中，保持了隊形的整體性和穩(wěn)定性：表明本文變形算法可以較好地保證隊形的整體性。

5.2 實(shí)驗(yàn)二

圖6（a）使用給每個個體指定目標(biāo)位置的隊形恢復(fù)方法，圖6（b）采用加入Lloyd算法的隊形恢復(fù)方法，分別將這兩種方法在t=3s、t=6s以及隊形何時完成恢復(fù)的情況進(jìn)行了對比，t=0s為初始隊形。表1將最終恢復(fù)目標(biāo)隊形所需的時間以及整個過程中個體相互碰撞交叉的次數(shù)進(jìn)行對比。從圖6（a）可以看出，群體隊形在恢復(fù)過程中多次出現(xiàn)交叉碰撞甚至混亂現(xiàn)象，當(dāng)t=10s時，形變隊形才完成恢復(fù);從圖6（b）可以看出，加入Lloyd算法后，隊形碰撞和交叉的現(xiàn)象明顯減少，當(dāng)t=8s時，隊形已經(jīng)完成恢復(fù)，效率更高。

6 結(jié)語

本文提出了基于Voronoi圖的群體隊形控制算法，將整個隊形劃分成一個包含所有智能體的Voronoi圖隊形網(wǎng)格，然后運(yùn)用人工勢能場和RVO進(jìn)行合理避障，再結(jié)合虛擬彈簧系統(tǒng)使隊形在形變過程中保持整體穩(wěn)定，最后采用Lloyd算法快速恢復(fù)群體目標(biāo)隊形，實(shí)現(xiàn)了群體智能體在虛擬環(huán)境中的隊形變換。

實(shí)驗(yàn)結(jié)果表明，本文提出的算法能夠使隊形在障礙環(huán)境中實(shí)現(xiàn)良好的群體避障，且維持隊形的整體形變效果，驗(yàn)證了本文算法的可行性和有效性。下一步，我們將繼續(xù)完善復(fù)雜場景中的隊形變換方法，將其應(yīng)用到影視預(yù)演系統(tǒng)中，提高隊形形變和隊形恢復(fù)的效率。

參考文獻(xiàn) （References）

[1] CHEN Y Q， WANG Z M. Formation control： a review and a new consideration [C]// Proceedings of the 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway， NJ： IEEE， 2005： 3181-3186.

[2] HENRY J， SHUM H P， KOMURA T. Interactive formation control in complex environments [J]. IEEE Transactions on Visualization & Computer Graphics， 2014， 20（2）： 211-222.

[3] 李祖寧，何武.可變形網(wǎng)格引導(dǎo)的群體隊形仿真[J].中國圖象圖形學(xué)報，2017，22（7）：969-977.（LI Z N， HE W. Deformable guiding mesh-based simulation of group formation [J]. Journal of Image and Graphics， 2017， 22（7）： 969-977.）

[4] 鄭利平，程亞軍，周乘龍，等.異構(gòu)群體隊形光滑變換控制方法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2015，27（10）：1963-1970.（ZHENG L P， CHENG Y J， ZHOU C L， et al. Research on smooth formation control of heterogeneous crowds [J]. Journal of Computer-Aided Design & Computer Graphics， 2015， 27（10）： 1963-1970.）

[5] ANDERSON M， MCDANIEL E， CHENNEY S. Constrained animation of flocks [C]// Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Aire-la-Ville， Switzerland： Eurographics Association， 2003： 286-297.

[6] REYNOLDS C W. Flocks， herds and schools： a distributed behavioral model [J]. ACM SIGGRAPH Computer Graphics， 1987， 21（4）： 25-34.

[7] 紀(jì)慶革，潘志庚，梅林，等.團(tuán)體操虛擬編排和演練原型系統(tǒng)[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2004，16（9）：1185-1190.（JI Q G， PAN Z G， MEI L， et al.Virtual arrangement and rehearsal of group calisthenics [J]. Journal of Computer-Aided Design & Computer Graphics， 2004， 16（9）： 1185-1190.）

[8] XU J Y， JIN X G， YU Y Z， et al. Shape-constrained flock animation [J]. Computer Animation and Virtual Worlds， 2008， 19（3/4）： 319-330.

[9] KWON T， LEE K H， LEE J， et al. Group motion editing [J].ACM Transactions on Graphics， 2008， 27 （3）： Article No. 80.

[10] 梁家海.移動機(jī)器人編隊的運(yùn)動控制策略[J].計算機(jī)應(yīng)用，2011，31（12）：3312-3314.（LIANG J H. Motion control strategy for mobile robot formation [J]. Journal of Computer Applications， 2011， 31（12）： 3312-3314.）

[11] 柴運(yùn)，熊濤.基于二層鄰居信息的多智能體系統(tǒng)編隊控制[J].計算機(jī)應(yīng)用，2017，37（8）：2264-2269.（CHAI Y， XIONG T. Second-order information based formation control in multi-agent system [J]. Journal of Computer Applications， 2017， 37（8）： 2264-2269.）

[12] 李健，毛天露，蔣浩，等.群組動畫中的隊形約束與控制方法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2010，22（7）：1158-1165.（LI J， MAO T L， JIANG H， et al. Shape constraining and control in crowd animation [J]. Journal of Computer-Aided Design & Computer Graphics， 2010， 22（7）： 1158-1165.）

[13] 鄭利平，趙建明，劉玉飛，等.基于幾何約束機(jī)制的團(tuán)體操隊形輔助設(shè)計平臺[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2013，25（8）：1198-1203.（ZHENG L P， ZHAO J M， LIU Y F， et al. Formation design platform of group calisthenics based on geometry-constrained mechanism [J]. Journal of Computer-Aided Design & Computer Graphics， 2013， 25（8）： 1198-1203.）

[14] 劉雪娜.三維點(diǎn)集Voronoi圖的算法實(shí)現(xiàn)[J].計算機(jī)輔助工程，2006，15（1）：1-3.（LIU X N. Implementation of Voronoi diagram algorithms for 3D point set [J]. Computer Aided Engineering， 2006， 15（1）： 1-3.）

[15] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots [J]. International Journal of Robotics Research， 1986， 5（1）： 90-98.

[16] 陳逸，高巖，王長波.基于Leader-Follower的分隊隊形控制尋徑算法研究[J].計算機(jī)應(yīng)用研究，2018，35（12）：3812-3815.（CHEN Y， GAO Y， WANG C G. Research on team formation control path finding algorithm based on Leader-Follower [J]. Application Research of Computers， 2018， 35（12）： 3812-3815.）

[17] 鄭利平，程亞軍，路暢，等.質(zhì)心Power圖下覆蓋路徑規(guī)劃算法[J].系統(tǒng)仿真學(xué)報，2017，29（5）：1120-1124.（ZHENG L P， CHENG Y J， LU C， et al. Coverage path planning algorithm based on centroidal power diagram [J]. Journal of System Simulation， 2017， 29（5）： 1120-1124.）