来源：第三维度   作者：毛天露，夏时洪，王兆其
    摘要 随着数字化人体运动仿真技术的日趋成熟，尤其是其应用的迅速推广，大规模人群运动仿真技术开始成为虚拟人合成领域新兴的研究热点。大规模人群运动仿真技术包括：人群运动建模和人群运动计算机可视化两部分。本文详细介绍了国内外针对这两个方面开展的研究工作，以及大规模人群运动仿真技术的应用现状与前景。
    一 引言
    大规模人群运动仿真，就是研究人群在各种环境、情节下的运动特征与规律，建立大规模人群运动的仿真模型，并在计算机生成空间（虚拟环境）中以三维的方式逼真地展示大规模人群的运动过程。大规模人群运动仿真技术，提供了人群运动的分析和演示工具，可应用的领域相当广泛。
    作为一种分析工具，大规模人群运动仿真技术可以应用于公共安全领域，如船舶、飞机等大型交通工具的设计，体育场馆、地铁站等大型公共设施的设计等等。以体育场馆为例，应用大规模人群运动仿真技术，可以根据体育场馆的设计规模，模拟球迷退场等常规情景下的大规模人群运动，辅助分析场馆的走廊宽度、出口数目和出口位置等设计是否合理；可以模拟球迷发生冲突、火灾、恐怖袭击等非常规情景下的人群运动，辅助建立紧急情况下人员的疏散方案、合理布置消防器材、分配警力；还可以作为场馆管理人员进行消防、反恐等安全方案预演及培训的辅助工具。与传统方法相比，以大规模人群运动仿真技术作为人群运动的分析工具，具有直观、灵活、高效、经济和无人员安全风险等诸多优点。
    作为一种演示工具，大规模人群运动仿真技术能够生成逼真的人群运动动画，如地铁站、商场中的人流，体育场馆中欢呼雀跃的人群等，提高虚拟场景的视觉逼真性。因此，可以应用于娱乐游戏、电影电视媒体、国防研究等等。
    实现大规模人群运动仿真，需要解决两项关键技术问题。其一是，研究并建立大规模人群运动的仿真模型，实现对人群运动的模拟；其二是，研究大规模人群运动的可视化技术，即如何将大规模人群运动以三维的方式逼真地展现到虚拟场景中。
    大规模人群运动仿真模型的研究工作才刚刚起步，还处于初步的探索阶段。由于人群运动的机制相当复杂，并伴有一定的不确定性，目前还没有完整、通用的人群运动仿真模型。
    本文将在第二节中详细介绍目前已有的人群运动建模工作。
    大规模人群运动可视化技术，主要涉及大规模三维数据的实时渲染。虽然目前计算机硬件，尤其是图形硬件的性能在以很快的速度增长，但随着人群规模和场景规模的扩大，实时渲染大规模模型仍然相当困难。国内外许多研究者曾试图通过细节层次技术2、点渲染技术3等尝试解决这个问题，具体内容将在第三节中详细介绍。
   二 人群运动建模技术
    人群运动模型，是对现实世界中人群行为特征的抽象和数学描述。建立通用的人群运动模型具有很大难度。一方面，人是自然界最复杂的智能体，日常生活中的每一件小动作，如喝水、购物，其背后都隐含着复杂的感知和决策过程，在这些方面人类对于自身认识还相当不够；另一方面，现实世界人群中的每个人都是一个独立的智能体，即使拥有共同的目标，每个人的立场、性格也不相同，甚至对于共同目标的认识也不尽相同，因此，很难抽象出隐藏在复杂现象背后的共性特征。
    目前，已有的人群运动模型基本还处于初步研究阶段，距离实用还有相当漫长的路程。下面本文将介绍其中较为成熟的几种。
    1 基于粒子系统的人群运动仿真模型
    粒子系统最早由W.T.Reeves于 1983 年引进到计算机图形学领域，用来进行一些自然模糊现象的建模和可视化，比如云、水、气体以及火焰等。法国的Eric Bouvier以粒子系统为原型建立了人群运动模型[1] 。
    在 Eric Bouvier 建立的模型中，每个人都是一个模拟对象―“粒子”，整个人群则看作是一个粒子系统，系统内的粒子间可以进行互动。一个粒子集合对应于一群具有相同行为模式的人。通过在粒子系统内设置各种力场，采用牛顿力学机制并辅以被赋予了概率的事件，通过仿真计算求得每个粒子的位置、速度、加速度等属性，以实现人群运动的模拟。
    粒子系统内的力场，取决于设置在场景中的各种物体。事件则用带有一系列参数的函数表示。这些参数包括：目的地、密度、在特定点的停留、障碍物等。事件的发生可以导致粒子位置的变动或粒子状态的改变。
    在粒子系统中，为了使粒子的运动更符合人类的特征，获得较为恒定的速度，需要引入摩擦力参数。同时还可以在粒子系统内设置粘合系数，用来衡量一个人群的凝聚力，从而决定群的聚合和分裂。在考虑碰撞避免时，Eric Bouvier 采用相对速度和相互距离，通过一定公式计算碰撞概率，据此调整个体的速度以避免碰撞。
    粒子系统建立了简单、实用的人群运动仿真模型，可以方便地实现一些运动特征较为明显，或者比较容易抽象的人群行为的模拟，如地铁站的人流等。但对于一些复杂的、需要较多决策知识的人群行为，还需要在该模型基础上添加大量工作，如：提供人群行为模式的学习方法、建立决策知识库等。
    2 恐慌状态下人群撤离运动仿真模型
    Dirk Helbing等系统地研究了恐慌状态下的人群撤离行为，建立了恐慌状态下人群撤离的运动仿真模型[5]。
    Dirk Helbing总结了恐慌状态下人群撤离的特征：1）人群以（或者试图以）比平时快得多的速度移动；2）个体间开始出现推挤和肢体的相互碰撞；3）人群的移动，特别是在通过一些狭小的过道时，变得无序；4）来自各个方向的人流涌入出口；5）堵塞开始形成；6）堵塞处，个体间的肢体碰撞加剧，个体受到的压力可能突破 4,450 牛顿/米2警戒线；7）由于出现跌倒或受伤的个体，撤离的速度进一步减慢；8）个体行为出现从众倾向；9）撤离过程中，部分出口被人群忽略或没有很好地利用[5]。
    Dirk Helbing 建立的运动仿真模型，仅仅针对恐慌状态下的人群撤离行为，以粒子系统为基础，着重研究和分析个体的受力情况，根据个体的受力情况计算个体的移动速度，模拟恐慌状态下人群撤离的典型行为特征，计算人群通过狭隘通道和出口撤离的速度，并计算可能的受伤人数。

