硕士论文-基于DirectX90的3D游戏引擎研究与实现.pdf

武汉理工大学 硕士学位论文 基于directx9.0的3d游戏引擎研究与实现 姓名：龚向宇 申请学位级别：硕士 专业：计算机应用技术 指导教师：徐东平 20070501 武汉理工人学硕士学位论文 摘要 游戏引擎在游戏开发中起着至关重要的作用，如同汽车发动机在汽车制造 中的作用样：一款性能优越兼容性强的汽车发动机不仅可以极大提升一辆汽 车性能，而且可以极其方便的用于组装生产其它汽车。同样一款好的游戏都有 一歙强大的游戏引擎作支撑，游戏引擎是游戏开发中最核心最重要的部分，其 具有很强的重用性、独立性、通用性。游戏引擎可以非常方便的移植到其它同 类型游戏开发中，极大的缩短游戏开发周期，提高游戏开发的效率。在游戏开 发过程中游戏引擎是独立于具体游戏开发的，它是先于具体游戏开发之前完成， 通过提供底层接口给游戏开发者开发具体的游戏。 3 d 游戏引擎的开发将涉及到复杂的数学、几何变换知识，对数学理论知识 有较高的要求。微软d i r e c t x9 0s d k ( s o f t w a r ed e v e l o p m e n tk i t ) 包是一组 w i n d o w s 平台上的多媒体a p i ( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ) ，对基础的 数学几何变换作了封装，通过其提供的开发接口可以极大的方便游戏开发，提 高开发效率，可以让我们将时间集中在主要问题的研究上。 本文主要研究内容分为如下三部分：第一部分讲述3 d 游戏编程所需数学基 础知识及d i r e c t 3 d 基础知识，主要介绍向量和矩阵运算、d i r e c t 3 d 顶点、深度 缓存等概念。第二部分设计游戏引擎框架，研究从图形建模、渲染管线、光栅 化处理管线至最后图像显示全过程。重点阐述3 d 几何变换、剔除算法、纹理 映射，几何模型设计。第三部分阐述游戏中人工智能常用算法，通过对a ，算法 的研究提出并实现一种优化的a 算法。对游戏引擎中网络通讯系统的实现作了 详细研究，提出并实现服务迁移、人机切换。 关键词：引擎；几何变换；剔除：纹理映射；模型 武汉理工大学硕士学位论文 a b s t r a c t t h eg a m ee n g i n ep l a y sam o s ti m p o r t a n tr o l ei nt h eg a m ed e v e l o p m e n tt h e s a n l ea sa u t oe n g i n ei nt h ea u t o m o b i l em a n u f a c t u r e ，o n ee x c e l l e ma u t oe n g i n ew i t h s t r o n gc o m p a t i b i l i t yn o to n l yc a l lp r o m o t ea c a r sp e r f o r m a n c ed r a m a t i c a l l l y ，b u t a l s oc a l lb ec o n v e n i e n t l yu s e df o rt h ec o n s t r u c t i o no fo t h e ra u t o m o b i l e s t h es a l n ei s t h a ta g o o dg a m em u s th a v eas t r o n gg a m ee n g i n et os u p p o r t ，t h eg a m ee n g i n ei st h e m o s ti m p o r t a n tc o r ep a r ti nt h ep r o c e s so fg a m ed e v e l o p m e n t , i th a sv e r ys t r o n g i n d e p e n d e n c e a n d u n i v e r s a l i t y t h eg a m ee n g i n e c a nb e v e r y c o n v e n i e n t l y t r a n s p l a n t e d i n t ot h e d e v e l o p m e n to fo t h e r s i m i l a rg a i n e s ，s h o r t e n sng a m e d e v e l o p m e n tp e r i o dg r e a t l y ，e n h a n c e st h ee f f i c i e n c yo fg a m ed e v e l o p m e n t i nt h e p r o c e s so fg a m ed e v e l o p m e n tt h eg a m ee n g i n ei si n d e p e n d e n tt ot h ep r a c t i c a lg a m e d e v e l o p m e n t t h e r e f o r e ，i t i s f i r s t l yd e s i g n e da n dd e v e l o p e d ，i tp r o v i d e sm a n y f u n c t i o n st ot h eg a m ed e v e l o p e rt h r o u g hb o t t o mi n t e r f e r c e s t h ed e v e l o p m e n to ft h e3 dg a m ee n g i n ew i l li n v o l v et o c o m p l i c a t e d m a t h e m a t i c s 、g e o m e t r yw a r t s f o r m a t i o nk n o w l e d g e ，a n di ti sn e c e s s a r yf o rh i g h r e q u i r e m e n t so ft h em a t h e m a t i c st h e o r i e s m i c r o s o f td i r e c t x9 0s d k ( s o f t w a r e d e v e l o p m e n tk i t ) i sas e to f m u l t i - m e d i aa p i ( t h ei n t e r f a c eo ft h ea p p l i c a t i o n p r o g r a m m i n g ) b a s e do n w i n d o w so s ( o p e r a t i o ns y s t e m ) ，i th a si m p l e m e n t e d m a n yb a s i cm a t h e m a t i c sa n dg e o m e t r yt r a n s f o r m a t i o n s b yu s i n gi t si n t e r f a c e si t w i l lb et r e m e n d o u sc o n v e n i e n tf o rt h eg a m ed e v e l o p e ra n di tg a nl e tu sf o c u so ht h e k e yp r o b l e m t h et h e s i sm a i n l yd i s c u s s e st h ef o l l o w i n gt h r e ep a r t s ：t h ef i r s tp a r tr e l a t e st h e b a s i cm a t h e m a t i c sa n dd i r e c t 3 dk n o w l e d g e ，m a i n l yi n t r o d u c e sv e c t o ra n dm a t r i x o p e r a t i o n , d i r e c t 3 dv e a i e x ，d e p t hb u f f e rc o n c e p t s t h es e c o n dp a nd e s i g n st h e f r a m e w o r ko fg a m ee n g i n e ，t h ed i s c u s s i o ni n c l u d e st h ew h o l ep r o c e s sf r o ms e t t i n g u pm e s h s ，s h a d e rp i p e l i n e ，r a s t e r i z e rt os h o w i n gi m a g e i te m p h a s i s e so nt h e3 d g e o m e t r yt r a n s f o r m a t i o n , c u l l i n ga r i t h m e t i c , t e x t u r em a p p i n g ，d e s i g no fg e o m e t r y m o d e l s t h et h i r dp a r tr e l a t e st h ec o n l l n o na r t i f i c i a li n t e l l i g e n c ea l g o r i t h mi nt h e i l 武汉理i ：大学硕十学位论文 g a m e t h r o u g h t h er e s e a r c ho ft h eb a s i ca + a l g o r i t h mih a v es u g g e s t e da n d i m p l e m e n t e df i no p t i m u ma 4a l g o r i t h m t h i sp a r ta l s oi n t r o d u c e st h er e a l i z a t i o no f n e t w o r kc o m m u n i c a t i o ns y s t e mo ft h eg a m ee n g i n e ，s u g g e s t sa n di m p l e m e n t st h e s e r v i c e m i g r a t i o n ，s w i t c h m gb e t w e e np l a y e ra n dr o b o t k e y w o r d ：e n g i n e ；g e o m e t r yt r a n s f o r m a t i o n ；c u l l i n g ；t e x t u r em a p p i n g ；m o d e l i i i 武汉理，i ：大学硕士学位论文 1 1 课题背景 第1 章绪论 近几年来，由于3 d 硬件绘图技术的突破，使得实时绘制的游戏画面越来 越精致，更加逼近真实世界。在游戏产业中，3 d 游戏己经逐渐取代2 d 游戏而 成为游戏市场的主流，即使是网络游戏，也慢慢趋向3 d 化。虽然开发3 d 游戏 过程中存在着诸如技术更新快、程序人员与美工的配合、各厂商所生产的3 d 硬件规格和特性不同、失败率高等风险，但不可否认，3 d 游戏已是大势所趋。 作为3 d 游戏核心的3 d 游戏引擎技术的发展会日趋成熟，游戏开发的困难度也 将随着3 d 游戏引擎技术的成熟而逐渐降低。随着3 d 游戏引擎技术的成熟发展， 游戏开发厂商可以将其开发的重心放在游戏内容及游戏设计上，未来游戏厂商 将可以摆脱复杂的3 d 绘图技术的程序设计、沟通不易、跨平台等困难，而更 容易地设计出画面华丽、内容充实的游戏。 曾经有一段时期，游戏开发者关心的只是如何尽量多地开发出新的游戏并 把它们推销给玩家。尽管那时的游戏大多简单粗糙，但每款游戏的平均开发周 期也要达到8 到l o 个月以上，这一方面是由于技术的原因，另一方面则是因为 几乎每款游戏都要从头编写代码，造成了大量的重复劳动。后来一些有经验的 开发者摸索出了一种方法，他们借用上一款类似题材的游戏中的部分代码作为 新游戏的基本框架，以节省开发时间和开发费用，引擎的概念就是在这种机器 化作业的背景下诞生的。我们可以把游戏的引擎比作赛车的发动机，大家知道， 发动机是赛车的心脏，决定着赛车的性能和稳定性，赛车的速度、操纵感这些 直接与车手相关的指标都是建立在发动机的基础上的。游戏也是如此，玩家所 体验到的剧情、关卡、美工、音乐、操作等内容都是由游戏的引擎直接控制的， 它扮演着中场发动机的角色，把游戏中的所有元素捆绑在一起，在后台指挥它 们同时、有序地工作。简单地说，引擎就是“用于控制所有游戏功能的主程序， 从计算碰撞、物理系统和物体的相对位置，到接受玩家的输入，以及按照正确 的音量输出声音等等。引擎相当于游戏的框架，框架打好后，就只需往里填充 内容即可，因此一个好的游戏引擎对于我们以后的开发有着非常重要的作用， 武汉理工大学硕士学位论文 是整个开发的基础。而且一个好的3 d 引擎还能快速的应用于其它领域如当前 流行的视景仿真等。 1 2 课题研究的目的和意义 游戏的关键在于游戏通用引擎。游戏引擎包括了一套完整的游戏开发工具 与运行基础，包含了开发一套游戏所需的最核心的技术。自主知识产权的通用 游戏引擎是我国游戏企业参与国际竞争的核心竞争力。高性能的游戏引擎是游 戏企业技术积累的最好方式，它通过封装技术难点为游戏软件开发者提供开发 包和系列工具，使得“复制”游戏成为可能。这样可以极大缩短游戏产品开发 周期，降低游戏开发的技术难度，为形成国产游戏市场，刨造巨大经济、社会 效益提供根本保证。 游戏引擎是一个处理游戏底层技术的平台，使用游戏引擎，游戏开发人员 可以不用花过多精力去处理系统架构、内存管理、图像绘制等一些底层的技术， 能够加快游戏开发的进度，节省开发的成本，游戏引擎不仅可以用与游戏开发， 还可以用于视景仿真等其它3 d 图形领域。在当前3 d 游戏网络化的高速发展下， 如何在电脑配置不能大规模升级的前提下最合理的使用资源，优化配置，获得 最佳的图像效果就对3 d 游戏引擎提出了更高的要求 我国当前在游戏引擎方面研究比较落后，如果我们没有自主研发的高性能 的游戏引擎，就无法从根本上赶超国际水平，就无法抵抗大量国外游戏的冲击， 同样不能带动其它产业的发展。因此，自主研发高性能的3 d 游戏引擎对我国 以后游戏产业的发展有着非常重要的作用。 1 3 国内外研究发展现状 在国外，3 d 游戏引擎技术发展较早，技术较为成熟，市场上流行的几大 3 d 游戏引擎如u n r e a l 、q u a k e 、l i t h t e c h 都来自国外，国内游戏引擎的研究起 步较晚，还没有成功推向国际市场的游戏引擎。针对国内网络游戏技术与研究 滞后的现状，“8 6 3 ”计划子2 0 0 3 年年中首次通过了“网络游戏通用引擎研究及示 范产品开发”与“智能化人机交互网络示范应用”两个与网络游戏相关的项目，前 者由金山公司、中科院计算所以及北京航空航天大学联合承担，后者由中科院 2 武汉理【大学硕士学位论文 自动化所与炎黄新星承担。我国在国产游戏的研发实力上还是远远不够，虽然 一直以来众多国产游戏受到不少国内游戏玩家的簇拥，但在技术上相对韩同和 欧美的作品差距还相当之大，在人物造型、场景设罱方面还显得非常单薄，而 且一直在2 d 或是在2 5 d 上徘徊，一直以来并没有一款真正3 d 意义上的佳作 出现。国产游戏不管是技术还是产业积累方面，都想急于求成，这在某些程度 上决定了基础层次面的薄弱。而且作品的模仿开发较多，游戏本身没有从本质 上得到提高，没有从模仿中提高然后形成自己的文化系统或者游戏规则系统。 国产研发商对待游戏的开发一般采取了这样两种态度：一是选取热门的传统题 材，例如西游记、封神演义。导致了游戏的千人一面；二则是完全舍弃一些可 行的传统题材，去制作一些根本不熟悉的东西，比如一些魔幻式的欧美风格的 游戏。从2 0 0 4 年开始国产网游已经逐渐形成了自己的风格，之前国产游戏几乎 全是采用国外引擎，这些引擎都是国外比较落后甚至濒于淘汰的产品。其后有 些研发商已经能够根据需要修改游戏引擎，使设计出来的游戏更为精彩：也有部 分厂商购买国外一流游戏引擎进行研究和游戏开发，从而真正拉近了与国外游 戏厂商在技术上的差距，更有些厂商开发出自己的游戏引擎，虽然还显租糙， 但却跨出历史性的一步了。发展到现在的3 d 游戏引擎虽然已经摆脱了2 d 引擎 的影子，但从根本上来说还是存在着很多的技术瓶颈，根本无法实现对世界的 高度拟真，而3 d 本身窆间感的混乱还给游戏带来了许多新的问题，例如长时 间游戏后玩家产生的不适，游戏地图的扩大和方向感混乱，贴图量增大和画面 的粗糙，游戏容量的扩大及游戏速度的降低，游戏编程上的反向b u g 增多等 等，这些都是3 d 游戏不可避免的缺点，还有许多需要改进的地方。 1 。4 主要研究内容 本文的研究目标是设计和实现了一个功能基本完备的3 d 引擎系统。研究 内容首先是游戏中涉及到的数学知识以及d i r e c t 3 d 基础知识，探讨d i r e e t 3 d 中 诸多关键技术的实现原理，设计本游戏引擎的基本架构。其次是引擎的核心处 理模块，主要包括渲染、灯光、纹理、剔除、碰撞检测等。渲染是引擎的核心， 所有要表现的物体与动作都是最后通过渲染引擎实时计算出来并显示在屏幕 上。渲染在引擎的所有部件当中是最复杂的，它的强大与否直接决定着最终的 输出质量。碰撞检测是游戏引擎中物理系统的核心部分，它可以检测游戏中各 3 武汉理i ：大学硕十学位论文 物体的物理边缘，当两个3 d 物体撞在一起的时候，这种技术可以防止它们相 互穿过，这就确保物体撞在墙上时不会穿墙而过，因为碰撞探测会根据模型和 墙之间的特性确定两者的位置和相互的作用关系，保证了游戏场景的真实性。 最后在引擎中加入了优化的人工智能算法，对多人网络游戏提供网络支持。本 文拟解决的关键问题： l 、设计并实现了一个具备主要图形渲染功能的3 d 引 擎，为游戏开发人员提供了一个开发平台，使开发人员可以完全独立于底层图 形a p i 进行游戏开发；2 、人工智能与网络功能在游戏引擎中的实现。3 、实 现一个基于所开发引擎的3 d 小游戏。 本课题将实现一个基本的3 d 游戏引擎，研究的主要内容如下所示： 1 ) 三维场景渲染技术 主要研究3 d 几何变换、3 d 渲染管道、剔除算法、纹理映射、灯光特效、 光栅化、摄像机控制、碰撞检测算法。 2 ) 游戏逻辑 三维数据文件的读取，3 d 图形文件、声音文件的载入，处理来自键盘、鼠 标输入控制信号。 3 ) 网络通讯模块 实现基于t c p i p 的多入网络连接，探讨多人网络游戏中引擎的处理功能， 提出并实现服务迁移、人枫切换。 4 ) 人工智能模块：研究并实现基于d i j k s t r a 算法的路径查找。从另一个角 度优化a ，算法。 4 武汉理 大学硕士学位论文 第2 章3 d 游戏引擎基础 2 1 数学基础知识 几何学中，我们用有向线段表示向量，向量的两个属性是他的长度和他的 顶点所指的方向，因此，可以用向量来模拟既有大小又有方向的物理模型。向量 为在3 维空间中表示方向提供了方便。 2 1 1 向量基本运算 ( 1 ) 向量相等 几何学上，有同样方向和长度的两个向量相等。向量与位置无关。有同样 长度和方向的两个向量是相等的，即使他们在不同的位置。数学上，我们说有 同样维数和分量的向量相等。 例如：如果u x = v x , u y = v y ，且u z = v z 那么( u x ，u y ，u z ) 2 ( v x ，v y ，v z ) 。 ( 2 ) 向量相加 通过分别把两个向量的各个分量相加得到向量之和，注意在相加之前必须 保证它们有相同的维数。 例如：u + v = ( u x + v x ，u y + v y ，u z + v z ) ( 3 ) 向量相减 通过分别把两个向量的各个分量相减得到向量之差。 例如：u v ；( u x v x ，u y v y ，u z - v z ) ( 4 ) 数乘 通过一个数与向量相乘得到数乘结果，向量将按比例变化，但不会改变向 量的方向，如果希望改变向量的方向可以通过用负数去操作。 例如：k v = ( k v x ，k v y ，k v z ) ( 5 ) 点乘 点乘是指两个向量的乘积，其结果是一个标量。 例如：u v = u x v x + u y v y + u z v z 利用余弦定律，u v = l u l l v l e o s o ，表示两个向量的点乘是它们的模和夹角 5 武汉理【：大学硕十学位论文 的余弦之积。因此，如果u 和v 都是单位向量，那么u - v 就是它们夹角的余弦。 因此我们就有如下结论： u v = 0 ，那么u 上v 。 u v 0 ，那么两个向量的角度0 小于9 0 度。 u v o b i e c t ( x 7 ，y ) 。 有两种基本投影方法：平行投影和透视投影。平行投影( p a r a l l e lp r o j e c t i o n ) 使用一组平行投影将三维对象投影到投影平面上去。透视投影( p e r s p e c t i v e p r o j e c l i o n ) 使用一组由投影中心产生的放射投影线，将三维对象投影到投影平面 上去。 透视投影是最常用的一种投影类型，对于透视投影，因为视棱锥的近端比 远端小，所以这就产生了离摄像机近的物体被放大的效果，会使近处的对象看 起来比远处的大一些。对于透视投影，视锥可以被初始化成金字塔形，将摄像 机放在顶端，这个金字塔再经过前、后两个剪切面的分割，位于这两个面之间 的部分就是视锥，只有位于视锥内的对象才可见。如图4 2 所示： 图4 2 透视投影中视锥 在视锥中，摄像机与视口空间原点闻( 前剪切画中心) 的距离被定义为变量 d ，通过在z 方向平移d ，将摄像机平移到原点。平移矩阵如下所示： 作投影变换的投影矩阵如下： loo0 o l0 0 o 0lo oo dl lo 00 o1o o o0 1 1 d o o o l 1 6 武汉理工大学硕士学位论文 将平移矩阵与投影矩阵相乘，得到如下合成的投影矩阵 loo0 o1oo o o11 d oo do 下图显示了透视投影变换如何将一个视锥变换成到投影坐标空间。 一 n 嚣睹切l 矗f 中心 “ l 缢。口机衍簧 险8 i ， ， 匕 o ) r e n d e r ( o b j e c t ) ； e l s e c u l i n g ( o b j e c t ) ； ) ) 4 1 2 3 灯光特效 在3 d 游戏中，为了更加真实的表现场景，提高场景的真实性，我们加入灯光 特效。灯光能帮助表现物体的立体感以及物体的体积。当使用灯光时，我们不 再自己指定顶点的颜色。d i r e c t 3 d 中每个顶点都通过灯光引擎来计算顶点颜色， 该计算是基于定义的灯光资源，材质以及灯光资源关心的表面方向。通过灯光 模型计算顶点颜色会得到更真实的场景。 灯光通常分为环境光和直射光：环境光均匀充满整个场景，为所有实体提 供一个恒定的照明，没有方向性；直射光一般由光源产生，具有方向性。 在d i r e c t 3 d 中灯光色彩由以下几个部分表示：对于直射光和材质的颜色， 通常由4 个代表红、绿、蓝、a l p h a 混合浮点分量表示，其取值范围【o 0 ，1 0 1 。 a l p l l a 混合主要仅针对材质而言，当其值为0 0 表示完全透明，为1 0 表示不透 明。对于环境光颜色由4 字节代表红、绿、蓝、赳p l l a 混合的整数描述，其取 2 1 武汉理工大学硕士学位论文 值范围为0 - 2 5 5 。我们经常会提到灯光和材质的颜色，两都之间的区别是：灯 光的颜色定义了光线中各个颜色分量的多少，例如红，绿，蓝均为1 0 时，表 现为自光，都为0 0 表示没有光。材质的颜色代表了光线反射时的数量多少， 例如红= 绿= 蓝= a l p h a = 1 0 表示所有光线都被反射，材质看上去为白色，红= 蓝= 0 0 ，绿= a l p h a = 1 0 则表示只有绿光被反射，即材质看上去为绿色。 d i r e c t 3 d 支持三种类型的光源： 1 ) 点光源 从一个点向周围均匀地发射光线，有颜色、位置、作用范围，光强随距 离而衰减，向所有方向都发出光( 类似于白炽灯) 。 2 ) 聚光灯 由相互平行的光线组成( 如：太阳光) ，只有颜色和方向，没有光源位 置，也没有作用范围和衰减，物体所受到的光照都相同。 3 ) 平行光 光束为圆锥，分为内、外核两部分。内核最亮，且亮度保持不变，外核 较暗，沿径向有衰减。 d i r e c t 3 d 需要知道顶点法线以便它能够确定灯光照射到物体表面的角度， 顶点法线是描述顶点方向的向量，一旦计算了每个顶点的灯光，d i r e c t 3 d 需要 知道每个顶点的表面方向，注意顶点法线不一定和面法线相同，如球体的顶点 法线和三角形法线就不相同。 给场景增加灯光特效的步骤i l ) 允许使用灯光。 2 ) 为每个物体创建材质并且在渲染相应物体前应将材质附予物体。 3 ) 创建一个或多个光源，设置为可用。 4 ) 将其他附加光源设为可用。 4 1 2 4 纹理映射 纹理映射是一种三角形赋予图象数据的技术。这让我们能够更细腻更真实 地表现我们的场景。一个纹理是一个类似像素矩阵的表面，它能够被映射到三 角形上。在d i r e c t 3 d 中个纹理是通过i d i r e c t 3 d t e x t u r e 9 接口来表现的。 1 ) 二维纹理映射建模 二维纹理映射就是从二维纹理平面到三维物体表面的映射。一般二维纹理 武汉理 大学硕士学位论文 平面是有范围限制的。在这个平面区域内，每点都可用数学函数表达，从而可 以离散的分离出每点的灰度值和颜色值，这个平面区域称为纹理空间，一般将 纹理空间的平面区域定义在【o ，1 】。 纹理映射是确定物体表面一点p 在纹理空间中的对应点( u ，v ) ，从而纹理空 间中的点( 1 i ，v ) 处的纹理值就是物体表面点p 的纹理属性这样屏幕上显示像素 的颜色可通过从物体空间对应点的映射得到，当确定了物体表面的纹理属性，接 着就是将物体表面上各点所对应的纹理值作为光照明模型中的相应参数进行光 强度计算再绘制画面。 2 ) 两步法纹理映射 是一种独立于物体表面的纹理影射技术，将纹理空问到物体空间的映射 分为两个简单的映射复合。两步法纹理映射的核心是引进一个包围物体的中介 三维曲面作为中间映射媒体，主要过程分两步：第一步将二维纹理映射到一个 简单的三维物体表面，如平面，球面，圆柱面，立方体表面，采用不同的中间映 射媒体生成的纹理效果是不同的，要根据目标物体表面来选择。 s ：( u ，v ) ( x ，y ，z )一s - 映射 第二步将三维物体表面上的纹理映射到目标物体表面 0 ：( x i ，y f ，z ) 一 ( x ，y ，z )一0 映射 0 映射一般有4 种：第一种取视线在物体表面可见点( x ，y ，z ) 处的反射与中 间映射媒体表面上的交点( x i ，y - ，z 1 ) 作为( x ，y ，z ) 的映射点。称为环境映射。第二 种取物体表面可见点( x ，y ，z ) 处的法线与中间映射媒体表面上的交点作为映射 点。第三种取物体中心到可见点( x ，y ，z ) 的射线与中间映射媒体表面上的交点作 为映射点。第四种中间映射媒体表面上的点( x ，y i z ) 处的法线与物体表面的交 点为( x ，y ，z ) ，“，) ，z f ) 为( x ，y ，z ) 的映射点。环境映射是近似的模拟光线跟踪，但 没有光线跟踪复杂，所以能大大提高光线跟踪算法的效率，其应用最广泛。 3 ) 凹凸纹理映射( b u m p m a p p i n g ) 两步法纹理映射方法只能实现物体表面的颜色纹理，不能实现物体表面几 何形状的凹凸不平而形成的粗糙质感。凹凸纹理映射是一种无须修改物体模型 就能实现物体表面凹凸不平效果的纹理映射技术。由于物体表面的光强度是由 物体表面的法向量决定的，凹凸纹理映射通过对物体表面各采样点的法向量作 微小的调整来改变物体表面的光强度，达到凹凸不平效果。但不是任何调整都 能产生凹凸不平的真实感效果，我们需要建立数学模型，定义物体表面参数方 武汉理。l 大学硕十学位论文 程，在( m ，n ) 点的法向量为： 矿= v ( m ，”) ( 4 6 ) 设v m ，v n 分别是v 在i i l n 上的分量，那么在( m ，n ) 点的单位法向量为 n = n ( m ，n ) = v m v n i v m v n ( 4 7 ) 现在用一个微小调整的函数p ( m ，n ) ，一般这个函数是连续可微的，那么 通过函数p ( m ；n ) 调整的点( m ，n ) 的新法向量为： v ( m ，”) = v ( m ，) + p ( m ，n ) n ( 4 8 ) 其中： 矿。坍：v m + 尸打z ， ( 4 9 ) v n = v n + p 槲 ( 4 1 0 ) 从而得到新的单位法向量： 其中： k v 。m x v 九= n + d d = p m a p n b a = n x v n b = n x v m ( 4 1 1 ) ( 4 1 2 ) ( 4 1 3 ) ( 4 1 4 ) 对于函数p ( m ，n ) ，可以用一张凹凸图来离散的给出各点的值。 4 ) m i p - m a p p i n g ( m u l t u m i n p a r v o - m a p p i n g ，阶层式贴图映射) 纹理映射常常需要将纹理图案映射到不同大小的物体表面，理想的情况是 物体表面大小和纹理图案大小致但实际物体表面大于或小于纹理图案的情 况很多，这时必须取这区域的纹理属性值如像素颜色的平均值作为对应表面的 纹理属性，但当物体表面形状复杂时，计算平均值并不能精确得到物体表面的 纹理属性。为了使这个大小差异变小，我们为纹理创建m i p m a p s 链。也就是说 将一个纹理创建成连续的变小的纹理m a p ，并对它们等级进行定制过滤。 m i p - m a p p i n g 确定屏幕上可见表面的纹理过程如下： 首先计算屏幕上可见表面的中心在纹理空间上的映射点坐标( 1 l ，v ) 。 然后确定纹理空间中以( 1 l ，v ) 为中心，边长为d 的正方形，一般d 为表面在纹 理空间中映射的区域的最大边长。 最后根据d 的大小确定使用哪一级的纹理m a p 。 2 4 武汉理， 大学硕十学位论文 4 1 3 光栅化 光栅化处理阶段主要是将进行过几何变换的几何图元转换为二维图像的过 程，经过转换后图像的每个点都包含诸如颜色、深度、纹理数据等信息。光栅 化后的像素点和它的相关信息合起来称作碎片。整个光栅化处理流程如右图4 ，6 所示： i光栅化准备工作 j i光栅化 i l ，碎片处理 i i显示输出 图4 7 光栅化处理 1 ) 光栅化准备阶段 剔除不需要光栅化的三角形，计算三角形的边斜度，颜色渐变层，贴图坐 标梯度。 2 ) 光栅化 三角形光栅化主要应用于像素点，计算三角形所覆盖的像素的坐标，计算 每个内部像素的数据，包括r g b a 颜色、深度、纹理坐标等信息。处理凸凹形 多边形，转换多边形为线段和像素点。在渲染时，流水线会贯穿每个三角形的 表面进行顶点数据插值。有五种可能的数据类型可以进行插值包括：漫反射色、 镜面反射色、漫反射阿尔法( 三角形透明度) 、镜面反射阿尔法、雾因子( 固 定功能流水线从镜面反射的阿尔法分量中取得，可编程顶点流水线则从雾寄存 器中取得) 。顶点数据可以是各种类型的数据，顶点数据通过顶点声明定义。 对一些顶点数据的插值取决于当前的着色模式，如表4 。1 所示。 武汉理，【：大学硕十学位论文 表4 1 着色模式 着色模式描述 在平面着色模式下只对雾因子进行插值。对所有其它的插值对 平面 象，整个面都使用三角形第一个顶点的颜色。 t 高洛德在所有三个顶点间进行线性插值。 一 根据不同的颜色模型，对漫反射色和镜面反射色的处理是不同的。在r g b 颜色模型中，系统在插值时使用红、绿和蓝颜色分量。颜色的阿尔法成员作为 单独的插值对象对待，因为设备驱动程序可以以两种不同的方法实现透明：纹 理混合或点画法。可以用d 3 d c a p s 9 结构的s h a d e c a p s n l 成员确定设备驱动程 序支持何种插值。 顶点用于描述位置和方向。图元中的每个顶点由指定其位置的向量、颜色、 纹理坐标和指定其方向的法向量描述。四元数给三元素向量的 x ，y ，z 】值增加了 第四个元素。用于三维旋转的方法，除了典型的矩阵以外，四元数是另一种选 择。四元数表示三维空闯中的一根轴及围绕该轴的一个旋转。四元数包含了有 价值的信息，但它们真正的价值源自可对它们执行的两种操作：合成和插值。 对四元数进行插值与合成类似。两个四元数的合成如下所示： q = q i q 2( 4 1 5 ) 将两个四元数的合成应用于几何体意味着“把几何体绕a x i s 2 轴旋转 r o t a t i o n 2 角度，然后绕a x i s l 轴旋转r o t a t i o n l 角度”。在这种情况下，q 表示绕 单根轴的旋转，该旋转是先后将q l 和q 2 应用于几何体的结果。 使用四元数，应用程序可以计算出一条从根轴和一个方向到另一根轴和 另一个方向的平滑、合理的路径。因此，在q l 和q 2 间插值提供了一个从一个方 向变化到另一个方向的简单方法。 当同时使用合成与插值时，四元数提供了个看似复杂而实际简单的操作 几何体的方法。例如，设想我们希望把一个几何体旋转到某个给定方向。我们 已经知道希望将它绕a x i s 2 轴旋转r 2 度，然后绕a x i s l 轴旋转r l 度，但是我们 不知道最终的四元数。通过使用合成，我们可以在几何体上合成两个旋转并得 到最终单个的四元数。然后，我们可以在原始四元数和合成的四元数闻进行插 值，得到两者之间的平滑转换。 d i r c a 3 d 扩展( d 3 d x ) 工具库提供如下使用四元数的函数： 武汉理工大学硕士学位论文 d 3 d x q u a t e m i o n r o t a t i o n a x i s 4 1 i 函数：给一个定义旋转轴的向量增加个旋 转值，并在由d 3 d x q u t e r n i o n 结构定义的四元数中返回结果； d 3 d x q u a t e r n i o n m u l t i p l y 【4 1 i g l 数：合成四元数： d 3 d x q u a t e m i o n s l e r p t 4 1 i 甬：在两个四元数间进行球面线性插值( s p h e r i c a l l i n e a ri n t e r p o l a t i o n ) 。 d 3 d x 工具库提供的数学函数中包含了许多辅助函数，可以简化对二成员 和四成员向量的使用。 3 ) 碎片处理 经光栅化处理后像素进入碎片处理阶段，此阶段将处理并保存像素的颜色 和深度值，主要处理过程包括纹理映射，雾化，反锯齿，最后单独对每个碎片 处理。纹理映射将图像数据从系统内存传递到在线纹理存储器中，使用内插值 纹理坐标来查找纹理内存并且获取颜色数据。雾化效果打开时，物体随着距离 的延长而淡出，其雾化效果随着观察者距离的增加而增强，我们可以使用不同 的雾化混合因子的值来达到雾化效果，并对每个碎片进行雾化计算。当高频信 息通过低频像素采样时，会发生锯齿，反锯齿技术尝试减轻赝样锯齿，根据碎 片所覆盖的像素的总量调整像素颜色。单个碎片处理主要是对碎片进行一系列 的测试，当通过测试时，碎片数据可以直接替代帧缓冲中现有的数据。否则， 根据某些模式的状态，碎片数据可能与帧缓冲已有数据结合。常用的测试方法： 一是剪切测试( s c i s s o rt e s t ) ，判断碎片是否在视口中，如果测试失败，碎片 将被抛弃。二是a l p h a 值测试，将碎片的a l p h a 值与固定参考值进行比较，如 果测试失败，碎片将被抛弃。三是蒙板测试( s t e n c i lt e s t ) ，将碎片的蒙板值 与蒙板参考值进行比较。四是深度测试，判断新进入的碎片是否比以前已经渲 染过的碎片更近，将新进入的碎片深度值与深度缓冲器中的当前值进行比较， 如果测试失败，碎片将被抛弃，否则如果需要更新，则更新为碎片的深度值。 最后在某些情况下我们将对不能通过测试的碎片进行混合，将新进入的碎片的 颜色与帧缓冲区中碎片所在位置的颜色相结合，将颜色写回到帧缓冲区。 武汉理，r 大学硕士学位论文 4 2 摄像机控制 摄像机系统决定了玩家如何观看3 d 物体，在物体被转换到摄像机空阳j 后， 生成视图平截锥体，我们所看到的游戏物体都是在此平截锥体中，摄象机的原 理如图4 8 ： 毵赛点 圈4 8 摄像机原理 不同的摄像机系统呈现在我们面前的游戏物体是完全不同的，一台摄象机 有以上画面中的一些属性： 1 ) 观察点：摄象机摆放的位置 2 ) 目标点：摄象机对着一个地方 3 1 观察范围：圆锥形状投影范围的夹角大小，单位是弧度。 4 ) 可见的最近和最远距离：这两个距离中间的观察范围就是可见区域。 5 1 纵横比：显示时候的宽和高比例，一般为l 。 常用的摄像机系统有如下三种： 1 ) 第一人称摄像机 摄像机的位置用位置和姿态来表示，键盘鼠标控制位置姿态的改变，如c s 等第一人称射击游戏都是采用此类摄像机。 2 ) 第三人称摄像机 摄像机处于旁观角色，如古墓丽影中采用此类摄像机。 3 ) 球形摄像机 球形摄像机总是指向同一个点，或者观看同一个位置，但是它能够在球面 上围绕着物体自由移动。玩家使用鼠标滚轮来缩放摄像机，通过增加或者减小 2 r 武汉理1 ：大学硕十学位论文 摄像机所运动的球体半径，我们能够改变从摄像机到物体的距离。 d i r e e t 3 d 为开发者提供了多种摄像机类型的封装。 4 3 碰撞检测与响应 1 ) 碰撞检测的提出 碰撞检测在3 d 游戏中至关重要，好的碰撞检测要求人物在场景中可以平 滑移动，遇到一定高度内的台阶可以自动上去，而过高的台阶则把人挡住，遇 到斜率较小的斜坡可以上去，斜率过大则把人挡住，在各种前进方向被挡住的 情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。在满足这些要 求的同时还要做到足够精确和稳定，防止人物在特殊情况下穿墙而掉出场景。 碰撞检测做得好了是应该的，不易被人注意到，因为这符合我们日常生活中的 常识。做得差了却很容易让人发现，人物经常被卡住不能前进或者人物穿越了 障碍。 碰撞检测是一个四维的问题，即三维空阃加上时阃。在三维空间内，两个 物体处于不同的位置，有不同的速度和加速度，沿一定的轨迹运动，我们要判 断其是否会在未来发生碰撞。显然这样计算太复杂，因为此时静态的检测问题 变成了动态的预测问题。三维空间本来就已经很复杂，再加上时间将更复杂。 通常我们在更新物体位置和处理碰撞检测时常常回避了物体移动轨迹问 题，只计算下一步物体的位置和近在眼前的可能的碰撞。如果此时有碰撞的可 能，物体就停在原来位置。这是一种离散的算法，而不是连续的算法。因为物 体的下一个位置决定于最小的步距，也就是对空间的离散采样。而且它只考虑 在下一个时刻的物体位置，这样就把时间固定了。使得碰撞检测问题减少了时 间这一维的复杂性。当前这种离散算法得到广泛的使用，但它也存在很多问题。 主要就在于其离散性上。因为不是连续地考虑时间和空间，有可能出现以下情 况： 物体在t l 的时候位于墙的左侧，根据其速度和加速度等数据，我们可以计 算出在下一个时间t 将位于墙壁右边。如果我们不考虑f l 0 。 4 ) h ( n ) = ”( n ) ( h + ( n ) 为实际问题的代价值) 。 a + 算法实现寻路时占据大量的c p u 时间，尤其是在大地图上有大量对象 在寻路的时候。以下方法将有利于提高寻优速度： 1 ) 尽量在程序中使用更小的地图或者更少的寻路者。 2 ) 不要同时给多个对象寻路，取而代之的是把他们加入一个队列，把寻路过 程分散在几个游戏周期中。 3 ) 尽量使用更大的地图网格，这降低寻路中搜索的总网格数。 4 ) 使用路径点系统计算长路径，或者预先计算好路径并加入到游戏中。 5 ) 预处理地图，标明地图中哪些区域是不可到达的。 a 的下限是，当告诉要寻找通往那些区域的路径时，会搜索整个地图，直到 所有可到达的方格，节点都被通过开启列表和关闭列表的计算，这会浪费大量的 c p u 时间。可以通过预先确定这些区域来避免这种情况的发生，用某些种类的数 组记录这些信息，在开始寻路前检查它。 5 2 3 优化的a 宰算法 通过观察，我们可以发现，所有的最优路线，如果是一条折线，那么、其 每一个拐弯点一定发生在障碍物的突出边角( 可以认为是一个凸多边形的顶点 处) ，而不会在还没有碰到障碍物就拐弯的情况，所以我们在搜索路径时，其 实只需要搜索这些凸多边形顶点，如果可以将各个顶点连接成一条通路就表示 找到了最优路线，而不需要每个点都检索一次，这样就大大减少了搜索次数， 不会因为距离的增大而增大搜索时间。 3 8 武汉理一l ：大学硕十学位论文 伪代码如下： 在主程序中遍历得到场景中凸多边形顶点并计算相互可达的顶点分组信息 存入临时表t b lv e r t e x 中。 g e t p a t h f r o m g o o d a 0 e n d n o d e = 9 0 建目的结点； s t a r t n o d e = 创建起始结点； 将e n d n o d e 与可以直达的凸多