（计算机应用技术专业论文）continuum方法的改进及其在群体动画中的应用.pdf

中山大学硕士学位论文 摘要 论文题目：c o n t i n u u m 方法的改进及其在群体动画中的应用 专业：计算机应用技术 硕士生：于鸿磊 指导老师：纪庆革副教授 摘要 人群仿真是基于计算机图形学、力学、心理学、社会学等多种学科的一种 仿真建模技术，已经被广泛地应用于许多领域。现实社会中的公共安全及建筑 设计领域，要求精度和效率更高的仿真模型，以便更好地模拟人群来辅助设计； 虚拟世界仿真领域，例如计算机游戏、虚拟辅助场地训练等，对人群仿真技术 领域提出了更高逼真度和艺术化的要求。 人群仿真的建模方法主要包括基于力的微观方法以及基于场的宏观方法。 c o n t i n u u m 模型将群体看成是一个连续的整体，是宏观方法的一种。运动中的 人群具有流体的某些性质，该方法可以很自然地模拟大规模人群的运动，但是 在表现队形的变形细节方面却无法满足要求。本文以c o n t i n u u m 为基础进行改 进，并控制队伍运动，进行逼真的队形变换，在虚拟环境模拟领域具有广泛的 应用价值。本文的主要工作包括以下方面： 1 对c o n t i n u u m 方法的改进。改进后的c o n t i n u u m 方法在模型中加入了队 形的细节信息，利用队形图来表示队伍中个体间的关系，因此可以通过控制队 形图的变换来控制队形的变换。在运动路径规划方面，本文将队形中的边界点 和非边界点分开讨论。边界点会检测环境场中势能的变化，按照一定的规则来 变换位置，同时本文考虑整个队形所具有的刚体性质，非边界点则用 a s r i g i d a s p o s s i b l e 插值算法根据边界点的移动来得到合理的移动位置，使得群 体运动的人群可以在自然运动的同时能够保持队形细节。改进后的模型加入了 交互操作的计算方法，行进中的队伍在与含有障碍物的环境交互时，预设的静 态环境势能场与队伍个体间的动态力场叠加，群体在运动中从整体上感知势能 变化，从而变换队形以顺利的绕过障碍物，使得变形过程更加真实。 中山大学硕士学位论文 摘要 2 实验与讨论。本文通过实验讨论了改进后的方法的运算时间以及在真实 性方面的提高。实验场景中设置了障碍物，我们可以观察队形在运动的过程中 整体队形与场景的交互以及个体之间的交互，以使群体运动的队伍在复杂环境 中合理调整队形顺利到达目标区域。 关键词：人群仿真，c o n t i n u u m ，a s - r i g i d - a s p o s s i b l e 插值，群体动画 n 中山大学硕士学位论文 a b s t r a c t t i t l e ：g r o u pa n i m a t i o nu s i n gc o n t i n u u mm e t h o d m a j o r ：c o m p u t e ra p p l i e dt e c h n o l o g y n a m e ：y uh o n g l e i s u p e r v i s o r ：a s s o c i a t ep r o f j iq i n g g e a b s t r a c t c r o w ds i m u l a t i o ni sak i n do fm o d e l i n gt e c h n o l o g yt h a ti sb a s e do nv a r i o u s s u b j e c t ss u c ha sc o m p u t e rg r a p h i c s ，m e c h a n i c s ，p s y c h o l o g ya n ds o c i o l o g y n o wi t i sw i d e l ya p p l i e di nal o to ff i e l d s f o re x a m p l e ，m o r ee f f i c i e n tm o d e l i n gm e t h o di s n e e d e dt oh e l pd e s i g n i n gb u i l d i n g sa n do t h e rp u b l i cf a c i l i t i e si np u b l i cs a f e t ya n d a r c h i t e c t u r a ld e s i g nd o m a i n v i r t u a lw o r l ds i m u l a t i o ns u c ha sc o m p u t e rg a m e sa n d d i g i t a lm o v i e s ，a l ec a l l i n gf o rm o d e l i n gm e t h o dw i t hh i g h e rf i d e l i t ya n dm o r e a r t i s t r y m o d e l i n gm e t h o d so fc r o w ds i m u l a t i o nc a l lb ed i v i d e di n t ot w oa p p r o a c h e s ： o n ei s m i c r o s c o p i cm e t h o dt h a ti sb a s e do nf o r c et h e o r y , w h i l ea n o t h e ri s m a c r o s c o p i cm e t h o dt h a ti sb a s e do np o t e n t i a lf i e l d c o n t i n u u mc r o w dm e t h o di sa k i n do fm a c r o s c o p i cm e t h o d st h a ti sb a s e do nf l u i dt h e o r y c r o w di ng r o u pi sl i k e t h ef l u i d c o n t i n u u mm e t h o dc a ns i m u l a t et h em o v e m e n to fl a r g ec r o w dw e l l h o w e v e r , w ec a n n o tg e tt h ed e t a i l so fg r o u pd e f o r m a t i o nu s i n gt h i sm e t h o d t h i s p a p e ri m p r o v e dc o n t i n u u mm e t h o di no r d e rt om a k ei ta v a i l a b l et og r o u p a n i m a t i o n a n di tw o u l db ev a l u a b l ei nv i r t u a le n v i r o n m e n ts i m u l a t i o n t h ef o l l o w i n gi st h e m a j o r w o r k ： 1 i m p r o v et h ec o n t i n u u mm e t h o d t h ei m p r o v e dc o n t i n u u mm e t h o di sb a s e d o n5h y p o t h e s i z e s g r o u pc a nb ee x p r e s s e dw i t hf o r m a t i o ng r a p h ，s ot h a tw ec a n c o n t r o lt h eg r o u pd e f o r m a t i o nb yt r a n s f o r m i n gt h eg r a p h f o rp a t hp l a n n i n g ，t h e b o u n d a r yv e r t i c e sa n dn o n e b o u n d a r yv e r t i c e sa ler e s p e c t i v e l yc a l c u l a t e d b o u n d a r y v e r t i c e sw o u l df i n dn e x tp o s i t i o na c c o r d i n gt op o t e n t i a lf i e l d ，w h i l en o n e - b o u n d a r y v e r t i c e sd e c i d et h en e x tp o s i t i o nu s i n ga s - r i g i d - a s p o s s i b l ei n t e r p o l a t i o n ，a c c o r d i n g t ot h ep o s i t i o n so fb o u n d a r yv e r t i c e s g r o u pc a l lp r e s e r v es h a p ed e t a i l sw h i l em o v i n g b e s i d e s ，i n t e r a c t i v ec a l c u l a t i o ni sa d d e dt ot h em e t h o d y o us h o u l dp r e - s e tp o t e n t i a l f i e l do fs c e n es ot h a tt h eg r o u pc a ni n t e r a c tw i t he n v i r o n m e n t a n dw h e ng r o u p i i i 中山大学硕士学位论文 a b s t r a c t m o v e s a v o i d i n go b s t a c l e s ，t h e d e f o r m a t i o nw o u l dp r o c e s sr e a s o n a b l y a n d r e a l i s t i c a l l y 2 e x p e r i m e n t a la n a l y s i s w ed i s c u s st h er u n t i m eo ft h ei m p r o v e dc o n t i n u u m a n df i d e l i t yo fs i m u l a t i o n o b s t a c l e sa r es e ti nt h es c e n e w ec a l ls e en o to n l yt h e i n t e r a c t i o nb e t w e e nt h eg r o u pa n de n v i r o n m e n t ，b u ta l s ot h ei n t e r a c t i o nb e t w e e n i n d i v i d u a l si nt h eg r o u p b a s e do nt h e s ei n t e r a c t i o n s ，t h eg r o u ps h a p ed e f o r m s r e a s o n a b l yt oa v o i dt h eo b s t a c l e sa n d r e a c hd e s t i n a t i o n k e y w o r d s ：c r o w ds i m u l a t i o n ，c o n t i n u u m ，a s r i g i d - a s - p o s s i b l ei n t e r p o l a t i o n , g r o u pa n i m a t i o n i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人 和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本 人承担。 学位论文作者签名：于多码磊 日期：印，年莎月j 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料 室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、 缩印或其他方法保存学位论文。 学位论文作者签名：于；穆彩 日期：少加年占月a 日 导师签名： 虬钦奉 日期：z p 年石月多日 中山大学硕士学位论文 引言 第1 章引言 在论文的开始，首先介绍人群仿真研究的背景、意义以及各种建模技术综 述，然后概括叙述论文的主要工作以及全文内容的安排。 1 1 人群仿真研究的背景 自从十九世纪末开始，社会学及心理学领域就有对人群行为的研究。随着 近几十年来信息革命的爆发，计算机硬件和软件的飞速发展给众多的学科和行 业提供7 i i 曼好的工具平台。加之计算机图形学的发展，基于计算机虚拟仿真平 台的人群仿真应运而生。 人群仿真主要指人群运动的仿真，研究的是如何表现人群中的个体在各种 环境和特定条件下的运动特征及规律。它以力学、心理学以及社会学等学科为 基础，利用相应的算法和建模方法，在计算机虚拟环境中，建立起模拟人群运 动以及人群中的个体与环境交互的仿真模型，并利用可视化技术在虚拟环境中 逼真地展现出人群运动以及交互的过程。 人群仿真包括大规模人群运动仿真和群体动画。前者基于丰富和成熟的科 学理论，侧重于大规模离散人群，主要用于人群疏散分析以及复杂场景模拟等； 后者则侧重于小规模的特定人群，基于特定的算法，用于队形编辑及变形等特 定领域的模拟。 随着人群建模技术和计算机软硬件的发展，人群仿真已经成为许多虚拟环 境应用的重要工具。人群行为建模技术的主要难点在于满足群体协作的复杂 性、实现数据处理的海量性以及表现个体行为多样性与不确定性。正如a d r i e n t r e u i l l e 1 所说：“实时的人群仿真是非常困难的，因为要在计算机中展示很大 一个人群的各种行为和特性，这是复杂性非常高的一项工作 。这就依赖于研 究人员设计更为合理和富有创新性的模型和算法，虚拟人群行为建模技术仍然 是计算机图形学领域中的富有挑战性的课题。例如，公共安全及建筑设计等领 域都迫切需要更加精确并符合实际的人群仿真模型，来实现人群疏散仿真及场 景模拟等；数字电影、电脑游戏等数字娱乐产业，也需要人群仿真能够满足更 中山大学硕士学位论文 引言 加艺术化的和更高逼真度和实时性的要求。 人群仿真的建模方法主要包括基于力的微观方法，以及基于场的宏观方法。 微观方法主要包括社会力模型、基于智能体的方法以及细胞自动机模型等，这 些传统的方法都依附于宏观数据处理或算法设计，表现效果达不到局部人群仿 真和艺术化的标准，不日 匕1 5 1 6 区1 3 好的满足大规模人群复杂行为建模的要求；宏观方 法是将运动的人群视作一个整体，它可以更自然的模拟大规模人群的运动。 h u g h e sr l 于2 0 0 2 年 2 】最早提出了将人群作为连续的整体进行模拟的理论， a d r i e nt r e u i l l e 等人【l 】对其进行了简化和修改，它与经典流体动力学有很大相似 性，运动中的人群可被看作是“会思考的流体”，一个整体运动的人群中个体相 当于流体中的粒子。这样，人物运动的研究就可转化为流体力学中流体运动的 模拟和可视化。 随着建模技术的发展以及算法的改进，人群仿真建模方法将会不断的完善， 也会越来越多的应用于社会生活当中，更好的满足真实性、合理性、实时性以 及艺术化等不同方面的要求。 1 2 课题研究的意义 人群仿真在现实世界中得到了大量的应用。现实社会中的公共安全及建筑 设计领域，以及虚拟世界中的实时仿真领域和非实时仿真领域，都在建模效率 和逼真度等方面对人群仿真提出了更高的要求，人群仿真的研究具有非常重要 的现实意义。 首先，人群运动在现实生活中无处不在，广场上、街道上、办公楼内以及 车站内等，只要是人多的地方就会存在人群运动，因此人群运动可以作为一种 分析工具应用到非常多的领域，包括公共安全，城市建筑，环境工程，交通工 程乃至，i i , 理学和社会学等等，这些学科的仿真研究都迫切需要更加符合实际的 人群行为模型。其中特别针对火车站这种人群密度非常高的地方，例如每年春 运阶段的广州火车站，从公共安全方面考虑，如果调度不合理，很可能造成拥 挤甚至踩踏事件，尤其是在有紧急情况发生的情况下，恐慌推挤的现象更加严 重。因此大规模人群疏散模型就得到了很大的应用，能够很好的模拟大型场馆、 车站、建筑物等在火灾、自然灾害等发生时大规模人群紧急疏散的情况，帮助 2 中l i l 大学硕学位论文 引i 建筑设计师和调度者研究更好的疏散路径以及提高建筑的安全性。h e l b i n g 曾 经在2 0 0 0 年发表文章s i m u l a t i n g d y n a m i c a lf e a t u r e so f e s c a p ep a n i c 【3 】，文中 他总结出人群逃生的九个特征，以社会力为基础建立了疏散模型，并认为逃生 场景中的个体行为可以用社会心理学和动力学原理来解释表达，即个体心理因 素、周围的人的行为和环境特征共同影响个体的行为趋势。 另一方面人群仿真会大量的应用在影视特效、虚拟世界、以及计算机动 画等非实时仿真领域。人群仿真可以作为一种展示的工具，生成逼真的人群运 动的动厕a 我们曾经对经熟影片魔戒中逼真的大规模的战争场面惊奇不已 ( 图1 一l ( a ) ) t 这些效果几乎可以以假乱真。计算机仿真越来越多的应用到影 视领域，这样既能保证影片的质量，又可以很大程度的缩减成本。自从电脑动 画产生后，随着仿真技术的完善以及和艺术性的结合的日趋完美，这些影片中 的人物会给观众留下非常深刻的印象。 ( a ) 魔戒中大规模战争场面 ( b ) 北京奥运会丌幕式“和平鸽”表演 图i - l “和平鸽”队形变换及大规模战争模拟 另外，在实时仿真领域，人群仿真也十分广泛地应用在虚拟团体排练以及 游戏等领域。在2 0 0 8 年举行的北京奥运会的开幕式上，张艺谋导演动用大量 的演员，在场地中不断变换着队形，特别是和平鸽的队形变换( 图1 1 ( b ) ) ， 美轮美奂。但是对于一万多人的演员阵容的排练，如果没有借助于一些工具， 那么演员对于队形变换的路径以及导演从整体上把握变换的节奏，都是相当困 难的a 建国6 0 周年国庆的等演出和即将到来的2 0 1 0 广州亚运会的开幕式，训 练、彩排、表演，怎样做到精确无误怎样做到队形的完美顺畅的运动同时又 能很好的保持队形，这是人群仿真技未新的应用，具体来说，就是群组队形的 保持与控制。在计算机游戏领域，游戏的设计要在保证实时性的前提下，尽可 能的提供高真实的场景和逼真的角色，以使得用户操作顺畅增强用户体验。 中山大学硕士学位论文引言 本文研究将c o n t i n u u m 方法改进并应用到群体动画领域，属于宏观方法与 微观方法相结合的方法。模拟的群体运动的队形变换自然，运动路线顺畅，可 以应用于场地艺术模拟，例如大型演出排练，也可以用于游戏、电影中的人群 与群组交互的复杂场景等领域。 1 3 人群仿真建模技术综述 人群仿真包括大规模人群运动仿真和群体动画。前者基于丰富和成熟的科 学理论，侧重于大规模离散人群，主要用于人群疏散分析以及复杂场景模拟等； 后者则侧重于小规模的特定人群，基于特定的算法，用于队形编辑及变形等特 定领域的模拟。 人群运动建模技术是大规模人群运动仿真和群体动画的基础。按照对群体 关注的整体性来划分，可以粗略地将群体行为建模方法化分为微观方法和宏观 方法。本节将对这些方法归纳和分类。 1 3 1 微观人群仿真建模方法 下面首先介绍几种传统的人群仿真建模方法，包括社会力模型( s f m ) 、细 胞自动机( c a ) 模型、基于a g e n t 的方法、基于粒子动力学的方法以及基于规则 的方法等等，这些都是属于微观方法的范畴。 基于物理和社会力学的方法 基于力的人群运动仿真方法是以物理学运动定律、力学以及社会学为根基 的。h e l b i n g 在文献【4 】中提出社会力模型( s f m ) ，它从社会学及力学角度考虑 了人群的运动，把力作为个体运动的内部动机，是经典人群运动仿真模型之一。 社会力是对行人运动时的内部动机和行人间影响因子的一个量化，因此称 之为社会力。社会力模型可以简单的总结为式( 1 1 ) ： 等= 丘+ f l u c t u a t i o n s ( 1 - 1 ) 其中， 4 中山大学硕士学位论文引言 丘= 霹( 吃，坨瓦) + 易( 瓦，艺一易) 9 + 瓦( 吃，艺- 芦；) + z p o ，( 瓦，元一亏，f ) ( 1 - 2 ) b口 式中表示是行人的受力方程。行人的受力分为三个部分，第一部分为加速 度，描述了行人为了达到期望的运动速度而采取的速度变化；第二个部分为斥 力，反映了一个行人要与其他行人或边界保持一定距离，否则斥力会随距离变 小而变大；第三个部分表示了行人间的动态交互现象。f l u c t u a t i o n s 项是考虑进 行人行为的随机变化，文中假设行人的各种行为是等概率的，例如，从障碍物 左边或右边绕过的概率相等。另外，模型可以表现出行人行为的意外变化、某 些刻意的改变以及一些近亲行为等现象。运动方程( 1 1 ) 是一个非线性的耦合 郎之万方程，可以较真实的模拟如群聚效应等行人运动特性。 另外h e l b i n g 在文献【3 】中考虑到人群中的个体逃跑时的恐慌心理，结合粒 子系统，通过实验发现了由于个体心理及动作急躁而拥堵在门口，造成了“欲、 速则不达”现象。基于社会力模型的人群仿真方法可视性不强，主要用于疏散 研究。这种方法主要针对恐慌状态下的人群个体受力以及恐慌因素，计算了疏 散速度和受伤人数等。随后文献【4 对文献【3 】中的恐慌模型进行了泛化处理，使 模型可以适用于不同类型的个体在同一环境中同时存在的情形，并可以模拟群 组的行为。 h e l b i n g 的社会力人群仿真模型，针对人群疏散这一特定的人群运动进行模 拟，模型模拟方法简便，其逼真性可以用于各种人群疏散现象的研究。社会力 模型还考虑到了疏散个体的恐慌因素以及对人员损伤的估计，对人员疏散的方 案设计有很大的参考价值。 细胞自动机( c a 模型) 在许多研究领域，细胞自动机即c a ( c e l l u l a ra u t o m a t a ) 模型有广泛的应 用。在人群仿真领域，c a 模型将环境模拟为一系列的格子，将行人个体模拟 为在格子里运动的细胞【5 】，细胞在格子上的移动用来模拟行人的运动。这种模 拟方法中的个体是离散的，并且人群运动的模拟兼有动态性和系统性，它利用 简单的建模方式模拟人群运动，能够达到很高的实时性。 文献【6 】利用了动态和静态区域相结合的方法，但不能有效考虑运动个体间 的交互，因为它不是基于物理。而在文献 7 q a 所提到的基于网格的方法中，就 中m 学硕 悦电文 0 i 言 考虑到了物理因素，并且具备碰撞检测与碰撞避免机制。 文献【8 】提出了一种基于细胞自动机人群仿真方法，考虑到细胞自动机的状 态将环境进行空间抽象，并对空间中的变化元素和移动个体进行规范化处理， 考虑了移动个体在运动时相互之间的交互关系。这种细胞自动机方法，实验场 景使用了三维空间的模拟方式，但是仍然没有脱离经典的二维平面细胞自动机 的实质核心，运动模拟效果如图l 一2 所示。 幽1 - 2 划胞自动机万法模撒散粜 文献 8 】所述是非常经典的c a 模型方法，它用非常严谨的逻辑语言来定义 模型。所述的模型主要由一个三元组( s p a c e ，a ) 定义的。其中，s p a c e 是指 细胞个体的集合a 所处的环境，即实验的虚拟环境：细胞个体根据环境中特定 位置势能f 往环境中运动井与其他个体交互。 集合a 中的每个细胞个体也可以用一个三元组定义：c j ，p ，f 。其中f 是 细胞个体的类型( 此方法将细胞个体分为不同的类型，对应卟同的运动状态) ； j 表示细胞的状态其取值是根据细胞个体的类型来决定；p p 是细胞个 体在空问中所处的位置。细胞的类型7 是对细胞状态、感知能力和行为的描述， 每种不同类型可以用( z ，p e r c e p t i o n , ，a c t i o n ，) 来定义，其中，指细胞状态的集 合；p e r c e p t i o n 。是一个函数，呻l j l 。j 它表示如何通过势能 值以及敏感阚值来决定细胞的状态；a c t i o n , 是对细胞行为的描述。 基于a g e n t 的方法 在其他诸多研究领域中，基于a g e n t 的方法有广泛的应用。a g e n t 个体的 综合反映是方法的基础，人群中的个体是用a g e n t 来表示和控制的，人群的运 动特性也是通过单个a g e n t 的运动状态决策，以及多个a g e n t 之间的交互、协 作来表现的。按照智能性的不同，可将a g e n t 的行为分为两种层次 9 j ，高层次 中山大学硕士学位论文引言 的行为包括个体导航、a g e n t 间的交互、学习以及行为决策等；而低层次行为 则包括a g e n t 个体之间以及a g e n t 与环境之间的碰撞检测和躲避行为。在通常 情况下，a g e n t 的行为都应该受到一些规则的约束，这样才能准确体现出复杂 的高层和低层行为。 然而基于a g e n t 的方法大多都是进行局部避免碰撞，虽然可以建立某些高 层次智能行为，但是a g e n t 主要是强调个体的决策，是由个体到群体，自下而 上的模拟，所以对人群的某些整体行为的模拟无法保证效果。 m u s s e 和t h a l m a n n 在基于a g e n t 的人群仿真中加入一些社会学的方法【1 0 】， 是a g e n t 方法的一个典型应用。个体间社会因子影响个体行为的决策，进而展 现群体的某些运动特性。 文献【l l 】提出了一种基于自主a g e n t 的方法实现的h i d a c 系统。这个系统 的建模方法综合了粒子模拟的方法和社会和物理力建模方法，使a g e n t 具有感 知其周围的一定区域环境的能力，并以此来调整自身运动，可模拟出人群在疏 散情形下的推搡、挤压现象以及产生的后果。它主要是用于模拟现实的大规模 高密度的人群流动。a g e n t 的下一时刻位置的选择是通过考虑此时刻的速度、 a g e n t 遇到障碍物或其他个体所产生的排斥力、停止规则和等待规则以及避免 个体摔倒的力等因素来决定的。 不同于社会力模型，h i d a c 方法里的a g e n t 可以展示多种个体行为，如必 要时让行、排队等。这些行为是物理规则和心理规则的结合。也与基于规则的 a g e n t 模型和细胞自动机模型不同，这个方法可以真实的模拟一个行人试图通 过推搡其他行人来开辟自己前进的道路；另外，“不耐烦”的情绪因素导致的 行为决策也被加入到了模型中，少数个体会因为等不及与人群一起运动而另选 路径加快速度或者在人群里穿梭，增加了人群运动中个体行为的多样性。 基于粒子动力学的方法 众所周之，粒子系统开始提出主要是用来模拟一下自然现象的如云、雾、 烟、气体以及火焰等，粒子系统被用来进行人群仿真是在上世纪八十年代引进 的，e r i eb o u v i e r 【1 2 】以粒子系统为原型进行人群仿真，将现实当中的人用粒 子来代替进行现实环境的模拟。 在粒子模型中，每一个人用个粒子来代替，整个人群由很多的粒子构成 为一个复杂的系统，人与人之间的交互，人与障碍物之间的交互，就用粒子来 7 中山大学硕士学位论文引言 代替。首先，将粒子系统中的每一个粒子进行物理上面的量化，将其赋予质量， 体积，位置，加速度，速度，位移等等。然后，对这个粒子系统进行受力分析， 主要是利用牛顿力学、概率论统计学等知识计算粒子下一时刻的物理量。将人 与人之间的挤压也体现在粒子之间的挤压和相互作用，粒子不仅是简单的刚 体，而是带有一定弹性的物体。在人群运动仿真中，一般会考虑控制粒子间距 离来完成避碰机制，而事件的描述则需要对一系列函数设置参数，包括目标点、 密度、障碍物、速度等等，事件的开始可以导致粒子位置变动或状态改变，一 般用于单出口或者双出口紧急疏散情况的模拟。 文献 1 3 1 的社会学模型就是一种粒子系统的改进，其将人看成是一个不能 压缩的刚体，通过社会学和心理学的知识建立模型，然后通过牛顿力学定理将 其量化，求得各个重要的物理量，并对粒子的状态进行更新。 文献 1 4 1 提出了一种典型的利用粒子系统从微观角度进行人群疏散模拟的 方法，在这个模型中，作者利用经典的粒子模型，并综合了力学的方法，同时 考虑到了目标力、社会力和粒子力三种力对每个粒子的影响。虽然模拟能够达 到预测的作用，但是使用粒子模拟时，可视化程度太低，由于粒子是一种比较 统一的东西，不能完全体现人体的结构特征，比如，人体的肩宽、长就不能完 全的体现出来，对于人群的仿真具有很大的制约作用。 基于路径规划的方法 基于路径规划的方法在人群仿真当中是使用的比较多的，这种方法是通过 事先将大致的路径规划好，然后为了躲避人与人、人与动态障碍物之间的避碰 而对全局的路径进行修改，使得既能达到全局的路径最优，又能使人群之间能 顺利的避碰。使用的比较多的方法有基于图论中的一些算法，比如最短路径算 法，v o r o n o i 图、三角剖分等等，现在的一些启发式算法也经常使用，比如说 算法就是在游戏动画当中使用的一种比较多的路径规划算法。 文献 1 5 1 提出了一种可以在复杂动态的环境中对大规模人群的运动进行导 航的算法。这种算法运用了一种可适应弹性全局路径图( a e r o ，a d a p t i v ee l a s t i c r o a d m a p s ) 来规划行人的运动路径， 其实这篇文章的一个基本的思路就是利 用最短路径算法进行导航，在导航的过程中还涉及到人与人的避碰问题。首先， 对于虚拟环境当中的虚拟人使用最短路径建立起全局的路径图，路径图由路径 的节点和边组成，此算法路径的节点是能随着人群的变化而调整的。但是在最 8 中j i 夫学颈学位论i 弓| 占 短路径算法中，路径的边宽度是不予表示的，边上的点只能有一个人，而且在 俩个虚拟人相遇的时候不能够很实际的进行躲避，为了能够实现这种躲避算 法，也为了在仿真中条边上面能容纳很多人文章将原来的路径进行拓宽， 可以使这些拓宽的边上面同时可以通过很多的人，并且定点是会随着人群中人 的变化会动态变化的，如图卜3 所示： m h 4 一 殴壁 7 1 、1 ，7 、 图l - 3 弹性路径躲避动态障碍物 1 5 】 经过拓宽后的路面就更加适合人群仿宴，而且对于人与人之间的相互碰撞 是通过一些规则来进行的，有了这些规则，虚拟人能够很容易的躲避相向和同 向的虚拟人。 文献【l6 】最大的亮点在于把g a ( g e n e t i ca l g o r i t h m ，遗传算法) 算法应用 到了路径规划当中，将人群仿真与人工智能中的复杂算法结合，找到了一种解 决疏散路径计算问题的新方法。文章对人群仿真重新进行建模，将路径中的每 个节点看成是一个基因，然后将运些基因进行组合就形成了染色体，然后通过 适应度函数的选取和计算、繁殖、变异等步骤，最后得到较为优秀的染色体， 也就是路径规划问题的一个解。 虽然基于路径规划的方法为人群运动仿真开辟了一条新思路，解决了行人 全局运动规划的一个难题，但是很多的路径规划算法对于行人之间的避碰只是 基于一些规则，这样的规则在某些时候是不能很好的体现人的智能性的，而且 行人都是独立在规划的路径上运动，也不能表现行人间的组行为，在这些方面 还足有待进一步的研究和改进。 其他建模方法 另外，还有b d i ( b e l i e f - d e s i r e i n t e n t i o n ) 模型 1 7 】【1 8 】和基于小动物实验等 方法，在b d i 模型中，一个b d l 个体的精神状况表现在三个方面：信念( b e l i e f s ) ， 由智能体对环境的熟悉程度决定；期望( d e s i r e s ) ，表现出智能体要做出的事件： 意图( i n t e n t i o n s ) ，是智能体对期望的表达与目的。在基于小动物实验的模型中， 主要是用蚂蚁这类的小动物进行试验，是生物学的实验方法。实验中对其周围 中山大学硕士学位论文 引言 的环境进行一定的改变，然后观察动物在紧急情况下的反应，以此来推测人的 真实情况并对疏散进行预测分析。 【1 9 】【2 0 】 2 l 】分别从不同角度对人群仿真及其应用进行了总结或回顾，它们 各自的叙述方式不同，侧重点也不尽相同。而且由于写作时间的制约，对这些 方法的介绍不能做到面面俱到，也不一定能涵盖所有最新的研究进展，对建模 方法叙述主要集中在传统方法上。 1 3 2 宏观人群仿真建模方法 人们在不断的对大规模人群的研究当中发现了很多规律，尤其是当人群密度 比较大时，人群的流动就有像一些想流体一样的特性，有些人将人群的特性和 流体结合，提出了流体动力学模型。比较有名的有利用流体动力学来控制人群 的n a v i e r - s t o k e s 方程 2 1 ，h e l b i n g 在文献 3 】中也总结出当人群的密度大到一 定的程度时，人与流体有着很多的相似点。 不同于传统的微观方法，基于流体力学的方法，将所有的运动的人视作一 个整体，或者说一个整体运动的连续的流体，这就是连续流人群仿真方法。每 一个个体的运动相当于流体中的一个个粒子。流体动力学模型用类似于流体的 方法去阐述人的速度与周围环境的关系，以及人群密度对速度的影响。这些方 法的一个共同特点就是将人群的行为看成是一个整体来对待，简化了个体行为， 比如用密度来处理碰撞检测，当密度达到一定的程度，人与人之间的相对速度 就变成零，而且也用一个场能去控制整个场景当中人群的走动。 最早在理论方面对这种现象进行建模的是h u g h e s 2 ，他在文章中很细致的 从理论上面对人群仿真和流体的一些特征进行了证明，并且使用他的理论对一 些现象进行了模拟。 h u g h e s 在文献【2 3 】讨论和回顾了模拟人群流动的c o n t i n u u m 模型，并且研 究了这个模型在不同密度人群中的特点，并对这种方法进行了从连续到离散的 过程，从理论上对人群的仿真做出了阐述。h u g h e s 随后用c o n t i n u u m 方法分别 对麦加朝圣和a g i n c o u r t ( 1 4 1 5 ) 战役进行了模拟，对不同密度人群的运动特性进 行了研究。在2 0 0 6 年a c ms i g g r a p h 的一篇文章c o n t i n u u mc r o w d s 1 当中 t r e u i l l e 等人对h u g h e s 的方法进行了修改和简化，非常真实的对人群仿真进行 1 0 巾i 【 学硬学位论文 引占 了建模，并且达到了非常真实的效果尤其是对大规模超大规模人群的仿真有 非常好的效果( 图1 - 4 ) 。这种方法是建立一定的假设基础之上，在1 4 节中将 详细叙述这个方法的框架。 这种连续的方法在m a r c e l op a r a v i s i 等人【2 4 】在修改后的c o n t i n u u m 方法 1 】 的基础上，加入了一种局部控制的机制来修饰高层次人物运动，从而使得用户 可以定义路径信息来影响人群在模拟中的运动，相信更多连续的人群仿真方法 还将陆续被研究出来。 圈i - 4 c o n t i n u u m c r o w d 人群仿真 另外，有研究人员把宏观方法与微观方法结合使用的方法。f a r e n c 等人提 出了具有可扩展能力的虚拟人群行为分层建模方法，m u s s e 等人 1 0 又为分层人 群行为赋予了人群不同的自治程度，但是复杂的个体行为还无法实现。y e r s i 等人提供一种分层控制的方法来简化大规模人群的模扭问题，他们将整个场景 的人分成多个等级，对于不同等级的人群分别进行不同程度的模拟。作者表示 他们的方法能够实时地控制数千人的运动。另外，g u o 等人利用一个基于地板 场( f l o o rf i e l d ) 的细胞自动机模型模拟逃生情形将场地分成小格，并使行人 占有多个格，模拟行人逃生行为。 1 3 3 群体动画模拟技术 在人群仿真领域的分支群体动画方面，纪庆革等人 2 5 】在模拟群体运 动的方法和算法方面开展了研究，提出了一种基于组事件的团体操编排方法， 并应用虚拟人群技术对大规模团体操和场地艺术的编排进行研究。团体操编排 系统采用有指导的虚拟人群仿真技术，设计并实现了一十团体操编排和演练原 中山大学硕士学位论文 引言 型系统。该系统的作用是通过给定的队形图案来帮助对场地艺术训练和演示提 供指导，由团体操队形设计子系统和虚拟排练子系统两部分构成，它能够为团 体操编排人员改进队形变化的设计质量和提高设计效率提供了方便的操作平 台，为团体操编排和演练人员的训练提供辅助和效果展示，在场地艺术领域有 非常大的应用价值。 s i l v e i r a 等人【2 6 】提出一种基于b v p ( b o u n d a r yv a l u ep r o b l e m ) 管理人群的 组运动的方法，利用拉普拉斯方程得到对应的边界势能值，此方法的优势在于 能够实时地模拟大规模人群的组运动。k w o n 等人【2 7 提出了一种对人群的组运 动进行编辑的方法。他们利用d e l a u n a y 三角剖分记录队形和组的运动信息，使 用拉普拉斯算子对组的运动进行编辑，同时又保证队形和角色路线只有最小的 改变。它提出了一种群体队形过渡变换的算法，基于这种算法的队形变换编辑 器可以产生群体自由变换不同队形的动画，也可以把计算出的路径应用到三维 场景的模拟中，但是基于旋转插值计算出的变换路径过于拖沓，有太多的冗余 弧线。 文献 2 8 1 结合群体运动的空间性和时空性，提出了一种可交互的群体运动 的方法。这种方法最大的特点就是可以交互地编辑人群的群组，并且人物在群 体运动过程当中，尽可能地保持群体队形的细节。此方法提供了一个可交互操 作平台使用户可以通过锁定或者拖拽群组中的人物来改变队形。 s i l v e i r a 等人【2 9 】提出了一种鲁棒的算法来控制人群的组行为，群组的运动 是通过势能变化来驱动的。群组队形可以通过跟场地、障碍物的交互进行一定 的变形，同时考虑了环境和队形因素对群体运动的影响。这种方法中的群组队 形是一种柔性队形，可以使群组根据障碍物、地形对队形做出适当的调整，但 是它所设置的势场只侧重于表现队形的控制，无法自然表现人群流动，从而不 能用于复杂的人群运动场景。 1 4c o n t i n u u m 方法及变形技术 本节中我们将简要介绍c o n t i n u u m 方法的实现，主要是基于a d r i e nt r e u i l l e 简化后的模型【l 】。接着讲述了图形变形技术，作为后面群体动西仿真中队形变 形的基础。 1 2 中山大学硕士学位论文引言 1 4 1c o n t i n u u m 人群运动模型 a d r i e nt r e u i l l e 等人在文献【1 对c o n t i n u u m 方法进行了修改，简化了某些计算， 使其更适合于计算机模拟。c o n t i n u u m 模型的一个重要特性就是它只适合有目标 的人群，对于无目标的人群，则不适合模拟。 不同与h u g h e s 原作中提出的三个假设，他们提出了四个假设，以此来导出支 配人群动力学的数学模型。这四个假设如下所述： 假设1 ：每个人都试图到达一个特定的地理目标g s r 2 。 假设2 ：人们都是尽可能以最大的速度移动，可以以一个最大速度场厂来表示。 在位置x 处的个体，移动方向是0 ，那么他的速度就是文= f ( x ，o ) n 。，根据作者 的叙述，n 。是指向方向0 的一个单位向量。 假设3 ：存在一个不适场g ，如果g ( x 7 ) g ( x ) ，那么人们更喜欢处在位置x ，而 不是x 。 假设4 ：人们会选择行进路径，以最小化一个由3 部分组成的线性组合：路径长度， 到达目标的时间和路径上的不适因子。 因此，如果g 是目标点，n 是到达固定目标点g 的所有可能路径的集合，假 设速度场厂和不适场g 在某一时刻是固定的，那么一个处在位置x 的人将会选择 路径p n 来最小化以下的线性组合： c r i p l d s ，+ f l 、i p l d t + 业 。埘 l i r _ ，、i l 、- 一i 一 l o ， 其中，口，和，是权重，击和班分别表示对路径长度和时间的积分。 注意到d s = fd t ，重新推导和化简后可得单位耗费： 肛，黼c 奎盟半 ( 1 - 4 ) 设势能函数为，那么每个人的移动就是反相于势能场的梯度方向，也就是 向着势能下降的方向，则每一步的移动为： 江删， m 5 ) 行人的速度是受密度影响的，模拟计算时，行人的运动主要是二维平面位置 中山大学硕士学位论文 引言 变化的运算，高度根据地形等因素单独计算。密度分为高、中、低三种情况，低 密度时，行人速度是最高、最低速度根据斜坡高度差的插值；中密度时，行人速 度是全局平均速度与拓扑速度根据最高、最低密度的插值；高密度