图 1 人群通过一个狭隘出口撤离的模拟结果
    个体受力情况和运动速度的关系可用公式（1）表示，其中mi是个体i的质量， 是个体i的初始速度， 是个体初始运动方向， 是个体期望的经过Ti时刻后的运动速度， 是周围人群施加给个体 i 的力， 是周围建筑如墙壁、障碍物等施加给个体i 的力。图 1 是恐慌状态下人群撤离的模拟结果。


    Dirk Helbing 等建立的模型，虽然仅针对恐慌状态下的人群撤离这一特定的人群运动，但该模型具有较高的逼真性，能够仿真人群在恐慌状态下撤离的各种典型现象，并提供了人员损伤估计，对于建筑物内人员安全撤离方案的制定具有极高的参考价值。
    3 ViCrowd 人群运动模型
    ViCrowd模型由瑞士联邦技术研究所计算机图形实验室的Soraia 等提出[16]。ViCrowd模型定义了虚拟人三个不同层次的集合：人群（crowd）、团队（group）和个体（agent）。而后定义了人群的三个大方面的属性：知识（Knowledge）、信念（Beliefs）和意图（Intentions）。
    其中知识主要涉及虚拟环境中的各种信息，包括：障碍物、基于环境的人群动作和行为、人群知识等。其中，障碍物定义了场景中各个物体的位置，或是人群可行走和不可行走的区域；基于环境的人群动作和行为知识，包括在一定区域内的路径规划，IP 点（人群必须经过的位置）和 AP 点（人群必须执行特定动作的位置）的定义等；人群知识，则是各个群的领导人的记忆库中储存的有关人群的各种信息。
    信念主要包括人群即将执行的动作和行为。它可以分为三个方面：
    1)人群和群的行为：比如聚集、跟随、更换目标、吸引、排斥、分裂、空间占用和安全检测等。
    2)情感状态：比如喜怒哀乐等。
    3)个人信念：比如个体是否要脱离或加入一个群、个体在人群中的地位等。

    意图则表示人群目标。
    除了以上人群的结构和性质，ViCrowd 模型定义了虚拟人行为的三个自由度层次，即被引导的（guided），规划的（programmed）和自治的（autonomous）。被引导的（Guided）行为，又称外部控制（external control）行为，即受到用户实时交互控制而激发的行为。规划的（Programmed）行为，也称脚本控制（scripted control）行为，即受到程序预先设定的脚本激发并控制的行为。自治的（Autonomous）行为，即内在行为（innate behavior），是由虚拟人根据自身的知识、环境的影响等而自我激发并控制的行为。在人群运动模拟中，外部控制行为的优先级最高，其次是脚本控制行为，最后是自治行为，如图 2 所示。

 2 行为优先级（由上到下降低）
   ViCrowd 模型的多层次结构如图 3 所示。


