Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (6): 1799-1803.DOI: 10.11772/j.issn.1001-9081.2018102210

• Virtual reality and multimedia computing • Previous Articles     Next Articles

Group formation control method based on Voronoi diagram

HUANG Dongjin1,2, DUAN Siwen1,2, LEI Xue1,2, LIANG Jingkun1,2   

  1. 1. Shanghai Film Academy, Shanghai University, Shanghai 200072 China;
    2. Shanghai Engineering Research Center of Motion Picture Special Effects(Shanghai University), Shanghai 200072 China
  • Received:2018-11-05 Revised:2019-01-07 Online:2019-06-17 Published:2019-06-10
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61402278), the Innovation Program of the Science and Technology Commission of Shanghai Municipality (16511101302), the Research Program of Shanghai Engineering Research Center of Motion Picture Special Effects (16dz2251300), the Film Peak Discipline Project of Shanghai University.

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

黄东晋1,2, 段思文1,2, 雷雪1,2, 梁景坤1,2   

  1. 1. 上海大学 上海电影学院, 上海 200072;
    2. 上海电影特效工程技术研究中心(上海大学), 上海 200072
  • 通讯作者: 黄东晋
  • 作者简介:黄东晋(1982-),男,浙江温州人,讲师,博士,主要研究方向:虚拟现实、计算机图形学、物理仿真;段思文(1994-),女,湖北黄冈人,硕士研究生,主要研究方向:群体队形控制;雷雪(1994-),女,四川成都人,硕士研究生,主要研究方向:群体动画路径规划;梁景坤(1996-),男,安徽天长人,硕士研究生,主要研究方向:群体行为模拟与仿真。
  • 基金资助:
    国家自然科学基金资助项目(61402278);上海市科技创新计划项目(16511101302);上海电影特效工程技术研究中心资助项目(16dz2251300);上海大学电影学高峰学科项目。

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

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

关键词: 群体仿真, 队形控制, Voronoi图, 弹簧系统, Lloyd算法

CLC Number: