基于Voronoi圖的群體隊形控制方法

黃東晉 段思文 雷雪 梁景坤

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

關鍵詞：群體仿真;隊形控制;Voronoi圖;彈簧系統;Lloyd算法

中圖分類號： TP391.9

文獻標志碼：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 引言

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

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

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

1 相關工作

隨著計算機群體動畫技術的快速發展，群體隊形變換仿真技術被廣泛地應用到各個領域，如何利用計算機仿真出形象逼真的群體隊形變換成為計算機圖形學、虛擬現實等技術領域的學者們一直以來研究的熱點。目前，群體隊形控制技術主要是從隊形劃分、隊形變形和隊形恢復三個方面進行研究。

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

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

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

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

2 群體隊形網格生成

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

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

3 群體隊形變形

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

群體隊形在避障過程中，每個個體因為所處位置不同會受到不同方向的力，促使它們各自有不同的運動軌跡，特別是當碰到較大障礙物時，會出現使隊形割裂分散現象，導致群體隊形形變的整體性被破壞。本文采用虛擬彈簧系統的思想來控制隊形的形變來解決上述問題，將隊伍進行網格化，構建一個覆蓋整個隊伍的平面三角形網格W（N，L），其中，N={Ni}為網格中的頂點集， L={Lij}為網格中的邊集。該三角形網格與初始隊形中的Voronoi網格的對偶Delaunay三角形一樣。將三角網格的每條邊看作一根彈簧，則整個三角網格構成一個彈簧系統。進入障礙范圍的智能體，其運動方向和速度在吸引力和排斥力的合力作用下發生變換，彈簧系統發生動態伸縮形變，而沒有到達障礙勢能場范圍的智能體為了保持彈簧系統的新平衡，自發調整方向和位移，進而形成變形網格。

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

4 群體隊形恢復

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

5 實驗結果與分析

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

實驗一：設計群體隊形形變控制的對比實驗，驗證形變算法的有效性。

實驗二：設計群體隊形恢復的對比實驗，驗證網格劃分和Lloyd算法在隊形恢復階段的高效性。

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

實驗四：在不同的場景下從初始階段、變形階段和恢復階段三個方面進行實驗，驗證本文提出的算法在群體隊形形變控制方面的有效性和穩定性。

5.1 實驗一

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

5.2 實驗二

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

6 結語

本文提出了基于Voronoi圖的群體隊形控制算法，將整個隊形劃分成一個包含所有智能體的Voronoi圖隊形網格，然后運用人工勢能場和RVO進行合理避障，再結合虛擬彈簧系統使隊形在形變過程中保持整體穩定，最后采用Lloyd算法快速恢復群體目標隊形，實現了群體智能體在虛擬環境中的隊形變換。

實驗結果表明，本文提出的算法能夠使隊形在障礙環境中實現良好的群體避障，且維持隊形的整體形變效果，驗證了本文算法的可行性和有效性。下一步，我們將繼續完善復雜場景中的隊形變換方法，將其應用到影視預演系統中，提高隊形形變和隊形恢復的效率。

參考文獻 （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] 李祖寧，何武.可變形網格引導的群體隊形仿真[J].中國圖象圖形學報，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] 鄭利平，程亞軍，周乘龍，等.異構群體隊形光滑變換控制方法[J].計算機輔助設計與圖形學學報，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].計算機輔助設計與圖形學學報，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].計算機應用，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] 柴運，熊濤.基于二層鄰居信息的多智能體系統編隊控制[J].計算機應用，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].計算機輔助設計與圖形學學報，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].計算機輔助設計與圖形學學報，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] 劉雪娜.三維點集Voronoi圖的算法實現[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].計算機應用研究，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] 鄭利平，程亞軍，路暢，等.質心Power圖下覆蓋路徑規劃算法[J].系統仿真學報，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.）