图 3 ViCrowd 模型的分层结构. 
    图 4、5 是采用 ViCrowd 模型进行仿真的一些结果。

图4、图5基于 ViCrowd 模型的人群运动仿真
    ViCrowd 模型对人群行为进行了系统的抽象，划分并定义了人群的不同属性、人群的行为层次和人群的控制层次。ViCrowd 模型不受场景、情节和人群行为模式的限制，是比较通用的人群运动建模方法。但 ViCrowd 模型目前还仅仅是人群运动模型的一个框架，其框架中的每一层次都有待充实和完善。
  4 Brogan and Hodgins 模型
    型，主要针对具有显著物理特征的人群[3,4]，融合了粒Brogan and Hodgins建立的人群运动模子系统的一些原理，但在建模过程中更多地使用动力学原理，对人群的速度、位置、加速度变化进行了更多地考虑和限制，同时也从物理角度应用动力学原理建立个体运动仿真模型。模拟结果如图 6 所示。

图 6 Brogan and Hodgins 的人群运动仿真
    Brogan and Hodgins 建立的模型，是粒子系统针对具有显著物理特征的人群行为的一种扩展，适用于马拉松、自行车赛、游泳等体育项目的模拟仿真。
    5 基于场景情节设置(scenarios)和规则描述(rules)的人群运动仿真模型
    东京大学的Yohei Murakami等提出了基于场景情节设置（scenarios）和规则描述（rules）的人群运动模型，并开发了便于交互描述的情节描述语言（scenario description languages Q）和进行交互模式描述的IPC (Interaction Pattern Card) ，在此基础上开发了FreeWalk and FlatWalk人群运动模拟系统[22,23]。
    Yohei Murakami 提出的模型通过四个方面来进行一个情节描述：
    2. 定义一个词汇表（
    3. 描述情节（describing scenarios）；
     extracting interaction patterns）；
    4. 抽象交互模式（
    5. 整合虚/实试验（integrating real and virtual experiments）；
   具体情节需要依据具体的使用情况来设定。
    实际应用有一定难度。而针对特定应用 的行为特征、建立人群运动模型则较为容易。目前已经有不少针对特定应用的人群运动仿真系统，如：模拟在轮船失事情况下乘客逃生过程的火情人群运动可视化技术大规模人群运动仿真，需要在计算机中以三维的方式逼真地绘制人群运动的仿真结果。
    逼真的三维人体模型至少包含 5,000 个面片，利用常规方法渲染成百上千，甚至上万个三维人体介绍几种能够用于人群运动可视化的技术。
    目前只有固将复杂度做得很低，但是，由于人体视觉的苛刻要 而当模型离人眼很远，模型的复 。有一种比较简单的做法是针对同一个模型，存储几个具有不同几何复杂度的代替品，然后根据场景中模型与视点间的距离来判断在该场景应defining a vocabulary）；
    Yohei Murakami 等提出的模型也不受场景、情节和人群运动模式的限制，是一种通用的人群运动建模方法，但在如何学习并建立人群运动规则等方面都有待完善。目前通用的人群运动建模方法均处于初步研究阶段，系统，在限定模拟场景或情节并给定人群目标的情况下，研究人群maritimeEXODUS 系统；模拟在地铁、港口等典型建筑物失况下人群逃生的 Vegas 系统等等。
    3 模型，在现有机器硬件条件下几乎不可能。然而，大规模三维数据的实时渲染是计算机图形学领域研究较为成熟的分支之一，其中的很多技术可以借鉴。下面本文将 1 细节层次技术细节层次技术（LOD）是通过降低单个模型的几何复杂度，从而降低单个模型的几何渲染时间，以达到提升可渲染的模型规模的目的。通过建模软件得来的人体模型，定的几何复杂度。虽然可以通过人工的方式，求，当模型离人眼很近的时候，简单模型的真实感不够强，杂度却还可以更低（但不可以消失）当使用哪一个，这种做法就是静态 LOD 技术。静态 LOD 的方式比较简单，但存储多个代替品的方法对内存提出了苛刻要求。而且，在不同的代替品切换的时候，往往会有视觉上的突变（Pop-up）现象，不够连续和真实。动态 LOD 技术则可以避免这些问题。它对单个模型通过计算，建立一个具有多级复杂度的、新的模型表达方式-----多分辨率模型，以“原始模型＋计算记录＋算法”的方式构成。给定一种复杂度，就能够找到对应的合适的代替品。
    而且在相邻的代替品之间进行切换的时候，可以做到视觉和几何数据的平滑过渡。出来的几何模型，每次通过去除这个模型当中的三角形的一条边（删除因此而消失的顶点和为简化效 ，具有很高的研究价值 用价值 。其他LOD算法参见文献控制，非常适合应用于人群运动的三维可视化。此外，动态或者是真实场景的照片，对于那些通过实体几何造型难以得由于动态LOD技术的突出代表渐进网格（PrOGREssive Meshes），是 90 年代中后期由微软的Huges Hoppe等人在格网（mesh）优化的基础上提出。主要想法是，对一个由三角面片建模面片）、并对剩下的简化几何体进行优化，持续操作并形成一个多分辨率模型[11,12,13]。除去特定的优化部分，这种思想被许多人采纳，并形成了许多其它种类的LOD算法。1997 年，卡内基梅隆大学（CMU）的Garland & Heckbert等人就在这种思想的指导下，使用一种二次误差测度（quadric error metric）作 指导模型简化和优化的工具，获得了很好的时空效率，果也非常好 和实 [7,8][6,21,10,17,2,24,14]。
    在人群运动仿真中，人群在场景中的位置通常情况下具有很大的流动性。LOD 技术不仅降低了模型的复杂度，而且动态 LOD 技术还提供了平滑的视觉过渡和对模型的动态LOD 技术发展了许多年，其中许多成熟的算法稍加修改即可应用的人群模型上。利用动态 LOD 技术，在当前主流 PC 机上，可渲染的人群规模大约在 100 左右。
    2 图像渲染技术      图像渲染与普通的基于实体造型的渲染方式不同，它以一系列场景的图像为输入，通过合成产生不同视角的新图像输出。基于图像的渲染技术在目前来说，比基于实体造型的技术有很多优势。它与场景的复杂度无关，使得复杂场景的实时交互问题得到解决；此外，由于它使用的是预先渲染好的图像，到的或者根本就不可能得到的真实场景，不管其复杂度有多高，图像渲染都能工作。然而，当前的图像渲染技术依赖于对已有图像的采样和插值产生新的图像，当这种采样不充分的时候，就会发生不可思议的错误。例如，如果图像过少，就难以产生在场景里面的高频部分，比如说高光效果。图 7 是利用图像渲染技术渲染的虚拟社区[19]。

 7 虚拟社区图
    理论上利用图像渲染技术以 2.5 维的方式对人群运动仿真结果进行三维可视化表达，可渲染的人群规模不受限制，虽然视觉逼真性不够，并且需要作较多的预处理工作。
    3 点渲染技术
    点渲染技术（PSR）打破了模型只用多边形(尤其是三角形)进行渲染的模式[9] 。在点渲染技术中，模型是以一系列紧密的面的采样点来表示的。这些采样点从相互正交的方向采样获得，包含颜色信息、深度信息、法线信息，并允许同Z缓存复合、Phong光照5和阴影等技术共存。同图像渲染相似的是，它根据物体的多个方向的采样数据，合成各种新视角下的几何模型和渲染结果。不同之处在于，点渲染中，每个顶点携带了比图像象素更多的信息，而且，采样点的颜色与采样的视角方向无关(view-independent)。
    使用点作为渲染的图元是因为这种方法简单、速度快。顶点能够很快地被画出来，不需要多边形剪切，扫描转换，纹理映射或凹凸贴图，从而避免了多边形渲染时大量的计算开销。
    而且采样点很少有冗余，不像图像渲染中的渲染图元往往需要采样多次，所以点渲染的方式既使用了大量内存，又充分有效地利用了这些内存。
    像上的映射，阴影计算，及寻找和修补点画的方式带来的“视觉漏洞”等问题。基于点渲染的算法包括点采样和渲染两个部分。点采样的目标是从合适的模型表面位置，抽取出合适数目和合适信息的点；而渲染部分解决点的可视化剪切，从三维点到二维图实际中的点渲染，在现在的硬件设施上，速度比多边形渲染高出几个数量级，与图像渲染相比，视觉效果更为逼真。图 8 是利用点渲染技术渲染的体育场馆[20]。

