（计算机应用技术专业论文）虚拟群体模拟中的大规模场景简化技术.pdf

匕工三l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：望毯日期：为向年上月匆目 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：壑缢盘导师签名： 日期： 莶壁兰达( 彳苷京趸) 年月 日 摘要 摘要 大规模群体动画一直是虚拟现实技术研究的热点之一。群体动画技术广泛应 用于游戏、电影动漫、建筑规划以及火灾等灾难现场模拟与辅助指挥。通过群体 行为的真实模拟，可以辅助电影动漫产生真实宏大场景效果；可以在公共场所 ( 商场、体育场馆、娱乐场所等) 规划设计中模拟验证安全通道等设计的合理 性；可以为智能交通管理( 红绿灯有效设置，主干路口的交通流量管理) 提供模 拟环境；也可以为灾难现场指挥提供指导和训练平台。目前这个方面的研究得到 了广泛的重视，对群体动画的研究和创作工具产生了极大的需求，同时一套完整 高效的群体动画设计与制作工具也将促进影视动画等方面数字媒体产业的发展。 作为群体动画技术的一个关键技术，模型简化占据着不可替代的重要位置。要 实现大规模的场景，必然会涉及要绘制和渲染大量的模型，而对于实时场景渲染 来说，渲染速度和模型的视觉逼真度是两个非常重要的指标。要达到两个指标的 和谐统一，那么就必须选择一个很好的算法来实现渲染速度和模型显示逼真度的 折中。 对于静态模型，现有技术已经很好的实现了模型简化。根据简化算法的简化方 式可将其分为四大类：顶点聚类算法、增量式简化算法、采样算法和自适应细分 算法。在这四类模型简化算法的基础上发展起来的静态大规模场景简化技术也比 较完善，如基于细节层次模型的大规模场景简化技术和基于点采样的大规模场景 简化技术等。本文就以上算法和技术做了具体的研究和分析，并生成了一种新的 算法：一种基于点采样的模型简化算法和大规模场景简化技术。 虽然静态大规模场景简化技术已经比较完善，但动态的大规模场景的简化技 术才刚起步，实现效果也不理想。针对这种情况，在提出的新算法中，加入了动 态模型的简化新方法。实验结果表明：在保证场景的渲染速度和视觉真实性的条 件下，能很好的实现3 0 0 0 0 人的实时动画。 关键词：群体动画，实时渲染，点采样，层次细节模型，层次实例化 a bs t r a c t l a r g e s c a l eg r o u p sa n i m a t i o nh a sa l w a y sb e e no n eo fm eh o tr e s e a r c h a r e ao f v i r t u a lr e a l i t yt e c h n o l o g y g r o u pa n i m a t i o ni sw i d e l yu s e di ng a m e s ，m o v i e s ，c a r t o o n ， a r c h i t e c t u r a lp l a n n i n ga n dd i s a s t e rs i m u l a t i o n ( 1 i k ef i r e ) a n da s s i s t a n tc o n d u c t o r g r o u p b e h a v i o rt h r o u g hr e a ls i m u l a t i o n sc o u l db ea s s i s t e df i l m sh a v ea r e a le f f e c to fs c e n e s ； v e r i f ys e c u r ec h a n n e lc a nb es i m u l a t e dt od e t e r m i n et h er e a s o n a b l e n e s so f s u c hd e s i g n i np u b l i cp l a c e s ( s h o p p i n gm a l l s ，s p o r t ss t a d i u m s ，e n t e r t a i n m e n tv e n u e s ，e t c ) ；s i m u l a t e d e n v i r o m e n ti sm a d ea v a i l a b l et ot h ei n t e l l i g e n tt r a f f i cm a n a g e m e n t ( t h ee f f e c t i v e s e t t i n g so ft r a f f i cl i g h t s ，t r u n kr o a dj u n c t i o n st r a f f i cf l o wm a n a g e m e n t ) ；g u i d a n c ea n d t r a i n i n gp l a t f o r mh a sb e e np r o v i d e dt ot h ed i s a s t e rs c e n e t h er e s e a r c hh a s b e e nw i d e l y a p p r e c i a t e d ，t h er e s e a r c ha n dt h ec r e a t i v et o o lo fg r o u pa n i m a t i o n h a sag r e a td e m a n d a t t h es a l n et i m eac o m p l e t ea n de f f i c i e n tg r o u po fa n i m a t i o nd e s i g na n dp r o d u c t i o nt o o l s w i l la l s of a c i l i t a t et h ec o n n e c t i o no fd i g i t a lm e d i ai n d u s t r i e s a sak e yt e c h n o l o g yo fa n i m a t i o n ，m o d e ls i m p l i f i c a t i o nc a nn o tb er e p l a c e d t o a c h i e v el a r g e s c a l es c e n e s ，t h e r ew i l li n e v i t a b l yb ei n v o l v e di nd r a w i n ga n dr e n d e r i n g a la 】? g en u m b e ro fm o d e l s ，b u tf o rr e a l t i m es c e n er e n d e r i n g ，t h er e n d e r i n gs p e e da n d v i s u a lf i d e l i t ym o d e l sa r et w ov e r yi m p o r t a n ti n d i c a t o r s i n o r d e rt oa c h i e v et h e h a n n o n i o u su n i f i c a t i o no ft w oi n d i c a t o r s ，w em u s tc h o o s eag o o da l g o r i t h mt og e tt h e t r a d e o f fo ft h er e n d e r i n gs p e e da n dv i s u a lf i d e l i t y f o rt h es t a t i cm o d e l t h et e c h n o l o g yh a sa c h i e v e dav e r yg o o dm o d e ls i m p l i f i c a t i o n t h em o d e ls i m p l i f i c a t i o na l g o r i t h m sc a nb ed i v i d e di n t of o u rm a i nc a t e g o r i e s ：v e r t e x c l u s t e r i n g ，i n c r e m e n t a ls i m p l i f i c a t i o n ，t h es a m p l i n ga l g o r i t h m a n da d a p t i v es u b d i v i s i o n b a s e do nt h e s ef o u ra l g o r i t h m s ，t h es t a t i ct e c h n i q u e sh a sd e v e l o p e dv e r yp e r f e c t ，s u c ha s t h er e d u c t i o nt e c h n i q u eo fl a r g e s c a l ea n i m a t e dc r o w d b a s e do nt h el e v e lo fd e t a i l m o d e l sa n dt h er e d u c t i o nt e c h n i q u eo fl a r g e s c a l ea n i m a t e dc r o w d b a s e do np o i n t s a r n p l i n g t h i sp a p e r h a sd o n ead e t a i l e dr e s e a r c ha n da n a l y s i so fa b o v ea l g o r i t h m s ，a n d g e n e r a t ean e wa l g o r i t h m ：t h er e d u c t i o nt e c h n i q u eo fl a r g e - s c a l ea n i m a t e dc r o w d b a s e do np o i n t s a m p l i n g w h i l et h es t a t i cs c e n eo ft h es i m p l i f yl a r g e - s c a l et e c h n o l o g yh a sb e e nr e l a t i v e l y i i a b s t r a c t s a t i s f a c t o r y , b u tt h ed y n a m i c st e c h n o l o g yi so n l yj u s tt h eb e g i n n i n g i nv i e wo ft h i s s i t u a t i o n ，i nt h en e wa l g o r i t h m ，w ea d dan e wm e t h o dt os i m p l i f yt h ed y n a m i cm o d e l t h er e s u l t ss h o wt h a t ：i nt h ec o n d i t i o no fe n s u r i n gt h es c e n er e n d e r i n g s p e e da n dv i s u a l a u t h e n t i c i t y , o u ra l g o r i t h mc a ng e tar e a l - t i m ea n i m a t i o nw i t h3 0 ，0 0 0p e o p l e k e y w o r d ：g r o u p sa n i m a t i o n ，r e a l t i m e r e n d e r i n g ，p o i n ts a m p l i n g ，l e v e l o f d e t a i l ( l o d ) m o d e l ，h i e r a r c h i c a li n s t a n t i a t i o n i i i 目录 目录 第一章绪论1 1 1 课题来源1 1 2 课题背景和研究意义2 1 3 虚拟群体模拟技术的国内外现状3 1 4 群体动画的广泛应用前景8 1 5 论文的主要工作和创新点11 1 6 论文的章节安排1 1 第二章网格模型简化技术综述。1 3 2 1 顶点聚类1 3 2 2 增量式简化15 2 3 采样算法l9 2 4 自适应细分2 0 2 5 网格简化技术在大规模场景中的应用2 1 2 5 2 1 历史和发展2 3 2 5 2 2 基于点采样的大规模场景简化技术分类2 4 2 5 2 3 基于点采样的大规模场景算法基础2 4 第三章一种基于采样点的大规模场景简化算法设计2 7 3 1 模型表面的点采样2 7 3 。2 过度采样点的去冗余2 9 3 3 三角形面片和采样点的折中3 0 3 4 动画的实现3 3 3 5 大规模场景的建立- 3 4 3 6 算法总框架3 5 第四章群体动画系统设计3 8 4 1 群体动画系统框架描述：3 8 4 2 群体实时渲染子系统4 0 4 3 场景简化模块4 1 4 4 场景绘制模块4 4 i v 目录 第五章群体动画系统的实现。4 6 5 1 群体动画系统的基本配置4 6 5 2 基于点采样的模型简化技术实现和效果展示4 7 5 3 群体动画系统的实现和效果展示5 0 第六章总结和展望5 2 6 1 总结5 2 6 2 展望5 3 j 酵【谢5 4 参考文献5 5 攻读硕士期间取得的研究成果6 0 v 第一章绪论 第一章绪论 随着计算机的广泛应用以及计算机图形学和计算机硬件的发展，人们已经越 来越不满足于高质量的仿真图片，从而使用计算机生成动态场景模拟的虚拟现实 技术就逐渐进入了人们的生活。在虚拟现实技术日趋成熟的今天，其应用领域已 从3 d 游戏逐渐走向了电影，建筑表现，文物古迹复原，城市道路桥梁规划产品演 示动画，虚拟动画( 如虚拟演播室) 、虚拟舞台，过程模拟动画( 如生产线生产过 程、交通煤矿事故过程等等) ，可见虚拟现实技术己悄悄地延伸到了各行各业。 虚拟现实技术模拟真实物体的方式由于其精确性、真实性和无限可操作性， 使其成为一个有用的工具，被广泛应用于医学、教育、军事、娱乐等诸多领域。 特别是在影视广告制作和游戏场景模拟方面，虚拟现实技术这项新技术带给入耳 目一新的感觉。由于人的社会性，大规模人群一直作为研究和分析的重要领域。 群体研究的工具，虚拟群体模拟技术的出现和发展极大的促进了人们对大规模群 体的研究进程，同时由于该技术的不完善和不成熟使得大规模群体的研究还停留 在一定的高度上。现阶段，虚拟群体模拟技术存在着一些技术上的难题，这些难 题主要都是由场景的特性所决定的，包括个体的独立性、运动性、场景规模、逼 真度以及实时性等要求。这也是本文研究的基础和起点。 1 1 课题来源 本文的研究内容是模型简化技术在虚拟群体模拟中的运用和实现，是依据“虚 拟环境下群体动画实时模型与绘制技术”项目( 8 6 3 项目) 展开的。主要研究内容 是群体行为的实时策略和渲染，包括：( 1 ) 群体行为的实时策略：动态环境描述 感知；群体知识模型；群体行为路径规划；个体动作规划；( 2 ) 大规模群体角色 的渲染。目标是开发出5 种环境下的群体行为演示系统：正常情况下的自然漫游； 地震情况下街道上群体逃生行为仿真模拟；室内火灾情况下群体逃生行为仿真模 拟；城市环境中的行人和车流量仿真模拟；室外地形环境下大规模行军仿真模拟。 电子科技大学硕士学位论文 1 2 课题背景和研究意义 虚拟群体模拟技术又称为群体动画技术，群体动画技术广泛应用于游戏、电 影动漫、建筑规划以及火灾等灾难现场模拟与辅助指挥。通过群体行为的真实模 拟，可以辅助电影动漫产生真实宏大场景效果；可以在公共场所( 商场、体育场 馆、娱乐场所等) 规划设计中模拟验证安全通道等设计的合理性；可以为智能交 通管理( 红绿灯有效设置，主干路口的交通流量管理) 提供模拟环境；也可以为 灾难现场指挥提供指导和训练平台。目前这个方面的研究得到了广泛的重视，对 群体动画的研究和创作工具产生了极大的需求，同时一套完整高效的群体动画设 计与制作工具也将促进该方面数字媒体产业的发展。 群体行为的模拟不是简单个体的集合，群体的特点是所有个体有一个共同的 目标，同时还要满足个体在一定范围的自由发展。群体行为模拟的真实性还需要 研究实际生活中群体的特性，特别针对人群还需要研究人的社会性以及群体中个 体的心理特性。如果只是一群个体盲目运动，个体之间不存在相关性，则个体数 目再多也不能模拟出真实的群体效果，也看不到群体的协调性。 用计算机产生群体动画需要对群体进行描述和控制，实现群体行为的抽象或 者对真实世界群体行为模型的模拟。用传统动画制作方法和图形控制方式直接描 述绘制群体活动，存在很大的问题。例如针对数以万记的群体中的个体行为，单 用脚本对每个个体进行行为规划，其过程不仅单调而且繁琐；另外，采用这种方 法规划出的个体行为和路径很难避免非自然的效果存在。即使想通过人工手段加 入群体中个体行为的约束条件，也很难保证其正确性，例如个体之间的碰撞规避 等。同时，这样设计的群体很难进行再编辑。例如需要改变群体的某些特性以产 生面对灾难发展的异常情况模拟。因而，用脚本对群体的每个个体进行控i i i 矛1 编 程并非不可能，但应该还有更好的方法来产生更有效、更鲁棒、和更可信的群体 动画。 另一种模拟群体的方法是将群体行为简单化假定为个体行为相互作用的结 果。因此为了模拟群体，首先需要模拟个体行为。即使只是部分的行为也可以， 但这些行为至少应该包括使个体形成群体所必要的所有行为。而为了支持这种对 个体进行控制的结构，还必须模拟个体的部分感知机制和在特定环境中行动的物 理模型。如果个体的模拟具有正确的群体特征，则创造群体就简化成了创造一些 个体的实例，并使它们h = 术1 1 互作用。 2 第一章绪论 1 3 虚拟群体模拟技术的国内外现状 早在19 世纪末集体行为就已经开始研究，但尝试用计算机模型来模拟人群行 为则是在最近才开始的，很多这方面的工作都是在9 0 年代中期和末期开始的。目 前研究来自多个领域需求，如计算机图形学、机器人技术学、训练系统、建筑、 物理学、安全科学和社会学。这些领域都创建了人类群体的模拟。尽管人群模拟 研究的基础范围比较广，但是值得注意得是，学科间的交叉研究的想法却很少， 这是由于某个领域的研究者通常很少关心其他领域所做的工作。 以上的群体模拟方法都是基于特定应用的，关注集体行为的不同方面，使用 的也是不同的建模技术。比如在一些模拟撤退中使用的流和网络模型( f l o wa n d n e t w o r km o d e l s ) ，统一规划群体中个体的行为；另一些领域中则采用个体智能行 为模型来反应群体动作，个体的行为模型需要建立相关的物理规律、社会学模拟 的复杂规则、c h a o s 方程等。 这些行为建模的方法主要侧重于控制的不同方面，比如粒子系统，羊群系统 ( f l o c k i n gs y s t e m ) ，以及动作系统等。下表1 1 是这些系统的一个比较。 表i - 1 各种不同群体建模系统的比较 。j 。， ，。 粒子系统 77 羊群系统v i c r o w dm o d e l；动作系统i ：i ，?j r ，口 ： 。，?、? 层次：羊群，层次：人群，组，代可以层次性 结构， ，r， 非层次性的 代理理地描述 参与者7 很多 止匕 很多 少量 智能无一止匕 止匕 高智能 基于物理学是 有些是 不是不是 碰撞检测并且作出反应避免碰撞避免碰撞避免碰撞 力量域( f o r c e不同的程度：预定义 控制 f i e l d s ) ，整体趋势局部趋势行为，行为规则和指 规则 g l o b a lt e n d e n c y ) 导控制 电子科技大学硕士学位论文 b o u v i e r 1 1 ，b r o g a n 2 】【3 】采用粒子系统和动力学来为群体运动建模。 r e g n o l d s t 4 j 1 5 】提出一个分布行为模型，该模型模拟具有感觉能力的行动者所组成的 群体行为。h e l b i n g 6 】根据前面的模型提出了一个模拟行人移动方法。m a t a r i c 7 】和 n o s e r t 8 】在控制集体行为方面，提出了局部规则( 1 0 c a lr u l e s ) 的概念。t u t 9 】进一步 将人工生命应用来建模行为动画，个体以虚拟代理方式，具有人工视觉和感知环 境的能力。b l u m b e r y 1 0 】在一个交互式虚拟环境中构建了很多运动的自治虚拟人， 这些虚拟人的运动通过多种层次进行控制。p e r k i n 1 1 】贝0 提出了i m p r o v 系统，该 系统预先定义好了交互行动者的行为。 ( 1 ) 基本群体行为模型 c r a i gr e y n o l d s 1 2 】提出b o i d s 系统，首次完整给出了一个群体行为控制的模 型。该模型重点针对动物群体来实现的。该模型提出了群体作用于个体的三种规 则( 中心吸引力、速度跟随、相互排斥力) ，以及组合的方式解决了群体行为中 个体行为一致性与随机性的问题。该模型能够完成很多复杂的群体行为，例如模 拟鸟群朝同一方向飞行，接着群体尖端部分个体会转向，其余部分自然跟随，形 成鸟群通过群体模型传达转弯的行为，而形成自然的波浪状形。j a r e dg o ”】在 b o i d s 系统基础上进行扩展，提出个体行为自主角色方式，角色运动被定义为三个 不同层次：最低层次，角色只采取独立的几种行为，如：搜寻、跟随、逃跑、合 群等。在中等的和高等的层次，角色将这些行为合一，即可以同时进行多种组合 行为，只是在行为的合并方式和数量上有所区别。t ua n dt e r z o p o u l o s 【9 】提出在逻 辑上扩展b o i d s 系统，群体中个体以“代l 里( a g e n t ) ”实现自主感知。该模型可以很 好模拟鱼群的行为，鱼的状态机模型中有：饥饿，性欲和恐慌等状态，鱼的反应 取决于其内部状态和外部环境。最后对鱼的运动控制通过实际建立的一个质点弹 簧的物理模型来实现。 m u s s ee ta l 【1 4 j 模拟了群体的合作。将群体设想为人工生命体，人工生命由具 有动机的、感知的、行为的和认知的部分行人模型( 也叫代理) 构成。其中每个 代理都有自身的行为准则，对多个自治代理在环境中模拟产生一些未知的、复杂 的结果。环境可以表示为层次数据结构，这样就有效的支持了对自治行人感知的 查询，并能驱动他们的行为反应和维持他们进行局部和全局规划的能力。 a n d e r s o ne ta l 【l5 】提出一种受限的群体动画。a g e n t 组成的群体在预先定义的路径 上运动，而传统的基于约束的动画都是使用固定路径或者关键帧的，但他们的工 作更倾向于离线的动画生成。 ( 2 ) 人的群体行为模拟 4 第一章绪论 人类动画一直是计算机图形学中具有挑战性的问题【1 6 1 。心理学家和社会学家 已经对人类的行为活动进行了多年的研究。最近几年，行人模拟又受到c g 研究 者的广泛关注【1 7 1 。这个课题同样引起了人工生命【18 1 、建筑学和城市规划【1 9 】【2 0 】等 领域的兴趣。图形研究者已经参与到可视化建筑工程规划之中，其中包括行人动 画。 s o m m e r 首先开始了对人的群体行为模式研究，j a m e s 和他的学生记录了 o r e g o n 城市所观察的人群。他们随机观察了7 4 0 5 个行人群、运动场人群、游泳人 群、以及购物人群等，并跟踪对1 4 5 8 人在多种情况下的行为进行了观察。他们发 现所有人群中，7 1 是两人组成的群体，2 1 的群体包含3 个人，6 的包含4 个 人，仅2 的包含5 个以上的个体。 在行人动画中，较早的研究关注于综合自然运动( n a t u r a ll o c o m o t i o n ) 和路径 规划。h e l b i n g 6 】研究了人的行为动画，行为动画又进一步的受到了其它研究者的 重视和发展【9 】【2 l 】【2 2 】。行为动画是整个分布式行为系统的推动力。分布式行为系统 综合了鸟群、鱼群、兽群以及低等动物的行为、人的性格，群体行为等。低层次 的群体交互行为在许多学科【2 3 】【2 4 】【2 5 1 中得到了发展。动画研究者、迪斯尼电影公司 和其它的工作室都热衷于将这些技术用于游牧部落战斗题材的电影。 ( 3 ) 非实时群体动画技术 在非实时群体动画中，群体行为的模拟主要关注两个方面目标，第一个是关 注行为的真实性方面，这种行为的真实性通常可以通过诸如撤退模拟器、社会学 人群模型，或者是人群动力学模型来模拟，并简单地进行平面层次的展现。另一 个关注的是高质量效果的呈现，例如电影作品、游戏等。这种情况下，行为模型 的真实性不是主要目标，令人信服的虚拟效果是更重要的。这种效果的实现部分 是靠行为模型，部分是靠在制作过程中人为的干涉。这里，行为模型不需要非常 匹配真实的世界，他们的目的是让漫画家( a n i m a t o r ) 的工作更加容易接受。然而， 最近的趋势好像是要将这两类模拟进行合并( c o n v e r g e ) 。 在电影制作方面，p d i 和p i x a r 致力于将群体动画效果搬上电影屏幕。在 电影“蚁哥正传”中建立了两个系统，用这两个系统实现电影中成千上万蚁群的 活动场面。其中，群体模拟系统( c r o w ds i m u l a t o rs y s t e m ) 实现上千个蚂蚁的运 动模型，综合考虑个体受力的情况( 比如障碍物、目标等) ，以及过程控制规则 ( 比如羊群行为，有限状态机等) 。混合系统( b i e n d i n gs y s t e m ) 的目地则是简化 设计者的工作，避免他们为群体中的一个个个体去创建和指派个体动作。在另一 个电影“b u g sl i f e ”中，4 4 6 6 种不同的个体动作被创建，用来描述2 2 8 种不同的 电子科技大学硕士学位论文 行为，比如紧张，好奇，大笑，欢呼，鼓掌，奔跑，行走，惊慌等等。p i x a r 的团 队开发了一个系统，允许基本动作以一种可变的灵活的方式被接合在一起形成新 的行为。 h e l b i n g 6 1 把行为动画原理向创造真实的、自治的动画角色方面前进了一大 步。尽管行为动画是有一定效率的，但是由于采用的硬连线编码存在很大问题。 b l u m b e r g 和g a l y e a n 1 1o j 开始引入新的机制来给动画设计者更多的行为控制权。 b l u m b e r 的核心著作中考虑了高级认知能力，比如知识表示、推理、规划等。 b a d l e r 【l 引，b a t e s 2 6 】在利用a i 技术在动画人物卡通角色方面取得了一定成果。p e r l i n 【l l 】提出了给动画设计者有用的行为建模工具。a r i j o n 2 7 1 实现用层次有限自动机进 行摄像机控制。 实时群体模拟非常困难，因为一大群人所表现出来的行为是极其复杂的。一 个群体模型不仅包含个体的动作和环境的约束，同时还要解决人与人之间的交互 问题。更进一步，模型还必须能够反映出动态变化环境中的智能路径规划，如个 体不断地调整他们的路径以响应拥塞及其它动态信息。前面很多研究都是基于代 理的模式，也就是说，每个个体的计算都是分别进行的。基于代理的方法使用较 多的原因是：1 ) 真实人群都是每个个体各自分别的计算自身的决定，这样的模型 可以捕获每个人的特殊状态：可见性、与其它步行者的距离等局部因素；2 ) 不同 的个体可以设置不同的模拟参数，从而产生不同的复杂行为。然而基于代理的模 型也存在缺陷：不容易产生出一贯真实的行为准则；对每个个体的全局路径计算 很快就变为资源杀手，特别是在实时环境中。结果，大多数代理模型都将局部碰 撞规避从全局路径规划中分离出来，而这两种不同目的的计算不可避免的要产生 冲突。此外，局部路径规划通常会导致“近视”，从而产生不真实的人群行 为。这些问题会在拥塞严重和环境变化快速的情况下将迅速恶化。 ( 4 ) 实时人群体行为模型 对大规模人群运动进行建模最自然的方式就是基于代理的方法，在该方法中 每个人能够独立地规划其自身的行为。这主要是因为人都有自己不同的个性，并 能根据个人目的作出决定。如此的动态性( 或许是它们最精妙的形式) 展现在【2 8 】 的工作中。他不仅对行为的动态性( 诸如，刺激响应) ，而且还对认知方面( 如， 知识和学习) 进行了建模。后来，这种模型在【；9 】中对行人可见性( p e d e s t r i a n v i s i b i l i t y ) 和路径规划作了扩展。由s t e p h e nr e g e l o u s 创办的m a s s i v e 软件公司， 发行了一套能够达到产品级质量的人群模拟软件【3 0 1 ，它给予动画的创作者为群体 中的每个个体代理的细节进行描述的自由。虽然上述的系统都可以创造超真实感 6 第一章绪论 的群体，但大多数专门的技术还是被要求用来为每个个体设计“正确”的模型。 最近的研究表明，没有现成的方法可以覆盖特定情景的所有范围，而这些情景很 适合于安全领域【3 。更重要的，为了准确地对人类的推理和拥塞决策进行建模， 对每个个体的计算开销是很大的。为此，对大多数精确的模型往往无法满足实时 要求。 为了改善基于代理的方法的性能表现，也为了避免为每个个体的认知建模的 复杂性，研究者已经对群体模型提出了许多简化模型，包括局部方法( 1 0 c a l m e t h o d s ) 、预计算的静态路径、以及在粗略环境图上的全局路径规划。局部受控 个体的研究可以追述到r e y n o l d s 4 】的工作，他指出紧急情况下的群体行为可以由 简单的局部规则来产生。r e y n o l d s 的技术产生出了可视地受约束的鸟群和鱼群。 此后，出现了大量的关于使用局部受控代理模型对人群建模的研究。r e y n o l d s 5 】 扩展了可能的行为集合。其他工作如m u s s e 3 2 】提出了社会学问题，p e l e c h a n o 3 3 】提 出的心理学影响，h e l b i n g 3 4 】和c o r d e i r o 3 5 3 提出了社会动力，以及b r o g a n 提出了非 一般运动动态性( n o n t r i v i a lm o t i o nd y n a m i c s ) 等等。 不同于真实的人，局部受控的代理不会执行全局或中间范围的规划去避免非 局部的拥塞或交错流动的行人。当其他行人充分靠近时，通过改变运动来防止碰 撞。许多有趣的碰撞规避方法已经被提出，包括几何模型、基于格子的规则、依 靠密度的技术、行为模型、粒子作用力交互模型，以及贝叶斯决策过程。最终， 局部碰撞规避仅能在捕获人们用来平滑地避免动态拥塞的固有地长期规划过程中 做到这样的地步。因为人们总是在不断向前计划着，真实的行人是不会在他们经 过拥塞区域时，产生近距离失策或卡壳( n e a r - m i s s e so r “v i s u a lb u m p s ”) 的现 象。 仅有碰撞规避是不能建立真实群体的模型的，因为人群有其全局的目标。因 此，许多局部群体模型将碰撞避免和全局导航结合起来。一般地，全局规划以基 于图技术或静态势场来实现。l a m a r c h e 3 6 】使用精心设计的拓扑的预计算来允许实 时进行每个代理的全局路径规划，这种规划考虑了可见性。他们使用独立的碰撞 规避过程，因而个体容易在拥挤的情况下被卡住( g e t t i n gs t u c k ) 。b a y a z i t 3 7 为了 同时进行全局规划和碰撞规避，使用了粗略的基于图的路标，达到了令人满意的 效果。s u n g 3 8 】将概率图与d e c o u p l e dp l a n n e r s 同运动图与约束相结合，来计算行人 详细的运动。p e t t r 6 ”】使用静态场景导航图来实时地寻找行人行径的路径，但没 有考虑碰撞或拥塞。k a m p h u i s 4 0 】扩展了路径计划从而使代理可以呆在一起。“等 人【4 l 】提出一种首领罡艮随者模型，通过只对首领执行全局规划，从而以一种更少的 7 电子科技大学硕士学位论文 系统开销的方法，来降低了全局规划的开销。g o l d e n s t e i n 等人【4 2 】介绍一种精心设 计的3 层技术，用一种在障碍物周围的静态势场来处理局部和全局的导航。 k i r c h n e l l 4 3 使用预计算的，静态的势函数来研究疏散( e v a c u a t i o n ) 现象。一般地， 静态势场没有处理场景变化的问题，如交通灯改变和走出拥塞。 基于代理人群建模也被用于对城市规划、路径设计、及评价的交通运输研究 m j 。h e l b i n g 的社会动力模型在这个邻域很有影响，而且被证明能够重复产生特 殊的群体现象。商业上存在许多高逼真度人群模型：e g r e s s 系统【4 5 】使用基于细 胞的方法来模拟群体的宏观行为；群体动态方法( c r o w dd y n a m i c s ) 【3 l 】使用一个 校准的基于代理的框架来精确地对大量群体现象进行建模。 多代理路径规划在机器人领域也被广泛地研究，主要集中在多个机器人的协 作方面。集中化的规划者在时空上为所有代理设计动作【4 6 】，这些方法在机器人领 域是领先的，但并不适用于由为自身目标作了优化的个体组成的群体。与我们的 工作比较接近的是“d e c o u p l e d ”p l a n n e r s ，在这里，代理决定自己的行为。这些 算法需要优先级策略来消除冲突的规划【4 7 】。p a r k e r 【4 8 】研究了局部和全局规划之间 的平衡。势场也被用于机器人导航。 对于群体合成，一种可选的方法已经从流动性的动态群体中浮现出来。 h u g h e s 4 9 开发了一个模型，将行人表示为密度场，并提出了一对偏微分方程来描 述这种群体动态性。最重要的是，这个系统由一个进化的势函数来驱动，以优化 的方式来引导密度场到达其目标。具体的描述可参见【5 0 1 ，以及后来对中世纪战争 的分析的应用中f 5 1 1 。这种方法的一维版本也经过真实人群数据得到证实【5 2 】。一维 人流可选的连续统模型也被分析了【5 3 】。在图形学领域，c h e n n e y 5 4 】的流片( f l o w t i l e s ) 理论证实了诸如拥塞避免之类的人群属性能够用无分歧流( d i v e r g e n c e f r e e f l o w s ) 来达到满意结果，尽管它们没有涉及到人群的其它重要方面。 1 4 群体动画的广泛应用前景 随着群体动画技术的不断发展，其在各个领域中的应用也越来越广泛，而对 其要求也越来越高。用户希望群体数量更加的庞大，渲染效果更加的真实，同时 希望群体对用户的要求能做出更精确更快捷的反映。这一系列的要求都是建立在 计算机的强力支撑上的，同时也需要有更高效的群体渲染算法和软件加速技术。 就目前群体动画的使用范围来看，群体动画的发展前景是非常乐观的。 1 、游戏和影视动画产业中的应用 第一章绪论 就目前群体动画在游戏和影视动画产业中的应用来看，其应用是受限的，最 主要的原因是群体动画的实时效果和渲染的复杂性决定了群体动画在这一领域的 应用。但随着图形硬件和加速技术的不断提高，群体动画可以实现别的技术在游 戏和影视中无法比拟的非凡效果。在已有的游戏和影视中我们已经可以看到群体 动画的应用了，如泰坦尼克号中沉船的场景，魔兽世界的宣传动画中，大规模群 体混战的场面等，这些场景规模宏大，而且演艺条件苛刻，不可能使用如此巨大 的规模去实现真实效果，而只能采用群体动画技术来实现。群体动画在游戏和影 视动画产业中的应用会越来越广泛，这必将使其成为游戏引擎的一个核心技术继 续发展。下图1 1 为电影木乃伊归来3 中大规模的木乃伊军团的场景。 图1 - 1 大规模动态场景技术在影视动回中的应用 2 、虚拟训练系统中的应用 在警察军队的虚拟训练系统和普通的逃生系统中，将不可避免的会涉及到公 共场所的危机情况处理，如火灾，地震，炸弹预警等危险的情况。在这些情况下 无可避免的将处理大规模人群的疏散，撤离和逃生，这就要求群体动画要具有很 精确和快捷的实时响应效果，由于群体动画的渲染复杂性和人群在遇到危险情况 下的不确定性，使得群体动画在虚拟训练系统中的应用收到一定的限制。但随着 群体技术的不断发展，该技术必将成为虚拟训练系统中不可替代的一个重要的组 成部分。图1 2 为某大楼逃生系统设计方案模拟图。 9 电子科技大学硕士学位论文 图l - 2 大规模动态场景技术在虚拟训练系统中的应用 3 、数字展示平台上的应用 随着计算机技术的日新月异，数字展示系统逐渐进入了人们的生活。在数字 展示平台上，群体动画也得到了一定的发展，如大规模公共场所的数字展示，在 这类场景中将涉及到大规模的群体运动，通常境况下人群处于正常状态，而对于 像安全通道和交通管理等场景的数字展示，还将涉及到群体处于异常状态下的运 动，同样由于群体的渲染复杂性和异常情况下运动的不确定性，使得群体动画在 该方向的发展收到了一定的限制。但随着渲染技术和群体技术的发展，群体动画 在该方向的发展将会更为顺畅。图1 3 为某城镇生活数字展示图。 图1 - 3 大规模动态场景技术在数字展示平台上的应用 1 0 第一章绪论 1 5 论文的主要工作和创新点 本文对群体动画的相关技术做了比较详细的介绍，重点研究了群体动画实时 渲染技术中关于模型简化的相关技术，内容主要包括基于不同方法的模型简化技 术算法实现，各种方法的比较，重点研究了基于采样点的模型简化技术的算法改 进和实现，以及动态场景中基于采样点的模型简化技术的运用。 论文的主要工作： ( 1 ) 介绍了当前已有的模型简化技术：顶点聚类、增量式简化、采样和自适 应细分，并对几种技术的优缺点进行了对比和分析。对大规模场景简化技术进行 了介绍和分析。 ( 2 ) 重点研究了基于采样点的模型简化技术，主要研究内容包括：采样点的 选取和裁剪技术，三角面片和采样点的混合技术，采样点和三角形面片的渲染技 术以及静态模型的采样点简化实现。 ( 3 ) 研究了运用基于采样点的模型简化技术来实现大规模群体的动画显示， 主要技术包括：基于关键帧的动画实现和文件替代技术的动画实现。 论文的主要创新点： ( 1 ) 为了加速模型的采样速度，采用固定网格的方法对原始模型进行采样， 摒弃了对原模型进行随机采样要逐个采样点进行选取的过程。 ( 2 ) 为了实现三角形的正确选取，而不直接使用固定网格采样出来的采样点 进行判断，而是对采样出来的采样点进行一系列的融合操作，获得正确采样的采 样点，删除掉冗余的采样点，再对其进行采样点和三角面片的选取。 ( 3 ) 分析和研究了当前已有的群体动画渲染技术，摒弃了基