傅正扬 姜忠鼎

(复旦大学上海市数据科学重点实验室 上海 201203)(复旦大学软件学院 上海 201203)

0 引 言

近年来，随着计算机技术和硬件水平的不断提高，计算机可以在虚拟场景中进行规模更加庞大的群体仿真。大规模群体仿真技术可以提高虚拟场景的临场感和趣味性，在游戏娱乐、演习训练、建筑设计等领域具有重要的应用价值。

游戏引擎是为游戏研发设计的集成化开发工具，包含一系列游戏开发和场景制作常用的功能模块，开发者可以使用这些功能模块加快游戏和虚拟场景的开发速度。游戏引擎通常内置动画系统、导航系统和物理系统等功能模块，可以实现小规模的群体仿真。但随着群体数量的不断增加，游戏引擎内置功能模块的计算量也大幅度增加，导致游戏引擎内置的功能模块难以高效地实现大规模群体仿真，场景帧率难以满足应用的需求。

大规模群体仿真技术包括群体动画渲染和群体行为模拟两个方面。对于大规模群体动画渲染，层级细节技术(LOD)的研究和应用最为广泛。层级细节技术利用了观察者和显示设备的分辨极限，根据模型占据观察者可视区域的大小，动态更变绘制模型的复杂程度，提升实时渲染效率[1]。但是层级细节技术无法降低CPU计算模型蒙皮动画的消耗，随着场景群体模型数量增多，CPU的蒙皮动画计算会成为大规模群体动画渲染的瓶颈[2]。遮挡剔除技术(Culling)计算场景中观察者视锥区域和模型之间的遮挡关系，不绘制场景中完全被遮挡的模型。在游戏引擎中，可以使用层级数据结构加速计算模型的遮挡关系[3]。如果观察者视锥区域存在大量未被完全遮挡的群体模型，遮挡剔除技术难以有效地提升渲染效率。对于共用一套网格与动画的群体，GPU蒙皮渲染(GPU Skinning Instancing)[4]预采样这套网格与动画的所有数据，在实时渲染中利用着色器的系统变量(System Variables)为群体中的个体设置动画状态。GPU蒙皮渲染在一次Draw Call中使用GPU批处理大量个体的蒙皮动画计算和渲染，大幅度降低了CPU在蒙皮动画计算上的消耗。

大规模群体行为模拟一直是国内外研究的热点。自主性群体行为算法(Autonomous boids)是学术界和工业界应用比较广泛地群体行为算法[5]，该方法引入了聚合性(Cohesion)、分离性(Separation)、队列性(Alignment)三个群体行为基准，使用力模型表示这三个群体行为基准来模拟群体行为。自主性群体行为模拟仿真结果逼真，但是随着群体数量增加，群体之间发生碰撞的概率也大幅度增加。基于速度模型的最优互相碰撞避让算法(ORCA)可以有效地降低群体仿真中碰撞发生的次数[6]，最优互相碰撞避让算法独立计算群体中每个个体的碰撞避让策略，可以利用多线程并行加速计算，当群体数量较大时，最优互相碰撞避让算法也能在极短的时间内完成个体的碰撞避让计算[7]。近年来，国内外许多研究者在最优互相碰撞避让算法上不断改进，以适应一些复杂的应用场景。文献[8]在最优互相碰撞避让算法基础上提出一种适用于超大规模人群碰撞避让模拟的算法，将场景区域划分为多个矩形区域，以矩形区域为单位进行算法计算，牺牲局部矩形区域的碰撞避让精度，提高了算法对于超大规模人群碰撞避让的运算速度。文献[9]通过动态平衡短时间和长时间内碰撞发生的概率，提高最优互相碰撞避让算法对障碍物躲避的精准性，但是算法耗时也有所增加。文献[10]在最优互相碰撞避让算法的基础上引入多边形旋转的概念，使得改进后的RRVO算法在群体拥堵的情况下更快地摆脱群体死锁不动的僵局。文献[11]对三维空间下的最优互相碰撞避让算法进行改进，将改进后的算法应用于无人机实时躲避其他无人机和静态障碍物。