图 8 虚拟体育场馆
    点渲染技术的视觉效果优于图像渲染技术，而且所需的预处理工作较少，在现有主流显卡支持下，人群可渲染的规模能达到上千。
    4 典型应用示例
    人群运动仿真技术可应用的领域相当广泛，其中应用最早、需求最迫切是公共安全领域，主要应用于一些突发公共安全事件中的大规模人群紧急疏散模拟。例如：maritimeEXODUS船只及海上应急系统、英国诺丁汉大学的矿山安全及紧急管理模拟系统、德国 Fraunhofer研究所的特遣部队应急模拟系统、日本虚拟现实技术中心的地震模拟系统等。这些应用系统的场景较为单一，人群具备单一的目标（如逃生），人群的行为特征较为明显，因此建立的人群运动模型较为逼真可信。
    maritimeEXODUS 船只及海上应急系统是公共安全领域最为成熟的应用系统。该系统是在英国格林威治大学火灾安全工程组开发的 EXODUS 疏散系统上发展起来的，已经被广泛地应用在全世界 18 个国家。该系统可以对船只中人－人、人－建筑、人－环境之间的交互进行复杂的分析，能够方便地用来进行船只设计、疏散安排、救生艇大小和位置的分析。同时，它还能够对各种类型的船只上，各种情况下数量庞大的人群及其行为进行模拟。除了进行突发事件的可视化模拟，它还可以用来模拟船上的正常人员流通，用来在登船、登岸时指引乘客。同时，它还有专门的 FIRE-EXIT 软件来进行火灾事故模拟，有专门的 SHEBA 软件来对人的行为数据进行采集和学习。图 9 为该系统的界面。但 maritimeEXODUS 系统在仿真结果的三维可视化方面还有待改进，这也是当前人群模拟应用软件的通病之一。


