（计算机应用技术专业论文）手机室内3d游戏渲染引擎研究.pdf

浙扛大学硕上学位论文 摘要 手机游戏市场的需求渐渐从2 d 过渡到3 d ，但是由于占市场大份额的中低 档手机处理器性能的限制，目前很少有能在中低档手机运行的3 d 游戏，因此在 这些手机卜研究并开发3 d 渲染引擎将具有广阔的市场。 通过实验研究分析了3 d 游戏渲染流水线的构建过程，分析了3 d 真实感图 形学中的算法基础和目前成熟的3 d 游戏引擎中使用的技术，分析其优缺点，在 手机平台上实现的可行性，将在处理器主频率为3 3 4 4 m h z 的手机平台上研究开 发个室内3 d 游戏渲染引擎。 刈室内3 d 游戏场景的建模进行厂简化，具体分析了窄间划分技术，包括二 元空间划分c o i n a d s p a c e p a r t i f o n ) ； 1 潜在可见集( p o t c t l a l v i s i b l es e t ) ，十要使用二元 空间划分技术进行排序，提出并使用包围盒( b o u n db o x ) 与潜在可见集技术进行大 规模的剔除操作，对于角色的动画与光影效果进行了简化，提出一个快速的计算 方法，针对纹理压缩，提出了基于块编码的有损压缩算法。 研究r 光线投射( r a y 。c a s t i n g ) 技术，分析了其算法过程，投影的几何关系等等， 诈采用光线投射技术来构建手机上的室内3 d 游戏渲染引擎。 分析了在手机上开发3 d 游戏渲染引擎的性能瓶颈，针对这些问题，研究分 析了各种优化技术，尤其是针对手机a r m 7 平台的一些优化技术。 给出1 r 采用简化方案和优化技术的实验结果，并作了分析，构建的室内3 d 游戏渲染引擎在主频率为4 0 m h z 的中低档手机上取得了流畅的刷新速度。 关键词： 渲染引擎，二元空间划分，潜在可见集，光线投射 塑垩查堂堕主堂垡丝兰 一 a b s t r a c t w i t hm o b i l ep h o n et e c h n o l o g yp r o g r e s s i n ga ta ni n c r e d i b l ep a c e ，m o b i l eg a m e p r e v a i l si n t h ee n t e r t a i n m e n tm a r k e t m o b i l eg a m e se v o l v ef r o ms i m p l eg r a p h i c a l g a m e st oc o m p l e xg r a p h i c s i n t e n s i v e3 dg a m e s h o w e v e rb e c a u s eo fl o wc o m p u t i n g p o w e r ，f e w3 dg a m e sh a sb e e nd e v e l o p e df o rm o b i l ep h o n eo fl o wp e r f o r m a n c e d e v e l o p i n ga3 dr e n d e r i n ge n g i n ef o rt h e s ep l a t f o r m sw i l lm a k eg r e a tb e n e f i t s 3 dp i p e l i n e s o m eg r a p h i c sa l g o r i t h m sa n ds o m ep o p u l a r3 dg a m ee n g i n ei s a n a l y z e d a f t e rd o i n ga l o to fr e s e a r c h ，a ni n d o o r3 dg a m er e n d e r i n ge n g i n ew i l lb e b u i l ta i m i n ga tm o b i l ep h o n eo fl o wc o m p u t i n gp o w e r m o d e lo fa l li n d o o rg a m ew o r l di ss i m p l i f i e d a ni n d o o r3 dg a m er e n d e r i n g e n g i n ei sb u i l to nm o b i l ep h o n e ，e l i m i n a t i n gh i d i n gf a c eb yu s i n gb i n a r ys p a c e p a r t i t i o n ( b s p ) ，c u l l i n ga n dc l i p p i n gb yu s i n gb o u n db o xa n dp o t e n t i a l v i s i b l e s e t ( p v s ) as i m p l i f i e da n i m a r i o na n dc h a r a c t e rs y s t e ma n dl i g h tm o d e la r eb u i l t a l o s s yt e x t u r ec o m p r e s s i o na l g o r i t h mb a s e do nb l o c ke n c o d i n gi sp r o p o s e d m a t hb e h i n dr a y c a s t i n ga n dt h ea l g o r i t h mw a si l l u s t r a t e da n dg a m ew o r l d w a s r e n d e r e db yr a y c a s t i n g b o t t l en e c ko fm o b i l e3 dg a m er e n d e r i n ge n g i n ew a sa n a l y z e d s o m eo p t i m i z i n g t e c h n i q u e sw a si l l u s t r a t e d ，e s p e c i a l l ys o m et e c h n i q u e sb a s e d o na r m 7 p l a t f o r m s o m ee x p e r i m e n t a lr e s u l t sa r eg i v e n ，t h ei n d o o r3 dg a m er e n d e r i n ge n g i n ec a l l b e t i no nm o b i l ep h o n eo fl o wc o m p u t i n gp o w e rw i t hs m o o t ha n i m a t i o n k e y w o r d s ： r e n d e r i n ge n g i n e ，b i n a r ys p a c ep a r t i t i o n ，p o t e n t i a l v i s i b l e s e t ， r a y - c a s t i n g i i 浙江大学硕士学位论文 第章绪论 随着移动技术的快速发展，一些应用开发平台如i 2 m e 、b r e w 、s y m b i a n 的成熟，手机游戏变得越来越流行。手机游戏逐渐从简单的小游戏，向大规模高 冲击的视频游戏发展，并大有从2 d 进化到3 d 的趋势，嵌入式平台上也推出了 嵌入式o p e n g l 标准o p e n g le s l ”，同时很多高档手机上出现了a t i 加速卡， 可以预见在不久的将来，3 d 游戏在手机上将非常流行，而要开发3 d 游戏必须 先构建3 d 图形系统，也就是3 d 渲染引擎。 3 d 渲染引擎，是把3 d 世界渲染到屏幕上的一个图形系统，主要的工作就 是负责处理通过3 d 场景与角色建模生成的数据结构( 包括所有的光源、动作和 常规状态信息) 以及玩家或相机所在的视点渲染整个3 d 世界【2 。生成的图形具 有定的真实感效果，有纹理、材质和光照等效果。 通过上述定义可知，开发一个3 d 游戏必须先对场景与人物角色，进行建模， 并生成一定的数据结构，而3 d 渲染引擎，就是根据这些数据结构以及玩家的视 点位置将图形投影到屏幕上，在手机上开发3 d 渲染引擎，就要构建一个这样的 投影显示系统。 同前3 d 游戏渲染引擎的研究，主要是在p c 平台上进行，成熟的游戏引擎 有d o o m 、q u a k e 和u r e a l 等1 ，这些引擎采用了图形加速卡的硬件支持技 术，手机上的3 d 游戏引擎研究很多也是采用了硬件支持技术，如国外的手机游 戏公司g a m e l o f t 在高端手机上开发出多款3 d 游戏，这些手机大都有图形加速 卡，并且有o p e n g l ，e s 的支持，而针对中低档手机的3 d 游戏研究开发，目前 还不是很多。 3 d 游戏引擎根据游戏场景的不同可以分为室内和室外两种游戏引擎，室内 游戏中玩家大部分时间在室内，而室外则是大部分时间在空阔的场地，针对场景 的特点，对两种引擎通常采用不同的空间划分方法，使用不用的技术，本文的研 究对象为室内渲染引擎。 1 2 课题研究意义及主要内容 目前手机用户使用的中低档手机，主频率在3 3 - - 4 4 i v i h z ，没有图形加速卡 的支持，也没有相应的3 d 图形库的支持，但是国内手机用户大部分使用的是这 种手机，如果能在中低档的手机上实现3 d 游戏引擎，将有巨大的市场前景。本 论文的目标是在中低档手机平台上实现室内3 d 游戏渲染引擎，能够渲染出具有 一定真实感效果的游戏场景，同时保证具有流畅的速度。 浙江大学硕士学位沦文 但是中低档手机计算能力，存储空间受到很大的限制，开发3 d 室内渲染引 擎存在较大的困难。首先，这类的手机没有类似于o p e n g l 和d i r e c t x 的3 d 图 形库，整个3 d 流水线必须从底层开始构建；其次，3 d 渲染涉及到较多复杂的 数学运算和真实感图形学中的复杂算法，对于计算性能较差的手机来说，很多算 法难以实现；再次，室内3 1 2 ) 游戏往往场景较大，并且比较复杂，不能将所有的 建模数据都传送到渲染流水线，必须使用高效的算法，进行剔除操作，最后当场 景越来越复杂时，增加了对内存的需求，必须对纹理贴图进行压缩，同时还要保 证有较快的实时解码速度。 针对这些困难，主要研究工作集中在如下几个方面： 1 介绍分析了3 d 游戏渲染流水线过程，研究三维真实感图形学算法基础 与目前3 d 游戏引擎使用的技术，分析其优缺点及在中低档手机平台上软件实现 的可行性，包括光照模型和纹理映射技术。 2 提出场景建模的一个简化模型，利用二元空间划分( b s p ) 2 , 7 1 包围盒和 潜在可见集( p v s ) 吲在b r e w n 平台上构建室内3 d 游戏渲染引擎，对角色建模， 光照模型进行了简化，提出了一个快速计算方案，并使用基于图像块编码的思想， 在b r e w 平台上实现了对纹理贴图的压缩。 3 剖析了光线投影( r a y - c a s t i n g ) 日技术，并使用其来渲染场景。 4 研究总结了基于a r m 7 1 5 , 6 平台的一些优化技术，特别是针对3 d 游戏引 擎中r a y c a s t i n g 的优化。 5 给出了简化方案与优化技术的实验结果，并作了详细的分析。 本文的后续章节将这样安排： 第二章，介绍分析了3 d 游戏渲染流水线过程，研究了构建3 1 ) 游戏演染引 擎的真实感图形学算法基础和目前成熟的游戏引擎中使用的技术，分析其优缺点 及在手机平台上软件实现的可行性； 第三章，对室内游戏场景进行建模，利用b s p 和p v s 加速技术，来进行大 规模的剔除操作和排序，提出基于图像块编码思想的纹理压缩方法； 第四章，采用r a y c a s t i n g 技术进行场景的渲染； 第五章，研究总结r 一些优化技术，尤其是针对a r m 7 平台的； 第六章，总结与展望。 2 浙江大学硕士学位论文 瓣相关削群毳别谁阶 本章分析了3 1 3 渲染引擎的基本流程与关键技术，研究目前在成熟3 d 游戏 引擎中使用的真实感图形学算法。 2 13 d 渲染流水线概述 目前的3 d 游戏引擎通常是以三角形来对场景和物体进行建模的，并构建成一 个三角形链表，传送到3 d 演染流水线，赢到最终显示到屏幕上，图形加速卡提供 j ，对三角形渲染的硬件支持。典型的3 d 游戏渲染过程如图2 1 所示。三维计算机图 形的生成一般需要经历场景造型、取景变换、视域裁剪、消除隐藏面及可见光亮度 计算等步骤。物体开始在局部坐标系中进行建模，经过模型变换，它以一定的形状、 尺寸存在于场景坐标系的某个位置。在场景坐标系中指定物体的表面属性和光照属 性，根据视点的位置和视线的方向，进行物体的剔除，然后进行视域变换，置入视 点坐标系中。在视点坐标系中，进行视域网棱锥裁剪，然后进行纹理的映射，光照 计算，再进行光栅化计算，最后进行显示。 在游戏引擎中，3 d 流水线可以分为以下几个关键的阶段倒：1 可见性确定包括 裁剪、剔除和消隐；2 分辨率确定；3 变换，光照；4 光栅化。裁剪与剔除是3 d 游 戏中比较关键的两个阶段，对于3 d 游戏来说，特别是场景比较复杂的游戏，为r 保征有稳定的帧数，必须尽早将不可见的三角形从渲染流水上剔除，对部分可见的 进行裁剪，再将可见的部分继续传送到渲染流水线的下一个过程。 2 1 1 裁剪与剔除 裁剪就是确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便 只显示落在显示区内的那部分图形。裁剪算法必须比显示图形要快，否则裁剪过 程不仅不能提供一个加速，反而会成为一个负载。游戏开发中对裁剪的要求是在 3 d 流水线中尽早的进行裁剪工作。 ( 一) 三角形裁剪 现在几乎所有的加速卡都支持三角形级的裁剪。可以把所有的三角形都传送给 图形加速1 ，不可见的部分将被丢弃，只有可见部分占用光栅化阶段的时间。但是 这并不意味着在游戏编程中可以不用自己编写代码来进行裁剪。将不可见的三角形 传给图像加速卡，浪费了数据线的有限带宽，所以必须使用其它方法将不可见的三 角形剔除。 ( 二) 对象剔除 由于三角形裁剪受到数据总线传输速度的限制，所以需要在三角形传送给图形 加速卡之前进行裁剪，而软件实现的三角形裁剪，对于实时3 d 游戏来说达不到所 要求的速度，需要进行更高抽象层的裁剪，提高处理对象的粒度。比较好的方法是 浙江大学硕十学位论立 脚相关削群费胡询介 本章分析了3 d 渲染引擎的基本流程与关键技术，研究目前在成熟3 d 游戏 引擎中使用的真实感图彤学算法。 2 j3 1 ) 渲染流水线概述 目前的3 d 游戏引擎运常是以三角形来对场景和物体进行建模的，并构建成 个二角形链表，传送到3 d 演染流水线，宜到最终显示到屏幕上，图形加速 提供 r 对二角形渲染的硬件支持。典型的3 d 掳戏渲染过程如图2 1 所示。三维计算机图 形的生成一般需要经历场景造型、取景变换、视域裁剪、消除隐臧面及可见光亮度 训算等步骤。物体开始在局部坐标系中进行建模，经过模型变换，它以一定的形状、 尺寸存在于场景坐标系的某个位置。在场景坐标系中指定物体的表面属性和光照属 一m 根据视点的位置和视线的方向，进行物体的剔除，然后进行视域变换，置入视 点坐标系中。在观点坐标系中进行视域四棱锥裁剪，然后进行纹理的映射，光照 计算，再进行光栅化计算。最后进行显示。 在游戏引擎中，3 d 流水线可以分为以下几个关键的阶段“：1 可见性确定包括 裁劐、剔除和消隐；2 分辨率确定；3 变换，光照；4 光栅化。裁剪与剔除是3 d 游 戏巾比较关键的阿个阶段，对于3 d 游戏来说，特别是场景比较复杂的游戏，为r 保征有稳定的帧数，必须尽早将不可见的三角形从渲染流水上剔除，剥部分可见的 进行裁剪，再将可见的部分继续传送到渲染流水线的下一个过程。 2 1 1 裁剪与剔除 裁剪就是确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便 只显示落在显示区内的那部分图形。裁剪算法必须比显示图形要快，甭则裁剪过 程不仅不能提供一个加速反而会成为一个负载。游戏开发中对裁剪的要求是在 3 d 流水线中尽早的进行裁剪工作。 ( ) 三角形裁剪 现在几乎所有的加速卡都支持三角形级的裁剪。可以把所有的三角形都传送绘 图形加速 ，不可见的部分将被丢弃，只有可见部分占用光栅化阶段的时间。但是 这并不意味着在游戏编程中可以不用自己编写代码来进行裁剪。将1 i 可见的三角形 传给图像加速卡，浪费了数据线的自限带宽，所以必须使用其它方法将不可见的二 角形剔除。 ( 二) 对象剔除 由于三角形裁剪受到数据总线传输速度的限制，所以需要在三角形传送给图形 加速卡之前进行裁剪，而软件实现的三角形裁剪，剥于实时3 d 游戏来说达不到所 要求的速度，需要进行更高抽象层的裁剪，提高处理对象的粒度。比较好的方法是 要求的速度，需要进行更高抽象层的裁剪，提高处理对象的粒度。比较好的方法是 浙江大学硕士学位论文 基于对象的剔除操作，使用某种算法判断对象与视景体的几何关系，完全不可见时 可以将整个物体剔除，它可能有几千个三角形组成。这样会提高整个流水线的性能， 尤其对于室内的游戏来说。 物体 图2 1 典型的3 d 游戏渲染流水线 常用的方法有两种：包围球和包围盒技术。包围球如图2 2 所示，当包围球 完全处于视域外时，可以完全的剔除，不必对三角形进行逐个的测试，从而可以 提高性能。 物体 ”。、 r 。 莉_ - 7 - 僻 、q 芝 莎 图2 2 包围球测试示意图 浙江大学硕士学位论文 2 1 2 消隐 消隐就是根据视点和视线方向，决定场景中哪些物体的表面是可见的，哪些 是被遮挡而不可见的。常用的消隐算法有画家算法，z b u f f e r ，b s p 算法【1 叫等。 画家算法根据景物表面与投影面的距离进行排序，从离视点最远的景物表面开 始，依次计算每表面的光亮度并将其写入屏幕缓冲区，离视点较近的景物表面的 颜色值将覆盖原有的颜色，从而实现消隐，这个算法的时间复杂度至少为 o ( n l o g n ) ，并且对于相互交叉的物体不能保证渲染的正确性，因此在游戏中很少 使用。在目前的3 d 游戏引擎中普遍使用的是z b u f f e r 算法【7 j ，工作原理是在内 存中开辟一块跟屏幕对应的缓冲区，存储对应点处的z 值，在渲染景物时，跟 对应的z 值进行比较，如果比它小( 距离投影平面近) 则渲染到屏幕上，并将 它的z 值改写到对应点，否则不渲染景物。该算法简单，而且大多数图形加速 卡都提供了硬件支持。b s p 技术比较适合于软件实现的消隐，它也是d o o m ， q u a k e 中使用的算法，采用二叉树的数据结构，对场景预先做好排序，在渲染 的时候只要根据视点的位置遍历b s p 树，就可以保证正确的消隐，对于构建的 比较好的b s p 树，遍历的时间复杂度是o ( 1 0 9 n ) ，它以一定的空间来换取时间效 率。 2 1 3 坐标变换 现在流行的3 d 游戏引擎坐标问的变换是通过矩阵的运算来进行的，图形加 速卡都提供了硬件级的矩阵运算支持。矩阵n 嗣可以对所有形式的变换进行统一 的形式化表示，如一个简单的平移变换可以表示成： 旋转 i x y 。z 11 - - 上y z 1 1000 ：。17 ：l = x + t ，+ 瓦z + i ， tlt 1 而在右手坐标系下相对坐标系原点绕坐标轴旋转0 角的变换公式是：绕x 轴 i x yz 1 1 = 1 x y z 10 1 1 l0 c o s 0 1 j io s i n 口 00 0 s i n 0 c o s 0 0 使用矩阵的缺点是运算量比较大，简单的平移可以通过3 个加法运算完成， 使用矩阵却需要1 6 次乘法和1 2 次加法完成，对于没有硬件加速的手机，不能用 矩阵实现坐标和投影的变换。 浙江大学硕士学位论文 在游戏中，为了产生明暗过渡自然的真实感图形，首先必须建立光照模型，它 描述了物体表面的颜色与其空间位置、朝向、物理属性( 反射率、折射率) 关系。 依据光照模型、绘制算法具体计算对应屏幕上各像素的物体表面的颜色，并最终硅 示图形。模拟物体表面的光照明物理现象的数学模型称为光照模型m 。它分为简单 光照模型和整体模型。 2 2 1 简单光照模型 简单光照模型也称为局部光照模型，假定物体不透明，只考虑光源直接照射在 景物表面产生的光照效果。当光照射在某一表面上时，它可能被吸收、反射或者折 射。其中入射到表面上的一部分光能被吸收并转化为热，其余部分被反射或折射。 反射光和透射光决定了物体的颜色。光能中被吸收、反射或透射的数量决定于光的 波长。某些波长的光被有选择的吸收，则离开物体表面的反射光和透射光将具有不 同的能量分布，这时物体呈现出颜色。物体的颜色取决于它所选择吸收的那部分光 的波长。 ( 一) 环境光 在避光的地方，景物没有受到光源的直接照射，但其表面仍具有一定的亮度， 使它们是可见的。这是因为光线在场景中经过复杂的传播后，形成了弥漫于整个 空间的光线，称为环境光；在简单光照模型中，把环境光在空间中作均匀分布来 处理，即在任何位置、任何地方上强度都一样，记为l ，在分布均匀的环境光 的照射下，物体表面呈现的亮度未必相同，因为它们的环境光反射系数彳i 同，记 为k 。，物体表面所呈现的亮度记为t ，由此得到只包含环境光的光照明方程为： ，。= k 。，。 由此看出，若一个物体的k 。= 0 ，则无论环境光多么强，该物体都是黑色的。 并曰，当同一物体表面的e 为常数，则其上的亮度相同。 ( 二) 漫反射 只考虑环境光来绘制物体时，虽然不同的物体具有不同的亮度，但同物体 的表面亮度是一个恒定的值，没有明暗的自然过渡，所以必须考虑引入点光源， 儿何形状为一个点，位于空间中的某个位置，向周围所有的方向上辐射等强度的 光，亮度记为，。在点光源的照射下，物体表面的不同部分亮度不同。亮度的 大小取决于它的朝向以及它与点光源之间的距离。粗糙、无光泽的物体表面对光 浙江大学硕士学位论文 的反射表现为漫反射。在表面某点上，这样的表面对入射光在各个方向上呈强度 相| 司的反射。因而无论从哪个角度看，该点的亮度都是相同的。 对于给定的表面，记其在p 点的法向为丙，从p 点到点光源的矢量为云， o 为丙与z 的夹角，p 点的漫反射光亮度l 由l a m b e r t 余弦定律确定： d = l p 髟c o s t 9 ，口( o ，；, r 2 ) 其中，k 。【o ，1 ，为物体表面的漫反射系数，由上式可以看出，j 。只与入 射角。有关，而与反射角无关，即与视点的位置无关。如图2 3 所示，。的强度 在各个反射方向上相等。入射角0 必须在0 到；r c l 2 之间变化，当日 ：, r 1 2 时反射 光线将被物体自身遮挡而照射不到p 点( 对于不透明的物体) 。若与l 都已 经规范化，则亮度方程可以表示为： ，。= ，。心( z 丙) n 图2 3 漫反射光强度与入射角有关 ( 三) 镜面反射 光滑的物体表面如金属或塑料表面在点光源的照射下会形成一块特别亮的 区域，它是物体表面对入射光进行镜面反射引起的。镜面反射遵循反射定律，反 射光与入射光位于表面法向两侧。对于理想反射面如镜面，入射角等于反射角， 观察者只能在反射方向上才能看到反射光，而偏离了该方向则看不到任何反射 光。对于非理想反射面，如苹果等的表面镜面反射模型由p h o n g 模型给出： 如图2 4 所示，p 为物体表面上一点，l 为从p 指向光远的矢量，为入射 角，矿为从p 指向视点的矢量，盯为矿与天的夹角，p h o n g 模型表示为： f ；= i p k ；c o s “8 浙江大学硕士学位论文 其中，t 为从矿方向上观察到的镜面反射光的亮度，显然，在o c = o 的方向 上，取得最大值。将c o s 口= 矿蠢代入上式，得到： ，= j 。墨( 矿天) ” 图2 4 非理想镜面反射 ( 四) p h o n g 模型 简单光照模型模拟物体表面对光的反射作用，光源为点光源，反射作用分为 环境光、漫反射和镜面反射。p h o n g 光照明模型的综合表述为：由物体表面上的 一点p 反射到视点的光强i 为环境光的反射光光强t 、理想漫反射光强，。和镜面 反射光，。的总和。 ，= ，。+ d + ，。= ，。k 。+ ，。【k , t ( l ) + 0 1 r ) ” ( 五) 光的衰减 光的衰减分为两个阶段：从光源到物体表面的过程中的衰减和从物体表面到 人眼过程中的衰减。总的效果是物体表面亮度的降低。 光在光源到物体表面的衰减过程中，光强按1 d 2 进行衰减，衰减函数为： 1 八们刊呱石才可d 光在物体表面到人眼过程中的衰减使用深度暗示技术：最初用于线框图形的 显示，使距离远的点比近的点暗一些。经过改进，这种技术同样适用于真实感图 形显示。 浙江大学硕士学位论文 、 3 f 焉 3 、 z 图2 5 深度暗不 如图2 5 所示：设前参考面z ：z ，后参考面z = 乙，其比例因子分别为s ，和 s b ( s s 和邑 0 ，1 ) 。给定物体上一点的深度值z o ，该点对应的比例因子s 。按照 下式确定： 当z o z ，时，s o = s ， 当z o 1 ) & o x f b e f ，如图3 8 所示，通过将移动到下一个 颜色分量的值用0 屏蔽掉，就可以获得各分量降低后的整体的颜色值，对于亮度 增强为原来的2 倍，4 倍等，可以采用同样的方法。 3 6 纹理的压缩 手机平台上不仅处理器的速度比较低，存储器容量也是非常的小，要构建比 较元素比较丰富的场景，必然要求有很多纹理贴图，并且也是分辨率比较高的， 浙江大学硕士学位论文 闭此对内存空剧提出了较大的挑战，必须对纹理进行压缩。对于压缩方法的要求 是解码的速度必须快，因为是实时渲染的。 l11 l10 1 111 1 0 l 111 图3 8r g b 格式颜色式整体运算示意图 3 d 游戏中对图像的质量要求通常不高，早期的3 d 游戏也因为处理器的性能原 因有很多的块状效应。在手机3 d 游戏中，屏幕比较小，对图像的要求也不如2 d 游 戏r 串那么高，因此可以采用有损的压缩算法。在研究图像的i p 昭压缩方法时，发 现可以使用块编码的思想，对高分辨率的图像进行有损压缩。 具体的过程如下：把纹理按4 x 4 的大小为单元来划分块，编码时以块为单位来 进行，编码后的单元由一个4 色查找表和1 6 个索引组成。对于不透明纹理贴图，从 4 x 4 的单位块中选择两个像素点的颜色，总共3 2 b i t s ，这两个颜色加上使用一个插入 算法在其中插入两个新的颜色值，构成了四色查找表。四色查找表决定了块中每个 单，i 的实际的颜色值，这样对于每个点的颜色值，可以使用2 b i t 的索引来表示，每 个块被编码为3 2 个b i t 。简单透明纹理保留四色查找表中的第四个颜色来表示该单 元透明，第三个颜色是给出的两个颜色的平均值。区分不透明纹理和简单透明纹理 的方法是看给出两个颜色的存放次序。编码格式如图3 9 。 该算法实现的关键是在单元块中寻找两个实际的颜色值，然后通过插值构成一 个颜色表，而这个颜色表要能保证与实际的图像单元比较误差最小。由于纹理压缩 不要求实时行，可以通过简单的比较来获得最优结果，对于分辨率比较高的纹理能 够获的不错的效果，但是分辨率比较低的情况，效果比较差。这种算法的解码比较 简单，能够获得较快的速度。 捅值公式通常采用如下简单的公式：c o l o r 0 0 、c o l 0 1 0 1 分别代表从4 x 4 的单元中 选取出的两种颜色，c o l o r l 0 、c o l o r l l 分别代表插值后构成的颜色，那么有如下的关 系： c o l o r l 0 = c o l o r 0 0 3 2 x c o l o r l l l 3 c o l o r l l = 2 c o l o r 0 1 3 + c o t o r l l 3 浙江大学硕士学位论文 至至l! ! ! ! 竺l f菖color01colorl01 l 互i i 困i 图3 9 纹理压缩的编码格式 0 00 1 1 1l l l l0 00 10 1 l l 0 0 0 01 1 1 01 01 00 0 3 7 1 剔除的比较 室内游戏引擎的关键就是在于场景的建模与大规模的剔除操作，本文通过 b s p + p v s 技术来进行空间的划分，通过实验表明，它能够有效地减少重绘，能 够将比例控制在5 0 一1 5 0 。图3 1 0 是在b r e w 平台手机上实现的3 d 室内渲染 引擎对图3 1 所示的场景渲染图。 图3 1 0 采用b s p + p v s 实现的场景 d o o m 第一一代和第二代游戏引擎中，仅仅使用了b s p 和包围球来进行剔除 操作，根据图3 1 的场景对使用p v s 和不使用p v s 进行了如下的数据分析：第。 浙江大学硕士学位论文 列表示玩家所在的房间，第二第三列分别表示使用不同的技术最多传递到流水线 的房间数目： 包围球包围球+ p v s s 173 s 26 4 s 375 s 455 s 575 s 674 s 774 表3 ，1 根据图3 1 对使用p v s 和不使用p v s 的比较 通过上面的比较可以知道，采用这样的剔除方案明显好于仅适用包围盒剔除 的技术，这只是一个简单的场景，比例优势不是很明显，对于d o o m 引擎中比 较复杂的场景，使用p v s 就可以看出很大的优势，d o o m 中重绘比例通常达到 1 0 0 0 一2 0 0 0 ，而本引擎中可以控制在5 0 1 5 f p o 。 3 7 2 人物造型与光影效果的比较 对于人物角色的处理采用了跟2 d 游戏中s p r i t e 类似的技术，相对于三角形 建模的角色造型，可以提高游戏的渲染速度。 对于光影效果，本文简单的采用了明暗效果来区分，在d o o m 使用了类似 的模型，不过采用了查表的方法来实现。而实验表明在手机上的访问存储器的操 作，耗时是比较大的，超过了简单的逻辑运算，通常a r m 7 平台上的访存操作需 要3 个时钟周期【5 】，而本文提出的简化与快速计算方法，针对一个像素，可以通 过1 个时钟周期完成，在实际的游戏中，对于处理器主频在4 0 m h z ，屏幕像素 为1 2 0 x 1 4 4 的手机来说，可以将渲染速度提高1 - 2 倍。 3 7 3 纹理压缩的实验结果 在对纹理的压缩中，采用了基于块编码的压缩思想。目前大部分手机上的颜 色为1 6 位，对于4 x 4 大小的图像，需要1 6 x 2 x 1 6 = 5 1 2 位来表示，通过采用3 6 节中基于块的有损压缩算法需要1 6 x 4 + 1 6 x 2 = 9 6 位来表示，因此可以达到的压 缩比为9 6 5 1 2 = 3 ：1 6 。图3 1 1 显示了在手机平台上使用该算法压缩后的效果图， 由于分辨率较低，效果不是很好，难以满足2 d 游戏的图像质量的要求，但是对 于图像要求不高的3 d 游戏来说，可以在渲染引擎中使用。 浙江大学硕士学位论文 3 8 本章小结 图3 1 1 使用基于块编码的有损压缩示意图 本章提出了手机上3 d 场景与角色建模的简化模型，构建了一个3 d 渲染流 水线，与流行3 d 游戏引擎相比，减少了相关的环节；提出了使用b s p 、包围盒 和p v s 的技术，进行场景的排序与剔除操作；对光照效果提出了简化模型；并 针对纹理压缩提出了基于块编码的有损压缩方案，实验结果分析表明，这些模型 的建立与算法的提出，能够在手机手机上取得不错的效果，性能与传统方案相比 性能有较大提高。 浙江大学硕士学位论文 第四章基于聊砌碰嚷蜊塑勖案 场景与人物角色的模型，决定了3 d 渲染流水线采用的渲染方案，根据第三 章中场景的特点，可以采用r a y c a s t i n g 技术 1 ，来进行快速的渲染。本章在研究 d o o mi i 的源代码的基础上总结分析了r a y c a s t i n g 技术，并且分析了可以使用 r a y c a s t i n g 模拟的d o o m 中所没有的特性。 4 1r a y - e a s 衄的定义 r a y c a s t i n g 起源于游戏w o l f e n s t e i n3 d 6 ds o f t w a r e ) ，玩家处于迷宫一样的三维 环境中，跟多个对手作战的同时，必须找到出口。因为快速流畅的动画，它成为 当时的经典，而其使用的渲染技术就是r a y - c a s t i n g 。r a y - c a s t i n g 是通过跟踪从视点 到简化场景中物体的光线来进行投影变换的技术口”。如图4 1 所示： r a y c a s t i n g 把简化成a 一样的场景投影变换成b 。从定义看r a y - c a s t i n g 和光线跟踪算法 ( r a y t r a c i n g ) 没有什么区别，实际上在图形学中把r a y c a s t i n g 作为r a y - t r a d n g 发射出 的光线跟物体仅进行一次求交测试的特例，通常运用于医学上图形显示。但是从 游戏编程的角度，本文的r a y c a s t i n g 是另一个含义，它发射的光线在一个二二维平 面上，并进行跟踪投影，而r a y - t r a c i n g 的光线在三维空间进行。因为r a y - c a s t i n g 需要跟踪的光线比r a y - t r a c i n g 要少，求交测试简单，在速度上比r a y t r a c i n g 要快。 简化的2 d 世界 阿产 视点 a 图4 1r a y - c a s t i n g 示例 3 d 圭影 r a y c a s t i n g 的缺陷： r a y c a s t i n g 跟光线跟踪算法r a y - t r a c i n g 相比速度快，因为它利用了一些几何条 什上的限制，在大多数情况下，场景中墙与地面的角度都是9 0 度，另一个限制 就是视点不能绕z 轴旋转。同时因为几何形状的限制，r a y c a s t i n g 创建的场景比 较简单，生成的图像也不是很真实。 浙江大学硕士学位论文 4 2r a y - c a s l i n g 算蝴 r a y - c a t s u n g 要通过坐标来描述其中的投影几何关系，坐标系的定义，将采用 如图4 2 所示的坐标系，角度按逆时针方向依次增大。 y y x 9 酽 1 e 。- 图4 , 2r a y c a s u n g 采用的坐标系 在投影和演染整个场景世界之前，定义如下属性：玩家以第一视角观察建立 的整个游戏场景，玩家具有高度、视角( f o v ) 和位置等属性。投影平面有尺寸大 小属性如宽度w 和高度h 。如图4 3 所示。在场景中的玩家能够看到他前面的所 有东西，所以必须定义一个视域( f o v ) 。f o v 决定了玩家能看到的场景世界的范 围。大部分游戏使用6 0 度、9 0 度的视角或者更大。图4 4 展示了b r e w 平台上 实现的r a y - c a s u n g 技术，图中显示的根据第三章中建立的场景模型渲染出来的墙 壁，天花板与地板的效果。 攘拳费苗餮荛 线 一 图4 3 玩家视域的定义 正是场景几何条件的限制，使得r a y c a s t i n g 技术可以快速的工作，与光线跟 踪算法不同，它不为屏幕上的每个像素跟踪一条光线，而是为屏幕上的每一垂直 列跟踪一条光线，视域( f o v ) 的最左端将被投影到屏幕的最左端起始列，视域的 最右端将被投影到屏幕的最右边，如图4 5 所示，因为墙壁与地面天花板的角度 都是9 0 度，并且玩家的视线与地面是水平的，墙壁的投影必然是在投影屏幕 浙江大学硕士学位埝文 图4 4 最终投影的结果 上一列列竖直排列的，因此通过跟踪屏幕上的每一列，就可以完成渲染的过程， 需要跟踪的光线数目跟屏幕的宽度相等，而光线跟踪算法( r a y - t r a d n 曲则需要跟踪 w h 条光线才能完成渲染的过程，显然r a y - c a s t i n g 运算量远远的小于光线跟踪 算法。 图4 5 从左到右跟踪与屏幕每一列相对应的光线 使用r a y - c a s t i n g 渲染这样的场景只需要从左到右跟踪w 条光线。基本的算法 步骤如下： 步骤1 ：根据玩家朝向角度，减去4 5 度( f o v 的一半) ； 步骤2 ：按照步骤1 中的角度从玩家的位嚣发射一条光线； 步骤3 ：跟踪步骤2 中的光线直到到达墙； 浙江大学硕士学位论文 步骤4 ：记录玩家到墙的距离，和光线的长度，并根据玩家与投影面的几何何关 系计算出实际的墙在屏幕上投影的高度，并在屏幕上演染出这列墙； 步骤5 ：增加一个角度，使得下一条光线对应屏幕上的下一个垂直列，重复 图4 6r a y c a s t i n g 算法演示过程 步骤2 ，3 ，4 ，直到到达屏幕的最后一列。 对于步骤4 中，墙的投影高度关系的确定，如图4 7 ： i b 。 ，轨瓣刚朋p ， ， 撼 、7 4f 0 y 、 ni角“ 图4 7 墙的投影高度关系示意图 这是一个场景俯视图，因为墙体与地面垂直，所以可以用线段a b 来表示墙体， 线段e f 表示投影平面，点。代表玩家的视点，玩家的朝向与发出的光线的夹角 为a ，光线与投影面的交点也就是在屏幕上的投影点为点c ，用h 表示墙的实际 高度，h 表示墙a b 在点a 处在屏幕上投影的高度，玩家到投影平面的距离为 p r o j e c t i o n ，光线的长度也线段o a 的长度为l ，玩家到墙面的距离为d ，从视点 。到墙的垂线与光线的夹角为b ，则由几何关系可知： 鱼：丝：p ro j e c t i o n ：p r o j e c t i o n ) ( c o sb h o a l c o s a d c o s a 浙江大学硕士学位论文 在使用r a y c a s d n g 技术时，纹理映射跟普通的二维纹理映射含义是样的， 就是从纹理空间到景物空间的映射过程。但是，因为场景建模的简化，墙体的形 状比较规则，使得纹理映射的计算过程变得简单。r a y - c a s t i n g 在进行纹理映射时 通常选用一个正方形的位图来作为纹理，纹理的尺寸大小跟一块墙体的实际大小 一致。墙体形成的纹理，将是位图分割成一列一列之后缩放而形成。如图4 8 所 示，手机中红线标识的墙的投影，由上方位图中红线标识的那列缩放形成。 图4 8r a y c a s t i n g 下的纹理映射示意图 使用r a y - c a s t i n g 进行纹理映射时，通常分成了两个步骤：1 通过图47 中的 几何关系，计算出这段墙体的纹理在位图中所对应的列，并取得这列数据；2 对 这段纹理进行缩放，投影到屏幕上。通过一定的优化，这个过程跟2 d 三角形纹 理映射双线形插值相比，性能上有很大的提高，减少运算量。 当地板与天花板要进行纹理映射或者使用阴影时，同样使用r a y c a s t i n g 的技 术，如图4 9 ，将有如下步骤：从墙在屏幕上投影的底端开始， 步骤1 ：从这个像素点发射条光线到玩家的眼睛； 步骤2 ：延长这条光线直到它与地板相交、交点就是地板纹理上的颜色值点； 浙扛大学硕士学位论文 步骤3 ：得到纹理上该点的颜色值，将它渲染到屏幕上。 步骤4 ：将屏幕上的投影位置下移一个像素，重复步骤1 - 3 ，直到到达屏幕的底 端。 图4 9 地板投影示意图 地板投影几何关系示意图如4 _ 1 0 所示：点0 代表玩家视点的位置，点p 代表玩 家的脚底位置，b 代表地板上需要投影的点，c 代表该点的投影，线段o d 表示视 点。到c 的垂直高度，用h 表示，玩家的高度用h 表示，玩家到投影面的距离 为p r o i e c f i o n ，到b 点所在处与投影面平行直线的距离为d ，p b 与玩家朝向的夹 角为a ，则有如f 的关系：h ，= 罢，要确定纹理的颜色值，关键就是要确定b ，口d 的位置，则 p 6 ：c d x h ：p r o j e c t i o n x h ：旦 hh c o s a c o s a 由此可以确定b 的位置，得到颜色值。 图4 1 0 地板投影几何关系示意图 浙江大学硕士学位皓文 天花板的渲染跟地板的原理是一样的，只不过是墙的顶部开始，到屏幕的顶 部结束。 4 5 运动的摸拟 3 d 类游戏中，玩家至少要能够有三种运动方式：平移和旋转。平移至少要 能在x 轴和y 轴方向的自由移动，这些只要通过对玩家的坐标位置进行改变就可 以达到。旋转只要改变玩家的朝向就可以达到，如图4 1 1 。 图4 1 1 玩家的朝向旋转一个角度 使用r a y c a s t i n g 还可以模拟仰视与俯视，如图4 1 2 ，只需要将投影平面向上 移动一定的距离，投影的结果近似模拟了仰视，对于俯视只需要将投影平面n t 移动一定的距离。 图4 1 2 模拟仰视 在第三章介绍的场景模型中，使用了b s p 进行消隐，排序，使用了包围盒 与p v s 进行剔除，然后将所有可能见到的墙壁都传送到底层的3 d 渲染流水线。 在这里将使用r a y c a s t i n g 的技术进行渲染。通过以上的分析可知，底层的渲染可 以用r a y - c a s t i n g 来一步完成，第三章的3 d 流水线可以表示成如图4 , 1 3 所示：在 r a y c a s t i n g 的投影过程中，可以完成相机变换、裁剪、纹理映射和光栅化所有的 i 作。 浙江大学