软件实现三维地图引擎的研究

软件实现三维地图引擎的研究
2010年12月08日
　　写在前面：
　　这篇东西，本来写下来是想去投出版社的。结果打听下来，这还要一笔不大不小的花费，除了审稿费，还有版面费，少的几百，多的上千。艾，写的也不咋地，先放在这里好了。等哪天手头宽裕了再说吧（顺便说一下现在的出版社可真是向钱看啊）。
　　1，    引言：
　　当前在许多导航类产品中地图引擎的使用已经很多见了，特别是随着近些年硬件技术的发展，加上许多三维的图形绘图软硬件库的支持，使得三维地图引擎的使用也变得比较常见了。可以说一款好的三维地图引擎对于整个产品来说是显得相当重要的。
　　针对于应用层的地图图形软件开发使用的比较普遍的三维图形库有OpenGL、Direct3D等。这些图形库都是针对于三维图形绘制特别优化的，包括对一些关键算法和特定绘图硬件设备的支持。它们提供了一些灵活的接口调用而将具体的实现方式完全的封装了起来。这样为开发人员在使用时提供了相当的便利。但也使得开发人员不清楚图形库的具体实现方式，只专注于应用的实现。
　　本文的目的是想通过介绍纯软件方式实现的三维地图引擎，使得人们了解三维地图引擎的基本结构和流程，内部的实现方式，从而能够更好的掌握三维地图引擎开发的原理和本质。
　　2，    三维引擎简介：
　　通常按用途划分三维引擎基本上可以分为：太空引擎、地形引擎、FPS室内引擎、光线投射和体素引擎、混合引擎。
　　2.1、太空引擎：
　　该引擎在三维引擎中不是那么复杂。在大多数情况下，三维太空游戏是基于物体的，这意味着所有的实体都是物体，在渲染之前，有很多物体已经从流水线中剔除；然后在渲染期间，使用简单的画家算法或Z缓存对组成每个物体的多边形进行排序，然后将光照、动画等通过常规方式处理。
　　2.2、地形引擎：
　　比太空引擎复杂点的是地形引擎。当然，地形引擎中需要处理的不光是地形，还有处于地形中的物体，包括复杂的动画和地形跟踪算法。然而，地形引擎的主要问题是，如何表示世界数据库，它可是非常庞大的。
　　例如，假设要创建一个大小为100000*100000单位的多边形网格世界，其中每个多边形的大小为200*200单位。这意味着该多边形网格包含大约250000（（100000/200）*（100000/200））个多边形。
　　2.3、FPS室内引擎：
　　FPS的全称是第一人称射击，这种引擎比较棘手。首先、玩家大部分时间都在室内，这就要求清晰的细节和近距离；其次，FPS世界在日益增大，多边形数据库也将随之增大，这意味着不能简单的将整个世界传递给三维流水线，而必须使用空间划分技术将世界区分，以最大限度的减少需要考虑的多边形。
　　2.4、光线投射和体素引擎：
　　原则来说，多边形的引擎基本上都是基于光线投射和体素的。光线投射是一种被用于很多三维FPS游戏中的技术，这些游戏是基于向前光线跟踪的，即从玩家的视点投射一条光线，穿过视平面，直到遇到物体。这种技术可以非常快的生成三维场景。
　　2.5、混合引擎：
　　该种引擎被设计成可以同时模拟太空、陆地和FPS。它的意义在于，很多时候你可能想创建一个有多种环境的世界，这样你不得不使用多个不同类型的引擎，以便根据要完成的任务使用合适的引擎，而不是使用一个引擎来完成所有的任务。
　　3，    三维地图引擎的基本构架：
　　3.1、三维坐标系的问题：
　　在我们了解三维地图引擎构架之前，先了解一下三维坐标系的问题。在三维的世界中有着很多不同的坐标系，每种坐标系表达的意义都是不同的，而他们之间又有着一些特定的转换关系。主要的坐标类型有以下几种：
　　A,模型坐标（局部坐标）
　　B,世界坐标
　　C,相机坐标
　　D,透视坐标
　　E,屏幕坐标
　　模型坐标，也称局部坐标。是表示在创建物体时物体本身所处的坐标系坐标。
　　世界坐标表示的是虚拟空间中的实际位置，物体将在虚拟空间中移动和被变换。
　　当我们的实现处于某一个位置观察物体时，则需要定义相机坐标系，同时将世界坐标转成相机坐标。
　　将三维空间中的坐标通过透视变换映射到平面坐标系上的坐标称之为透视坐标。这种坐标的变换称为透视变换。
　　将通过投影变换得到的一系列的点根据屏幕的尺寸和相关参数显示在屏幕上，这便是屏幕坐标。
　　以上各个坐标系之间存在着相互转换的关系，正常情况下绘制一个三维物体需要经过模型坐标，到世界坐标，到相机坐标，到透视坐标，到屏幕坐标的变换。
　　图1 包含光照处理的坐标转换流水线
　　3.2、渲染三维世界：
　　了解了以上的一些坐标概念，我们便可以进一步去了解一下三维渲染的世界，可以从线框的绘制模式转变为填充的绘制模式。三维渲染主要包括以下三部分：
　　光照模型
　　纹理映射技术
　　三维裁剪技术
　　3.2.1、光照模型：
　　所谓光照模型，是根据光学物理的有关定律计算画面上景物表面各点投影到观察者眼中的光亮度和色彩组成的公式。
　　一个好的光照模型应该满足以下要求：
　　（1）能产生较好的立体视觉效果；
　　（2）在理论上具有一定的合理性或严密性；
　　（3）较小的计算量，以保证较快的绘制速度。
　　对于自然景物的地形表面，光照模型可考虑以下几项影响：
　　（1）光源的位置；
　　（2）光源的强度；
　　（3）视点的位置；
　　（4）地面的漫反射光；
　　（5）地面对光的反射和吸收特性。
　　按照光源的种类我们可以分为以下几种：
　　（1）定向光源；
　　（2）点光源；
　　（3）聚光源。
　　按照光的传播路径可以分为以下几种： （1）环境光；
　　（2）散射光；
　　（3）镜面反射光。
　　3.2.2、纹理映射技术：
　　纹理映射技术的使用是为了让三维地形图更有真实感。这是一个将纹理空间中的纹理像素映射到屏幕空间中的像素的过程。
　　如果对于多边形来说纹理太大或太小，那么纹理需要被过滤以匹配空间。有两种过滤方式：放大和缩小。放大过滤器将纹理放大，缩小过滤器将纹理缩小。纹理放大通常很简单，会获得一张模糊的图像，而纹理缩小比较复杂，不正确的缩小会导致锯齿。
　　图2 像素级别的mipmap
　　3.2.3、三维裁剪技术：
　　在三维图形系统中，裁剪是相当重要的主题，如果没有对集合体进行正确的裁剪，不但无法正确的显示，还有可能导致一系列诸如内存崩溃、除零异常等等问题。剪裁的目的就是把落在用户定义的窗口外的部分图形裁减掉，从而为图像识别和图像处理提供清晰的对象。
　　三维图形剪裁分为两种：一种是图像空间剪裁。在所要渲染的物体都被转换为屏幕坐标后，再使用屏幕空间或视口对其进行裁剪。图像空间剪裁很易于实现。但也意味着对每个物体都要进行剪裁，无论其在或不在窗口内。因而效率不高；另一种是物体空间剪裁。在对几何体进行投影变换前，先用视景体对物体进行剪裁，然后再对其进行坐标变换。根据特定的剪裁区域对构成三维空间的基本几何体进行剪裁。可以根据二维或三维视野的剪裁区域对物体或多边形进行裁剪，然后将裁减后的多边形传给三维流水线的下一个阶段进行处理。大多数三维图形引擎都采用物体空间剪裁的方法。
　　4，    软件实现三维地图引擎：
　　不依赖于三维图形库，使用软件的方式实现三维地图引擎的方式可以让我们更加了解三维地图引擎的内部算法与结构。为了实现软件的三维地图引擎，我们首先需要了解一些关键数据结构的定义，其次会介绍一下常用的算法。以下涉及到的数据结构和代码都是用C/C++语言实现的。
　　4.1、软件三维地图引擎的主要数据结构：
　　（1）表示三维点数据的结构：
　　如何表示一个点在三维空间中的相关信息对于之后算法的编写和优化是比较重要的。
　　//这是三维点数据的结构
　　//点数据采用齐次坐标的表示方式。一共有4个变量。分别是x、y、z轴//的坐标和分量w
　　typedef struct VECTOR4D_TYP{
　　Union{//以联合的数据结构表示方便存储和调用
　　float M[4];
　　struct{
　　float x,y,z,w;
　　};
　　}; 
　　} VECTOR4D, POINT4D, *VECTOR4D_PTR, *POINT4D_PTR;
　　//这是带有法线向量的点的数据结构，也是以齐次坐标的方式表示面中的//各个点
　　typedef struct VERTEX4D_TYP{
　　Union{//以联合的数据结构表示方便存储和调用
　　float M[9];
　　struct{
　　float x,y,z,w;// 点数据
　　float nx,ny,nz,nw;// 各个点的法线向量
　　int attr;// 点的属性
　　};
　　}; 
　　} VERTEX4D, *VERTEX4D_PTR;
　　（2）表示物体的结构：
　　在三维世界中，所有的物体都是多边形组成，而多边形最小可以表示为一个三角形。所以我们需要先了解一下三角形的结构，然后再看一下物体的表示结构。
　　//表示一个多边形面的数据结构，用到了我们之前定义的点的结构
　　typedef struct POLY4D_TYP{
　　int state;//状态信息
　　int attr; //多边形的物理属性
　　int color; //绘制多边形的颜色
　　char *texture;//如果使用材质贴图的话，存放材质贴图的数//据指针
　　int mati;//材质贴图的类型
　　VERTEX4D_PTR vlist;//多边形点的数据存放列表
　　float nlength;//多边形的点的数量
　　} POLY4D, *POLY4D_PTR;
　　typedef struct OBJECT4D_TYP{
　　int id; //物体的ID编号，唯一对应的识别表示
　　char name[64]; //物体名
　　int state; //物体所处的状态
　　int attr; //物体的物理属性
　　int mati; //该物体所用材质贴图的索引
　　float *avg_radius; //物体的平均半径，用来做碰撞检测
　　float *max_radius; //物体的最大半径，用来做碰撞检测               VECTOR4D world_pos; //物体在世界坐标中的位置
　　VERTEX4D_PTR vlist_local;//物体的多边形坐标的数据指针
　　VERTEX4D_PTR vlist_trans;//经过坐标转换之后的坐标数据指针
　　VERTEX4D_PTR head_vlist_local;//多边形坐标的头指针
　　VERTEX4D_PTR head_vlist_trans;//转换之后多边形坐标头指针
　　char *texture;//如果物体使用材质贴图，则是材质贴图的指针
　　int num_polys; //物体的多边形数目
　　POLY4D_PTR plist; //多边形的数据指针
　　} OBJECT4D, *OBJECT4D_PTR;
　　（3）表示相机位置的结构：
　　//相机的数据结构
　　typedef struct CAM4D_TYP{
　　int state; //当前相机所处的状态
　　int attr; //当前相机的物理属性
　　VECTOR4D pos;//当前相机所处在的世界坐标中的位置
　　float view_dist;//视线的深度
　　float near_clip_z;//相机视角的近裁剪面
　　float far_clip_z; //相机视角的远裁剪面
　　float viewplane_width;//裁剪面的宽度
　　float viewplane_height;//裁剪面的高度
　　float viewport_width;//视口的宽度
　　float viewport_height;//视口的高度
　　float viewport_center_x;       //视口中心点的x坐标
　　float viewport_center_y;       //视口中心点的y坐标
　　} CAM4D, *CAM4D_PTR;
　　（4）表示光照的数据结构：
　　光照其实有很多种的模型，而在一个光照的数据结构中要尽量做到能包含所有的模型参数。同时一个场景中可能会有多个光源。
　　//光照的数据结构
　　typedef struct LIGHT_TYP{
　　int state;//光照的状态
　　int id;//光照ID号，唯一识别光源的标志
　　int attr;//光源的物理属性
　　int c_ambient;//环境光照系数
　　int c_diffuse;//漫反射光照系数
　　int c_specular;//镜反射光照系数
　　VECTOR4D pos;//光照模型所处世界坐标中的位置
　　VECTOR4D dir;//光照模型在世界坐标中的传输方向
　　float kc, kl, kq;//衰减系数
　　float spot_inner;//聚光源的内射角度
　　float spot_outer;//聚光源的外射角度
　　float pf; //聚光源的功率系数
　　} LIGHT, *LIGHT_PTR;
　　（5）表示渲染材质的结构：
　　//渲染材质的数据结构
　　typedef struct MAT_TYP{
　　int state; //材质的状态
　　int id; //材质的ID号
　　char name[64]; //材质名
　　int attr; //材质的物理属性
　　int color; //使用填充方式的颜色
　　float ka, kd, ks, power; //作用在当前材质上的一些光照系数因子
　　int ra, rd, rs; //当前材质如果有多个光源同时作用时的系数
　　char texture_file[80];//材质贴图的文件名
　　BITMAP_IMAGE texture; //实际的文件内容
　　} MAT, *MAT_PTR;
　　4.2、经典的三维地图引擎的相关算法：
　　三维地图引擎从模型的建立到最后效果的输出需要经过几个大的步骤，包括坐标转换，光照渲染，纹理映射，三维裁剪，空间划分和可见性算法等。下面详细介绍一种比较常见的纹理贴图算法的软件实现。 4.2.1、Mipmapping纹理贴图：
　　我们前面已经简单介绍过了Mipmapping纹理贴图的原理，该算法主要是用于解决走样的问题。
　　为实现Mipmapping,需要创建有纹理组成的mip链，其中每个纹理的大小都为前一个纹理的1/4（沿每条轴缩小一半），最后一个纹理的大小为1*1。另外，这些mip纹理都是使用滤波器（平均滤波器、箱型滤波器、高斯滤波器）生成的。渲染多边形时，根据多边形离视点的距离或多边形被投影后的面积，选择使用合适的mip纹理。这样，将最大限度的减少闪烁和低频走样/波形图案。接下来使用伪代码的形式分析源码。
　　int Generate_Mipmaps(BITMAP_IMAGE_PTR source,//原始纹理     BITMAP_IMAGE_PTR *mipmaps, //指向mip纹理数
　　//组的指针
　　float gamma)// gamma 修正因子
　　{
　　// 这个函数创建一个mip纹理链
　　// 调用该函数时，mipmap指向原始纹理
　　// 该函数退出时，mipmap指向一个指针数组，其中包含指向各个mip级// 纹理的指针
　　// 另外，该函数返回mip等级数，如果发生错误，则返回-1
　　// 最后一个参数gamma用于提高mip纹理的亮度，因为平均滤波器会降// 低亮度
　　// 该参数大于1.0时，将提高亮度；小于1.0时将降低亮度；为1.0时没// 有影响
　　//计算mip等级数
　　//为指针分配内存
　　//将元素0指向原始纹理
　　//设置宽度和高度（它们相同）
　　//使用平均滤波器生成各个mip纹理
　　for (int mip_level = 1; mip_level width; x++)
　　{
　　for (int y = 0; y height; y++)
　　{
　　//需要计算4个纹素的平均值，这些纹素在前一个mip纹理//中的位置如下：
　　// (x*2, y*2), (x*2+1, y*2), (x*2,y*2+1), (x*2+1,y*2+1)
　　//然后将计算结果写入到当前mip纹理的(x,y)处
　　//提取每个纹素的R,G,B值
　　//计算平均值，并考虑gamma参数
　　//根据5.6.5格式，对R,G,B值进行截取
　　//写入数据
　　} // end for y
　　} // end for x
　　} // end for mip_level
　　//让mipmaps指向指针数组
　　*mipmaps = (BITMAP_IMAGE_PTR)tmipmaps;
　　//成功返回
　　return(num_mip_levels);
　　} // end Generate_Mipmaps
　　5，    结语：
　　随着三维地图引擎技术在国内的迅猛发展，地图引擎市场逐渐成为一个新兴的增值亮点，掌握引擎的核心开发技术将是广大开发人员的必修课，希望本文对三维地图引擎系统的软件设计构架和对应算法的研究能够起到一定的抛砖引玉的作用。