图 9 maritimeEXODUS 系统界面
    5 总结
    总得来说，大规模人群运动仿真技术才刚刚起步，需要研究和解决的问题还有很多。在人群运动仿真建模方面尚缺乏通用的建模方法和完善的模型框架；在人群运动可视化方面，视觉效果的逼真性和可渲染模型的规模还有待进一步提高。同时，我们也必须看到，大规模人群运动仿真技术作为一种新颖的人群运动分析与演示工具，随着公共安全、游戏娱乐等领域需求的急剧增加，有望在不久的将来大规模应用，带来极大的社会效益和持续的经济效益。
    参考文献
    [1] Bouvier, E.; Cohen E.; and Najman. L. "From crowd simulation to airbag deployment: particlesystems, a new paradigm of simulation". Journal of Electronic Imaging 6(1), 94-107 (January 1997).
    [2] Brodsky D., and Watson B., Model simplification through refinement. In Proc. Graphics Inteface’00,pages 221-228, 2000.
    [3] Brogan, D. and Hodgins, J. “Group Behaviours for Systems with Significant Dynamics”.Autonomous Robots, 4, 137-153.1997. 
    [4] Brogan, D.C., Metoyer, R.A. and Hodgins, J.K. "Denvironments". In IEEE Computer Graphics and
    [5] Dirk Helbing, IIIes Farkas, Tamas Vicsek, Simnature, 2000, July 487-490.
    [6] Eck M., De Rose T., Duchamp T., Hoppe H., Louof arbitrary meshes. In Computer Graphics Prpages 173-181,Aug.6-12 1995
    [7] Garland M., Heckbert P.S., Surface simpSIGGRAPH 1997, August 1997, p.209-16
    [8] Michael Garland, Multiresolution Modeling:-- State of the Art Reports, pages 111--131, 1999
    [9] J.P.Grossman, y, Grossman MIT PhD.thesis, Point Sample Rendering 1998.
    [10] Gueziec.A.Surface sim rktown:IBM Research Divison T.J.Watson Research Center Research Report, RC 20440(90191),://www.watso.ibm.com:8080/search_paper.shtml.
    [11] Huges Hoppe. PrOGREssive meshes. In SIGGRAPH’96 Proc., pages 99-108.simplification of triangle meshes. International Journal of Image and Graphics, 3(4):1-18, 2003.
    作者简介：
    毛天露：中国科学院计算技术研究所数字化技术研究室助理研究员，在职博士生。主要研究方向为虚拟现实。
    夏时洪： 中国科学院计算技术研究所数字化技术研究室虚拟人合成课题组组长，博士，副研究员，主要研究方向为人体运动仿真与角色动画。
    王兆其： 中国科学院计算技术研究所数字化技术研究室副主任，研究员，博士生导师，主要研究方向为虚拟现实与智能人机交互。