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

栅格环境下基站覆盖范围的密级计算与仿真UDC编号10486武汉大学硕士学位论文栅格环境下基站覆盖范围的计算与仿真ThesisforMasterDegreeCaculationandsimulationofbasestationcoverageareabasedonGrid-DataApril,2008郑重声明本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄袭、造假等违反学术道德、学术规范与侵权行为，本人愿意承担由此而产生的法律后果与法律责任，特此郑重声明。学位论文作者（签名）：摘要传统的基站选址方法要紧依靠建设人员的实地勘察。这样做不仅费时费力，也难以充分考虑当地复杂的地理状况，只能凭借经验与有限的实地勘察试验来确定站址的选择,通常把站点选在高山或者高层建筑上，以期获得较大的覆盖范围。但实际上，这种选址方式有很大的主观性，容易造成覆盖范围不足或者重复覆盖形成信号之间的相互干扰等情况。本论文结合栅格数据的特点，研究了如何有效地读取与处理数据的算法，着重研究下列几个方面的内容：1）由于栅格数据量较大，因此要提出算法来对它的显示与处理进行优化，通过自己管理Frustum解决了栅格数据的高效显示，为场景中的每个对象定义一个包围盒与一个包围球并为视场FrUSlUm建立一个包围盒一个包围球一个包围锥的办法，能够非常高效地剔除与加载对象，另外由于使用了四叉树化分场景的，更进一步提高了效率。2） GPU编程对栅格数据的计和与显示。GPU编程把对数据的预处理与显示结合起来，以加快数据的处理时间。3）基站覆盖范围的计算与仿真。通过分析栅格数据对信号的传播进行计算。利用三维模型计算仿真基站覆盖范围，能够形象直观的辅助我们为基站选址科学地做出决策。科学的基站选址能够有效的扩大基站无线覆盖范围，更好地做到无缝连接，汲取更多的用户与话务量，同时能降低建设成本，提高收益，不管在技术实现上还是在市场运作上都有很大的意义。关键词：基站覆盖范围FrUStUm优化GPU三维模型ABSTRACTThetraditionalwaytoBasestationlocationdependsonthefieldworkoftheconstructors,whichisnotonlytotaketimeandalotoftrouble,butalsodifficulttoconsiderthecomplicatedlocalgeographicalconditionsadequately.Inthisway,peopleonlyresorttheexperienceandlimitedfieldworkexperimentstodecidethepositionsofthestationsandusuallychoosethehighmountainsorbuildingsasthestationspotsinordertoprovidelargercoveragearea.Infact,peoplehavegreatsubjectivityinsuchaway.Finally,itmakesthecoveragearealessenoughorintersectionaleasily,causingthejamamongthesignalsandsoon.Incombinewiththecharacteristicsofrasterdatathispaperstudiedthealgorithmsonhowtoreadandprocessthedataeffectively.Whichfocusonthefollowingaspects:1) Becausewehavetodealwithaabundantofrasterdatain(henormalusage,wemustmakeouralgorithmtooptimize(hedisplayandprocessing.Todefineaboundingboxaboundingsphereforeachobjectanddefineaboundingboxaboundingsphereandaboundingconeforthefrustum,wecansolvethedisplayingoftherasterdataefficiently.Andtheusingofquad-treeofthesceneapproachcanfurtherenhanceefficiency.2) ThecalculationanddisplayofrasterwithGPU.GPUcandopreprocessinganddisplayofdatatogether.3) Basestationcoveragecalculationandsimulation.Byanalyzingtherasterdatatodothecalculationofthespreadofthesignal.Use3DModelcombiningwiththeHertzianWavesTransmitWastageForecastModeltoemulatethecoverageareasofthebasestationstochoosethepositions,whichcanhelpustochoosethepositionsvisuallyandmakedecisionsscientifically.Choosingthepositionsscientificallycanenlargethecoveragearea,linkseamlesslyandattractmorecustomerstoimprovetheamountofthephonecallaswellasreducethecostandimprovethebenefit,whichhasgreatmeaningsbothintechniquerealityandmarketoperation.Keywords:Basestation,CoverageArea,FrustumOptimize,GPU,3DModel目录摘要情退!未定义书签_¥ABSTRACT旦111目录I*第1章绪论11. 1选题意义11.2 国内外研究现状21.3 研究目标与章节安排31.3.1 1研究目标31.3.2 技术路线31.3.3 章节安排4第2章栅格数据与GptJ编程简介52.1 栅格数据的特点52.1.1 栅格数据结构52.1.2 矢量与栅格数据的比较62.1.3 3空间栅格数据的分层存储72.2 栅格数据的处理72.2.1 点云数据的分层处理算法72.2.2 点云数据的构网82.2.3 3栅格数据的优化处理82.3 GPU编程82.3.1GPU的概念82.3.2可编程管线92.3.3HLSL与GLSL92.3.4Cg编程语言102.6小结11第3章栅格数据的处理的算法优化133.1 平截头体优化处理133. 1.1Frusum定义134. 1.2基本算法1155. 1.3优化1186. 1.4基本算法2197. 1.5优化2228. 1.6反求Frustum的6个平面253.2 LOD优化处理283.2 .1Lod的概念283.3 .2求塌陷边293.2 GPU编程优化303 .2.1CG编程的通常步骤304 .2.1绘制地形313.3 小结33第4章栅格环境下基站范围的计算354.1基站覆盖范围的通常计算方法354.2计算栅格环境下的覆盖范围391.1.1 2.1栅格数据的存储与读取401.1.2 算法优化处理411.1.3 凸包算法422 .3小结43第5章仿真及结果455 .1图形软件接口455. 1.1OpenGL455 .2软件架构465.1.1 软件开发环境465.1.2 软件开发方法465.1.3 基本数据结构466 .3创建三维场景475.3.1创建三维地形475.3.2基站覆盖范围的计算485.3.3仿真结果49第6章总结与展望59参考文献母漏致谢错误I未定义书签.二第1章绪论1. 1选题意义与其它现代技术一样，移动通信技术的进展也呈现加快趋势。为了达到更高比特率数据业务与更好的频谱利用率，目前移动通信正在向第三代（3G）移动通信系统过渡。第三代移动通信能够实现全球统频段，统一标准，无缝覆盖；实现高服务质量，高保密性能，高频谱效率；可提供一系列的新业务，如多媒体通信、高速商务处理、遥测业务与用户通过移动通信网接入因特网或者企业网等业务。能够预见在不远的将来，全世界将会有与有线电话一样多的移动通信用户。与此同时，美国正在研究第四代移动通信技术（即4G）,其研究的目标是提高移动电话访问互联网的速率。据国家信息产业部统计，2007年，中国手机用户已有54728.6万户，全国手机普及率达到每百人38.3部。手机短信发送量为2790.2亿条，较上年同期增长37.5%>"O而全球手机用户数量已达到26亿，估计2010年将增至40亿，其中中国与印度将是要紧增长地区。手机在人们的日常工作生活中扮演着十分重要的角色。当前，在我国的一些偏远山区与许多自然环境恶劣的地区，还没有能够实现通信信号的覆盖，而当地的人民群众十分渴望进行移动通信。同时，在人们使用手机的过程中，经常会碰到信号质量不好，干扰强烈等问题，严重影响了人们的通话质量。这就对移动运营商提出了更高的要求，务必提供足够的信号覆盖范围，并保证通话质量，既基站选址问题。移动通信信号由发射机（基站）提供。基站覆盖范困要紧受当地地形（山区）与建筑（城区）的影响，如何选择一个尽量少受阻挡，能够保证话务质量的站址，是工程人员十分关心的问题。实际建设过程中，往往需要建设人员实地勘察。这样做不仅费时费力，也很难找到科学的站址。目前，在工程人员当中还没有形成一个比较科学的基站选址方法。通常工程人员进行无线基站选址时，难以充分考虑当地复杂的地理状况，只能凭借经验与有限的实地勘察试验来确定站址的选择，通常把站点选在高山或者高层建筑上，以期获得较大的覆盖范围。但实际上,这种选址方式有很大的主观性，容易造成覆盖范围不足或者重复覆盖形成信号之间的相互干扰等情况。目前三维城市模型中实现的软件很少，较为成熟的有三维日照分析软件。随着虚拟现实技术与数码城市GIS的进展，有必要建立这样一个系统进行基站选址。利用三维地理模型结合电磁波传播损耗预测模型仿真基站覆盖范围，以之来辅助基站选址，能够形象直观的帮助我们进行基站选址，科学的做出决策。科学的基站选址能够有效的扩大基站无线覆盖范南，更好地做到无缝连接，汲取更多的用户与话务量，同时能降低建设成本，提高收益，不管在技术实现上还是在市场运作上都有很大的意义。由于矢量需要人工测量采集，因此周期长时效性差，且建模复杂，因此非常昂贵不易获取，而栅格数据正好克服了这些缺点，栅格数据的获取非常方便。现在城市的进展非常快变化非常大，传统的非常耗时的矢量数据采集显然不能反映实际，因此本论文选取了在栅格数据为平台来研究基站的覆盖。但是受制于栅格数据本身的特点，大规模数据实时处理一直是目前虚拟现实方面的瓶颈，如何快速高效地读取计算与渲染这些数据是使用栅格数据所必需面对的难题，因此要求我们改进算法以达到有用的要求。1.2 国内外研究现状在法国国家信息与自动化研究所，运用栅格影像技术人们能够自由在虚拟与现实之间转换，能够非常自由地对真实物体进行三维重建与动作捕捉。随者计算机技术的进一步进展，虚拟现实与我们的生活将日益密切，而栅格影像技术也将为虚拟现实艺术掀开新的篇章。目前栅格数据的获取技术已经非常成熟，特别是机载雷达能够实时获取地形表面三维空间信息与影像。地面三维激光影像扫描仪通过近几年也在快速地进展，在测程范隹I、测距精度、测量速度、测量采样密度、激光安全等方面取得较大的进步，测量数据处理软件功能方面也在不断完善中。欧美与日本关于电磁波传播损耗预测模型的研究进行的较早，也相对比较深入。根据传播损耗预测方法的性质，能够将已有的传播损耗预测方法分为确定性模型小刀与统计模型两类区网。确定性的无线传播预测是种极其复杂的电磁学问题，电磁覆盖的数学复杂度使它不可能预测高度精确的无线传播。统计预测模型由于其简单易行而广泛运用于移动通信网络规划与优化，但是其运用时需要移动网设计者对当地传播环境做主观判定，同时计算方法与修正量均有限定范围，无法根据具体的传播环境来确定预测参数，这就必定会产生预测误差。为了能够尽量减少误差，国内外学者提出了很多改进的模型。目前国内已经开展了电磁波传播场强预测有关方面的研究I山川，基站覆盖范围仿真研究I与基站选址软件的研发。其中广东移动通信公司茂名分公司与北京超图地理信息技术有限公司合作，使用超图公司SUPerMaPGlS技术，基于组件式地理信息系统平台SuperMapObjects成功研发了无线基站选址软件。但是该软件只能应用于山区、丘陵、农村等不考虑建筑信息的地区，不能应用于城市(特别是建筑物密集的大型城市)内基站选址，同时其所使用的文件数据都有一定的格式限制且只能在数据量小的情况下进行测试，因此在实际中对数据与具体地形有一定的限制。国外在城市规划设计与辅助软件开发方面已经形成一个成熟的体系。在三维建模方面有3DSMAX、MAYA软件；在虚拟仿真上有MultigenCreatorZVega软件；在地理数据查询与空间分析统计方面GlS工具软件就有ArCGIS、MAPINFO软件，而且许多国外的规划设计工作室都拥有各自独立开发的规划辅助软件。另外，国外的许多开发小组提供了一些开源的通用型三维环境建模软件，如VTP(VisualTerrainProject)、OGRE(Object-OrientedGraphicsRenderingEngine)、TerrainView等，非常方便我们进行二次开发。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 .块码是有成长度编码扩展到二维的情况，使用方形区域为记录单元；四叉树编码是最有效的栅格数据压缩编码方法之一，还能提高图形操作效率，具有可变的分辨率。二、栅格数据的优缺点：优点为数据结构简单，便于空间分析与地表模拟，现实性较强；在栅格数据结构中，点实体表示为一个像元；线实体则表示为在一定方向上连接成串的相邻像元集合；面实体由聚集在一起的相邻像元结合表示。这种数据结构很适合计算机处理，由于行列像元阵列非常容易存储、保护与显示。缺点为数据量大，投影转换比较复杂。用栅格数据表示的地表是不连续的，是量化与近似离散的数据，是地表一定面积内（像元地面分辨率范围内）地理数据的近似性，如平均值、主成分值或者按某种规则在像元内提取的值等；另一方面，栅格数据的比例尺就是栅格大小与地表相应单元大小之比。像元大小相关于所表示的面积较大时，对长度、面积等的度量有较大影响，这种影响还与计算长度、面积的方法有关。4 .1.2矢量与栅格数据的比较一、矢量数据结构筒介矢量数据结构是通过记录坐标的方式尽可能精确地表示点、线与多边形等地理实体，坐标空间设为连续，同意任意位置、长度与面积的精确定义。矢量结构的显著特点：定位明显，属性隐含。其中，矢量数据的有如下优缺点：优点为数据结构紧凑、冗余度低，有利于网络与检索分析，图形显示质量好、精度高：缺点为数据结构复杂，多边形费加分析比较困难。二、两者比较：栅格数据操作总的来说容易实现，矢量数据操作则比较复杂；栅格结构是矢量结构在某种程度上的一种近似，关于同一地物达到于矢量数据相同的精度需要更大量的数据；在坐标位置搜索、计算多边形形状面积等方面栅格结构更为有效，而且易于与遥感相结合，易于信息共享；矢量结构关于拓扑关系的搜索则更为高效，网络信息只有用矢量才能完全描述，而且精度较高。关于地理信息系统软件来说，两者共存，各自发挥优势是十分有效的。为什么选择栅格数据：，棚格数据的选取_1批注Iyl:该为：数据类型的选用由以上的比较可知矢量数据与栅格数据各有优缺点，因而它的的应用范围也会有一定的差异，矢量数据作为一种精度高，表现复杂的数据要紧用于三维建模软件等的存储格式。而栅格数据由因此点云或者碘构好|的风格或巧网，由于,批注嬴数据量大，其几何信息的获得也需要通过专门的算法处理来提取，加之海量数据的处理算法比较耗时，因此在实时渲染方面也有一定的难题。从基站覆盖范围的预测与计和方面来讲，基站覆盖范围的计算要紧是用以模拟与反映真实的场景并为基站地点的选择的部署与以后的城市规划作决策与分析，因此应该使用实际的数据，传统的矢量数据由于其要紧是人工野外测量，因此其获取很耗人力，而且人工测量的速度较慢,有的时候跟不上城市的进展变化。但是只要通过选取合适的改进算法来优化栅格数据的处理工作，就能够避免或者减少海量数据的计算与分析处理的性能瓶颈。本论文后面的章节将会通过提出相应的改进算法来解决海量数据的处理问题，并以基站的覆盖范围为例使得栅格数据能够用以实时的分析与处理，为后续的分析决策打下基础。5 .1.3空间栅格数据的分层存储由于栅格数据通常非常庞大，因此对其的存储与管理办法通常是按照对精度的要求不一致对其分层存储。首先通过对点云数据进行构网形成基本的原始栅格数据。再按照不一致的精度级别要求使用LoD技术对其进行减化，再将这几种不一致级别的栅格数据分别存储。然后在程序的运行过程中通过视点与对象的不一致距离程序会读取相应精度的数据。2.2栅格数据的处理2.2.1 点云数据的分层处理算法由于点云只要绘制成点，没有遮挡，因此无法使用三角形简化算法。Carsten等人在QSPIaFOl基础上提出了顺序点树模型，它根据绘制过程中点片误差大小，由粗到细构建了顺序树状结构，并使用紧凑的文件布置方式,提高了绘制的效率。然而，Carsten等解决的仍旧是面状物体的绘制，同时，其用来操纵显示精度的普通树结构并不适合对点云数据进行裁切处理。四叉树格式规整，能够快速地对树上点云数据进行裁切。其中有一种方法是借鉴QSplai中紧凑组织数据的做法，使用多精度排序四叉树存储模型，使得每一层上的点云分布基本均匀，同时给出了一个大数据量下快速构建均匀分布四叉树的方法，来实现实时渲染大量LlDAR点云数据，通过绘制时数据量的自习惯操纵达到实时效果UL2.2.2点云数据的构网点云三角化算法是逆向工程技术中的一个研究热点。三角网格模型是逆向工程中逆向策略中的建模基础。国际上，许多学者已经提出了大量的三角化算法，这些方法大致能够分为基于Delaunay三角化的算法、基于有符号距离函数的算法、基于区域增长的算法等三类。2.2.3栅格数据的优化处理构好网的数据通常通过直接渲染三角形的方式来显示它们，这在渲染小量数据时是一个不错的选择，但是由于其本身的固有特点，栅格数据通常都会很大，而且由于本文使用的栅格数据是由点云数据构网形成的，因此不可避免地，其数据量是一个非常庞大的数字，因此传统的方法在这里会遇到性能的I瓶颈，实际的/I批注皿情况是这些数据是如此之大，以致于假如不进行某些处理的话，程序很难运行起来，因此设计出一套算法来优化它是一个必不可少的步骤。由于本论文接下来的两章将会专门来讨论如何优化与改善显示与处理栅格数据，以达到有用的目的。2. 3GPU编程2.3. 1GPU的概念GPU相当于CPU在电脑中的作用，它决定了该显卡的档次与大部分性能，同时也是2D显示卡与3D显示卡的区别根据。2D显示芯片在处理3D图像与特效时要紧依靠CPU的处理能力，称之“软加速”。3D显示芯片是将三维图像与特效处理功能集中在显示芯片内，也即所谓的“硬件加速”功能。NVIDIA公司在1999年公布GeForce256图形处理芯片时首先提出GPU的概念。GPU使显卡减少了对CPU的依靠，并进行部分原本CPU的工作，特别是在3D图形处理时。GPU所使用的核心技术有硬件T&L、立方环境材质贴图与顶点混合、纹理压缩与凹凸映射贴图、双重纹理四像素256位渲染引擎等，而硬件T&L技术能够说是GPU的标志。2001年，NIVIDA公司的GeFOrCe3苜先引入了可编程的顶点着色器(VeneXShader)单元。紧接着在2002年，可编程的像素着色器(PiXeIShader)单元也加入了GPU。在绘制时，GPU苜先接收CPU以三角形顶点形式的发送的几何数据。然后由可编程的顶点着色器单元进行处理，完成几何变换与顶点属性计算等功能。接着，这些三维空间的三角形由一个固定功能的光栅生成器转换为二维屏幕上的像素。每个像素的最终颜色值都通过运行在像素着色器上的小程序运算而得。2007年，NVIDIA率先引入了TeSIa通用GPU计算架构，最终目的是将CPU与GPU合二为一。另一方面，AMD计划于2009年推出内建GPU核心的Fusion处理器，而Intel整合GPU的Nehalem处理器将与之正面交火，届时，处理器将全面进入整合GPU时代。2.3.2可编程管线传统的固定功能管线(fixed-ftnclionpipeline)本质上是系列操纵特定类型的数据如何渲染的规则与策略方式。明显地，随着GPU的快速进展，许多原先只能通过软件编程在CPU上处理的高级功能，现在都能够直接交给GPU,但是每当GPU增加一条新的功能后，我们都需要我们的图形库(DirectX.OpenGD为之增加新的API,这样图形库就会急速膨胀，对程序员更是一种负担。可编程管线(PrOgrammabIePipeline)提供了条解决方案，假如说往常的固定功能管线编程就像汇编语言一样的话，那么可编程管线就像是高级语言，程序员能够抛开硬件的底层考虑而专注于实际应用的开发。可编程功能管线也就是对着色器(Shader)进行编程，着色器负责处理与显示最终结果(Shading).用于可编程功能管线的高阶语言有：DirectX中的HLSL.OpenGL中的GLSL.NVIDIA公司推出的Cg。DirectX8支持Shader1.X,Direct9与DireCt3D10支持shader2.X与3.X。2.3.3HLSL与GLSLHLSL是在direclX中使用的高阶着色语言(HighLevelShadingLanguage,HLSL),能够使用它来为Direct3D管线编写C网格的应用程序。微软率先在DirectX8中引入HLSL来进行可编程3D管线编写，在DirectX8中，既有传统的汇编式的固定功能管线编程的指令，也有HLSL式的可编程管线指令，而在最新版的DirCCIXIO中，则完全是纯粹的可编程功能管线，这意味着传统的固定功能管线的方式将不再支持。借助HLSL程序员非常方便地进行GPU编程开发。GLSL的全称是OPenGLShadingLanguage.也称作GLslang0OpenGLARB建立了OPenGL着色语言，为GPU的程式设计提供更加直观的方法。最初OPenGLL5是以扩充形式引入，后来C)PenGLARB在C)PenGL2.0核心中正式纳入GLSL。自1992年建立的OPenGL1.0起，OPenGL2.0是第一个OPenGL的重大修改版。使用GLSL有如下好处：具有跨平台的相容性，包含Macintosh>Windows与Linux等操作系统。所有支援OpenGL着色语言的绘图卡，都能够用来编写着色器。同意厂商为特定的绘图卡产生最佳化的代码。这两种语言非常类似，都是绑定在相应的图形接口之上的，但不能混用。2.3.4Cg编程语言Cg是种高级编程语言(CforGraphics),可使内容开发商更轻松、快捷地创建具有电影效果的实时图形。Cg是由NVIDIA公司与微软公司(NaSdaq代码：MSFT)密切合作联手开发的，开发人员借助该语言可更抽象地进行工作，无需直接针对图形硬件进行编程。通用、熟悉的CJike语法可迅速为图形平台开发出实时渲染的鲜锐视觉效果，并与微软公司公布的而向DireCtX9.0的高级渲染语言(HLSL)兼容。随着Cg与NVlDIA的Cg编译器的推出，开发人员将可更快地创建、共享与重新利用洎染引擎，这将使他们通过利用业界期待的鲜锐视觉效果与更强的真实感来创建更丰富的内容。Cg已经得到了赢得了业界的广泛支持，包含从游戏开发商到数字内容创建者，关于计算机图形行业而言，Cg是一个重要的里程碑，由于它使实时3D图形编程向电影渲染编程模式迈进了一大步。Cg将大大加快更趋复杂与兴奋人心的图形功能被使用的速度。Cg对GPU而言将起到C与C+对CPU所起的作用。CG中GPU处理如下：3DApplicationorGm3DAPICommandsH3DAPI:IOp<rvGlIorDrct301CPUGPUBoundaryGPUCommand&IDataStreamIAtsemNedPiXel.VertexIndexPolygons.LinesLocationPi*oIStream&PointsStreamUpdatesGPUIPrimitiveIRasterization&R>strI=AnWtd(H-FrontEndAe叼lnffpotoMOPeM图2-1目前，CG的最新版是2.0,它能够支持包含WilKiows、MacOSXLinUX等一系列桌面操作系统。由于CG是一个跨平台的语言，因此它大大了程序员编写跨平台程序的负担，同时由于它能够在运行期编译执行。因此它又能够利用各类GPU的最新性能，同时能够很容易地嵌入到opengkdirect3d等图形软件接口中。本论文中将会使用CG来进行CPU编程。使用CG编程有下列理由：（一）Cg是跨平台的Shader1）相同的CgShader源码能够编译成： 多种商业OPenGL扩展，如：ARB_vertex_prograin&ARB_fragment_prograin.）o NVIDlA特定的OPenGL扩展，如：GeFOrCe8的V_gpu_program4o DirectX9中的汇编shaders.如：ShaderModelsl.x,2.x,and3.x。 OpenGLShadingLanguage（GLSL）交叉编译。 DirCClX9HLSL交叉编译。 Sony公司的PlayStation3中支持的Cgo2）可用于多种操作系统:Vista,XP,2000,MacOSX,Linux,Solaris0（二）CG中还具有复杂的CgFXeffeelS系统，它与MiCrOSofl的DireClX9中的FX兼容。（三）具有一些其它的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中对平截头体的定义：图3-1平截头体能够依次将各个对象与FrUStUm来推断，但是这样的推断是线性级别的。因此为了提高速度，要使用到树形结构，这样能够把剔除处理速度提高到对数级别上。本论文中，我为我的剔除方法层次选择一个四叉树。假如是在空间中能够选择八叉树，但是本程序是基于地形的，因此为了避免算法过于复杂，本论文选择了四叉树，实际上，由于栅格数据具有高程信息，因此四叉树能够完全满足程序的需要。之因此选择一个四叉树还有一个原因是它的结构很容易可视化。一个四叉树实际上一个二维区域，这个区域通过一个树结构来建立，这个树结构的每个结构有四个孩子（如图3-2）,在这种情况下，其每个孩子占据它的父结点的一个四方块区域。其每个孩子又能够递归地分成四小块。而这些就构成了一个树形层次。子块被父块完全包围。通过把我们的世界建立成这种结构，就能够迅速地剔除掉大片的无关区域。由于当我们确定一个结点不可见时，则它的所有子节结都不可见。3.1.2 基本算法1规划这样一个结构的第一步是保证有基本的剔除与运行方法。这意味着我们要能够从我们的视图/投影矩阵中建构出6个平面，同时来测定一个球体是否在这个平截头体外或者一个包围盒是否在这个平截头体外。更精确的，我们要明白是否一个球体与盒是是否完全地包围在这个平截头体之内，或者完全在它之外，或者与这个平截头体相交。这要求我们接下来在我们的剔除系统中做更多地精确计算