基于以上分析，本文在GPU蒙皮渲染、自主性群体行为和最优互相碰撞避让算法上加入多线程优化，提出一种大规模群体仿真的方法，提升大规模群体仿真的群体动画渲染和群体行为模拟性能。针对群体动画渲染，本文在GPU蒙皮渲染算法上加入了群体动画状态的多线程计算，加速群体动画状态和蒙皮动画计算；针对群体行为模拟，将自主性群体行为的力模型算法改进为速度模型算法，计算个体的初始速度，再将初始速度作为多线程优化后的最优互相碰撞避让算法输入，实现群体行为的碰撞避让，同时利用多线程提升群体行为模拟的计算速度。最后，在一款基于Unity游戏引擎[12]和HTC Vive[13]开发的虚拟现实游戏中使用本方法进行实验，证明本方法可以与游戏引擎结合，应用于逻辑复杂的大规模群体仿真场景，提升大规模群体仿真的效率。

1 基于多线程加速的大规模群体仿真方法概述

大规模群体仿真包括群体动画渲染、群体行为模拟。这两个部分的计算相互独立、互不影响，可以分别优化。本文对已有的群体动画渲染和群体行为模拟算法分别进行改进，提出一种基于多线程加速的大规模群体仿真方法，用以提升大规模群体仿真的性能。基于多线程加速的大规模群体仿真方法流程如图1所示。

图1 基于多线程加速的大规模群体仿真流程图

在群体动画渲染方面，由于群体数量庞大，使用CPU计算群体蒙皮动画的方法会大幅度增加CPU的负荷，导致大规模群体仿真场景帧率过低，难以满足应用需求。本文对GPU蒙皮渲染算法[4]进行改进，加入了多线程并行计算，提出了基于GPU蒙皮渲染的多线程加速算法。该算法利用GPU高并行计算能力加速计算群体的蒙皮动画，并且利用CPU多线程加速计算群体的动画状态，提升群体动画渲染的性能。

在群体行为模拟方面，需要提升群体行为模拟和群体碰撞避让的计算性能。本文对基于自主性群体行为算法[6]和最优互相碰撞避让算法[7]进行改进，提出基于自主性群体行为和最优互相碰撞避让的多线程加速算法。该算法首先使用自主性群体行为算法模拟个体跟随群体的行为，并且将自主性群体行为算法的力模型改为速度模型，使得群体在运动过程中能极快地改变速度，以避让场景中障碍物；其次，该算法在最优互相碰撞避让算法的基础上加入了多线程加速，使用改进后的基于多线程加速的最优互相碰撞避让算法加速计算群体之间的碰撞避让行为，进一步提升群体碰撞避让的计算效率。

2 基于GPU蒙皮渲染多线程加速算法

在很多情况下，大规模群体使用同一套模型网格和骨骼动画，除了空间信息，绘制群体中每个个体的区别仅在于它们当前播放的骨骼动画种类与帧数是不同的。GPU蒙皮渲染算法[4]可以利用GPU的高并行计算能力加速相同个体的蒙皮动画计算。本文在GPU蒙皮渲染算法的基础上，加入了群体动画状态的多线程计算，进一步提升群体动画渲染的效率。

使用骨骼动画的模型包含骨骼层次框架，模型网格的每个顶点V与一个或者多个骨骼B绑定，每个骨骼B的初始姿势绑定矩阵是BP，对顶点V的影响权重为w。骨骼动画每一帧都包含所有模型骨骼的变换矩阵M，以变换模型骨骼B的方式改变模型网格的每个顶点V，实现骨骼动画的播放。网格顶点V位置的计算公式如下：

(1)

根据式(1)可知，模型预采样的数据包括以下几点：模型骨骼的层次框架、模型网格顶点与模型骨骼的绑定关系、模型骨骼的初始姿势绑定矩阵、以及所有骨骼动画对模型骨骼的变换矩阵。其中，所有骨骼动画对模型骨骼的变换矩阵数据十分庞大，需要以纹理的格式保存采样的数据结果，方便上传至GPU并行计算蒙皮动画。骨骼动画纹理相关的数据结构如下：

Struct AnimationTexture

//骨骼动画纹理结构

{

//骨骼动画数量

int animationCount;

//骨骼动画数组

Animation anims[animationCount];

……

}

Struct Animation

//骨骼动画结构

{

//骨骼动画帧总数

int frameCount;

//骨骼动画帧数组

AnimationFrame frames[frameCount];

……

}

Struct AnimationFrame

//骨骼动画帧结构

