基于Voronoi图的群体队形控制方法  

Group formation control method based on Voronoi diagram

作　　者：黄东晋 段思文[1,2] 雷雪 梁景坤 HUANG Dongjin;DUAN Siwen;LEI Xue;LIANG Jingkun(Shanghai Film Academy,Shanghai University,Shanghai 200072 China;Shanghai Engineering Research Center of Motion Picture Special Effects (Shanghai University),Shanghai 200072 China)

机构地区：[1]上海大学上海电影学院,上海200072 [2]上海电影特效工程技术研究中心(上海大学),上海200072

出　　处：《计算机应用》2019年第6期1799-1803,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61402278);上海市科技创新计划项目(16511101302);上海电影特效工程技术研究中心资助项目(16dz2251300);上海大学电影学高峰学科项目~~

摘　　要：影视作品中采用群体队形控制技术来制作大量角色处于某种队形运动的场景,但许多群体队形技术往往侧重于对自由移动的个体角色进行控制,而忽视了对队形运动的整体控制,导致场景画面缺乏美感性、整体性和条理性。针对这些问题,提出了基于Voronoi图的群体队形控制方法。首先,将群体队形进行Voronoi图空间划分,建立一个包含所有智能体的队形网格;然后,提出一种新的群体队形形变算法,采用人工势能场和相对速度障碍法进行合理避障,再结合弹簧系统使群体队形在形变过程中尽可能保持整体稳定;最后,采用Lloyd算法快速恢复到目标队形。实验结果表明,该方法可以很好地模拟群体队形变换运动,适用各种复杂场景,具有美感、整体、条理的队形变换效果。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.

关 键 词：群体仿真 队形控制 VORONOI图 弹簧系统 Lloyd算法 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]