黃東晉 段思文 雷雪 梁景坤

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

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

中圖分類號(hào)： 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 引言

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

3 群體隊(duì)形變形

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

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

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

4 群體隊(duì)形恢復(fù)

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

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

為了驗(yàn)證本文算法的有效性，設(shè)計(jì)四組實(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è)計(jì)群體隊(duì)形形變控制的對(duì)比實(shí)驗(yàn)，驗(yàn)證形變算法的有效性。

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

實(shí)驗(yàn)結(jié)果表明，本文提出的算法能夠使隊(duì)形在障礙環(huán)境中實(shí)現(xiàn)良好的群體避障，且維持隊(duì)形的整體形變效果，驗(yàn)證了本文算法的可行性和有效性。下一步，我們將繼續(xù)完善復(fù)雜場(chǎng)景中的隊(duì)形變換方法，將其應(yīng)用到影視預(yù)演系統(tǒng)中，提高隊(duì)形形變和隊(duì)形恢復(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)的群體隊(duì)形仿真[J].中國(guó)圖象圖形學(xué)報(bào)，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)群體隊(duì)形光滑變換控制方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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] 梁家海.移動(dòng)機(jī)器人編隊(duì)的運(yùn)動(dòng)控制策略[J].計(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)編隊(duì)控制[J].計(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] 李健，毛天露，蔣浩，等.群組動(dòng)畫中的隊(duì)形約束與控制方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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)體操隊(duì)形輔助設(shè)計(jì)平臺(tái)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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ì)算機(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] 陳逸，高巖，王長(zhǎng)波.基于Leader-Follower的分隊(duì)隊(duì)形控制尋徑算法研究[J].計(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é)報(bào)，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.）