{

//骨骼数量

int boneCount;

//骨骼变换矩阵数组

Matrix4x4 mats[boneCount];

……

}

在虚拟场景中，群体中每个个体会因为场景逻辑发生变化而更变播放的骨骼动画种类，例如驻立、行走、攻击等骨骼动画，个体播放的骨骼动画种类由逻辑线程控制。其他工作线程根据个体当前骨骼动画已经播放的时间，计算个体当前播放的骨骼动画帧数。在大规模场景中，群体数量十分庞大，这里需要充分利用其他工作线程并行加速计算。在进行场景渲染时，渲染线程将所有个体的骨骼动画状态，以及预采样的模型和骨骼动画数据上传至GPU，由GPU批处理完成群体的蒙皮动画计算与渲染。其中，渲染线程为每个个体设置一个四维向量，表示个体的骨骼动画状态，标记个体使用的骨骼动画纹理数据片段。这个四维向量上传至GPU后作为着色器的系统变量，为每个个体的着色器设置一个不同的参数，表示个体当前的骨骼动画状态。基于GPU蒙皮渲染的多线程加速算法流程如图2所示。

图2 基于GPU蒙皮渲染的多线程加速算法流程图

本文提出基于GPU蒙皮渲染的多线程加速算法，利用GPU高并行能力完成场景中大规模群体动画的蒙皮计算和渲染，同时加入CPU多线程技术提升群体动画状态的计算速度，大幅度降低CPU在蒙皮动画计算上的性能消耗，为CPU模拟大规模群体行为腾出了大量的性能空间。

3 基于自主性群体行为和最优互相碰撞避让的多线程加速算法

在场景中模拟大规模群体行为时，首先需要根据场景的布局以及群体的目标移动位置，使用寻路算法确定个体的初始移动速度；其次，所有个体以一个整体运动；最后，个体还要避免与其他个体以及场景障碍物发生碰撞。本文假设每个个体能够获取其他个体以及场景障碍物当前的位置和速度，先将自主性群体行为算法的力模型改进为速度模型，模拟个体跟随群体的运动，使得个体能根据周围环境极快地改变自身运动速度，再对个体使用多线程加速后的最优互相碰撞避让算法，实现群体行为的碰撞避让。基于自主性群体行为和最优互相碰撞避让的多线程加速算法流程如图3所示。

图3 基于自主性群体行为和最优互相碰撞避让 的多线程加速算法流程图

3.1 基于自主性群体行为的速度模型算法

vc=Pcenter-Px

(2)

(3)

(4)

(5)

结合个体的寻路速度v0与群体速度偏量v′，考虑个体的最大移动速度vmax，个体的理想速度vpref的计算公式如下所示：

(6)

3.2 基于最优相互碰撞避让的多线程加速算法

在大规模群体仿真场景中，由于群体数量非常多，个体以vpref作为最终速度模拟运动会造成个体之间频繁发生碰撞。若使用物理引擎利用碰撞体模拟个体的碰撞，CPU将花费大量时间模拟个体的频繁碰撞，导致大规模群体场景帧率很低。

为了降低CPU在碰撞模拟上的性能损耗，本文使用最优互相碰撞避让算法代替物理引擎的碰撞模拟，实现大规模群体的碰撞避让行为。同时，本文在最优互相碰撞避让算法基础上加入了多线程优化，加入了所有个体、障碍物的Kd-Tree并行计算优化。本文使用的最优互相碰撞避让算法流程如图4所示。

图4 最优互相碰撞避让的多线程加速算法流程图

最优互相碰撞避让算法[7]需要设置群体中每个个体的初始移动速度作为个体避让的初始速度，本文使用个体的理想速度vpref作为最优互相碰撞避让算法的输入。最优互相碰撞避让算法假设每个个体都知道其他个体的当前速度和位置，因此能够预测个体何时会发生碰撞。对于个体之间的碰撞避让，最优互相碰撞避让算法将碰撞避让的行为平分给每对个体，个体以最低限度的速度调整完成每对个体之间的碰撞避让。对于个体和场景中静态障碍物的碰撞避让，最优互相碰撞避让算法将由个体完全承担碰撞避让逻辑；对于个体和场景中动态障碍物的碰撞避让，本文将动态障碍物当作最优互相碰撞避让算法中的个体求解，与个体之间的碰撞避让不同，个体和动态障碍物的碰撞避让行为完全由个体来承担。

