（计算机应用技术专业论文）三维游戏技术的研究与实现.pdf

哈尔滨工程大学硕十学位论文 摘要 三维游戏技术目前已经广泛应用于各种研究领域，如虚拟现实系统、汽 车模拟训练系统及军事仿真系统等。它推动诸多领域的发展，并已经成为当 今的研究热点。 基于三维游戏技术的重大意义，本文将主要对三维游戏中的碰撞检测技 术和路径搜索算法进行深入详细的研究。 首先，提出三维游戏系统的设计思想，设计三维游戏引擎的总体框架。 其次，通过对碰撞检测技术的深入研究，针对轴对齐包围盒碰撞检测算法中 的包围盒不紧密，检测不灵敏等缺点，对该方法进行了改进，改进后的碰撞 检测方法能有效地减少运算时间，提高游戏的运行速度。此外，论文详细研 究了游戏中的人工智能技术，主要针对人工智能技术中的有限状态机技术和 路径搜索算法迸行研究与分析，根据系统需求对a 路径搜索算法进行改进与 优化，通过分级路径搜索、约束a 算法搜索范围以及加权启发式函数来达到 快速、有效、真实地智能化路径搜索。最后，实现三维游戏系统，该系统渲 染流畅、真实性好、易操作、实用价值较高。 关键字：三维游戏；三维游戏引擎；碰撞检测；路径搜索 a b s t r a c t 3 d 卿et e c h n i q u e sa r ea p p l i e di ns e v e r a lf i e l d sr e c e n t l y , s u c ha sv i r t u a l r e a l i t ys y s t e m s i m u l a t i o nt r a i n i n gs y s t e ma n dm i l i t a r ys i m u l a t i o ns y s t e ma n d s o o n 3 dt e c h n i q u e sh a v ei m p e l l e dm a n yd o m a i n st o b ed e v d o p m e n ta n da r e b e c o m i n g h o tt o p i c a c c o r d i n gt ot h eg r e a ts i g n i f i c a n c eo f3 dg a m et e c h n o l o g y , t h i sp a p e r w l l l d od e t a i l e dr e s e a r c ho nm a i nt e c h n o l o g i e so f3 d f i r s t l y , t h i sp a p e rp u t sf o r w a r dt od e s i g nc o n c e p t ，d e s i g n st h e m a i nf r a m eo f 3 dg a m e s e c o n d l y , t h r o u g hr e s e a r c h i n gc o l l i s i o n d e t e c t i o nt e c h n o l o g i c s ，t h e ：i i i l p r o v e d c o l l i s i o nd e t e c t i o nm e t h o di sp r o p o s e db a s e d o na l i g n e da x i s b o u n d i n gb o xa c c o r d i n gt os o m ed i s a d v a n t a g e so fc o l l i s i o nd e t e c t i o n m e t h o d s t h ei m p r o v e dc o l l i s i o nd e t e c t i o nm e t h o de f f e c t i v e l y r e d u c e so p e r a t i o nt i m e ， a d v a i l c e dg 锄es p e e d t h i r d l y , t h r o u g hr e s e a r c h i n ga r t i f i c i a li n t e l l i g e n c ef o r3 d g a m e ，p a t hs e a r c hm e t h o di si m p r o v e da c c o r d i n gt o t h en e e d so fs y s t e m t l l e i m p r o v e di d e au s e sr e s t r i c t i n g s e a r c hr a n g eo fa 宰s e a r c ha r i t h m e t i cw i t ht h e s h o r t e s tp a t h i tc 趾g e ti n t e l l i g e n tp a t hs e a r c he f f i c i e n t l ya n df a c t u a l l y f i n a l l y , t h e3 dg 锄es y s t e mi sr e a l i z e db a s e do n3 de n g i n et e c h n o l o g i e s t h es y s t e mi s r e n d e r e ds m o o t h l y ，a u t h e n t i c a l l y , m a n i p u l a t e de a s i l y k e y w o r d s ：3 dg a m e ；3 de n g i n e ；c o l l i s i o nd e t e c t i o n ；p a t hs e a r c h 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：互搏伶 日期：p 口9 年3 月b 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：夏粤伦 e t 期：矽四年3 月f 弓e t 导师( 签字) ：写分需 嘲年；月够日 哈尔滨t 程大学硕十学位论文 1 1 选题意义与背景 第1 章绪论 随着经济和社会的发展，三维游戏开发已经成为社会各界的重要研究领 域。由于计算机软件和硬件的迅速发展及对游戏技术的深入研究，人们对游 戏的真实性和趣味性要求越来越高。游戏中的碰撞检测技术可以真实地反应 物体的作用；人工智能是模拟物体的智能性，不仅可以提高游戏的真实性， 也可以增加游戏的趣味性。于是，碰撞检测技术和游戏中的人工智能技术已 经成为目前游戏研究领域的热点问题。 目前，各界对碰撞检测技术及人工智能技术有一定的研究，但对应用于 游戏中的碰撞检测和人工智能研究较少，尤其是高校对三维游戏技术的研究 尚未普及。虽然有很多优秀的碰撞检测算法和人工智能技术，但是在游戏开 发中，不同的应用场合，对物体碰撞的实时性和精确性及游戏角色的智能性 的要求不尽相同。而大部分碰撞检测算法都是针对具体的应用场合设计的， 主要集中于在静态环境下两包围盒树之间的碰撞检测研究，对于动态虚拟场 景中多虚拟对象之间的高效碰撞检测算法还不多。 图形技术渲染出漂亮的游戏场景是不能够满足人们的需求，必须有合理 的人工智能技术来保证游戏的智能化和趣味性，这对人工智能技术提出了新 的挑战。在游戏中，寻路已经成为游戏中的一个核心部分，是人们研究的热 点问题。游戏中的精灵通常需要从一点移动到另外一点，这就要求能够找到 一条最佳路径，并合理地躲过障碍物，这种问题的解决就要用到人工智能的 路径搜索技术。搜索技术渗透在各种人工智能系统中，如专家系统、自然语 言理解、自动程序设计、模式识别、机器人学习、博弈都应用了搜索技术。 游戏中的路径搜索算法通常都是两个静态点之间的寻路，搜索的路径不自然， 搜索速度慢，算法效率低，还没有研究出种适合游戏的高效，快速的路径 搜索算法。 碰撞检测技术和人工智能技术不仅可以用于游戏开发，还广泛应用于教 育、虚拟现实、文物保护、地理信息系统、军事训练、科研、娱乐和商业等 哈尔滨t 稃大学硕十学位论文 领域。因此，加强三维游戏技术的研究具有重大的实际意义。如果成功研究 出适用于三维游戏的碰撞检测技术和人工智能技术将具有巨大的理论意义、 实用意义及广阔的应用前景。 本课题以三维游戏开发为依托平台，深入地研究游戏中的碰撞检测算法 和人工智能技术，针对碰撞检测算法中的计算量大，计算速度慢及碰撞检测 不精确的问题，通过分类包围盒、分段检测的方式与空间剖分方法相结合的 方法改进游戏中的碰撞检测，该改进方法可有效地提高碰撞检测算法的精度 和速度。此外，通过改进a 算法的路径搜索方式，约束搜索范围及加重启发 函数权值的方法来完善游戏中的路径搜索算法，改进a 路径搜索算法中的搜 索时间长，搜索速度慢等问题。 1 2 研究现状 2 0 世纪9 0 年代以来，随着软件技术的进步，硬件产品性能的提高，三 维游戏的真实性和趣味性越来越受到关注，游戏中的碰撞检测技术和人工智 能技术成为了各界的研究热点。 1 2 1 碰撞检测算法的研究现状 碰撞检测问题的研究起源于2 0 世纪7 0 年代，至今，已经在碰撞检测领 域做出了很多成果，已有了一些比较成熟的碰撞检测技术。 早期开始研究的是静态碰撞检测技术，d o b k i n 、a g a r w a l 、c h a x e l l e 等 在这方面做了研究。静态碰撞检测主要是检测静止状态中各物体之间是否发 生碰撞的算法，这在计算几何中得到了广泛应用，这类算法对算法精度要求 较高而对实时性的不作要求。 由于碰撞检测准确性要求的提高，c a m e r o n 、c a n n y 和r e d o n 在连续碰撞 检测算法进行了研究，但连续碰撞检测算法涉及到四维结构和时间的问题， 算法虽然精确，但计算复杂高，计算速度慢，在大规模场景中无法实时进行 碰撞检测。 王兆其、王志强、l i n 及j i m e n e z 等一直致力于基于物体空间的碰撞检 测算法，该算法是把层次表示法、几何推理、代数范式、空间划分、解析方 2 哈尔滨工程大学硕十学位论文 法和最优化方法等多种技术应用于碰撞检测。l i n 还提出了“最邻近特征算 法 并按照物体的特征进行区间划分。 h o f f 和k i m 等将图像空间碰撞检测和物体空间碰撞检测算法结合起来， 利用二者优点增强算法的功能，同时通过一定的负载平衡策略在c p u 与g p u 之间进行调配来保证算法的整体效率。 s m i t h e r a l 提出了一种基于a a b b 包围盒的角色变形体对象的方法，该方 法在每一步都重新计算对象的包围盒，其缺点是当模型复杂时不能得到实时 计算。 v a n d e nb e r g e n 提出了一种基于s o l i d 库的方法，并时刻由叶子节点开 始完成自底向上的更新，缺点是发生大尺度的变形时，a a b b 包围盒的紧密性 就比较差并且包围盒之间有很大的重叠区域。 y a s h i f u m ik i t a m u r a 等人提出了一种用于解决复杂场景下的变形体的碰 撞检测算法，这种算法的本质是包围盒方法与空间分解法的结合，该方法的 缺点是采用八叉树的数据结果复杂。 j m e z g e r 等人在模仿布料仿真时对层次包围盒结构做出了很多优化，它 采用的包围盒类型是k - d o p s ，由于k - d o p s 在最坏情况下只需k 2 次相交测 试，因此j m e z g e r 等人采用的是四叉树。方法的优点是减少相交测试时递归 调用尝试，一定程度上减少了内存消耗，此外它采用“向量圆锥解决自相 交的问题。 m a t t h i a st e s c h n e r 等人提出了一种优化的哈希表来解决变形体以及自 相交问题。 国防科学技术大学的魏迎海等人提出了一种基于固定方面凸包f d h 包围 盒层次的碰撞检测方法，该方法用于虚拟手术仿真，解决了复杂环境中的碰 撞检测问题。 浙江大学的范昭炜等人对实时碰撞检测技术进行了研究，利用图形硬件 的高计算性能、可编程性及多处理机的并行计算能力来加速碰撞检测过程。 1 2 。2 人工智能技术的研究现状 2 0 世纪7 0 年代游戏中的人工智能领域才开始引起注意。在最近几年中， 哈尔滨t 程人学硕十学何论文 智能游戏得到了长足的进步，从而使当今的智能游戏比以前的游戏更加有趣。 人工智能已经成为决定每个游戏成功的重要因素。游戏只靠图形技术渲染出 真实的场景是不够的，必须依赖合理的人工智能技术来保证游戏的真实性和 趣味性。 比较有代表性的是m i c r o p r o s e 公司的“文明”系列，它们采用了欺骗的 手段使虚拟人物来应对复杂场面。1 9 9 8 年，人工智能在三维游戏中的应用开 始被重视。l o o k i n gg l a s s 工作室开始在游戏中加入脚本序列技术并对人工智 能引擎进行改进，l o o k i n gg l a s s 工作室自行开发的d a r k 引擎，游戏中的敌 人可以根据声音辨认对物的方位，并且能分辨出不同的地面上的脚步声，在 不同的光照环境下有不同的视力等等一系列比较高端的人工智能技术。 近来，美国b l i z z a r d 娱乐公司的“魔兽争霸 采用了强大而有趣的策 略智能技术，m i c r o s o f t 公司的e n s e m b l e 工作室制作的“帝国时代”则具有 至今为止最强大的策略智能。v a l v es o f t w a r e 公司的“半条命 也应用了高水 平的战术智能，而e p i cg a m e s 公司开发的“虚幻竞技场 则因为其可扩展性 和高超策略而闻名。在模拟类游戏中，美国e a 公司久负盛名的“模拟人生 及“模式城市”最早成功采用了人工生命技术。其中，游戏t h es i m s 采用了 许多极具个性的智能体，证明了有限状态机和人工生命技术的巨大潜力。麻 省理工学院( m i t ) 主要研究三维引擎技术中的人工智能、机器人和计算机图形 学以及动画技术，并在人工智能技术方面做了很多成果。 1 3 存在问题 纵观国内外的相关资料，三维游戏技术的研究已经取得了很多成果，涌 现了很多的优秀的碰撞检测算法和人工智能技术，但是在不同的三维游戏中， 对碰撞检测实时性和精确性及人工智能技术的智能性和趣味性的要求都不相 同。 最原始的碰撞检测方法是一种费时的计算方法，对两个几何模型中的所 有基本几何元素进行两两相交测试，尽管这种方法可以得到正确的结果，但 当模型的复杂度增高时，o ( n 2 ) 次的相交测试是我们不能接受的。目前大部分 碰撞检测算法都是针对具体的应用设计的，主要集中于静态环境下的包围盒 4 哈尔滨工程大学硕十学位论文 碰撞检测效率的研究，对于动态复杂场景的碰撞检测算法还不多。实时性、 检测速度是三维游戏碰撞检测的核心问题。 搜索技术是人工智能技术的基本技术之一，在很多领域得到了广泛应用。 人工智能的搜索算法分为盲目搜索和启发式搜索，盲目搜索是穷举式搜索， 适用解决简单的问题，对于复杂的问题则要占用很多计算时间和空间。启发 式搜索则把问题具体领域的知识加入搜索算法中，控制搜索过程以提高搜索 效率。局部择优搜索法在搜索过程中选取最佳节点后舍弃兄弟及父亲节点， 这可能把最好的节点舍弃了，搜索结果不一定最佳。最优搜索算法在搜索过 程中没有舍弃节点，每一步估价都把当前节点和以前节点的估价值进行比较 得到最佳节点，但搜索时间和空间大。a 算法是典型的启发式搜索算法，在 复杂地图的情况下，标准a 算法的搜索速度慢，并且每个节点的相邻八个节 点都要进行搜索，造成存储空间浪费。显然，路径搜索算法存在着搜索节点 多、计算时间长，路径不平滑等问题。 1 4 本文的研究内容和所做的工作 本课题以三维游戏开发为依托，深入研究三维游戏技术，特别是碰撞检 测算法和人工智能技术中的路径搜索技术。主要研究工作包括： ( 1 ) 游戏技术研究现状 介绍国内外三维游戏技术的研究现状和发展趋向以及本课题的研究意 义，得出对三维游戏技术研究的重要性及游戏技术中尚存的问题，最后给出 本论文的主要研究内容和组织结构 ( 2 ) 三维游戏系统结构设计 通过对三维游戏引擎结构、场景模型、碰撞检测技术及人工智能技术的 研究，提出了三维游戏系统总体框架设计。 ( 3 ) 碰撞检测技术的研究 碰撞检测技术是实现三维游戏真实性的关键技术。本文通过对基于空间 剖分结构的碰撞检测算法、轴平行包围盒( a l i g n e da x i sb o u n d i n gb o xa a b b ) 碰撞检测算法、有向包围盒碰撞检测算法离散和有向多面体碰撞检测算法的 研究。针对轴平行包围盒碰撞检测算法计算量大、包围盒不精确的缺点进行 5 哈尔滨_ 丁稃大学硕十学位论文 改进。 ( 4 ) 游戏中的人工智能技术研究 游戏中的人工智能技术体现了游戏角色的智能，是三维游戏技术中的研 究热点。通过对有限状态机方法和路径搜索方法的深入研究，针对a 算法中 存在的不足，提出了分级路径搜索和加权启发函数的改进方法。 ( 5 ) 三维游戏系统的实现 首先在游戏引擎框架基础上导入游戏场景；其次对于改进后碰撞检测及 人工智能技术予以实现，最后设计三维游戏内容及游戏流程，实现了完整的 三维游戏系统。 1 5 论文的结构安排 第1 章是论文的绪论部分，主要介绍了三维游戏的研究现状和发展趋向 以及本课题的研究意义，得出对三维游戏技术研究的重要性，最后给出了本 论文的主要研究内容和组织结构。 第2 章提出了三维游戏系统的总体设计方案、框架结构以及软、硬件平 台，对游戏系统的各个部分进行了详细论述。 第3 章对多种碰撞检测算法的进行研究和总结，通过改进碰撞的检测方 式、分类设计包围盒及结合空间划分方法改进轴对齐包围盒的碰撞检测算法。 第4 章首先论述了人工智能技术在游戏中的功能及作用，然后对各种路 径搜索的算法进行研究分析，针对系统需求优化a 。算法，改进的a 。算法有 效地提高了n p c 路径搜索的性能和速度。 第5 章首先设计三维游戏系统的运行方案；研究多种建模方法，优化场 景，整合游戏引擎框架和游戏场景，并在三维游戏中实现了改进后的碰撞检 测功能和路径搜索算法。 结论部分：总结全文的主要研究成果和论文的创新之处，指出进一步的 工作重点和研究方向。 6 哈尔滨t 程大学硕十学位论文 第2 章三维游戏引擎的设计 本章对三维游戏技术进行了深入详细的研究，然后提出了游戏系统的组 织架构及三维游戏引擎的结构框架，并对系统的各个模块进行了详细论证。 2 1 设计思想 目前，三维游戏正朝着真实、快速、智能化的方向发展，这使得三维游 戏的开发需要借助多学科技术。通过对国内外三维游戏技术所取得的成果及 尚存的问题的研究，设计了一个三维角色扮演游戏，目的是通过对三维游戏 技术的分析，搭建三维游戏框架，应用碰撞检测技术及人工智能技术，实现 了三维游戏中角色的物理真实性及n p c 的智能化。 课题的主要任务分为游戏框架构建，场景建模，游戏功能设计三个主要 部分。框架搭建不仅要深入研究各游戏引擎模块的实现技术，还得合理设计 游戏各子系统间的关系。一个完整的游戏包括底层模块的游戏引擎、游戏场 景、表示游戏真实性的碰撞检测功能及人工智能技术。 游戏场景包括天空、动态云、动态水、花草树木、房屋院落、玩家角色 及非玩家角色等，模型类别有三维实体、二维精灵和几何图元。游戏场景建 模首先收集场景数据，对场景数据进行裁剪、锐化、调整颜色及饱和度等处 理后存储为t g a 、b m p 、p c x 位图格式，得到游戏系统的场景数据库。然 后运用专业软件对场景三维模型建模，最后用处理好的场景贴图资源对实体 模型进行纹理贴图、光照设计。 碰撞检测是实现游戏真实性的关键技术。游戏中的玩家角色如果对于墙 壁或者其它实体都视如空气般穿越，这不符合逻辑，也不符合现实。目前， 碰撞检测算法存在着数据计算量大，运算复杂，碰撞检测不灵活等问题。本 系统中的碰撞检测设计为：首先对游戏中的角色分块绑定包围盒，以提高碰 撞检测的精确度；碰撞分为两步检测，在设定阈值前的角色运动运用射线与 a a b b 进行相交检测，如果射线长度达到设定值，则进行a a b b 与a a b b 碰撞检测。 7 哈尔滨工程大学硕十学位论文 n p c 的路径搜索过程为：首先利用两点之间的向量运算得到n p c 玩家 角色之间的射线，然后n p c 射线方向直线运动；如果遇到障碍物的话，则在 障碍物处进行a 路径搜索，而对于每一个当前最佳点的下一次最佳点选择， 只取与玩家角色运动方向一致的四个点。 2 2 设计原则 三维游戏系统的开发，包括构建游戏引擎框架、三维建模、纹理贴图、 光照、人物的碰撞检测、n p c 的人工智能技术等，最后合成一个完整的三维 游戏系统。游戏系统是一个有机体，每一个环节都需要合理设计才能保证系 统开发成功，因此游戏开发过程要严格遵守一些规则。 1 程序编写原则 ( 1 ) 程序编程代码的可读性。由于游戏构架是由场景管理、渲染、物理系 统、音效等很多模块组成，代码量大而且极其复杂，所以需要建立一份简明 的命名规则；编写的代码因为还可能再修改或者别人查看，如果没有一定的 解释性语句，对自己或其他人来说可重用率几乎是零，所以在适当的地方加 相应注释；游戏是一个复杂的整体，如果各个类的继承层次过多，就会降低 代码的可读性，而且会使执行效率变低，所以尽量减少使用类的继承；由现 代的c p u 设计都使用了超长流水线设计，非常适合执行每行代码短而行数非 常多的代码，所以尽量使用短的代码形式。 ( 2 ) 平台和游戏的相关性与独立性。游戏有可能在不同的平台运行，也存 在要移植在别的平台上的问题，因此应当做到引擎架构与平台和游戏都无关， 否则在以后要修改一个引擎或者游戏是一个相当耗费时间的事。 2 引擎模块与接口设计原则 ( 1 ) 减少模块间的关系复杂度。游戏引擎由很多模块组成，而且每个模块 内部又都有大量的对象需要在各个模块间进行相互调用，如果模块间关系错 综复杂，将不利于模块化管理，对于程序运行也埋入了崩溃的隐患。 ( 2 ) 对类进行分层。对模块之间的相互调用都需要建立一个接口，对于不 同对象的类进行分层是为了更好隐藏底层的实现，从而减少复杂度。 ( 3 ) 减少类的数量。减少复杂度的另一个方法可是减少类的数量，把不同 8 哈尔滨工程大学硕十学位论文 功能的类合并为一个类，并让其对外表现多接口。 2 3 引擎总体设计 游戏引擎是开发游戏前编制好的一系列a p i 函数。游戏引擎框架是以模 块化的方式构建的，依据子模块与游戏的相关性可把游戏引擎分为游戏相关 层与游戏无关层。游戏相关层是包含了游戏的逻辑性程序；游戏无关层是游 戏引擎的重要部分，包括游戏场景管理、特效管理、图形渲染等等功能，它 是游戏引擎的核心部分，所有底层模块通过这一核心部分与逻辑层的程序进 行交互。通过对多种三维游戏引擎进行深入分析，提出了图2 1 所示的三维 游戏引擎体系结构。 游戏相关层 1人工智能模型加载游戏管理 i 彳 弋7 游戏无关层 三维游戏引擎 文件系统 场景管理相机匹配 数据容器文件加载 图像处理 控制台 碰撞检测 g u i j 特效管理l j 芑 底层模块l 图形渲染模块i 输入设备模块 l 声音模块i i 1 游戏相关层 图2 1 三维游戏引擎体系结构 9 哈尔滨t 程大学硕士学位论文 引擎只是游戏开发中的一个框架，引擎与应用之i 日j 的接口能使代码设计 变得更清晰，应用起来也会更简单。游戏相关层是游戏的逻辑性代码，位于 引擎的最顶层，它包含了与游戏相关的所有功能，如触、游戏角色、游戏事 件管理等功能，游戏相关层提供的就是游戏控制，以实现摄像器、模型属性、 光、音乐播放、输入操作、碰撞检测以及反馈等等相关的内容。 2 引擎核心模块 该模块是游戏引擎中最重要的模块，游戏的相关层通过它和底层的模块 交互的，它由以下几个子模块组成： ( 1 ) 场景管理模块。场景管理是游戏引擎中的重要部分，是表达场景中物 体的关联关系，记录各物体之间的继承关系，是保证场景正常显示的情况下， 尽量简化场景物体的表示，减少渲染场景的算法时间，降低空间复杂度，并 减少绘制场景所占用的设备资源和处理时间。 ( 2 ) 特效管理。特效是场景中的光源对处于其中的角色和场景的影响方 式。游戏的光影效果完全是引擎控制的，折射、反射等基本的光学原理以及 动态光源、彩色光源等高级效果都是通过引擎的不同编程技术实现的。 ( 3 ) 控制台。事件是对象状态的变化，事件的含义一般由程序来定义，程 序根据触发事件的不同，把不同的消息发送到与该事件相关的模块进行处理， 这就是控制台的职能。 ( 4 ) 图形渲染模块。图形渲染模块决定着输出画面质量，是游戏系统部分 评测性能优劣的重要依据，渲染引擎把模型、动画、光影、特效等所有效果 实时计算出来并展示在屏幕上。 ( 5 ) 输入设备模块。输入设备模块是通用化接口，它的职责就是负责键盘、 鼠标、摇杆或者其它外设的各种信号的通信和控制，它将具体物体设备抽象 化。 ( 6 ) 声音模块。处理游戏世界所有音效，包括背景音乐和各种事件声音的 管理和播放，一些高性能的游戏引擎还能实现3 d 音效和环境环绕音等复杂 的功能。 ( 7 ) 物理模块。物理系统是描述物体的运动遵循规律，例如，当角色跳起 的时候，系统内定的重力值将决定他能跳多高，以及他下落的速度有多快， 子弹的飞行轨迹、车辆的颠簸方式也都是由物理系统决定。碰撞检测是物理 1 0 哈尔滨下程大学硕十学何论文 系统的核心部分，它可以探测游戏中各物体的物理边缘。当两个3 d 物体撞 在一起的时候，这种技术可以防止它们相互穿过。 ( 8 ) 动画模块。目前游戏所采用的动画系统可以分为两种：一种是骨骼动 画系统，另外一种是模型动画系统，前者用内置的骨骼带动物体产生运动， 比较常见，后者则是在模型的基础上直接进行变形。引擎把这两种动画系统 预先植入游戏，动画师可以方便的为角色设计丰富的动作造型。 ( 9 ) 人工智能模块。为游戏中的非玩家控制角色的行为和决策提高智能支 持，游戏中人工智能在现代游戏引擎中越来越重要，它直接影响到游戏的可 玩性和游戏设计的复杂性。 2 4 游戏系统总体设计 本课题的目标是开发一个完整的游戏，为了保证游戏能够流畅地运行， 并达到高真实感场景渲染效果，根据游戏各部分的侧重点不同，本文将整个 系统分为三大部分：引擎搭建阶段、场景模型建造子系统和渲染输出子系统。 三个子系统在功能上相对独立，通过数据接口相互关联，游戏总体结构设计 如图2 2 所示： 图2 2 游戏系统总体结构图 哈尔滨t 程大学硕+ 学位论文 2 4 1 引擎搭建阶段 游戏引擎是软件工程中的软件重用思想的表现形式之一，游戏引擎把游 戏中最重要的功能集成起来形成通用的框架平台。游戏开发过程中可以利用 接口直接调用游戏引擎提供的功能，可以方便和快速地开发新的游戏。游戏 引擎的出现，极大的方便了游戏的编程实现。引擎搭建过程中更注重模块间 的联系和配合，渲染模型是引擎中的重中之重，尽量合理图形渲染流程。碰 撞检测和人工智能是游戏真实性的体现，更注重符合人物和n p c 本身特性的 技术，在游戏中，可以在精确性和运行速度上进行平衡设计。因此，合理搭 建游戏引擎是成功开发游戏的关键。 2 4 2 场景模块子系统 一个完整的游戏必须有场景，场景模型是游戏的环境因素，是游戏发生 的场所，是游戏的又一个重要部分。在游戏场景中，可以对每个模型的外形 用多边形进行拟合，而模型真实感则通过对模型外表赋予材质和光照来表现， 由于当今的三维造型软件已相当成熟，没有必要再重新三维模型的造型软件， 而是充分利用这些软件工具来建造游戏场景，然后通过数据模型转换得到需 要的三维模型。其建模过程基本分为两步：第一步称为几何建模，主要包括用 多边形或三角形构成场景模型的三维外形；第二步称为形象建模，主要是对 几何建模的外形进行纹理、颜色、光照等处理。 2 4 3 渲染输出子系统 游戏相关层的功能主要是三维数据库的调用、系统的优化、碰撞检测、 人工智能以及最终渲染效果的显示。在实时渲染时主要运用b s p 树对场景进 行优化：对于模型的简化主要是减少模型的面数，只做出模型的基本外观， 采用纹理映射对细节进行表示。输入设备控制的玩家角色前进、后退、左右 旋转，玩家角色与外界之间可以采用脚本系统进行交互。本课题采用键盘作 为输入手段，使游戏场景的人能够按照参与者行走的速度及方向进行实时变 换，对参与者的“行为给出视觉反馈，达到人机和谐、自然交互的目的。 1 2 哈尔滨1 ：程人学硕士学何论文 路径搜索算法非常耗时，如果把人工智能的计算设计在进程中按游戏渲 染顺序执行的话，游戏运行效率就会很低。所以，游戏引擎通常把比较复杂 的越计算另起一个线程计算。另外，游戏中的人工智能的应用体现了游戏的 趣味性，主要采用a + 路径搜索来更真实化地再现n p c 的活动智能化。为了 增强系统的真实感，针对玩家角色的运动还实时的输出三维仿真声音。 2 5 功能设计 三维游戏系统主要做以下几方面的工作：三维游戏引擎的简单构造、场 景模型的建立，摄像机视角变化，用户实时交互、n p c 的人工智能。 场景可分为室内场景和室外场景两个部分，室外场景则比较多，游戏初 始时，能看到美丽的花草树木、漂亮的古代建筑、真实的瀑布，蓝天白云， 太阳在运行走着，形成了日夜交替的动态环境。 游戏情节设计为：玩家角色进入游戏后，玩家角色必须通过一定的关卡 后才能成功走出系统设定的环境：每一道门都代表着一个关卡，在每个关卡 中，玩家角色会遭到n p c 的袭击，减少自己的生命值；同样，玩家角色也有 机会获得宝物来增加自己的生命值，当生命值为零时就意味着玩家角色死亡， 相反，如果玩家“活着 走出所有关卡，就成功通过游戏。图2 3 是游戏系 统所涉及的主要功能。 图2 3 游戏系统的功能图 哈尔滨t 程大学硕十学位论文 2 6 开发平台 本系统包括三维模型、路径搜索、人工智能及二维图像等很多场景数据， 在游戏运行中需要对场景进行渲染，所以对显卡的要求较高，因此我们采用 的计算机为2 5 6 m 显卡、1 g 内存和2 0 g 主频的配置。 三维游戏开发是采用w i n d o w s 操作系统、v i s u a lc + + 6 0 软件开发平台， d i r e c t x 应用程序接口、3 d sm a x 软件建模、p h o t o s h o p 处理的纹理图像。 ( 1 ) m i c r o s o f tv i s u a lc + + 。它是微软公司提供的基于c c + + 的应用程序集 成开发工具。v c 具有丰富的功能和大量的扩展库，使它能有效地创建高性能 的w i n d o w s 应用程序和w e b 应用程序，是软件人员常选的开发工具。 ( 2 ) d i r e c t x 。它是微软公司开发的运行于计算机平台的多媒体控制处理 引擎。基于d i r e c t x 应用程序编程接口开发的游戏可以运行于硬件抽象层上， 既充分利用了系统硬件的加速功能，又隐藏了硬件相关的设备特性。通过编 写与设备无关的高效代码，程序总是以最佳方式运行，具有效率高，易开发 的特点。 ( 3 ) 3 ds t u d i om a x 。它是d i s c r e e t 公司开发的基于p c 系统的三维动画渲 染和制作软件。其主要制作影视广告、影视特技、三维游戏模型、动画片和 建筑模型等。它的特点是：基于p c 系统的低配置要求；安装插件可提供 3 ds t u d i om a x 所没有的功能以及增强原本的功能；强大的角色动画制作能 力：可堆叠的建模步骤，制作模型有很大的弹性。 ( 4 ) p h o t o s h o p 。它是a d o b e 公司推出的跨越p c 和m a c 两界的大型图像 处理软件。它功能强大，操作界面友好，可以支持众多的图像格式，对图像的 常见操作和变换做到了非常精细的程度。是目前运用最广泛的图像处理和编 辑软件，己被广泛用于平面设计、三维动画、网页设计和多媒体等诸多领域。 2 7 本章小结 本章通过对三维游戏的系统框架、设计原则等进行了分析研究，提出了 三维游戏引擎的结构及三维游戏系统的架构方案。然后论证了系统框架及各 个子模块的功能要求，给出了各模块设计方案。最后确定了系统开发的硬件 及软件平台。 1 4 哈尔滨t 程大学硕十学位论文 第3 章碰撞检测技术的研究 碰撞检测是三维游戏中实现游戏角色真实感物理运动的主要算法。本章 通过对轴平行包围盒的碰撞检测算法、轴向包围盒的碰撞检测算法及离散有 向多面体碰撞检测算法的深入研究，针对碰撞检测算法的运算量大的问题做 了改进。经实验分析，改进的碰撞检测算法能有效地减少了运算次数，提高 了游戏的运行速度。 3 1 引言 碰撞检测的基本任务是确定两个或多个物体彼此之间是否有接触或穿 透，并给出相交部分的信息。在游戏世界中，两个或多个物体不可能同时占 有同一空间区域，如果两个实体发生了碰撞而无任何反应，或者不应该穿透 物体却穿透了，那么玩家就会感觉到不真实，从而影响游戏的沉浸度，这是 游戏所不应该发生的情况。因此，研究开发实时性和真实性较好的碰撞检测 技术再度成为多方关注的焦点。好的碰撞检测算法可以实时地进行碰撞检测， 实现物体真实的物理特性，而不增加系统的计算量。 3 2 碰撞检测算法分类 1 基于空间方法分类 碰撞检测州方法大体可分为基于物体空间的碰撞检测算法和基于图像 空间的碰撞检测算法。 基于物体空间的碰撞检测算法是把各种技术如层次表示法、几何推理、 代数范式、空间划分、解析方法和最优化方法等应用到碰撞检测中，如国内 的王兆其，王志强，国外的l i n ，j i m e n e z 等。基于空间剖分技术的碰撞检测 算法的难点在于处理不同的场景和具有不同形状及复杂度的物体时如何保持 一致的检测效率。 基于图像空间的碰撞检测算法是一类比较新的碰撞检测算法，它能有效 利用图形硬件的绘制加速功能来提高碰撞检测算法的效率。近几年图形硬件 1 5 哈尔滨t 程大学硕十学位论文 技术的匕速发展，图形加速卡在性能不断迅速提高的同时甚至出现了可编程 的功能，使得基于图像空间的碰撞检测算法进入了一个新的发展阶段。 2 基于检测方式分类 基于检测方式的碰撞检测啪卵，勰，分为离散点的碰撞检测和连续碰撞检测。 离散点的碰撞检测是指定某一时刻t 的两个静态碰撞体，看它们之间是 否交叠，如果没有交叠则返回它们最近点的距离，如果交叠则返回交叠深度、 交叠方向等。离散点的碰撞检测存在的问题是当检测到两个物体已发生交叠， 实际上已经有许多三角形发生了碰撞。 。 连续碰撞检测是较为自然的碰撞检测，在算法中指定在t 1 、t 2 这两时刻 计算两个碰撞体的位置，看它们在由t l 运动到t 2 时刻的过程中是否发生碰 撞，如果碰撞则返回第一碰撞点的位置和法线。连续碰撞检测减少了编写碰 撞响应逻辑，可以避免物体发生交叠或穿越，算法编写复杂，运算开销大。 3 基于层次包围体分类 层次包围体方法1 的核心思想是用体积略大而几何特性简单的包围体来 近似地描述复杂的几何对象，只需对包围体重叠的对象进行相交测试，通过 构造树状层次结构可以越来越逼近对象的几何模型。场景物体的层次包围体 树主要包括层次包围球树、a a b b ( a l i g n e da x i sb o u n d i n gb o x ) 层次树、o b b 层次树( o r i e n t e db o u n d i n gb o x ) 、k d o p 层次树( d i s c r e t eo r i e n t a t i o np o l y t o p e ) 、 q u o s p o 层次树( q u a n t i z e do r i e n t a t i o ns l a b sw i t hp r i m a r yo r i e n t a t i o n s ) 、凸 块层次树及混合层次包围体树等。 3 3 碰撞检测方法 3 3 1 轴对齐包围盒碰撞检测算法 碰撞检测算法中包围盒的创建很重要，a a b b 碰撞检测算法啪是使用最久 最广的算法之一。a a b b 结构简单、包围盒的创建方法简单、内存消耗少、 更新快、相互之问的相交检测快捷。物体的a a b b 被定义为包含该碰撞体，且 边平行于坐标轴的最小长方体，a a b b 的示意图如图3 1 所示。在构造a a b b 时，需沿着物体局部坐标系的轴向( x ，y ，z ) 来构造，a a b b 内的点满足下列等 式：x m i ns xsx m a x 、y m i n y y m a x 、z m i nszs z m a x 。两个顶 1 6 哈尔滨一r 程大学硕十学能论文 点可以表示为：= j 和p 嬲= j 。中心点 c = ( p 。i n + p 。) 2 ，尺度向量s = p 。缸一p 。i 。是从p m i 。指向p 一的向量，包含了 a a b b 包围盒的长、宽、高，a a b b 包围盒的半径向量r = p 。一c = s 2 ，它是 指向p 。的向量。定义一个a a b b 只需要p i n i n ，p 一，c ，s ，r 五个向量中的两个， 但是s ，r 不能作为定义a a b b 的配对选择。本系统采用p 面。，p m 娃表示一个 a a b b 的边界框，因为在实际运用中p r o m p 一的使用频率远远高于其它三个 向量，并且运用p l i l i 。，p 一计算c ，s ，r 三向量十分容易。 p 蛳。 y ( a ) 三维a a b b ( b ) a a b b 侦i j 面示意图 图3 1a a b b 包围盒 a a b b 间的相交测试最多只需要6 次比较运算，与其它包围体相比，a a b b 结构比较简单，内存消耗少，更新快，相互之间相交计算也很简单。 3 3 2 有向包围盒碰撞检测算法 o 明啪，本质上是一个最贴近物体的最小长方体，只不过该长方体可以根据 物体的阶矩任意旋转，是一个表面法向两两相互垂直的长方体。图3 2 是 o b b 示意图，o 是o b b 的中心点，b ”b v 、b 、v 都是归一化的正向边向量，l ” l v 、1 w 是中心o 到三个不同平面间的距离。 冬 西 i ，i ，i ! i “1 ，?0 ： b v 7 ，7 7 b i l ， y j y ( a ) 三维o b b z 侈y 匕一x 图3 20 b b 包围盒 1 7 ( b ) o b b 侧面示意图 哈尔滨工程大学硕士学位论文 不同o b b 树的叶子节点内包围的三角形之间的相交检测也可以利用分离 轴定理来实现：首先确定两个三角形的1 7 个分离轴，然后依次检查这两个三 角形在这1 7 个分离轴上的投影区间是否有重叠，以此来获取它们的相交检测 结果。r a p i d 算法的缺陷是无法判断两三角形面片之间的距离，只能得到二 者的相交结果。此外，r a p i d 也没有利用物体运动的连贯性，其算法需要有 预处理时间，一般只适用于处理两个物体之间的碰撞检测。 3 3 。3 离散有向多面体碰撞检测算法 k - d o p 的概念最早由k a y 等m ，提出的，它是根据景物的实际形状选取若干 组不同方向的平行平面对包裹一个景物或一组景物的层次包围盒技术。由 k 2 对平行平面包围而成的凸多面体，其中k 为法向量的个数。 k - d o p 碰撞检测是用超过3 对平行平面对来逼近对象，所有的平行平面对 都是方向相反的两个法向量所定义的半空间相交得到的。在应用中可以选择 简单的法向量的方向以简化平行平面对的计算。无论对于平面图形而言还是 对立体图形而言，凸包对对象的包裹最紧，所以只要合理地选择k 的大小以及 平行平面对的方向，就可以在碰撞检测的简单性和包裹物体的紧密性之间取 得较好的折中。 k - d o p 包围体可以比其它包围体能更紧密地包围物体，创建的层次树节点 越少，在相交检测时就会减少更多的冗余计算。同时，k - d o p 包围体之间的相 交检测更复杂。当k 值变大时，一方面减少了相交检测的次数，另一方面增 加了相交检测的计算量。因此选择合适的k 值可保证最佳的碰撞检测速度。 3 。4 相交检测 碰撞检测的基本问题是物体的求交，直观的算法是两两检测场景物体之 间的位置关系，目前多数基于物体空间的碰撞检测算法的效率与场景中的物 体的复杂度成反比关系，对于大规模的复杂场景，复杂度为o ( n 2 ) 碰撞检测 算法无法满足游戏实时性的要求。 碰撞检测算法的关键计算就是相交的检测，它是碰撞检测的基础。相交 检测可分为分静态测试和动态测试。 1 8 哈尔滨丁程入学硕士学位论文 静态测试是检测两个静止物体之间是否相交。它是一种布尔型测试，测 试结果只有相交或不相交两种结果，如果两个物体相交则可以获取更多信息， 但一般的测试目的只是要返回一个布尔值。 动态测试是应用最广泛的一种测试方法，它是针对两个运动物体而检测 它们之间是否相交及相交时间点。运动值则以参数形式来表达。这种测试返 回的结果不仅仅是一个布尔型的值，还会返回一个指明相交时间点的值。动 态测试可以包括线与线的相交检测，线与面的相交检测、面与面的相交检测、 线与球的相交检测、线与a a b b 的相交检测、球与球的相