栅格环境下基站覆盖范围的计算与仿真.docx

分类号 密级 U D C 编号 10486 武汉大学硕士学位论文栅格环境下基站覆盖范围的计算与仿真Thesis for Master DegreeCaculation and simulationof base station coverage areabased on Grid-DataApril，2008郑 重 声 明本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄袭、造假等违反学术道德、学术规范和侵权行为，本人愿意承担由此而产生的法律后果和法律责任，特此郑重声明。学位论文作者（签名）： 摘要传统的基站选址方法主要依靠建设人员的实地勘察。这样做不仅费时费力，也难以充分考虑当地复杂的地理状况，只能凭借经验和有限的实地勘察试验来确定站址的选择，通常把站点选在高山或高层建筑上，以期获得较大的覆盖范围。但实际上，这种选址方式有很大的主观性，容易造成覆盖范围不足或重复覆盖形成信号之间的相互干扰等情况。本论文结合栅格数据的特点，研究了如何有效地读取与处理数据的算法，着重研究以下几个方面的内容：1) 由于栅格数据量较大，所以要提出算法来对它的显示和处理进行优化，通过自己管理Frustum解决了栅格数据的高效显示，为场景中的每个对象定义一个包围盒和一个包围球并为视场Frustum建立一个包围盒一个包围球一个包围锥的办法，可以非常高效地剔除与加载对象，另外由于采用了四叉树化分场景的，更进一步提高了效率。2) GPU编程对栅格数据的计算与显示。GPU编程把对数据的预处理与显示结合起来，以加快数据的处理时间。3) 基站覆盖范围的计算与仿真。通过分析栅格数据对信号的传播进行计算。利用三维模型计算仿真基站覆盖范围，可以形象直观的辅助我们为基站选址科学地做出决策。科学的基站选址能够有效的扩大基站无线覆盖范围，更好地做到无缝连接，吸收更多的用户和话务量，同时能降低建设成本，提高收益，无论在技术实现上还是在市场运作上都有很大的意义。关键词：基站覆盖范围Frustum优化GPU三维模型ABSTRACTThe traditional way to Basestation location depends on the fieldwork of the constructors, which is not only to take time and a lot of trouble, but also difficult to consider the complicated local geographical conditions adequately. In this way, people only resort the experience and limited fieldwork experiments to decide the positions of the stations and usually choose the high mountains or buildings as the station spots in order to provide larger coverage area. In fact, people have great subjectivity in such a way. Finally, it makes the coverage area less enough or intersectional easily, causing the jam among the signals and so on.In combine with the characteristics of raster data this paper studied the algorithms on how to read and process the data effectively. Which focus on the following aspects:1) Because we have to deal with a abundant of raster data in the normal usage, we must make our algorithm to optimize the display and processing. To define a bounding box a bounding sphere for each object and define a bounding box a bounding sphere and a bounding cone for the frustum, we can solve the displaying of the raster data efficiently. And the using of quad-tree of the scene approach can further enhance efficiency.2) The calculation and display of raster with GPU. GPU can do preprocessing and display of data together.3) Base station coverage calculation and simulation. By analyzing the raster data to do the calculation of the spread of the signal.Use 3D Model combining with the Hertzian Waves Transmit Wastage Forecast Model to emulate the coverage areas of the basestations to choose the positions, which can help us to choose the positions visually and make decisions scientifically. Choosing the positions scientifically can enlarge the coverage area, link seamlessly and attract more customers to improve the amount of the phone call as well as reduce the cost and improve the benefit, which has great meanings both in technique reality and market operation. Keywords: Basestation, Coverage Area, Frustum Optimize, GPU, 3D Model目录摘要IABSTRACTIII目录V第1章绪论11.1选题意义11.2国内外研究现状21.3研究目标与章节安排31.3.1 研究目标31.3.2 技术路线31.3.3 章节安排4第2章 栅格数据与GPU编程简介52.1 栅格数据的特点52.1.1 栅格数据结构52.1.2 矢量与栅格数据的比较62.1.3 空间栅格数据的分层存储72.2 栅格数据的处理72.2.1 点云数据的分层处理算法72.2.2 点云数据的构网82.2.3栅格数据的优化处理82.3 GPU编程82.3.1 GPU的概念82.3.2 可编程管线92.3.3 HLSL与GLSL92.3.4 Cg编程语言102.6 小结11第3章 栅格数据的处理的算法优化133.1 平截头体优化处理133.1.1 Frusum定义133.1.2 基本算法1153.1.3 优化1183.1.4 基本算法2193.1.5 优化2223.1.6 反求Frustum的6个平面253.2 LOD优化处理283.2.1 Lod的概念283.2.2 求塌陷边293.2 GPU编程优化303.2.1 CG编程的一般步骤303.2.1 绘制地形313.3 小结33第4章 栅格环境下基站范围的计算354.1 基站覆盖范围的一般计算方法354.2计算栅格环境下的覆盖范围394.2.1 栅格数据的存储与读取404.2.2 算法优化处理414.2.3 凸包算法424.3 小结43第5章仿真及结果455.1 图形软件接口455.1.1 OpenGL455.2 软件架构465.2.1 软件开发环境465.2.2 软件开发方法465.2.3 基本数据结构465.3 创建三维场景475.3.1 创建三维地形475.3.2 基站覆盖范围的计算485.3.3 仿真结果49第6章 总结与展望53参考文献55致谢59第1章绪论1.1选题意义与其它现代技术一样，移动通信技术的发展也呈现加快趋势。为了达到更高比特率数据业务和更好的频谱利用率，目前移动通信正在向第三代(3G)移动通信系统过渡。第三代移动通信可以实现全球统一频段，统一标准，无缝覆盖；实现高服务质量，高保密性能，高频谱效率；可提供一系列的新业务，如多媒体通信、高速商务处理、遥测业务以及用户通过移动通信网接入因特网或企业网等业务。可以预见在不远的将来，全世界将会有和有线电话一样多的移动通信用户。与此同时，美国正在研究第四代移动通信技术（即4G），其研究的目标是提高移动电话访问互联网的速率。据国家信息产业部统计，2007年，中国手机用户已有54728.6万户，全国手机普及率达到每百人38.3部。手机短信发送量为2790.2亿条，较上年同期增长37.5%1 。而全球手机用户数量已达到26亿，预计2010年将增至40亿，其中中国和印度将是主要增长地区。手机在人们的日常工作生活中扮演着十分重要的角色。当前，在我国的一些偏远山区和许多自然环境恶劣的地区，还没有能够实现通信信号的覆盖，而当地的人民群众十分渴望进行移动通信。同时，在人们使用手机的过程中，经常会碰到信号质量不好，干扰强烈等问题，严重影响了人们的通话质量。这就对移动运营商提出了更高的要求，必须提供足够的信号覆盖范围，并保证通话质量，既基站选址问题。移动通信信号由发射机（基站）提供。基站覆盖范围主要受当地地形（山区）和建筑（城区）的影响，如何选择一个尽量少受阻挡，能够保证话务质量的站址，是工程人员十分关心的问题。实际建设过程中，往往需要建设人员实地勘察。这样做不仅费时费力，也很难找到科学的站址。目前，在工程人员当中还没有形成一个比较科学的基站选址方法。一般工程人员进行无线基站选址时，难以充分考虑当地复杂的地理状况，只能凭借经验和有限的实地勘察试验来确定站址的选择，通常把站点选在高山或高层建筑上，以期获得较大的覆盖范围。但实际上，这种选址方式有很大的主观性，容易造成覆盖范围不足或重复覆盖形成信号之间的相互干扰等情况。目前三维城市模型中实现的软件很少，较为成熟的有三维日照分析软件。随着虚拟现实技术和数码城市GIS的发展，有必要建立这样一个系统进行基站选址。利用三维地理模型结合电磁波传播损耗预测模型仿真基站覆盖范围，以之来辅助基站选址，可以形象直观的帮助我们进行基站选址，科学的做出决策。科学的基站选址能够有效的扩大基站无线覆盖范围，更好地做到无缝连接，吸收更多的用户和话务量，同时能降低建设成本，提高收益，无论在技术实现上还是在市场运作上都有很大的意义。由于矢量需要人工测量采集，所以周期长时效性差，且建模复杂，所以非常昂贵不易获取，而栅格数据正好克服了这些缺点，栅格数据的获取非常方便。现在城市的发展非常快变化非常大，传统的非常耗时的矢量数据采集显然不能反映实际，所以本论文选取了在栅格数据为平台来研究基站的覆盖。但是受制于栅格数据本身的特点，大规模数据实时处理一直是目前虚拟现实方面的瓶颈，如何快速高效地读取计算和渲染这些数据是使用栅格数据所必需面对的难题，所以要求我们改进算法以达到实用的要求。1.2国内外研究现状在法国国家信息与自动化研究所，运用栅格影像技术人们可以自由在虚拟和现实之间转换，能够非常自由地对真实物体进行三维重建和动作捕捉。随着计算机技术的进一步发展，虚拟现实与我们的生活将日益密切，而栅格影像技术也将为虚拟现实艺术揭开新的篇章。目前栅格数据的获取技术已经非常成熟，特别是机载雷达能够实时获取地形表面三维空间信息和影像。地面三维激光影像扫描仪经过近几年也在快速地发展，在测程范围、测距精度、测量速度、测量采样密度、激光安全等方面取得较大的进步，测量数据处理软件功能方面也在不断完善中。欧美和日本对于电磁波传播损耗预测模型的研究进行的较早，也相对比较深入。根据传播损耗预测方法的性质，可以将已有的传播损耗预测方法分为确定性模型3-7和统计模型两类35-38。确定性的无线传播预测是一种极其复杂的电磁学问题，电磁覆盖的数学复杂度使它不可能预测高度精确的无线传播。统计预测模型由于其简单易行而广泛运用于移动通信网络规划和优化，但是其运用时需要移动网设计者对当地传播环境做主观判定，并且计算方法和修正量均有限定范围，无法根据具体的传播环境来确定预测参数，这就必然会产生预测误差。为了能够尽量减少误差，国内外学者提出了很多改进的模型。目前国内已经开展了电磁波传播场强预测相关方面的研究11-14，基站覆盖范围仿真研究15和基站选址软件的研发16-17。其中广东移动通信公司茂名分公司与北京超图地理信息技术有限公司合作，采用超图公司SuperMap GIS技术，基于组件式地理信息系统平台SuperMap Objects成功研发了无线基站选址软件。但是该软件只能应用于山区、丘陵、农村等不考虑建筑信息的地区，不能应用于城市（特别是建筑物密集的大型城市）内基站选址，并且其所使用的文件数据都有一定的格式限制且只能在数据量小的情况下进行测试，所以在实际中对数据和具体地形有一定的限制。国外在城市规划设计和辅助软件开发方面已经形成一个成熟的体系。在三维建模方面有3DS MAX、MAYA软件；在虚拟仿真上有Multigen Creator/Vega软件；在地理数据查询和空间分析统计方面GIS工具软件就有ArcGIS、MAPINFO软件，而且许多国外的规划设计工作室都拥有各自独立开发的规划辅助软件。另外，国外的许多开发小组提供了一些开源的通用型三维环境建模软件，如 VTP(Visual Terrain Project)、OGRE(Object-Oriented Graphics Rendering Engine) 、Terrain View等，非常方便我们进行二次开发。1.3研究目标与章节安排1.3.1 研究目标从上述的国内外研究现状可以看出，尽管无线通讯、虚拟现实这些技术在国内外有很大发展，但是，将他们结合起来，具体应用于实际预测计算方面的例子很少。而本论文的目标就是将这二者结合起来，使用计算机和虚拟现实技术来进行基站的覆盖范围的计算与预测。栅格数据是一种应用非常广泛的数据，由于现代的机载激光雷达技术非常成熟，相比于需要人工测量采集的矢量数据其具有获取方便、成本低、时效性强、管理方便等特点，因为利用栅格数据来进行基站覆盖范围的计算是一个比较合理的选择。尽管栅格数据的精度没有矢量数据高，计算的结果有一定的误差，但是由于计算的基站覆盖范围是一个相对比较宏观的概念，所以其误差即使是在1米之内也不会影响效果，因此栅格数据能够满足需要而且只要方法得当其误差也是在允许范围之内的。栅格数据量很大，如何快速高效地处理和渲染海量数据是其中非常关键的环节，它将会直接影响到程序的实效性和实用性。因此本文将会重点研究如何更加快速实时地处理栅格数据，并依据既存的使用比较广泛的信号损耗模型来对基站的覆盖范围进行预算和仿真。1.3.2 技术路线本文着重研究如何在三维场景下实时地处理栅格数据，并以此来计算基站的覆盖范围。本文通过Frustum和LOD优化，可以迅速有效地渲染三维场景。基本满足了实际的需要。而GPU编程优化是为了将与图形有关的处理交给GPU，这样可以减少CPU的工作量，使CPU能够更专注地进行其它计算处理，而且还能充分利用高端显卡的新特性，有效地改善了渲染效果和渲染质量，从而提高了算法的效率。本文主要完成以下几个方面的工作：1) 海量栅格数据的有效管理和快速渲染。由于栅格数据量较大，所以要提出相关策略和算法来实现海量栅格数据的有效管理和快速渲染。2) GPU编程对栅格数据的计算与显示。GPU编程把对数据的预处理与显示结合起来。以加快数据的处理时间。3) 基站覆盖范围的计算与仿真。通过分析栅格数据对信号的传播进行计算。1.3.3 章节安排全文的主要内容为：第一章绪论，简单本论文研究的意义、背景和研究计划。第二章详细介绍了栅格数据的特点及GPU编程。第三章重点讨论了Frustum和LOD优化方面知识，以及本论文中具体采取方法与具体技巧。GPU编程概念和思路。第四章介绍了如何通过GPU编程来进行场景渲染与基站覆盖范围的计算。第五章介绍了如何使用软件构建三维地形模型，以及基于三维地形模型的基站覆盖范围仿真。第六章结论与展望，针对基于三维环境下的基站选址的应用和发展趋势作了简要的阐述。 第2章 栅格数据与GPU编程简介2.1 栅格数据的特点2.1.1 栅格数据结构栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。栅格结构的显著特点：属性明显，定位隐含，即数据直接记录属性的指针或数据本身，而所在位置则根据行列号转换为相应的坐标。一、栅格数据的编码方法：栅格数据的取得，可在专题地图上均匀地划分网格(相当于将一透明方格纸覆盖在地图上)，每一单位格子覆盖部分的属性数据便成为图中各点的值，最后形成栅格数字地图文件。也可以用数字化仪跟踪，得到矢量结构数据后再转换为网格结构，或用扫描数字化方法，逐步扫描专题地图，将扫描数据重采样和再编码得到栅格数据文件。栅格数据的获取需尽可能保持原图或原始数据的精度。在决定代码时尽可能保持地表的真实性，保证最大的信息容量。图形用网格覆盖后，常常会在同一格子下对应了几种不同的属性值，而每一个单元只能取一个值，在这种情况下，有不同的取值方法： 1. 中心点法：用处于栅格中心处的地物类型或现象特性决定栅格代码。 2. 面积占优法：以占栅格最大的地物类型或现象特征决定栅格代码。 3. 长度占优法：当覆盖的格网过中心部位时，横线占据该格中的大部分长度的属性值定为该栅格的代码。 4. 重要性法：根据栅格内不同地物的重要性，选取最主要的地物类型决定相应的栅格单元代码。对于特别重要的地理实体，其所在的区域尽管面积很小或不在中心，也采取保留的原则，台稀有金属矿区域等。 为了逼近原始数据精度，除了采用上述几种取值方法外，还可以采用缩小单个栅格单元的面积，增加栅格单元总数的方法，这样行列数也相应增加，每个栅格单元可代表更细小的地物类型，然而增加栅格个数、提高精度的同时也带来了一个严重的问题，那就是数据量的大幅度增加，数据冗余严重。为了解决这一矛盾，现已发展了一系列栅格数据压缩编码方法，如键码、游程长度编码、块码和四分树编码等。 直接栅格编码，就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码；压缩编码，包括1. 链码（弗里曼链码）比较适合存储图形数据；2. 游程长度编码通过记录行或列上相邻若干属性相同点的代码来实现；3. 块码是有成长度编码扩展到二维的情况，采用方形区域为记录单元；四叉树编码是最有效的栅格数据压缩编码方法之一，还能提高图形操作效率，具有可变的分辨率。二、栅格数据的优缺点：优点为数据结构简单，便于空间分析和地表模拟，现实性较强；在栅格数据结构中，点实体表示为一个像元；线实体则表示为在一定方向上连接成串的相邻像元集合；面实体由聚集在一起的相邻像元结合表示。这种数据结构很适合计算机处理，因为行列像元阵列非常容易存储、维护和显示。缺点为数据量大，投影转换比较复杂。用栅格数据表示的地表是不连续的，是量化和近似离散的数据，是地表一定面积内(像元地面分辨率范围内)地理数据的近似性，如平均值、主成分值或按某种规则在像元内提取的值等；另一方面，栅格数据的比例尺就是栅格大小与地表相应单元大小之比。像元大小相对于所表示的面积较大时，对长度、面积等的度量有较大影响，这种影响还与计算长度、面积的方法有关。2.1.2 矢量与栅格数据的比较 一、矢量数据结构简介矢量数据结构是通过记录坐标的方式尽可能精确地表示点、线和多边形等地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义。矢量结构的显著特点：定位明显，属性隐含。其中，矢量数据的有如下优缺点：优点为数据结构紧凑、冗余度低，有利于网络和检索分析，图形显示质量好、精度高；缺点为数据结构复杂，多边形叠加分析比较困难。二、两者比较：栅格数据操作总的来说容易实现，矢量数据操作则比较复杂；栅格结构是矢量结构在某种程度上的一种近似，对于同一地物达到于矢量数据相同的精度需要更大量的数据；在坐标位置搜索、计算多边形形状面积等方面栅格结构更为有效，而且易于与遥感相结合，易于信息共享；矢量结构对于拓扑关系的搜索则更为高效，网络信息只有用矢量才能完全描述，而且精度较高。对于地理信息系统软件来说，两者共存，各自发挥优势是十分有效的。三、为什么选择栅格数据：?该为：数据类型的选用栅格数据的选取由以上的比较可知矢量数据与栅格数据各有优缺点，因而它的的应用范围也会有一定的差异，矢量数据作为一种精度高，表现复杂的数据主要用于三维建模软件等的存储格式。而栅格数据由于是点云或者是构好？的风格的三角网，因为数据量大，其几何信息的获得也需要通过专门的算法处理来提取，加之海量数据的处理算法比较耗时，所以在实时渲染方面也有一定的难题。从基站覆盖范围的预测和计算方面来讲，基站覆盖范围的计算主要是用以模拟和反映真实的场景并为基站地点的选择的部署以及以后的城市规划作决策和分析，所以应该使用实际的数据，传统的矢量数据由于其主要是人工野外测量，所以其获取很耗人力，而且人工测量的速度较慢，有时跟不上城市的发展变化。但是只要通过选取合适的改进算法来优化栅格数据的处理工作，就可以避免或减少海量数据的计算和分析处理的性能瓶颈。本论文后面的章节将会通过提出相应的改进算法来解决海量数据的处理问题，并以基站的覆盖范围为例使得栅格数据能够用以实时的分析和处理，为后续的分析决策打下基础。2.1.3 空间栅格数据的分层存储由于栅格数据一般非常庞大，所以对其的存储与管理办法一般是按照对精度的要求不同对其分层存储。首先通过对点云数据进行构网形成基本的原始栅格数据。再按照不同的精度级别要求使用LOD技术对其进行减化，再将这几种不同级别的栅格数据分别存储。然后在程序的运行过程中通过视点与对象的不同距离程序会读取相应精度的数据。2.2 栅格数据的处理2.2.1 点云数据的分层处理算法因为点云只要绘制成点，没有遮挡，所以无法使用三角形简化算法。Carsten等人在QSplat30基础上提出了顺序点树模型，它根据绘制过程中点片误差大小，由粗到细构建了顺序树状结构，并使用紧凑的文件布置方式，提高了绘制的效率。然而，Carsten等解决的仍旧是面状物体的绘制，并且，其用来控制显示精度的普通树结构并不适合对点云数据进行裁切处理。四叉树格式规整，可以快速地对树上点云数据进行裁切。其中有一种方法是借鉴QSplat中紧凑组织数据的做法，采用多精度排序四叉树存储模型，使得每一层上的点云分布基本均匀，同时给出了一个大数据量下快速构建均匀分布四叉树的方法，来实现实时渲染大量LIDAR点云数据，通过绘制时数据量的自适应控制达到实时效果31。2.2.2 点云数据的构网点云三角化算法是逆向工程技术中的一个研究热点。三角网格模型是逆向工程中逆向策略中的建模基础。国际上，许多学者已经提出了大量的三角化算法，这些方法大致可以分为基于Delaunay三角化的算法、基于有符号距离函数的算法、基于区域增长的算法等三类。2.2.3栅格数据的优化处理构好网的数据一般通过直接渲染三角形的方式来显示它们，这在渲染小量数据时是一个不错的选择，但是由于其本身的固有特点，栅格数据一般都会很大，而且由于本文使用的栅格数据是由点云数据构网形成的，所以不可避免地，其数据量是一个非常庞大的数字，所以传统的方法在这里会遇到性能的？瓶颈，实际的情况是这些数据是如此之大，以致于如果不进行某些处理的话，程序很难运行起来，所以设计出一套算法来优化它是一个必不可少的步骤。因为本论文接下来的两章将会专门来讨论如何优化和改善显示和处理栅格数据，以达到实用的目的。2.3 GPU编程2.3.1 GPU的概念GPU相当于CPU在电脑中的作用，它决定了该显卡的档次和大部分性能，同时也是2D显示卡和3D显示卡的区别依据。2D显示芯片在处理3D图像和特效时主要依赖CPU的处理能力，称为“软加速”。3D显示芯片是将三维图像和特效处理功能集中在显示芯片内，也即所谓的“硬件加速”功能。 NVIDIA公司在1999年发布GeForce 256图形处理芯片时首先提出GPU的概念。GPU使显卡减少了对CPU的依赖，并进行部分原本CPU的工作，尤其是在3D图形处理时。GPU所采用的核心技术有硬件T&L、立方环境材质贴图和顶点混合、纹理压缩和凹凸映射贴图、双重纹理四像素256位渲染引擎等，而硬件T&L技术可以说是GPU的标志。2001年，NIVIDA公司的GeForce 3首先引入了可编程的顶点着色器（Vertex Shader）单元。紧接着在2002年，可编程的像素着色器(Pixel Shader)单元也加入了GPU。在绘制时，GPU首先接收CPU以三角形顶点形式的发送的几何数据。然后由可编程的顶点着色器单元进行处理，完成几何变换与顶点属性计算等功能。接着，这些三维空间的三角形由一个固定功能的光栅生成器转换为二维屏幕上的像素。每个像素的最终颜色值都通过运行在像素着色器上的小程序运算而得。2007年，NVIDIA率先引入了Tesla通用GPU计算架构，最终目的是将CPU和GPU合二为一。另一方面，AMD计划于2009年推出内建GPU核心的Fusion处理器，而Intel整合GPU的Nehalem处理器将与之正面交火，届时，处理器将全面进入整合GPU时代。2.3.2 可编程管线传统的固定功能管线（fixed-function pipeline）本质上是一系列控制特定类型的数据如何渲染的规则和策略方式。明显地，随着GPU的快速发展，许多原先只能通过软件编程在CPU上处理的高级功能，现在都可以直接交给GPU，但是每当GPU增加一条新的功能后，我们都需要我们的图形库（Directx、OpenGL）为之增加新的API，这样图形库就会急速膨胀，对程序员更是一种负担。可编程管线（Programmable Pipeline）提供了一条解决方案，如果说以前的固定功能管线编程就像汇编语言一样的话，那么可编程管线就像是高级语言，程序员可以抛开硬件的底层考虑而专注于实际应用的开发。可编程功能管线也就是对着色器(Shader)进行编程，着色器负责处理和显示最终结果(shading)。用于可编程功能管线的高阶语言有：DirectX中的HLSL、OpenGL中的GLSL、NVIDIA公司推出的Cg。DirectX8支持Shader 1.X，Direct9和Direct3D 10支持shader 2.X和3.X。2.3.3 HLSL与GLSLHLSL是在directX中使用的高阶着色语言（High Level Shading Language，HLSL），可以使用它来为Direct3D管线编写C网格的应用程序。微软率先在DirectX8中引入HLSL来进行可编程3D管线编写，在DirectX8中，既有传统的汇编式的固定功能管线编程的指令，也有HLSL式的可编程管线指令，而在最新版的DirectX10中，则完全是纯粹的可编程功能管线，这意味着传统的固定功能管线的方式将不再支持。借助HLSL程序员非常方便地进行GPU编程开发。GLSL的全称是OpenGL Shading Language，也称作GLslang。OpenGL ARB 建立了OpenGL 着色语言，为GPU的程式设计提供更加直观的方法。最初 OpenGL 1.5是以扩充形式引入，后来OpenGL ARB 在 OpenGL 2.0 核心中正式纳入GLSL。自1992年建立的OpenGL 1.0 起，OpenGL 2.0是第一个OpenGL的重大修改版。使用GLSL有如下好处：Ø 具有跨平台的相容性，包括 Macintosh、Windows 和 Linux 等操作系统。 Ø 所有支援 OpenGL 着色语言的绘图卡，都可以用来编写着色器。 Ø 允许厂商为特定的绘图卡产生最佳化的代码。 这两种语言非常类似，都是绑定在相应的图形接口之上的，但不能混用。2.3.4 Cg编程语言Cg是一种高级编程语言（C for Graphics），可使内容开发商更轻松、快捷地创建具有电影效果的实时图形。Cg是由NVIDIA公司和微软公司（Nasdaq代码： MSFT）密切合作联手开发的，开发人员借助该语言可更抽象地进行工作，无需直接针对图形硬件进行编程。通用、熟悉的C-like语法可迅速为图形平台开发出实时渲染的鲜锐视觉效果，并与微软公司发布的面向DirectX 9.0的高级渲染语言(HLSL)兼容。随着Cg和NVIDIA的Cg编译器的推出，开发人员将可更快地创建、共享和重新利用渲染引擎，这将使他们通过利用业界期待的鲜锐视觉效果和更强的真实感来创建更丰富的内容。Cg已经得到了赢得了业界的广泛支持，包括从游戏开发商到数字内容创建者，对于计算机图形行业而言，Cg是一个重要的里程碑，因为它使实时3D图形编程向电影渲染编程模式迈进了一大步。Cg将大大加快更趋复杂和激动人心的图形功能被采用的速度。Cg对GPU而言将起到C和C+对CPU所起的作用。CG中GPU处理如下22：图 2-1目前，CG的最新版是2.0，它可以支持包括windows、Mac OS X、Linux等一系列桌面操作系统。因为CG是一个跨平台的语言，所以它大大了程序员编写跨平台程序的负担，并且因为它可以在运行期编译执行。所以它又可以利用各种GPU的最新性能，并且能够很容易地嵌入到opengl、direct3d等图形软件接口中。本论文中将会使用CG来进行CPU编程。使用CG编程有以下理由：（1） Cg是跨平台的shader1) 相同的Cg shader源码可以编译成:1 多种商业OpenGL扩展，如：ARB_vertex_program & ARB_fragment_program.)。2 NVIDIA特定的OpenGL 扩展，如：GeForce 8的V_gpu_program4。3 DirectX 9中的汇编shaders，如：Shader Models 1.x, 2.x, and 3.x。4 OpenGL Shading Language (GLSL) 交叉编译。5 DirectX 9 HLSL 交叉编译。6 Sony公司的PlayStation 3中支持的Cg。2) 可用于多种操作系统: Vista, XP, 2000, MacOS X, Linux, Solaris。（2） CG中还具有复杂的CgFX effects系统，它与 Microsoft的DirectX 9中的FX兼容。（3） 具有一些其它的GPU着色语言中没有的特性，比如：对接口和可变数组的支持。2.6 小结本章通过对栅格与矢量数据的比较来说明了栅格数据的特点和选择栅格数据的原因及面临的难点。栅格数据一般比较庞大，所以在实际的使用中必需要运用一般的优化方法来满足实用的要求。本章还介绍了GPU编程的特点方法。GPU编程不但能够充分利用显卡的新特性提高渲染效果，而且还可以利用它来进行物理和数学计算，这样能够大大减轻CPU的工作量，使CPU更加专注于其它方面的操作。本论文中将会采用CG语言来进行GPU编程。第3章 栅格数据的处理的算法优化本章通过讨论栅格数据的渲染处理问题。对于如何提高算法的效率，本章将提出优化算法。通过平截头体优化处理加载场景对象，LOD优化和GPU渲染这些方式能够非常高效地解决栅格数据的处理问题，为后面的计算提出核心的算法。3.1 平截头体优化处理一般的OpenGL或Direct3D程序中，只需定义好一个平截头体（Frustum）就可以了，以后的剔除工作会交给API自己处理，但是，那样必需在渲染之前将所有的待渲染对象都加入到场景中，这对于耗资源的大对象来说是不可取的。本节中将通过数学法则提取出Frustum的六个平面，再将这六个平面与各个对象及其包围盒作比较，如果对象在Frusum之外，则直接不读取，只有对象在Frustum之内或与Frustum相交，我们才把对象读入到CPU或GPU，作下一步处理。这样可以大大提高程序的性能。3.1.1 Frusum定义平截头体（frustum）就是当前相机中所见的世界部分。其形状是一个中心对称的四棱台（如下图）。平截头体的6个面被命名为近平面、远平面、左平面、右平面、上平面、底平面。平截头体剔除就是来判定对象在场景中是否可见这一简单过程。因为它是3D中渲染必须要做一步处理，所以它可以处在渲染管线中对实体的其它处理之前。因为我们可以在对象层迅速地拒绝，就可以直接避免了后续的更加耗时的处理。所以可以在渲染流程的开始处理。这意味着不必把数据送到显卡，只要这个对象被平截头体剔除了，而这当然也带来了非同寻常的渲染速度。如下图，是OpenGL中对平截头体的定义20：图3-1平截头体可以依次将各个对象与Frustum来判断，但是这样的判断是线性级别的。所以为了提高速度，要使用到树形结构，这样可以把剔除处理速度提高到对数级别上。本论文中，我为我的剔除方法层次选择一个四叉树。如果是在空间中可以选择八叉树，但是本程序是基于地形的，所以为了避免算法过于复杂，本论文选择了四叉树，实际上，由于栅格数据具有高程信息，所以四叉树可以完全满足程序的需要。之所以选择一个四叉树还有一个原因是它的结构很容易可视化。一个四叉树实际上一个二维区域，这个区域通过一个树结构来建立，这个树结构的每个结构有四个孩子（如图3-2），在这种情况下，其每个孩子占据它的父结点的一个四方块区域