最优互相碰撞避让算法[7]需要先构建所有个体和障碍物的Kd-Tree，再计算每个个体的避让速度。为了提升算法的运算速度，本文在最优互相碰撞避让算法上加入了多线程优化，使用一个工作线程以固定频率构建所有个体和障碍物的Kd-Tree，其他工作线程根据最近一次构建完成的Kd-Tree计算每个个体的避让速度(见图4)。这种改进会略微降低最优互相碰撞避让算法的精度，导致场景中个体碰撞发生的次数提高，但是其他工作线程无需等待所有个体和障碍物的Kd-Tree构建完成，即可计算所有个体的避让速度，提高最优互相碰撞避让算法的运算效率。

4 实验结果与分析

4.1 应用实例

本文在一款虚拟现实第一人称射击游戏中，应用基于多线程加速的大规模群体仿真方法。该游戏是基于Unity游戏引擎[12]和HTC Vive[13]头戴式虚拟现实设备开发的，游戏场景包含大规模虫群陷阱关卡，当玩家踏入陷阱区域，大规模虫群从四周墙壁爬落，汇集成一个团队，避开场景中的障碍物向玩家移动并攻击，当虫群靠近玩家后，虫群会随机向玩家飞跃进行空中攻击。玩家可以使用枪械射击或者脚踩的方式攻击虫子。游戏大规模虫群陷阱的示意见图5和图6。

图5 大规模虫群陷阱(HTC Vive玩家视角)

图6 大规模虫群陷阱(Unity场景视角)

4.2 实验环境

实验使用1台PC作为虚拟现实游戏运行的节点，连接HTC Vive头戴式虚拟现实设备运行游戏。PC的硬件配置为Intel(R) Core(TM) i7- 6700HQ CPU @ 2.60 GHz，16 GB内存，NVIDIA GeForce GTX 1070图形显示卡。虚拟现实游戏的开发和运行环境为Microsoft Windows 10- 64 bit操作系统，Unity 5.5.1- 64 bit版本，HTC Vive虚拟现实设备。

4.3 实验结果

本节从群体动画渲染、群体行为模拟两个方面与Unity游戏引擎进行对比实验，验证大规模群体仿真方法的可行性。通过对比最优互相碰撞避让算法多线程加速前后的性能和碰撞次数，验证最优互相碰撞避让多线程加速算法的有效性。

对于群体动画渲染，本文在实验中分别使用Unity游戏引擎的Mecanim动画系统[14]，以及基于GPU蒙皮渲染的多线程加速算法渲染虫群，根据虫群渲染的CPU与GPU耗时证明方法的可行性。

表1给出虫群数量为200、400、600、800、1 000五种情况下，使用Unity Mecanim动画系统，以及GPU蒙皮渲染多线程加速算法实现虫群动画渲染的CPU耗时统计表。在CPU耗时统计中，Unity Mecanim动画系统比GPU蒙皮渲染的多线程加速算法多了蒙皮动画计算的步骤。

表1 虫群动画渲染CPU耗时统计表 ms

图7、图8分别给出了虫群数量为200、400、600、800、1 000五种情况下，使用Unity Mecanim动画系统，以及GPU蒙皮渲染多线程加速算法渲染虫群动画的CPU和GPU耗时折线图。

图7 虫群动画渲染CPU耗时折线图

图8 虫群动画渲染GPU耗时折线图

由图7可知，GPU蒙皮渲染多线程加速算法的CPU耗时远低于Unity Mecanium动画系统。这是因为GPU蒙皮渲染多线程加速算法将虫群动画的蒙皮计算由CPU转交给GPU处理，同时利用CPU多线程加速计算动画状态，因此GPU蒙皮渲染多线程加速算法的CPU耗时大幅度降低，大约只有Unity Mecanim动画系统的20%。

由图8可知，在虫群数量较小时，Unity Mecanim动画系统在GPU上的耗时略低于GPU蒙皮渲染多线程加速算法。这是因为GPU蒙皮渲染多线程加速算法需要在GPU完成虫群动画的蒙皮计算。随着虫群数量增多，GPU蒙皮渲染多线程加速算法充分利用GPU高并行计算的特性，GPU耗时基本不变；Unity Mecanim动画系统逐个渲染虫群，GPU耗时随着虫群数量的增加线性上升，逐渐超过GPU蒙皮渲染多线程加速算法的GPU耗时。

