基于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.）