（计算机软件与理论专业论文）群体动画实时渲染技术的研究.pdf

摘要 摘要 近年来，群体动画技术在多个领域中得到了广泛的应用。但是，以当前 的计算机硬件绘制能力来说，如果采用直接绘制的方法，则很难实现数量庞 大的群体动画的实时渲染。因此，人们更加重视群体动画实时渲染技术的研 究，使得这一领域成为极富挑战性的研究课题。本文研究群体动画实时渲染 技术，重点提高群体渲染的速率。本文对基于c p u 的矩阵调色板蒙皮技术 ( s k i n n i n g ) 、混合层次细节( l e v e lo f d e t a i l ，l o d ) 和替代物( i m p o s t o r s ) 的群体动画渲染技术以及基于g p u 的实例化( i n s t a n c i n g ) 群体动画渲染技 术进行了比较深入的研究。 群体动画的渲染实际上是由单个动画角色的渲染组成的。对于单个动画 角色的渲染，在应用程序是g p u 受限时，将优化工作交给c p u ，会取得非 常不错的优化效果。本文使用i n t e l 处理器上的流式s i m d 扩展( s s e ) ，在c p u 上对群体动画中常用的矩阵调色板蒙皮动画技术进行了优化。实验表明，使 用基于c p u 的群体动画渲染技术，在角色顶点受多个骨骼权重影响时，具 有非常好的性能提升。同时，本文还研究了一种通用的针对复杂网格模型的 优化方法。 三维复杂场景实时渲染技术的研究课题很多，但是大多都是局限于静态 场景对象。针对群体动画实时渲染，本文结合了l o d 和基于图像渲染的 i m p o s t o r s 技术，根据虚拟角色在最后屏幕中的细节信息来选择恰当的角色表 示，平衡了基于图像的渲染方法在渲染质量上的不足和几何渲染方法在效率 上的缺陷，有效地提升了群体动画的渲染效率。实验结果表明，该方法可以 用较小的渲染代价获得较高的渲染质量，满足实时渲染的要求。 图形硬件加速器的不断发展给实时群体动画的广泛应用带来了新的机 会。本文针对群体动画渲染中，大多数动画角色的模型完全相同的特点，从 减少绘制调用与状态改变的次数，降低对内存存储的需求着手，提出了基于 g p u 中实例化技术的群体动画实时渲染算法。实验表明，当使用实例化技术 渲染这类群体动画时，随着角色数量的不断增加，渲染性能将明显得到提高， 平均帧率比逐个角色单独渲染时高出4 0 以上。 摘要 最后本文对当前群体动画的发展方向进行了一些展望，并提出了一些在该领 域值得进一步研究的方向。 关键词：群体动画，实时渲染，基于图像的渲染，细节层次，替代物 i i a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，c r o w da n i m a t i o n sa r eb e c o m i n gm o r ep o p u l a ri nm a n y f i e l d s h o w e v e r , t h et r a d i t i o n a lr e n d e r i n gm e t h o d so nc u r r e n th a r d w a r ea r ef a r f r o me n o u g hf o r t h et a s ko fr e n d e r i n ga n da n i m a t i n gc r o w d so fv i r t u a lh u m a n si n r e a l t i m e t h e r e f o r e ，t h et e c h n o l o g i e so ft h er e a l t i m er e n d e r i n go fc r o w d a n i m a t i o n sh a v ef o r m e da ni m p o r t a n tr e s e a r c hf i e l d ，w h i c hi sv e r yc h a l l e n g i n g f o rm a n yy e a r st oc o m e t h i sd i s s e r t a t i o nf o c u s e so nr e a l t i m er e n d e r i n go f c r o w da n i m a t i o n st oe n h a n c i n gt h es p e e do fc r o w dr e n d e r i n g m u c he f f o r tw a s d e v o t e dt ot h ec p u b a s e ds k i n n i n ga l g o r i t h mf o rt h ec h a r a c t e r si nc r o w d s ，t h e r e a l t i m er e n d e r i n ga l g o r i t h mo fc r o w d sb a s e do nl o da n di m p o s t o r s ，a n dt h e i n s t a n c i n gm e t h o df o rg p u c r o w dr e n d e r i n g t h ep r o g r e s so ft h er e n d e r i n go fc r o w da n i m a t i o n si sa c t u a l l yc o m p o s e db y m a n yc h a r a c t e r s r e n d e r i n g f o rt h er e n d e r i n go fs i n g l ec h a r a c t e r ，ag o o de f f e c t w i l lb eg o tb yo p t i m i z i n gt h i so p e r a t i o no nc p uw h e nt h ea p p l i c a t i o ni s g p u r e s t r i c t e d t h i sd i s s e r t a t i o np r o p o s e dac p u - b a s e do p t i m i z e da l g o r i t h mt o a c c e l e r a t et h er e n d e r i n go fm a t r i xp a l e t t es k i n n i n gb yu s i n gt h es se ( s t r e a m s i m de x t e n d ) i n s t r u c t i o n0 ni n t e lp r o c e s s o r ，w h i c hi sv e r yp o w e r f u li nt h e r e n d e r i n go fc r o w da n i m a t i o n sw h e nt h ep o i n t so ft h ec h a r a c t e ra r ew e i g h t e db y m a n ys k e l e t o n s t h e r ea r eal o to fr e s e a r c h e sf o c u s e d o nt h er e a l - t i m e r e n d e r i n g t e c h n o l o g i e so f3 dc o m p l e xs c e n e s ，b u tt h e r ei n t e r e s t sa r e a l m o s to r i e n t e d t o w a r d st h es t a t i co b je c t s f o rt h er e a l t i m er e n d e r i n go fc r o w da n i m a t i o n s ，w e p r o p o s e dan o v e lh y b r i dr e n d e r i n ga l g o r i t h mf o rc r o w da n i m a t i o n st h a t s o l v e s t h ec l a s s i cp r o b l e mo fd e g r a d e dq u a l i t yo fi m a g e b a s e dr e n d e r i n gm e t h o d sa n d l o ws p e e do ff u l lg e o m e t r y - b a s e dr e n d e r i n g t h i si sr e a l i z e db yu s i n gi m p o s t o r s f o rc h a r a c t e r sw i t hl o wd e t a i l ，w h i l eaf u l l ，g e o m e t r y - b a s e dr e p r e s e n t a t i o nf o r c h a r a c t e r sw i t hf u l ld e t a i l t h er e s u l td e m o n s t r a t e st h i sm e t h o dc a p a b l eo f r e n d e r i n gc r o w da n i m a t i o n si nr e a l t i m ew i t ha l o wr e n d e r i n gc o s t i i i a b s t r a c t w i t ht h ed e v e l o p m e n to ft h eg r a p h i c sp r o c e s s o r ，an e wc h a n c ei sc o m i n gf o r t h er e a l t i m ec r o w da n i m a t i o n s b e c a u s em a n yc h a r a c t e r si nac r o w dh a v et h e s a m em e s h t h i sd i s s e r t a t i o nf o c u s e so nt h er e d u c t i o no ft h ea m o u n to f d r a wc a l l s ， s t a t ec h a n g ea n dt h er e q u i r e m e n to ft h em e m o r y , a n dp r o p o s e da ni n s t a n c i n g m e t h o df o rg p uc r o w dr e n d e r i n gb yr e u s i n gt h es a m em e s h e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ei n s t a n c i n g b a s e dc r o w dr e n d i n gt e c h n o l o g yc a nh e l pt o e n h a n c et h es p e e do ft h er e n d e r i n go fc r o w d c o m p a r e dw i t ht h et r a d i t i o n a l c r o w dr e n d e r i n gm e t h o d ，t h ef p so ft h er e n d e r i n go fi n s t a n c i n g b a s e dm e t h o di s 4 0 m o r eq u i c k l yt h a nt h ef o r m e r s k e yw o r d s ：c r o w da n i m a t i o n ，r e a l - t i m er e n d e r i n g ，i m a g e - b a s e dr e n d e r i n g , l e v e l o f - d e t a i l s ( l o d ) ，i m p o s t o r s i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：勺如缸日期：2 0 0 8 年3 月1 2 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：二丝导师签名：蓥睦茎支 日期：2 0 0 8 年3 月1 2 日 第一章绪论 1 1 课题来源 第一章绪论 本文的研究内容是实时群体动画中加速渲染技术的研究，是依据“虚拟 环境下群体动画实时模型与绘制技术( 2 0 0 7 a a 0 1 2 3 2 2 ) ”项目展开的。该项 目主要研究关于群体动画的若干关键技术，目标是构建一个群体动画引擎模 块，在我们已开发的三维图形引擎基础上增加群体动画控制模块，实现群体 行为验证演示系统。 1 2 课题背景 计算机动画作为计算机图形学的一个重要分支，是计算机图形学和艺术 相结合的产物。它是伴随着计算机硬件和图形算法高速发展起来的一门技 术，综合利用了计算机科学、艺术、数学、物理学和相关学科的知识在计算 机上生成绚丽多彩的连续的虚拟真实画面，给人们提供了一个充分展示个人 想象力和艺术才能的新天地。 而群体动画创作一直又是计算机动画创作中的一个技术热点、难点。 近年来，群体动画技术广泛应用于城市规划、电影动漫、游戏创作、训 练系统以及火灾等灾难现场模拟与辅助指挥中。通过对群体动画的真实模 拟，可以辅助电影动漫产生真实宏大的场景效果；可以在公共场所( 商场、 体育馆、娱乐场所等) 规划设计中模拟验证安全通道等设计的合理性；可以 为智能交通管理( 红绿灯有效设置、主干道路i s i 的交通流量管理) 提供模拟 环境；可以为警察和军队提供处理大量群体事件( 军队行军) 的训练系统； 也可以为灾难现场指挥提供指导和训练平台。目前，这方面的研究得到了广 大的重视，对群体动画的研究与创作工具产生了极大的需求。 但是由于在群体动画模拟中，所采用的动画角色模型制作技术日趋复 杂，动画系统各个模型之间的耦合度也日趋提高，致使群体动画的创作难度 日益加大。特别是当动画角色数量不断增多时，其计算量将呈非线性快速增 加，这极大地影响了群体动画的实时性，限制了这种方法的广泛应用。 电子科技大学硕士学位论文 1 3 研究目的和应用前景 随着群体动画模拟技术的日趋发展，尤其是其在各个领域的广泛应用， 人们对群体动画模拟不断提出了新的要求，群体渲染效果更加真实，渲染的 群体数量更多，并且还需要能实时地对用户的操作做出快速的反应，满足用 户的交互性需求。这些要求的实现都需要有强大的计算机计算能力为支撑， 然而就目前的计算机硬件水平来说，还不能够胜任这些工作，所以人们更加 重视群体动画渲染的算法和软件加速技术，使得这一领域成为重要的研究领 域和极富挑战性的课题。 实时群体动画的渲染技术在游戏产业、虚拟训练系统、数字展示等方面 有着非常广阔的应用前景。 1 ) 在游戏产业中的应用前景 在当前的计算机游戏中，群体动画的应用相对比较少。最主要的原因就 是由于群体动画实现的复杂性，尤其是当群体成员的数量增加时，为了能以 交互性的帧率渲染群体动画，满足实时性要求，需要较大的内存容量、高速 的c p u ，以及最新的图形硬件。此外群体动画创作本身也是非常复杂的。这 些都较大限制了群体动画在游戏产业中的应用。所以，研究群体动画实时渲 染技术，以交互性的帧率来渲染大规模的游戏角色，将成为未来游戏引擎中 的一个比较核心的技术，一旦突破这一技术，将提升游戏的表现品质。 2 )在虚拟训练系统中的应用前景 在警察和军队的训练模拟系统中，常常包含有对处理大量虚拟人群的虚 拟模拟，比如训练处理发生火灾、烟雾等危险情况下的人群运动。但是，一 是由于三维模型、场景本身的复杂性，二是由于大规模人群的运动，极大地 限制了此类训练系统的交互能力，不能很好的为用户提供辅助训练。因此， 只要群体动画实时渲染技术得到提高，使得在灾难等情况的人群指挥训练系 统中能够提供系统与用户的交互能力，则群体动画将在该领域得到很大的发 展空间。 3 ) 在数字展示领域中的应用前景 随着计算机图形学与虚拟现实技术的不断发展和成熟，数字展示领域也 2 第一章绪论 得到了较大的应用，比如城市数字化规划、校园数字化展示、交通流量展示 等等。这些数字化展示中都包含了大量的虚拟人群运动。就目前这些展示来 说，都还未增加数字展示的可交互性能力，让用户能实时地与群体交互，比 如通过设置红绿灯的时间，来观察人流和车流的变化，从而获得合适的红绿 灯设置范围。这些类似的需求都对群体动画实时渲染技术提出了更高的要 求。 1 4 国内外研究现状 大量3 d 虚拟角色的实时渲染一直都是具有挑战性的问题，即便是对于 当前具有多个存储资源、快速处理器和强大的图形处理卡的p c 系统来说， 大量3 d 动画的实时渲染仍将是个比较困难的任务。一方面要求渲染的群体 具有较强的真实感，另一方面又要求能提供交互性，满足实时性的要求，这 些都远远超过了计算机的硬件绘制能力。 目前在群体动画实时渲染技术方面的研究已经存在几种技术，这些技术 包括：裁剪技术、几何细节层次( l e v e l so f d e t a i l ，l o d ) 技术、基于图像的 替代物( i m p o s t o r s ) 技术和基于点的渲染技术( p o i n t b a s e dr e n d e r i n g t e c h n i q u e s ) 。前三类技术的一个共同思想是：在保持虚拟角色渲染的同时， 尽量减少场景的复杂性，降低需要渲染的多边形数量，从而加速渲染。 由于目前国内对于群体动画实时渲染方面的研究还处于起步阶段，本文 结束时，尚未出现相关方面的研究成果，所以，本文只对国外群体动画实时 渲染技术的研究现状做了介绍。 1 4 1裁剪算法 在真实群体模拟应用中，通常需要考虑两类问题：一是大规模静态场景 的可视化问题，二是可运动群体的可视化问题。由于这两类可视化问题包含 了成千上万的多边形面片，所以对具有大量群体动画的大规模场景进行渲染 将是一件非常耗费时间的事情。尽管能够以实时帧率来绘制成千上万的多边 形，但是对于如此之多的多边形绘制很有可能会在渲染帧间出现磁滞现象， 从而降低渲染画质和用户的交互能力。 为了解决这个问题，【l 】提出了裁剪算法，它的基本思想就是尽可能多地 电子科技丈学硕士学位论文 剔除掉那些在虽终的渲染图像上不可见的部分来达到降低场景复杂性的目 的。可见性剔除用在当物体在视锥体之外时，而闭塞剔除算法则用来在当物 体被场景中的其他部分所遮挡时，这些部分或全部不在视锥体之内的物体将 不会送到图形渲染管线。a i r e y 等人吐t e l l e r 和s e q u i n ”，l u e b k e 和g e o r g e s 4 使用了空间划分方法来尝试在一个复杂建筑场景中预先计算物体之间的可 视化遮挡关系。这些方法的中心思想是想预测下一帧中场景中的可见部分， 从而减少必须渲染的图元的数量。这需要使用存储器管理和观察者运动预测 来实现。 闭塞裁剪算法最主要的缺点是它需要对整个几何场景数据库进行特殊 的组织：场景通常被划分为多个小的单元。这使得闭塞裁剪算法不太适合于 像群体动画这样可变形的、运动的物体。由于这个限制，闭塞裁剪算法不能 应用到群体动画模拟上来。但是，如果所模拟的群体在一个比较密集的被遮 挡的虚拟环境中时，闭塞裁剪算法可应用在群体动画模拟的高层裁剪上，比 如裁剪掉被密集建筑物遮挡的运动的群体角色。 圈1 - 1 密集城市环境中的群体动画裁剪结果 t e c c h i a 5 蝗出了一个新的闭塞裁剪算法，基于二叉树合并的动态裁剪算 法，当视点离地面比较近时，建筑物就成为了非常有效的遮挡物。t e c c h l a 第一章绪论 的方法使用城市场景的离散性和属性来对不可见的静态几何模型和运动的 群体角色模型进行快速的裁剪。首先，先建立一颗几何场景的k d t r e e ，用 来作为二维网格的划分。然后，在每一帧渲染时，从当前视点建立一颗闭塞 树，并将该闭塞树作为k d t r e e 的叶子添加到k d t r e e 上，间接地将那些可 见的或者被遮挡的网格也作为k d t r e e 的叶子添加到k d t r e e 上。最后，在 对每一个群体角色做进一步处理之前，去检查被占据的网格的状态，是可见 还是被遮挡，如果该网格被遮挡，则剔除掉占据该网格的虚拟角色。图1 1 是在高度密集的城市场景中对运动中的群体动画进行裁剪的结果。 1 4 2 几何细节层次技术 在实际的群体动画模拟中，我们能够完全感知到的具备完整细节信息的 角色成员只占整个群体角色的较小部分。并且，通过实验表明，同等的对待 群体中的每一个成员是相当费时，同时也是没有必要的。当前的显示屏能同 时显示大约2 0 0 万个像素，而一个比较复杂的虚拟角色就能够包含大约 1 0 0 0 0 个三角形。即使我们假设每一个三角形被投影到一个像素，而且虚拟 角色之间并不存在任何的重叠，那被角色完全覆盖的显示屏也只能同时包含 2 0 0 个虚拟角色。当然，在实际应用中，渲染的角色数量还会更少些。比较 合理的估计是只需要渲染十几个具备完整细节信息并且可见的虚拟角色模 型，群体中的其他角色要么是被这些完全可见的角色所遮挡，要么就是处在 屏幕空间中不太重要的位置。所以，重点考虑那些比较重要的虚拟角色模型， 而用不太复杂的相似物来代替其他不重要的虚拟角色模型，这样做的意义更 大。 几何细节层次技术( g e o m e t r i cl e v e lo f d e t a i l ) 就是通过同一个物体的多 个不断降低复杂性的简化表示方法，来不断减少需要渲染的多边形面片的数 量，从而提高渲染的速度。在渲染每一帧时，需要选择合适的模型或分辨率。 选择的标准被称为几何模型l o d 解析器，通常是根据物体相对于观察者的 距离大小来进行选择。另外，物体的运动同样也需要考虑细节层次的作用， 即动作细节层次( m o t i o nl o d ) 使用l o d 的主要障碍是关于多分辨率的建模问题，也就是，关于从3 d 物体自动生成与原始物体尽可能相似的，简化的，粗糙的3 d 表示的问题。 为了克服这个i 口- j 题，a u b l e 等人【6 】通过b s p l i n e 片构建虚拟角色模型。他们 电子科技大学硕士学位论文 为每一个身体部分( 手臂、腿等) 附加一块b s p l i n e 片。这样就能比较容易 地生成身体各部分不断粗糙的相似网格模型。如图1 2 所示。值得注意的是， 他们对身体的末端部分采用比较灵活的简单纹理替代物表示，降低了表示的 分辨率，从而减少了需要渲染的三角形面片数量。 襄襄曩蹙 图1 - 2 多分辨率虚拟角色左边：网格： 右边：具有纹理的模型 在 7 i 中，h e c k b e r t 和g a r l a n d 对网格简化技术进行了概述。除了多分辨 率建模的问题以外，在虚拟现实应用中使用l o d 是非常简单的。f u n k h o u s e r 和s e q u i n 【s 1 针对为 个场景中的每一个渲染对象选择最好的分辨率提出了一 种有益的启发式算法。在该启发式算法中，需要考虑几个要素：图像空问大 小( i m a g e s p a c es i z e ) ，用于减少由远距离物体带来的复杂度；物体与视线 的距离，因为在视线范围之外，视觉系统不能正确感知物体的信息；动作， 当眼睛在观察快速移动的物体时，总是模糊不清。由于不同的物体在整个模 拟中所扮演的作用不一样，所以每个物体都被赋予了不同的优先权。为了避 免物体在两种l o d 之间进行切换时发生视觉上的偏移效果，还需要考虑滞 后作用。p r a t t 等人 9 1 在大规模、联网的虚拟环境中，已经将细节层次技术运 用到了虚拟人群的模拟上。他们使用了启发式算法来决定触发l o d 切换的 观察距离。在他们的应用中，每一个被模拟的虚拟角色人物具有四种不同的 分辨率，虽多可包含5 0 0 多个多边形面片，虽少的只有3 个多边形面片。从 观察者的角度来看，因为该系统能保持高速的刷新频率，所以这种方法还是 令人满意的。但是，由于只渲染了非常少量的多边形面片，所渲染的群体动 画所表现的真实感不强，所以从真实性和审美学观点来看，该方法的渲染效 果比较贫乏。 第一章绪论 1 4 3 基于图像的替代物技术( i m p o s t o r s ) 基于图像的替代物技术是用于加速群体动画渲染的方法之一。替代物实 际上是多个具有部分透明纹理的多边形，这些多边形包含了3 d 角色模型面 向摄像头的一个快照。 a u b l e b o l 等人将动态生成的布告板技术运用到了3 d 虚拟人物角色动画 的渲染上。在该方法中，纹理是在需要的时候才生成的，而不是事先就计算 好的，并且替代物的生成过程是和对3 d 虚拟角色模型进行快照( s n a p s h o t ) 并行执行的。这些被缓存起来的3 d 角色的快照将会在某些渲染帧中持续取 代几何模型，直到由于摄像机或者虚拟角色的移动足以引起使用其他快照 时，才会去刷新布告板上的纹理。 图t - 3 【l “使用i m p o s t o r s 技术实时地渲染了大量的城市虚拟人群；但是当视点拉近时被 渲染出来的虚拟人物匮质非常低 在使用布告板来进行群体动画渲染的主要研究工作中，t e c c h i a 等人【1 i 】 提出了一种虚拟城市中群体动画模拟的实时渲染方法。与先前的方法相比， 布告板不再是动态生成的，而是在预处理阶段就已经生成。快照( s n a p s h o t ) 是从分布在虚拟角色周围的视点采样得到的，这个过程将在动画的每一帧中 重复执行。在运行时，从接近于实际摄像机位置的视点拍摄的快照图像被用 作布告板的纹理。另外，布告板的侧面被当作投影到地面的阴影。通过改变 电子科技大学硕士学位论文 布告板的颜色，多重纹理增加了虚拟角色的多样性。在后期的工作中，他们 【1 2 1 加入了使用法线映射的光照效果。他们的这种使用预先计算好的替代物方 法要比动态替代物( d y n a m i ci m p o s t o r s ) 方法快，但是对纹理缓存的依赖性 比较大，这将导致低质量的渲染画质，如图1 3 所示。 1 4 4 基于点的渲染技术( p o i n t - b a s e dr e n d e r i n gt e c h n i q u e s ) 另外一种用于快速群体渲染的方法是使用基于点的渲染技术 ( p o i n t b a s e dr e n d e r i n g t e c h n i q u e s ) 。w a j l d 和s t r a s s e r 1 3 】提出了一种多分辨率 的渲染方法，该方法结合基于图像的多边形渲染技术( i m a g eb a s e da n d p o l y g o n a lr e n d e r i n g ) 。他们为动画的每一帧创建了一颗视点依赖的八叉树， 树上的每一个节点要么存储一个多边形，要么存储一个点信息。可以在一颗 八叉树到另一颗八叉树之间进行线性插值。当观察者距离视点比较远时，虚 拟角色使用点渲染技术来渲染，而当摄像头拉近，虚拟角色被放大时，则使 用多边形渲染技术来渲染虚拟角色；在这两者之间时，混合使用这两种技术。 1 5 论文的主要工作与创新点 本文对群体动画相关技术进行了比较详细的介绍，并重点对群体动画实 时渲染技术进行了研究和分析，内容主要包括大规模虚拟人群模拟所涉及的 若干关键技术、实时绘制技术和加速技术、虚拟3 d 角色模型的通用优化技 术、群体动画实时渲染加速算法。在对这些技术进行分析和研究的基础上， 提出了一个适用于大规模虚拟人群渲染的引擎架构。 论文的主要工作包括： 1 ) 对群体动画中常用的矩阵调色板蒙皮技术和i n t e l 处理器上的s s e ( 即 流式s i m d 扩展，s t r e a ms i m de x t e n d ) 指令进行了分析和研究，并 实现了使用s s e 来加速矩阵调色板蒙皮算法，提高了渲染效率。 2 ) 研究了计算机图形学中三维复杂场景的实时绘制技术和加速技术，并 将这些技术用于群体动画实时渲染中，在加速群体动画实时渲染上取 得了不错的效率； 3 ) 提出了基于可编程图形硬件的群体动画实时加速渲染算法，对该算法 的效率进行了分析，并在此基础上提出了进一步的改进方向。 第一章绪论 本文的主要创新点在于： 1 ) 将三维复杂场景实时绘制技术与群体动画模拟相结合，加速了群体动 画渲染的效率，有益于将实时群体动画应用到其他研究领域中； 2 ) 提出了基于g p u 中实例化( i n s t a n c i n g ) 技术的群体动画实时渲染加 速算法，通过重用存放在顶点缓存中的模型数据，将多个角色模型的 绘制在一次绘制调用中完成，减少了绘制调用和绘制状态的改变，节 省了c p u 的时间； 3 ) 提出了一种群体动画实时渲染的引擎架构。该引擎架构综合了群体动 画实时模拟的相关方面，内容包括了群体渲染和群体行为规划两个主 要的方面，为“虚拟环境下群体动画实时模型与绘制技术 ( 2 0 0 7 a a 0 1 2 3 2 2 ) ”项目的进一步开展提供了一些研究思路。 1 6 论文的章节安排 全文共分八章，对群体动画实时渲染技术进行了详细的分析与研究，主 要研究工作集中在第五、六、七章，章节安排如下。 第一章绪论。主要介绍本文的课题来源、课题背景，对国内外研究现 状进行综述，并指出论文作者的主要工作和创新点。 第二章群体运动模拟。本章主要介绍了群体运动模拟的相关技术，包括群 体行为的起源和研究领域、群体动画的需求和限制、群体动画领域的研究内容、 群体的行为建模、群体的环境建模等。 第三章实时绘制技术和加速渲染技术介绍。在这一章里，我们介绍了常用 的实时绘制加速技术，这些技术包括可见性裁剪技术、基于几何模型的实时绘制 和加速技术、基于图像的实时绘制和加速技术以及基于可编程图形硬件的加速技 术。虽然这些技术在以前的研究工作中，主要是应用在静态的三维复杂场景中， 但是对这些实时绘制和加速技术稍加修改，就可用于群体动画渲染中。 第四章群体动画渲染系统设计。本章提出了一种群体动画的引擎架构，指 出了群体渲染在整个群体引擎中的重要作用。该架构包括群体动画的两个主要部 分，即群体动画行为引擎部分和渲染部分。接着详细描述了渲染系统部分的设计。 9 电子科技大学硕士学位论文 第五章基于c p u 的矩阵调色板蒙皮( s k i n n i n g ) 技术优化研究。本章 在对群体动画中常用的矩阵调色板蒙皮动画技术和i n t e l 处理器上的s s e 做 了详细的分析和研究后，使用i n t e l 处理器上的流式s i m d 扩展( 即s s e ) ， 在c p u 上实现了对s k i n n i n g 算法的优化，取得了一定的加速效果。 第六章基于l o d 和i m p o s t o r s 技术的群体动画实时渲染算法研究。在对 细节层次技术( l e v e l so f d e t a i l s ，简称l o d ) 和替代物( i m p o s t o r s ) 技术做了较 为深入的分析和研究后，针对实时群体动画模拟的交互性要求，提出了基于细节 层次技术和替代物技术的实时群体动画加速算法，从减少需要绘制的三角形面片 数，降低三维场景复杂性的思路入手，根据群体中成员的重要性不同，对不同的 角色采用不同的模型表示，并根据视点的改变在不同表示之间切换，提高了群体 动画模拟的渲染速率，满足了实时交互性的要求。 第七章基于i n s t a n c i n g 技术的群体动画实时渲染算法研究。在分析和研 究g p u 中实例化( i n s t a n c i n g ) 技术的基础上，将该技术运用到群体动画渲染上， 通过重用内存中的角色模型数据，在一次绘制调用中，渲染多个虚拟角色，从而 减少了c p u 提交批次的时间和渲染状态改变的次数，把c p u 资源留给了逻辑处 理、物理系统、人工智能等其他任务，提高了群体角色渲染的速率。 第八章总结与展望。全文最后一章，对全文工作进行了总结，并对未来的 研究工作进行了展望。 l o 第二章群体运动模拟介绍 第二章群体运动模拟介绍 群体运动即是漂亮的，同时也是复杂的。漂亮是因为群体运动中的同步 性、同质性和一致性，使人在视觉效果上产生美感。比如闲游在山谷中数不 清的蝴蝶，草原上无边无际的羊群等等；在电影或者动画影片中，出现的壮 观的战争场面，常常会引起观众心灵的振奋，释放的感觉。而复杂则是因为 为了实现上述的壮丽场景，需要处理大量的数据。 所谓群体运动，是指在画面中有大量的群体，这个群体做着大致相同的 行为，即他们拥有同一个目标，但是仔细观察每个个体的动作和造型，又会 发现他们存在细微差异。 历史表明，在理解和控制群体人群的行为和动作方面，人们总是充满了 兴趣。心理学家和社会学家已经对人群的行为研究了很多年，他们研究的重 心是当人群因为拥有相同的目标而成为一个实体时所产生的效果。当这种情 况发生时，人们会失去他们原先的个体性，转而表现出群体实体的行为，这 种群体行为完全不同于他们单独时表现出来的个体行为。 只有在研究群体时，某些问题才会出现。比如，碰撞规避问题，与避免 个体之间碰撞的规避方法相比，在同一个地方涉及大量个体的碰撞规避方法 就需要不同的策略。同样地，适用于一起行走的群体的动作规划所需要的信 息自然要比实现单个个体动作规划所需要的信息多。即使群体中的成员代理 拥有相同的环境和目的，在他们作为群体的一部分时，所进行的路径规划也 与作为单独个体时是不一样的。 此外，群体并不仅仅是大量个体的简单组合，可以将群体划分为多个组。 当对待处于不同层次结构中的群体时，其他层次的群体行为可以同时存在。 为了适应不同组的结构( 比如，跟随、排斥、吸引等) ，组的行为则用来指 定该组整体的运动、行为和表现形式。为了改善群体的自治性和智能性，比 如感知能力、情绪状态、记忆力、沟通交流等，需要对个体的能力进行比较 详细的设计。然而，当我们考虑成千上万的个体时，由于硬件的限制和计算 的频率要求，不能够单独给每个个体提供这些复杂的行为。 电子科技大学硕士学位论文 为了实现群体的应用，需要其他的一些需求。比如，为了移植虚拟环境 到虚拟现实系统中，则需要保证群体运动模拟的实时性。为了给模拟群体的 行为提供工具，则需要社会习俗的内在联系。同样，为了模拟安全系统，则 需要提供正确性认证。 本节将介绍群体运动模拟的相关方面内容与研究，内容包括群体运动模拟的 起源和研究领域、需求和限制、所涉及的问题、群体运动中的路径规划和碰撞检 测、群体的行为建模、群体的环境建模、群体渲染等，并在这基础上，分析了一 些相应的应用。 2 1 群体运动模拟的起源与研究领域 群体行为早在1 9 世纪就已经开始研究【l4 1 ，但是尝试用计算机建模来模 拟群体行为则是最近才开始研究的。在过去的2 0 几年里，群体行为方面的 研究者涉及的领域非常广泛，比如建筑学领域【15 1 ，【16 1 ，【17 1 ，计算机图形学 领域【18 1 ， 1 9 】，【2 0 1 ， 2 1 】，【2 2 1 ，物理学领圳23 1 ，【2 4 1 ，【25 1 ，以及社会学领域【2 6 1 ， 【2 7 】都一直在进行关于群体行为的模拟。然而，尽管群体模拟基础非常广泛， 但是各学科间的交叉研究却非常少。 我们可以把群体运动模拟划分为两大领域。第一个领域重点研究动作行 为的真实性方面，该领域通常可以通过简单的2 d 可视化来对群体运动进行 模拟，比如撤退模拟、社会群体模拟。在该领域，模拟的行为通常从一个有 限的、可控制的效果( 比如人群冲向出口或者人群围成一个环状的群体结 构) ，到特定情况下的真实世界群体运动的一致有效性结果。在理想情况下， 模拟的结果是和真实人群运动相一致的。2 d 可视化效果是用来帮助理解模 拟结果的，但它不是至关重要的。多数情况下，一种具有颜色的点或者是可 变标识来描述群体中的成员就已经足够了。 第二个领域研究的目的就是要有高质量的可视化效果，比如在电影作品 创作和计算机游戏中的群体运动模拟。在这种情况下，行为模型的真实性就 不是太重要，而令人信服的视觉效果才是所关心的重点。 然而最近的研究趋势好像是要把这两个领域结合起来，成为群体运动模 拟的一个新研究领域。在这个领域中，面向可视化效果的群体系统尝试融合 更好的行为模型，从而简化令人信服的动画创作；而面向行为的群体模型则 第二章群体运动模拟介绍 尝试达到更好的可视化效果，尤其是在撤退模拟领域。可以预想到，训练系 统可能是要求最为苛刻的群体运动模拟，因为训练系统为了保证训练的有效 性，会同时要求群体行为的有效性复制和高质量的可视化效果。 2 2 群体模拟的需求和限制 相比于只涉及少量具有交互性的群体系统( 比如当前大多数计算机游 戏) ，或者是相比于非实时的群体运动模拟应用( 比如电影中的群体，或者 是离线模型计算之后的群体撤退模拟) 来说，实时群体动画面临更多不同的 挑战。同单个个体模拟相比，概念上最主要的不同就是需要对可视化、运动 控制、动作等在群体各个层次结构上的变化进行有效管理。当多个虚拟角色 个体组成一个群体时，不论是运动还是反应上，都应该与单个个体时表现不 同，这使得群体运动的模拟相当复杂。 同非实时群体模拟相比，实时群体模拟最主要的技术挑战就是对可计算 资源需求的不断增加，这些资源包括通用的处理能力、图形性能、存储空间 等。实时群体模拟最主要的限制因素是群体渲染。 2 3 群体模拟的相关问题 为了构造虚拟环境中群体的真实模拟，许多问题需要考虑，包括： 1 ) 虚拟个体的生成：怎样产生组成全新群体的单个个体? 怎样创建一个 具有所期望的特征的个体? 2 ) 群体动画：虚拟个体如何移动? 如何在静态环境和动态对象环境中避 免碰撞? 一个组以何种方式进行移动? 3 ) 群体行为的生成：虚拟群体如何对他们所处环境的改变进行响应? 个 体代理如何对其他个体代理的行为进行反应? 为多个代理进行认知 建模的合适方式是什么? 4 ) 虚拟群体的交互：哪些信息需要与用户进行交互来控制虚拟人群? 该 如何交互? 最有效的用于指挥群体的方法是什么? 5 ) 虚拟群体的渲染：怎样快速地显示多个运动的角色? 怎样显示外貌的 变化? 电子科拄大学硕士学位论文 6 ) 虚拟环境中群体的融合：环境的哪些方面需要建模? 环境中对象的哪 些描述适用于快速行为计算? 上面提到的各个方面在某种程度上，或多或少地交错联系。比如，渲染 的效率限制了行为和外貌的可能变化；上层的行为控制了低层的运动系统， 但是群体中的行为要对移动中面临的碰撞做出合适的反应；行为模型影响了 交互的可能性；环境表示又会对可能的行为产生影响：关联现实的和虚拟的 人群又将导致更为复杂的行为和环境表示等等。 2 4 群体运动中的路径规划与碰撞检测 2 4 i 碰撞检测 对于有指导的虚拟人群，首先要解决的是路径规划问题，其次还有碰撞 检测问题。在机器人领域有大量的相关内容可供参考，人们在研究虚拟人群 模拟的过程中也提出了些方法。m u s s e 等人口”通过检测个体前进方向上是 否有其他个体存在，判断是否有碰撞发生，并且采用两种规避碰撞荒略：等 待规避碰撞策略( 图2 - 1 ) 和绕行规避碰撞荒略( 圈2 2 ) 。hkk i m 等人口9 】 采用了分割区域的方法，并为每个人设置个触角圆柱体用于探测其所在方 形内其他的个体( 邻居) 。不足之处：触角圆实际上就是个体的感知范围， 太大计算量会增加，太小就不能模拟人的视觉。 j| 图2 - 1 等待规避碰撞策略图2 - 2 绕行规避碰撞策略 2 4 2 路径规划 r e y n o l d s 提出了领队跟随和路径跟随模式。对于被指定的组，领队跟随 运动模式的组内成员分为领队和跟随者，当指定领队的运动速度、方向和目 ju盟刊? 忸i，用 第二章群体运动模拟介绍 标位置以后，跟随者的运动就完全由领队控制，初始状态时的领队和跟随者 的相对位置关系和目标状态时的领队和跟随者的相对位置关系相同。同理， 路径跟随行为使组内个体沿着预先设定的路径行进，路径被抽象成轴线和半 径，这种路径类似公路、走廊或通道等。如果初始时个体距离路径较远，那 么他必须首先靠近路径，然后跟随路径行进。 k a l l m a n n 等人【30 】提出了一个基于完全动态局限性d e l a u n a y 三角测量的 快速路径规划算法。b a y a z i t 等人【3 1 】使用全局路标来改进在复杂环境中的群 体路径规划，通过使用嵌入在群体成员和路标上的规则信息，群体表现出多 种行为，包括回家、目标搜索、遮挡、领路等行为。t a n g 等人【3 2 】使用了一 种改进的a 木算法在由高度图生成的地形网格上进行路径规划。不久， l a m a r c h e 和d o n i k i a n t 圳为快速层次路径规划提出了一种几何环境的拓扑结 构，以及为虚拟群体提出了一种可反应的导航算法。p e t t r e 等人【3 4 】又展示了 如何使用三维圆柱体来自动地计算多层次导航图，此研究工作表面了如何重