综合分析可知，基于GPU蒙皮渲染的多线程加速算法应用于大规模群体仿真时，可以显著降低CPU与GPU在群体动画计算和渲染上的耗时。

对于群体行为模拟，本文在实验中分别使用Unity游戏引擎内置的物理系统[15]、导航系统[16]，以及基于自主性行为、最优互相碰撞避让的多线程加速算法模拟虫群行为，根据虫群行为模拟的CPU耗时与虫群碰撞次数证明方法的可行性。

表2给出虫群数量为200、400、600、800、1 000五种情况下，使用Unity游戏引擎内置的物理系统、导航系统，以及基于自主性群体行为、最优互相碰撞避让的多线程优化算法的CPU耗时统计表。其中，前者包括Unity导航系统和Unity物理系统两个步骤：Unity导航系统完成每个个体到目标点的寻路计算；Unity物理系统完成群体之间的碰撞模拟计算。本文使用的群体行为模拟算法分为自主性群体行为的速度模型算法和最优互相碰撞避让多线程加速算法两个步骤。自主性群体行为的速度模型算法完成群体行为的模拟计算，最优互相碰撞避让多线程加速算法完成群体避让行为的模拟计算。

表2 虫群行为模拟CPU耗时统计表 ms

图9、图10分别给出虫群数量为200、400、600、800、1 000五种情况下，使用Unity物理系统、导航系统，以及基于自主性群体行为、最优互相碰撞避让多线程加速算法的CPU耗时和碰撞发生次数折线图。

图9 虫群行为模拟CPU耗时折线图

图10 虫群行为模拟碰撞发生次数折线图

由图9可知，使用Unity物理系统和导航系统模拟虫群行为的CPU耗时，随着虫群数量的增加而大幅度增长。使用基于自主性群体行为和最优互相碰撞避让的多线程加速算法模拟虫群行为的CPU耗时，随着虫群数量的增加而线性增长，且远低于使用Unity物理系统和导航系统的方法，可以在虚拟场景中高帧率模拟大规模的群体行为。

结合图9和图10可知，使用Unity物理引擎和导航系统的方法，在群体数量较多的情况下，CPU耗时和碰撞发生次数都很高，而基于自主性群体行为和最优互相碰撞避让的多线程加速算法在保证场景高帧率的前提下，场景中群体每帧发生碰撞的次数也很少，证明方法的高精度性和高效性。

最后，本文通过实验比对最优互相碰撞避让算法多线程加速前后的CPU耗时和虫群碰撞次数，证明本文改进最优互相碰撞避让算法的可行性。图11、图12分别给出虫群数量为200、400、600、800、1 000五种情况下，最优互相碰撞避让算法多线程加速前后CPU耗时和碰撞发生次数折线图。

图11 最优互相碰撞避让算法多线程加速前后 CPU耗时折线图

图12 最优互相碰撞避让算法多线程加速前后 碰撞发生次数折线图

结合图11和图12可知，本文提出的最优互相碰撞避让多线程加速算法，以降低碰撞避让的精度为代价，有效地提升了算法效率。最优互相碰撞避让多线程的加速算法，无需等待所有个体和障碍物的Kd-Tree构建，算法耗时大约为改进前的60%。虽然碰撞避让的精度有所下降，碰撞发生次数大约是原始算法的2倍，但是碰撞次数与虫群数量的比例仍然很低，碰撞发生次数的增多几乎不影响群体仿真的效果。

5 结 语

面向大规模群体场景，本文设计并实现了一种基于多线程加速的群体仿真方法，提升大规模群体仿真中，群体动画渲染和群体行为模拟的性能。针对群体动画渲染，本文改进GPU蒙皮渲染算法，在使用GPU加速群体蒙皮动画计算的基础上，利用CPU多线程加速群体的动画状态计算，进一步提升群体动画渲染的效率；针对群体行为模拟，本文将自主性群体行为算法修改为速度模型，结合多线程优化后的最优互相碰撞避让算法，实现群体之间的碰撞避让，提升群体行为模拟的效率。实验结果表明，本文提出的基于多线程加速的大规模群体仿真方法可以很好地与游戏引擎结合，在复杂场景中高效地实现大规模群体仿真。未来方法将继续优化，以适应群体规模更大，逻辑更加复杂的应用场景。