毕业设计（论文）-道路工程网络三维交互式可视化关键技术及应用

[34]粒子系统（ParticleSystem）是由Reeves在80年代初提出的一种方法，主要用来解决由大量按一定规则运动（变化）的微小物质组成的大物质在计算机上的生成与显示的问题。粒子系统的应用相当广泛，大的可以模拟原子弹爆炸，星云演化，小的则可以模拟水波、火焰、烟火、云雾等场景，而这些自然现象用常规的图象算法（如调色板动画、动画贴图、基于多边形的渲染、光线跟踪渲染）是很难逼真再现的。只有基于物理模型的方法，才能模拟出随机而逼真的自然景象。粒子系统就是一种基于物理模型来解决问题的方法，它的核心不是在于如何显示，而是在于对微小物质模型的规则提取。粒子系统模型的表示可以很简单也可以很复杂，这取决你所模拟的对象。比如在对烟火的模拟中，我们可以让烟火由上百个小的粒子组成，每个粒子都具有以下一些属性及其规则，对各个属性施加不同的规则，就可以获得不同形态的烟火：(1)坐标。在烟火爆炸的时刻，每个粒子都有一个相同的初始坐标，随着时间的推移，粒子的新坐标将由它的旧坐标和加速度来求得。(2)速度。每个粒子都有一个随机产生的初始速度，粒子的新速度由加速度和空气阻尼来求得。(3)加速度。在烟火中，每个粒子的加速度都等于重力加速度。(4)颜色。粒子颜色取决于粒子的速度或生命值的大小。(5)生命值。每个粒子都有一个初始的随机生命值，这个值将随着时间的推移而逐渐减小，直到等于0。粒子系统在处理由大量单独粒子构成的场景模型时很有用处，但当涉及到需要考虑粒子间相互作用的场合时，由于计算量呈粒子数量的指数级增长，粒子系统就会显得有些力不从心。3.1.2道路三维模型总体构建方法在上述三维模型的构建方法中，体素表示法较适宜于描述较易分解为基本体素的物体，然后通过基本体素的交、并、差等布尔运算得到其三维表示，但对于道路场景的建模，因为它们均为非常复杂的不规则物体，较难将其分解为基本体素，所以不适合采用体素表示法。而采用八叉树结构表示，则会由于形体的不规则性，势必带来巨大的空间耗费。由于道路三维可视化所追求的是实时性和高度的真实感显示，而并不对几何造型进行如倒角、变形等编辑操作，实体的内部特征可略而不计，因此选择表面模型比选择体模型，会使数据结构和算法变得简化。如三角网数字地面模型，用一个个三角形面描述地形，并且记录三角形点、边及面的几何信息和拓扑信息的方法就是应用的边界表示法。图3SEQ图\*ARABIC\s15基于分割—归并思想的道路三维建模道路三维模型现状景物实体虚拟景物实体地物一般路基桥梁、隧道、涵洞等构造物图3SEQ图\*ARABIC\s15基于分割—归并思想的道路三维建模道路三维模型现状景物实体虚拟景物实体地物一般路基桥梁、隧道、涵洞等构造物沿线设施拼合计算地形道路三维整体模型3.2地形三维模型3.2.1地形三维模型概述地形三维模型是数字地面模型在三维可视方面的应用，其核心是数字地面模型的构建。数字地面模型的英文全称是DigitalTerrainModels，即DTM，该术语最早见于当时在美国麻省理工学院工作的著名教授米勒（C.L.Miller）的著作中。大约是从1955年到1960年其间，他和他的同事们致力于麻萨诸瑟州的土木工程和交通部门的研究工作，其主要目的是用摄影测量的方法获得足够的地形数据，然后，以这些数据为基础，进行公路工程的设计，以加速工程设计的进行。数字地面模型是一个按一定结构组织在一起的数据组，它代表地形特征的空间分布。通常，空间分布是用平面坐标系统X，Y表示的，而地形特征则是各个平面位置上地面点的高程Z。数字地面模型是地形起伏的数字表达，它由对地形表面取样所得到的一组点x，y，z坐标数据和一套对地形表面提供连续描述的算法所组成。这是一种狭义的定义，不少文献又把它叫做数字高程模型，简写为DEM。广义的DTM不仅有地表的高程数据，还有地表的其他属性数据，如地质，植被，水系等。通常，我们可由DTM来生成DEM，故大多数学者都不加区别地使用这两个词。DTM按其数据结构主要分为规则格网数模和不规则格网数模，因为数据点在XY坐标平面内的分布不外乎两种基本形式，即规则的栅格形式和随机形式。规则格网主要是规则矩形格网，它用一系列等间距地形的高程值表示，格网交叉点高程值就是对应地面某点的高程。其高程的获取可以通过摄影测量的方法对格网点进行取样，也可以由离散的原始数据点通过内插的方法获得格网点的高程。规则格网数模优点在于可以压缩存储，格网点平面坐标可由格网点在阵列中的行、列号整数取代，二维的行列号又可按先行后列或先列后行的规定转换为一维顺序号，而且序号可以取消，由记录的先后位置代替。另外其拓扑关系简单，算法容易实现。因此，规则格网在GIS领域有着广泛应用。但缺点是：(1)在平坦地区存在大量数据冗余；(2)网格大小固定，不能适应不同的地形条件，其规则的数据表示与不规则的地形特征不适应。最常用的不规则格网主要是不规则三角形格网（TriangulatedIrregularNet，简称TIN）。其基本思想是将数据点作为互不重叠的三角形上的各顶点，把地形表面看成由许多这样的三角形面所组成的折面进行逼近。TIN模型不改变原始数据点，能较好地顾及地貌特征，与不规则的地形特征相适应，可以表示地形特征线和任意形状的区域边界。具有较高的精度，并且数据冗余小，因此更适合地形三维动态显示。但其缺点是数据结构复杂，压缩空间小，在网络三维可视化中需要采取复杂的算法来对其进行压缩和简化。表3-1TIN与GRID对比表3-1TIN与GRID对比TINGRID数据冗余度低平坦地区高可压缩率低高数据结构复杂度高低同精度下内插点高程误差小大在道路工程的应用中，由于对地形精度有较高的要求，多采用不规则三角形格网作为数字地面模型。3.2.2约束Delaunay三角网模型的快速构建生成地形不规则三角网的核心是构网技术，目前已有多种构网技术，理论证明，在所有的构网原则中，Delaunay三角网(简称DT)是最优的。但标准DT只对点集V进行三角剖分，在构建数字地面模型中，为使模型更好地贴合地面，还需考虑散点间的约束关系，即地形特征线（山脊线、山谷线、陡坎等）的影响。考虑地形特征线约束的三角剖分称为约束Delaunay三角化（ConstrainedDelaunayTriangulation,简写CDT）。直接构建CDT的算法实现复杂，且效率不高，因此本文采用目前应用较多的两步法，首先构建DT，然后采用相关算法嵌入约束边，从而快速的构建了约束Delaunay三角网数字地面模型。迄今为止，国内外已经出现了不少标准DT的实现算法，归纳起来主要有三类：Shamos，Lee等为代表的分治算法，Lawson，Watson等为代表的逐点插入法及Green和Sibson等为代表的三角网生长算法，其中基于迭代原理的逐点插入法是较有代表性的一类算法，其基本思想为先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，采用LOP算法或Watson的数据相关三角形算法确保其成为Delaunay三角网。研究结果表明，逐点插入算法实现较简单，占用内存较小，但它的时间复杂度差，运行速度慢。特别是在大多数情况下，为了保证精度，所取的离散点数往往很多，算法的效率问题将变得更加突出。本文所采用的三角网即由逐点插入法所生成。该算法的基本步骤如下：1．建立初始三角网：求出给定点集的包容盒BOX（Xmin，Ymin，Xmax，Ymax），将包容盒沿对角线剖分为两个初始三角形，然后按以下步骤迭代，直到所有的数据点被处理。2．定位三角形：从点集中取出一点，在已建立的三角网中找到包含该点的三角形，如图3-6中(a)。3．确定影响域：从包含该点的三角形开始，依据三角形记录的拓扑信息利用空外接圆检测，找出外接圆包含当前插入点的三角形集，三角形集的外边界即是要寻找的影响域，如图3-6中(b)。4．影响域内的三角网重构：删除影响域内的三角形，依据Delaunay准则，在影响域内重新联网。方法很简单，只需将影响域的各边界与当前插入点顺次连接，如图3-6中(c)，所得三角化结果即为DT，证明参见文献。3-6逐点插入过程3-6逐点插入过程 （a）三角形的定位 （b）影响域的确定（c）影响域内三角网重构3.3道路三维模型道路设计线的曲面模型主要有三角网模型和孔斯曲面模型两种。3.3.1三角网模型三角网模型具有简单易建等特点，被广泛用来模拟自然表面或人工表面，因此三角网模型可作为设计曲面的表达式。依据平、纵、横设计结果，计算出横断面各角点的三维空间坐标，将相邻两个横断面对应角点联成三角网，沿线各横断面两两相连，即可构成设计线三角网模型，注意联网过程中还需考虑设计特征线的影响。设计特征线沿线路纵向表述为：路中线、路面边缘线、路肩边缘线、坡脚线等，沿线路法线方向为：各横断面设计线的水平投影。因此，设计线三角网模型也需顾及约束条件的三角网模型如图3-7所示。图3-7设计线三角网模型（俯视）可见，三角网模型的实质是用平面近似表示曲面。用三角网模型表达设计面具有如下特点：(1)在平曲线（圆、缓和曲线）上是以适当密度的折线（直线）代替曲线，这种近似处理对于精度要求较低时尚可，但随着精度的提高，密度太小，不能很好地描述曲线，因而要加密曲线段点的密度，这造成了存储空间的增大与搜索速度的降低。(2)对于范围较广的面状区域，三角形自动联网较繁，且规则不统一。由此可知，采用三角网模型描述设计面的关键是曲线段点的密度的确定和三角网的自动形成。除简单易建外，该方法的另一个好处是当地表面采用三角网模型时，可以实现模型方式的统一，便于将两个不同的模型合并为一个整体。3.3.2孔斯模型三角网模型的实质是用平面近似表示曲面，在三角形与三角形的连接处，特别是曲线路段容易出现折皱，而曲面模型是用一数学面来严格描述曲面片，可避免三角网模型的这一不足。对于道路的三维建模问题，可选用Coons曲面模型来描述设计面。1．Coons曲面模型的基本原理Coons曲面模型是基于计算几何理论发展起来的，它的发展经历了从理论到实践应用的过程。1967年孔斯（S.A.Coons）在一篇报告（SurfacesforComputerAidedDesignofSpaceForms,AD-663504,1967）中提出了适合于计算机辅助设计的几种构造曲面的方法。他所提出的构造曲面的方法堪称奠基性工作，对曲面造型的发展具有十分重要的影响，在当时被人们用来描述飞机机身、机翼和螺旋桨的外形等。目前，这些曲面模型已被广泛应用于计算机辅助设计与造型等，被称为Coons曲面。孔斯在他的论文中明确指出，构造曲面的目的是使曲面设计变得简单易行，从设计师的角度来看，方法要符合他们的习惯，使工作变得自然和容易，而不必去关心方法本身的数学细节，能集中精力改善设计本身的质量，为此应输入尽可能少的信息就可确定一张曲面，并且，如有必要可以通过输入原始信息来修改这些曲面。面对这样的设想，孔斯提出了一种曲面分片拼合造型的思想，这是一种通过连接若干“曲面片”（SurfacePatches）去构造并组成任意复杂曲面的方法，每个曲面片由四条边界确定，为了实现这个构型思想，关键是如何具体地构造出各种类型的曲面片，使之便于拼合，又能满足设计人员对曲面外型准确度的要求。孔斯继承了拉格朗日（Lagrange）和埃尔米特（Hermite）插值的思路，并发展了这些方法，形成了独树一帜的孔斯曲面法。2．Coons曲面的的本质60年代以前，曲面拟合方法中所有插值曲面涉及的仅仅是给定的一批型值点，曲面拟合的实质是对空间点的拟合。孔斯曲面与以前的曲面拟合方法相比较，其本质主要体现在构造孔斯曲面的三个重要思想：第一，孔斯认为，用插值于曲线上的离散点来构成曲面，倒不如用插值于边界的曲线来构造曲面更为合理；第二，孔斯曲面不是插值边界曲线上有限的数据信息，而是插值两组边界曲线上无限多个点，所以这种方法又被称为超限插值（transfiniteinterpolation）。第三，为了使构造出来的曲面片彼此能很容易地“缝合”，即拼合，孔斯又给边界曲线加上跨界导矢信息，曲面片应当不仅插值于四条边界曲线，而且要插值于此四条边界上任意给定的各阶跨界导矢（即边界斜率），在插值中还用到一组不同作用的混合函数（BlendingFunction）。3．Coons曲面模型的几种构造形式（1）双线性混合孔斯曲面片这是孔斯曲面中最简单的曲面片。双线性混合孔斯曲面片方便地实现了插值四条边界曲线的要求，而且用它来进行曲面拼合，由公共边界可以保证整张曲面的位置连续性，因此部分学者选择它作为道路或机场设计曲面的描述模型。但该模型仅是位置连续，达不到曲面片间的光滑连接。（2）局部双三次混合孔斯曲面片双线性混合孔斯曲面片利用了两对线性混合函数来满足插值四条边界的要求。为了解决双线性混合孔斯曲面片一般不能实现光滑拼接的问题。局部双三次混合孔斯曲面片采用两对三次混合函数实现了曲面边界的光滑连接。但采用双三次混合函数的结果，将导致曲面片的角点扭矢全部消失成为零向量，从而引起在曲面片角点处出现“伪平点”。为了避免这个问题，必须修改局部三次混合孔斯曲面片。（3）双三次混合孔斯曲面片双三次混合孔斯曲面片的生成与双线性混合孔斯曲面片的生成方法类似，只不过所采用的混合函数不同而已。双线性混合孔斯曲面片采用的是线性函数，而双三次混合孔斯曲面片采用的是三次埃尔米特插值函数。三次埃尔米特插值不仅要求端点位置信息，而且还要求端点切矢信息。由于此时位置信息恰好是整条曲线，而不是点，相应所要求的切矢信息也应沿整条曲线提供。这样，当沿公共边界有公共跨界切矢的两相邻双三次混合孔斯曲面片沿公共边界拼合时，两曲面片沿公共边界就达到了连续。在此基础上，提供以插值四条边界的双线性混合孔斯曲面片的扭矢为四角点扭矢，可以避免前面提到的问题。综上所述，Coons曲面模型实际上是双参数自由曲面模型，写成参数方程的形式为。它由四条边界曲线P(u,0),P(u,1),P(0,v),P(1,v)构成。从构造过程来看，首先沿u方向，然后沿v方向构造自由曲线来形成自由曲面；或先沿v方向再沿u方向构造自由曲面，且两者所得的曲面完全相同。构造过程采用的混合函数不同则构造出的Coons曲面也不同，曲面片之间连接的光顺性也不同。3.3.3道路三维模型构建图3-8道路三维网格线框模型和贴上纹理的模型在上述两种方式中，虽然双三次混合孔斯曲面片在数学上实现了曲面片光滑连接，但由于曲线方程复杂、计算量大，实现时要耗费大量的CPU时间，不利于道路三维场景的实时显示。因此，本文采用道路平、纵、横设计成果，先按一定的密度计算出横断面各个角点的三维空间坐标，然后将相邻两横断面对应角点两两相连，形成一个个四边形网格面片来构造道路三维模型，然后根据面片属性贴上相应的纹理图片。实践证明，在速度和场景效果上都能取得满意的结果。如图3-8所示为一段道路三维网格线框模型和贴上纹理的模型。图3-8道路三维网格线框模型和贴上纹理的模型第四章网络环境下模型数据的调度与传输第四章网络环境下模型数据的调度与传输4.1概述在传统的单机道路三维可视化研究中，仅需从本机硬盘传输模型数据至内存和显卡进行计算和渲染，数据传输问题对三维可视化效果的影响甚小。但在本研究中，需要通过Internet来将海量模型数据从服务器端传送至客户端，而当前的网络带宽还远不能满足动辄几百兆模型数据快速传输的实时性要求，导致网络已经成为Web3D系统运作的瓶颈。因此，采用合理的算法和策略对海量模型数据在网络环境中进行调度和传输是本文需研究的重点问题。本章中，提出了一种面向不规则三角网数字地面模型数据快速传输的基于累进网格的多分辨率简化算法，并结合此算法采取了一系列的策略来优化海量模型数据在网络环境下的调度和传输。4.2模型多分辨率简化算法4.2.1常用的地形三维模型简化技术为解决复杂三维场景渲染与计算机硬件性能间的矛盾，国内外学者对单机环境下地形三维模型的简化和压缩有较多的研究，而网络环境下关于不规则三角网的三维模型简化技术还较少见诸于文献，但可以借鉴于单机环境下的相关算法。常见的地形简化和压缩方法有顶点删除、边删除和面片压缩技术等。顶点删除技术在三角形网格中，若一个顶点与它周围三角面片可以被认为是共面的（这可以通过设定点到平面距离的阈值来判断），且这一点的删除不会带来拓扑结构的改变，那么可以将这一点删除，同时所有与该顶点相连的面均被从原始模型中删除，然后对其邻域重新三角化，以填补由于这一点被删除所带来的空洞，Schroeder的网格简化方法是最经典的基于删除操作的简化算法。这种算法较快，也不需要占用太多的内存，但是由于重新三角化需要将局部表面投影到一个平面，这种算法只适用流形，而且它在保持表面的光滑性方面存在一定的困难。随后又有算法对其改进，并提出了更精确的误差测度，这些算法可以生成较高质量的模型，但是需要花费更多的时间和空间，如图4-1所示为顶点删除操作示意图。图图4-1顶点删除网格简化算法边折叠技术该算法的基本思想是通过计算边的压缩代价，对折叠代价小的边先进行压缩，然后计算此次折叠所生成的新顶点位置（如图4-2），边折叠的关键就是折叠的次序以及边折叠后新顶点的位置。边折叠技术以微软公司的Hoppe提出的累进网格算法(ProgressiveMesh，简称PM)为优秀代表。Hoppe在1993年采用能量优化的方式来确定折叠次序和新顶点的位置，能量优化计算复杂，所需时间较长，但是生成模型的效果却是在所有化简方法中最好的。Garland和Heckbert在1997年提出了一种二次误差测度（Quadricerrormetric，简称QEM）来度量简化模型的近似度，由于该算法测度是基于顶点到平面的距离平方和，速度快，简化生成的模型质量较好，是一种非常有效的简化方法。图图4-2边折叠网格简化算法通过对边压缩的研究，学者们又提出了一种半边折叠网格简化算法，即在压缩过程中，不需重新计算压缩后的新顶点，而只是压缩到边的某个顶点，由于省去了计算新顶点的时间开销和存储开销，产生了较好的简化效果（如图4-3）。图4-3半边折叠网格简化算法图4-3半边折叠网格简化算法面片收缩技术根据一定的算法得到边或者三角形的压缩代价，对压缩代价小的边或三角形先进行压缩操作，然后计算压缩操作所生成的新顶点位置（如图4-4），一次三角形压缩操作可以删除4个三角形和两个顶点。图图4-4面片压缩网格简化算法4.2.2多分辨率网格基本原理构建多分辨率的渐进网格地面模型能够最大程度地保持地面模型的原貌，并大幅度地减少了实时地面模型数据传输量。其基本原理是：通过一定的规则(通常是地形起伏影响度)计算各个三角形的各边权值，并对权值进行排序，而后从权值最小的边开始进行边折叠操作将原始地面模型网格(用M表示)的分辨率逐渐降低，最后得到一个数据量大大减少的低分辨率网格(用M0表示)和对应各个边折叠操作的细节信息记录。相反的，将这些细节信息记录向M0中逐渐插入顶点和更新三角形可以恢复到原始网格M，如图4-5所示。从M到M0的简化过程是通过称为“边折叠（edgecollapse）”的操作实现的，即：从网格中删除某条边（vs，vt），并且将两顶点vs、vt融合形成一个新顶点，Hoppe的PM算法中是根据能量优化算法来计算新顶点的位置，该算法较为复杂且计算量大，本文中采用的半边折叠方法即顶点vs直接合并到vt，与边（vs，vt）相邻的两个三角形fl，fr也一并被删除，从而降低了网格的分辨率。相反，从M0重建出M的过程是由“点分裂（vertexsplit）”操作完成的。这恰是边折叠操作的逆过程，它向网格中添加了一个结点vt和两个三角形fl和fr。图4-5边折叠与顶点分裂图4-5边折叠与顶点分裂将细节记录信息逐次向低分辨率的数字地面模型可以逐步恢复出每次边折叠操作被删除的顶点、被删除的三角形、顶点被改变的三角形，从而逐步恢复出原始的具有较高分辨率的数字地面模型。边折叠过程如下：EdgeCollapse0EdgeCollapsek-1EdgeCollapsek-2EdgeCollapse0EdgeCollapsek-1EdgeCollapsek-2(M=Mk)Mk-1+Detail_k-1M1+Detail_1M0+Detail_0顶点分裂过程如下：SplitByDetail_k-1Split1ByDetail_1Split0ByDetail_0SplitByDetail_k-1Split1ByDetail_1Split0ByDetail_0M0M1Mk-1(Mk=M)4.2.3半边折叠要建立原始网格M的多分辨率PM表示，首先要执行一系列的顶点合并(即边折叠)操作，并在此过程中记录细节记录信息以便能够恢复到原来的拓扑结构。半边折叠的基本过程如下：（1）建立三角形权值优先级队列；（2）从待简化的三角形队列中，找出权值最小的三角形；（3）将权值最小的三角形中的权值最小的边进行边折叠，三角化边折叠所留下的“空洞”,并添加细节记录到细节记录序列中，同时计算新三角形的重要度值，将该值插入重要度优先级队列中；（4）如果满足条件则网格简化结束，否则转（2）继续执行下一个边折叠操作。在上述算法中首要解决的问题是顶点重要度排序问题。目前点的重要度的确定主要是根据点邻边的最小边长确定。从直观上理解，删除一个包含有最小边长的点对网影响最小，但该方法没有考虑地形的起伏状况，也会使网中的边长趋于平均，也就是网格的形状趋于一致，从而不利于保持几何模型的原始表面形状。本文提出了确定点重要度的一种新的方法。具体算法步骤如下：计算顶点法向量首先做如下定义：定义1.定义点P的星形邻域为所有与P点相关联(即与P点有直线相连)的顶点Sk组成的区域，记为Star(P)。显然，点P的星形邻域通常并不在同一个平面上，因此又有定义2。定义2.定义点P的星形邻域的平均平面A(Star(P))为使(4-1)取最小值的平面，其中为Sk点到平面A(Star(P))的距离。平均平面的计算方法如下：设A(Star(p))中每个三角形的法向量为nk，中心为ck，面积为Ak，则A(Star(P))的法向量n和中心c的计算式为：(4-2)(4-2)(4-3)则平面A(Star(P))的方程为(4-3)则顶点法向量为n=(a,b,c)T，且有a2+b2+c2=1。计算三角形权值(4-4)假定vi(i=1…n)是待简化三角形网格中的顶点，vj(j=1…m)是与vi相邻的顶点，记ni和nj分别为vi和vj相对于各个平均平面的法向量，那么ni与nj的夹角余弦表示为：(4-4)于是，边(vs,vt)的权值可以定义为：(4-5)(4-5)该式中，表示边（vs，vt）的空间长度。上式中第二项体现了vt点与其相邻点之间法向量的最大夹角。这个夹角越大，说明vt点附近几何起伏变化越大，但夹角余弦越小，所以式4-5计算出来的权值也就越大，于是这条边的删除操作就更应该越置后。另外，由于第二项的取值范围总是在[-1，1]中，为防止在边长很大的情况下第二项不能发挥作用，对上式作如下修改：(4-6)(4-6)这样，地面三维模型的地形起伏特征就能够在权值中得到很好地保留，但是这一公式又有可能导致一些狭长三角形被保留，为了防止这一现象，下面进一步修改权值公式：(4-7)(4-7)上式中，表示三角形中三边长度的最小值，表示三边长度的最大值。于是三角形越狭长，改项比值就越小，被删除的优先度就越高。如果给这三项加上不同的权值，就可以进一步修改各项对总权值的影响大小。注意，根据式4-7计算出来的边权值有两个结果(即分别由vs->vt和vt->vs计算得来)，取较小权值作为边（vs，vt）的权值。建立三角形权值队列上述算法中每一次循环都要寻找权值最小三角形的权值最小边，假如每次都进行全局搜索将非常耗时。因此，本算法中将2)计算的每个三角形权值存入到一个排序表中，这样每次边折叠操作就可以直接从表中读出权值最小的三角形，并进一步读出其权值最小边。当然，每做完一次边折叠，必须更新与vs相邻的三角形的权值，同时调整排序表，但这只是局部调整，时间消耗相对较小。进行半边折叠操作如图4-8所示，从三角形权值队列中逐步找出并删除权值最小的边(vt,vs)，将顶点vt合并到vs，删除同时包含这两个顶点的三角形fl、fr，并将vt所有相邻点(除vs)的连接关系为vt的改为vs，即将所有包含vt但不包含vs的三角形的顶点vt改为vs，一次半边折叠操作细节记录信息应包括：(1)被删除的顶点在顶点列表的索引和坐标；(2)被删除的两个三角形在三角形列表中的索引和顶点索引；(3)边折叠前后顶点被修改的三角形的顶点索引。与Hoppe的求解最优化网格的方法相比，这种给三角形加权的半边折叠算法在计算上更简单，而且只要合理地定义三角形的权值，就可以达到很好的简化效果。在进行边折叠的过程中由于网的形状是不可预知的，因此有可能会出现三角形的重叠情况。图4-6是一个典型的例子,如果在执行半边折叠的过程中v4合并到v5，则折叠后边(v2,v5)将与边(v1,v3)发生边交叉和三角形重叠现象，这样就得到了一包含重叠三角形的网，这种情况在简化过程中是不允许出现的，会导致简化后的地形三维场景发生“突起”或“尖角”的现象。为了防止这种情况的发生，在简化过程中要加入判断合并后三角形是否重叠的判断因子，即在折叠一条边之前判断简化后的网格是否重叠。图4-6三角形重叠图4-6三角形重叠内边界图4-7地形三维模型中的“内边界”另外，由于本文中所采用的地面三维模型为如图4-7所示的裁剪DTM，即把地形三维模型与道路三维模型的重合区域做了裁剪和拼接，因此包含图中所示的“内边界”顶点的约束边不能参加半边折叠操作，否则将可能导致简化后的地形三维模型与道路三维模型发生重叠或交叉的现象。为此，本文中将含有“内边界”的三角形作为独立三角形集，它们和与它们相邻的三角形都不参加半边折叠操作。内边界图4-7地形三维模型中的“内边界”4.2.4顶点分裂地面三维模型经过半边折叠处理后其结果为一个最简化的模型M0和一个细节记录信息序列EdgeColArray，进行半边折叠操作的次数可根据原始模型的大小和简化精度自行确定。在本研究中，半边折叠的逆过程即恢复原始模型的过程-顶点分裂是在客户端完成的：客户端多线程首先将M0下载完成后，立刻将最简化模型场景渲染出来，而细节记录信息则在后台使用另外一个线程下载，而后执行顶点分裂过程，将原始地形三维模型恢复出来，需注意的是恢复过程与半边折叠操作顺序相反，如半边折叠操作产生了n个细节记录信息，则顶点分裂操作则是从第n个细节记录信息开始倒数进行。定义如下数据结构保存细节记录信息：classEdgeColInfo{//被删除的点在地形顶点数组中的序号publicintDelPtNo;//被删除的点的坐标publicfloat[]DelPtXYZ;//被完全删除的两个三角形在三角形数组中的序号publicintDelTri1No;publicintDelTri2No;//被完全删除的两个三角形的顶点索引publicint[]DelTri1Index;publicint[]DelTri2Index;//保存一次半边折叠操作中所有一顶点索引被修改的三角形的索引数组publicArrayListarrChangedTri;}结合以上数据结构和图4-5，以下说明一次顶点分裂操作的具体算法步骤：（1）从细节记录信息序列中依次读取半边折叠操作记录；（2）根据DelPtNo和坐标DelPtXYZ和向网格中插入新地形顶点vt；（3）根据数组arrChangedTri恢复顶点vs，vt周围三角形的几何邻接关系；（4）根据DelTri1No、DelTri2No向网格中插入两个新的三角形：fl={vl,vs,vt}和fr={vr，vs，vt}。在顶点分裂过程中，由于每插入一个细节记录时，只需对几个数组进行顺序读取和插入操作，不涉及排序等耗时过程，因此顶点分裂效率很高。利用PM结构也可以执行选择性细化浏览，即在细化过程中只细化浏览者感兴趣的某个局部部分，而其余的部分仍保持原有的低分辨率，从而实现基于视点的分辨率的连续变化。4.3模型的离散化处理将复杂模型进行离散化处理是三维可视化研究中常用的提高渲染效率的策略，诸多模型简化算法都是以离散化子模型为基础。在本研究中，将道路三维模型和地形三维模型分别进行了分段和分块的离散化处理，在模型传递和客户端场景渲染的过程中都是以离散化后的子模型为单位。4.3.1地形三维模型的离散化处理本文中针对地形三维模型的离散化处理主要将用于两个目的：模型数据压缩传输和地形三维模型分块渲染。Denaulay三角化后生成的地形三维模型包括地形点集和三角形索引集两部分数据，前者保存了地形散点的空间坐标信息，后者则是Denaulay三角化的结果，二者的数据结构原型分别如下所示：classTerrPt//地形点{publicfloatx;publicfloaty;publicfloatz;};classTerrTri//地形三角形{ publicintIndex0;publicintIndex1;publicintIndex2;publicbooleanbToGrid=false;//划分网格时，标识该三角形已经放入一个网格中,以保证每个三角形只属于一个网格。publicbooleanbIsBorderTri=false;//是否为边界三角形(边界三角形不能参与边折叠过程)。};在地形三维可视化研究中，处理方法通常是将整个地形三维模型数据切分为一个MxN网格阵列，建立网格-散点-三角形的索引系统。参照这一思想，本文将Denaulay三角化生成的不规则三角网地形三维模型数据投入到图4-8地形三维模型离散化处理一个MxN的网格阵列中，单个网格覆盖范围大小可根据数据量大小灵活确定，具体原理如下：图4-8地形三维模型离散化处理定义地形网格数据结构如下：classTerrGrid//网格{doubledXMax,dXMin,dYMax,dYMin;//网格边界坐标HashtablehsPts;//保存网格范围内地形散点的哈希表HashtablehsTri;//保存网格范围内三角形索引的哈希表};建立网格阵列根据地形三维模型的边界坐标和网格大小确定网格阵列的网格个数和各网格的边界坐标，初始化各个网格的哈希表。拆分地形三维模型如图4-8所示，根据各个地形散点坐标和网格边界坐标，将地形点投入到网格中，即保存在网格对象的地形散点哈希表中。同时根据以下原则将三角形索引也投入到网格中：只要某三角形索引中的任意一个地形点位于某个网格范围内，便将该三角形索引保存至该网格对象的三角形索引哈希表，同时标识该三角形索引以保证一个三角形索引只会属于一个网格，防止出现跨网格的三角形保存到多个网格导致的数据冗余现象。4.3.2道路模型的离散化处理道路三维模型及其附属的工程结构物模型以平、纵、横的道路设计数据为基础来构建，平、纵、横数据是道路设计的数字化成果，平面数据主要记录线形中各个线元的设计参数，它表述的是道路中线的平面位置，它的设计成果是平曲线要素表和逐桩坐标表。而纵断面数据则表达了线路中线在立面上的位置以及填挖方状况，它的设计成果是竖曲线要素表及逐桩高程表。横断面数据则是对在道路中线的相应位置处法线方向的地表状况和设计形式的表达，它的设计成果是路基设计表。 因为道路的平、纵、横设计成果分别记录，其相互之间的关联性较差。而道路三维模型作为一个整体，在绘制时需要同时表达平、纵、横各个要素，直接使用设计数据的组织模式显然无法满足模型表达的需要。为此，本文中将每个横断面的各个角点坐标计算出来，在场景绘制时，将这些横断面数据前后两两相连，而平纵设计数据则作为道路场景组织和交互式查询的数据基础，如在场景中根据点选的屏幕坐标查询里程、平曲线半径缓长、高程等。道路平面数据和横断面数据结构的主要成员变量和功能函数如下所示：classPMDAT//平面数据类{ doubleXYArray[][]; //当前道路的平面线元数组 DLBZDLArray[]; //一条道路的断链数组 StringRoadName; //道路名，标识每条道路 publicStringXLC(doubleTYLC){……}//根据统一里程计算现场里程 publicStringTYLC(doubleXLC){……}//根据现场里程计算统一里程publicdoublePROJ_ML(doublex,doubley){……}//根据平面坐标计算里程publicvoidxlpoint_pz(xlpointPZ){……}//根据里程计算平面坐标 …… }; classCRSDAT//横断面数据类{ doublecml，dml; //当前横断面所处的里程(连续里程和现场里程) doubleDuanLuoInf; doubleZDesH，YDesH; //横断面上道路中心点的设计高程信息 doubleLZDK，RZDK; doubleRHFL[10]，RHFR[10]; //主线路面点个 doublezlmhd[3]，ylmhd[3]; intZDMXZ，YDMXZ; //左右幅断面性质 doubleZt，Yt; //填挖标志 doubleZHc，YHc，Y_ZHc，Y_YHc; intzptsum，rptsum，Lnpt，Rnpt; //点数 Point3dArrayRPTL，RPTR; //横断面上各点相对于中心点的高度 Point3dArrayPTRPTL，PTRPTR; //横断面上各点的平面及高程数据 …… //关联道路的数据}; 一个道路项目的设计成果通常由主线和若干个分离段组成，在本文中将主线和分离段平等对待，作为道路设计数据的组织单元，即主线和分离段的平、纵、横设计数据分别保存，这种组织方法为道路模型的离散化处理提供了可能。本文中根据以下方法将道路整体模型数据离散化后存入服务器缓存的哈希表中：分离段一般较短，以分离段名为关键字将其平、纵、横数据存入哈希表；主线贯穿始终，其横断面数据占据道路模型数据总量的大部分，将主线的横断面数据按里程划分为多个段落，以每个段落的起始里程为关键字存入哈希表；主线平纵设计数据，以自定义的名称为关键字存入哈希表。4.4数据调度与传输优化策略4.4.1数据缓存设计网络环境下，从远程客户端用户的请求生成到请求得到结果整个流程如下：浏览器通过URL地址查询DNS，DNS返回服务器的IP地址；浏览器根据IP地址建立一个TCP/IP链接；浏览器通过该链接向Web服务器发出一个HTTP请求；Web服务器根据请求的内容，在数据库或文件夹(即硬盘中)读取数据，形成一个结果发送给浏览器，并关闭链接；浏览器将返回的数据以某种形式(文字、图片、三维场景等)表达之。从以上流程可以看出来HTTP协议花费了很多的时间用在建立和等待链接上，因此可以尽量减少网络链接的次数和加快服务器端的处理速度来提高整个网络数据的传输速度。网络缓存技术是目前一种降低Internet流量和减少客户端用户响应时间的新兴网络技术，它的观念来自于计算机硬软件和网络的其它领域，如Intel架构的CPU中就使用缓存来提高内存存取的速度；各种操作系统在进行磁盘存取时也会利用缓存来提高速度；分布式文件系统通常也用缓存来提高客户端和服务器之间交互的速度。网络缓存既可以在网络服务器上，也可以在客户端，由此在本研究中将缓存分为两类：服务器端缓存和客户端缓存。服务器端缓存设计图4-9服务器端缓存数据调度图4-9服务器端缓存数据调度服务器端的数据缓存是面向所有用户的数据缓存，考虑到服务器内存容量一般都比较大，所以服务器端数据缓存量也比较大。而且服务器需要处理的是多用户的数据请求，因此服务器端的数据缓存设计需要面向多用户、全局数据范围，区别于客户端面向单个用户、局部范围的数据缓存。由于不同客户端的数据请求不相同，有可能会导致服务器端缓存中数据重复现象的发生，因此需要设计合理的数据缓存机制来对服务器端缓存进行管理。本文根据对模型数据离散化预处理的结果，在服务器端建立了一个基于索引的缓存管理机制：对于离散化后的道路子模型和数字地面子模型分别以里程和网格行列号为关键字建立索引，而后将它们存入数据库中。客户端根据索引向服务器端发送数据请求，Web服务器接收到请求后首先验证缓存池中是否存在该子模型数据，若有则直接从缓存池中取出发送给客户端，若没有，则从数据库中读取数据发送给客户端，同时将其以索引为关键字存入缓存池中。该过程如图4-9所示。缓存中用两个哈希表将道路子模型和数字地面子模型分别来进行保存和管理。客户端缓存设计根据道路网络三维可视化的快速实时化的要求，需要在客户端建立数据缓存，使得客户端需要再次显示道路三维场景时，可直接读取利用本地机器缓存中的数据，减少了数据的重复传输和用户等待时间，提高数据调度的效率。在传统的单机三维可视化中，通常以操作系统的文件映射机制在单机上来实现大数据量的硬盘与内存之间的快速传输，本文中，参考此机制使用J2EE中的java.nio包中的文件映射类来建立了客户端缓存区。操作系统的文件映射技术允许应用程序将磁盘文件与内存的实际地址空间相关联，从而使系统能够确定该文件位于何处，而当文件映射之后，Windows就将磁盘文件映射到地址空间，即程序认为该磁盘文件实际就是位于内存中，一旦访问该文件，就可象存取内存数据一样，从而大大加快了数据读写的速度。J2EE的java.nio包中的MappedByteBuffer

等类提供了java语言使用操作系统的文件映射技术的可能，再结合经过数字证书签名的Applet小程序取得在客户端磁盘读写文件的权限后，就可以方便地建立客户端缓存了。4.4.2数据压缩传输数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度，达到增大数据密度，最终使数据的存储空间减少的技术，它被广泛应用于文件存储、分布式系统、网络数据传输等领域，数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。数据压缩就是将字符串的一种表示方式转换为另一种表示方式，新的表示方式包含相同的信息量，但是长度比原来的方式尽可能的短。数据压缩技术主要可以分成有损压缩和无损压缩两大类，在三维可视化特别是基于Denaulay的地形三维可视化应用中，应用得较多的是无损压缩算法，经常使用的无损压缩方法有Shannon-Fano编码、Huffman编码、游程(Run-length)编码、LZ77编码和算术编码等。在网络三维可视化中，模型数据量非常大，而文本数据、属性数据、图形数据具有很大的压缩潜力，如一个double型变量的长度最多可以存储三个12位的空间坐标。因此在网络带宽相对有限的情况下，对模型数据进行压缩有利于数据在网络环境中的快速传输，本文中采用了网络传输中应用较多的GZIP包来对各种模型数据进行压缩和解压。GZIP最早由Jean-loupGailly和MarkAdler创建，用于UNIX系统文件的压缩，现在已经成为Internet上应用非常普遍的数据压缩格式。GZIP内部通常采用DEFLATE数据格式，而DEFLATE同时使用了Huffman编码和LZ77压缩算法来压缩数据。LZ77是一种压缩比很高的算法，运行时压缩解压时间很短，因此日益成为当前数据压缩技术中的一种主流算法。数据中重复字节越多用LZ77算法压缩率越高，在本研究中经过多次反复测试，使用GZIP进行模型数据压缩的压缩比通常高达50%-70%，大大减小了模型数据的传输量。服务器端压缩并发送道路子模型数据的步骤如下所示：通知网络传输层,以实现序列化接口类的二进制流形式传输数据response.setContentType("application/x-java-serialized-object");建立输出流，准备向客户端发送数据OutputStreamout=response.getOutputStream();建立GZIP输出流通道GZIPOutputStreamgOut=newGZIPOutputStream(out);ObjectOutputStreamobjStream=newObjectOutputStream(gOut);从缓存中获取数据，压缩后并向客户端发送数据objStream.writeObject(hsRoadData.get(kml));客户端读取模型数据后解压的过程如下所示：根据服务器端地址构建URL对象URLurlServer=newURL(sURL);利用URL对象打开客户端与服务器端之间的连接URLConnectioncon=urlServer.openConnection();设置连接的属性con.setDoInput(true);con.setRequestProperty("Content-Type","application/x-java-serialized-object");建立输入流对象InputStreamis=con.getInputStream();GZIPInputStreamgzipis=newGZIPInputStream(is);解压缩，读取数据至客户端内存ObjectInputStreamobjis=newObjectInputStream(gzipis);RoadModelDataroaddata=(RoadModelData)objis.readObject();关闭连接is.close();objis.close();4.4.3客户端多线程在网络领域中，多线程常被用来提高数据传输速度的传输速度。本研究中采用了多线程下载来进一步加快客户端获取模型数据的速度。多线程是这样一种机制：它允许在程序中并发执行多个指令流，每个指令流都称为一个线程，彼此间互相独立。线程又称为轻量级进程，它和进程一样拥有独立的执行控制，由操作系统负责调度。多线程是多任务的特殊形式，通常，多任务有两种类型：基于进程和基于线程的多任务。进程本质上是正在执行的程序。因此，基于进程的多任务就是允许您的计算机同时运行两个或者更多程序的特性。例如，基于进程的多任务允许您在使用电子制表软件或者浏览Internet的同时运行文字处理程序。在基于进程的多任务中，程序是调度程序可以分派的最小代码单元。多线程是为了使得多个线程并行的工作以完成多项任务，以提高系统的效率。多线程技术具有以下优点：(1)充分利用CPU资源，特别是当前多核微机流行，使用多线程技术能真正发挥多核微机的并行计算优势。(2)加快程序的执行效率，如能够把需较长时间执行的任务在后台来处理。(3)提高程序的界面友好程度，如执行任务时用进度条显示执行进度。(4)加快网络传输速度，可以充分利用服务器端带宽资源。道路网络三维可视化中，模型数据包括道路模型数据、地形三维模型数据、纹理图片数据、细节层次模型数据(即LOD简化的结果，将在第四章中介绍)等组成部分，采用GZIP技术压缩后它们的数据量都得到了减小，但其数据量仍然比较可观，一次性传输到客户端后再显示三维场景势必会导致很长的用户等待时间。因此，本文中提出了使用多线程来分别下载不同种类的模型数据，并通过“边下载边渲染”的策略来减少客户端的用户等待时间：用户不需要等待所有数据都被传输完毕后再来浏览场景，而只需根据初始视点下载到局部范围内的模型数据，而后将这一部分场景渲染出来，在显示的过程中，将后续的其它场景数据通过多线程在后台下载过来，示意图如图4-10所示。图4-10客户端多线程下载示意图图4-10客户端多线程下载示意图4.4三维模型总体调度流程本研究中的地形三维模型在服务器端经过边折叠处理后，生成的结果为一个最粗糙模型M0和一系列细节层次记录信息，从模型内部实现了模型数据量的多分辨率几何压缩。当道路路线较长、原始道路模型较复杂(如山区高速公路三维模型)时，使用边折叠算法生成的最简化模型其数据量仍然很客观，因此需结合离散化处理、数据压缩、多线程等优化策略对边折叠结果进行动态调度才能最大程度地发挥多分辨率简化的效用，达到简化模型和实时快速传输的目的。以下为结合边折叠算法和优化策略海量模型数据在网络环境下的总体调度和渲染流程：服务器端预先执行半边折叠操作，将原始模型拆分成最粗糙模型M0和n层细节记录信息E0,E1,……En，并分别对它们进行离散化处理，并将处理结果保存至服务器端缓存中的哈希表中，分别记为Hash_M0和Hash_E0，Hash_E1，……，Hash_En；客户端通过多线程首先从Hash_M0下载最粗糙模型的子模型网格块，下载顺序为根据初始视点由近及远，下载策略为“边下载边渲染”，即获取到部分网格块就将三维模型渲染展现给用户；下载完最粗糙模型之后，客户端辅线程在后台从服务器端Hash_E0，Hash_E1，……，Hash_En下载细节记录信息，并将原始模型快速恢复出来，同时将恢复后的模型数据存入客户端本地缓存中备份，下一次访问道路网络三维可视化系统时，则直接从缓存中读取数据；地形三维模型的渲染过程采取“离散化分块+视点相关”的可视范围撷取策略，即只渲染视点附近的少数几个离散化子模型。第五章客户端三维模型快速绘制技术研究第五章客户端三维模型快速绘制技术研究5.1概述在道路工程网络三维可视化中，客户端是负责场景渲染并和用户交互的图形接口，要达到三维场景实时交互式绘制的要求，提高客户端三维模型绘制的效率并保持场景绘制的流畅性、帧率也是本文需要研究的重点问题之一。传统的基于CPU的复杂三维场景简化处理算法通常是根据视相关法则以及某种误差衡量标准，通过CPU计算挑选出三角形(多边形)送往显卡进行绘制，这类算法在早期显卡能力较低情况下的确提高了大规模场景的绘制效率。然而近年来，随着图形处理硬件—图形处理器(GPU)的发展和普及，图形硬件对大规模复杂的三维场景的处理和绘制能力已经得到不断提高，特别是显存的不断扩大和显卡的各种扩展能力的出现，复杂场景绘制的瓶颈已经从GPU能力转向了CPU向GPU发送几何数据的带宽。因此，如何充分利用现代GPU性能进行场景的快速绘制、减少数据在CPU和GPU之间的I/O次数和时间、解放CPU去进行其它运算处理是当前复杂场景三维可视化研究的热点问题。本章针对道路工程Web3D中客户端显卡性能参差不齐的问题，在客户端Applet程序中验证用户显卡性能和扩展能力后，首先对三维模型进行视点相关的可视范围撷取，并根据客户端GPU性能水平选择显示列表、VBO等GPU扩展功能来加速道路三维场景的渲染，从而充分利用了客户端高性能GPU图形处理能力，达到道路三维场景客户端快速绘制的目的；其次，分析了高性能GPU的直接编程技术，并研究了其在道路三维场景绘制中的应用前景。5.1可视范围撷取图5-1平锥截体O可视范围撷取是指场景绘制前将不在视点可视范围内的多边形模型予以去除，当绘制时，只将位于视点可视范围内的多边形交给负责渲染管道工作的硬件来处理，这种方法可以从一定程度上提高场景渲染的速度。在以往的道路三维可视化研究中，一般是针对每个多边形进行可视性检验，这需要循环遍历构成场景的所有多边形，将占用较多的CPU运算时间。本文中在客户端渲染三维场景时，将道路离散化子模型和恢复到原始精度的地形离散化子模型作为最小单元，采用包围盒来实现快速的可视性检验，可以明显地减少计算时间，提高三维场景绘制的帧率和流畅性，使得CPU有更多的时间去处理其它运算需求。图5-1平锥截体O计算机图形学中透视投影定义视点可视范围通常是如图5-1所示的视锥体(平锥截体)，视点为O，本文剔除多边形的算法即以此为基础进行，按以下顺序剔除视点范围以外的三维模型：(1)剔除位于O点从右至左视角180度范围以外的几何体；(2)剔除不在near、far平面之间并不与它们相交的几何体；(3)剔除与O点x向张角和y向张角同时大于视锥x向张角和视锥y向张角的几何体。以地形三维模型的渲染为例，通常情况下由于在视域范围内地形的高程起伏差别不会很大，因此一般只需执行上述剔除过程的(1)和(2)即可，如图5-2a所示。而当单个地形网格覆盖区域比较大时，甚至可以省去以上剔除过程，直接提取视点附近几个子模型来渲染，同样可以达到视锥撷取的目的，如图5-2b所示。a.网格划分较密ba.网格划分较密b.网格划分较稀疏图5-2地形三维模型的可视范围撷取示意图5.2显示列表显示列表(DisplayLists)是OpenGL中常用的用来提高三维场景渲染速度的方法，Jogl中也对该技术实现了Java语言对显示列表的支持。常规的应用OpenGL绘制三维场景的方式多为立即模式(ImmediateMode)，该模式是以循环构建每一个场景实体的点、线、面的方式来绘制场景，当场景中有很多需要重绘的相同实体(如道路三维场景中的植被的绘制)或多次需要改变的状态时，这种方式也是一遍遍的调用产生这些实体(状态改变)的函数集。而显示列表则通过预存储场景构建函数集生成实体的方法来提高三维场景绘制的性能，对于需要多次重绘的三维几何图形，或者一些可能需要多次调用的状态更改，把它们对应的函数存储在显示列表中能够显著提高性能。使用显示列表，可以一次定义三维几何图形（或状态更改），并在以后多次执行它们。Jogl程序中采用显示列表提高场景绘制效率简单实用，以下道路三维场景中央分隔带上的植被绘制为例，介绍Jogl程序中采用显示列表快速绘制植被的过程。首先是显示列表的生成：{//生成一个植被显示列表的唯一标识iTreeDL=gl.glGenLists(1);//开始生成植被显示列表,第1个参数为显示列表标识，第2个参数表示//编译显示列表中的内容,使得每次绘制该植被时不需再编译这部分代//码函数gl.glNewList(iTreeDL,GL.GL_COMPILE);//构建一个植被的纹理和几何模型的函数gl.glEnable(GL.GL_TEXTURE_2D);texTree.bind();……//显示列表结束gl.glEndList();}在需要绘制植被的地方直接调用显示列表标识的方式即可：{……gl.glCallList(iTreeDL);}5.3VBO顶点缓存VBO(VertexBufferObject)顶点缓存是基于较高性能显卡的一种提高三维场景绘制效率的OpenGL2.0及以上版本提供的扩展功能，与显示列表一样，Jogl中也实现了对该扩展的支持。VBO顶点缓存通过使用顶点数组(VertexArray)和显示列表功能的组合，将大数据量的场景顶点数据加载到高性能显卡的显存中，而不是传统的系统RAM内存中，它不仅降低了每帧的内存操作，而且还大大减少了数据在显卡和CPU之间的传输。在道路工程网络三维可视化研究中，当客户端显卡性能支持此扩展功能时，使用它能够充分发挥GPU显存的高性能存储和处理能力，从而显著提高提高道路三维场景绘制的效率。本文中，结合5.1所述的可视范围撷取算法，采用客户端VBO扩展地形三维离散化子模型的绘制过程进行了优化处理，以下为其算法流程。由于不是所有客户端GPU都带有VBO扩展，因此在本研究中首先需要验证客户端GPU是否支持该功能：{StringsVersion=gl.glGetString(GL.GL_VERSION);//OpenGL1.5前的版本不支持VBOif(sVersion.charAt(0)=='1'){charch=sVersion.charAt(2);if(ch<'5')returnfalse;}//验证当前OpenGL是否支持VBO扩展returngl.isExtensionAvailable("GL_ARB_vertex_buffer_object");}在绘制地形三维场景时，初次绘制地形场景时通过可视范围撷取处理后范围将初始视点附近的顶点预存到VBO中，在后续的每一帧绘制时，经过可视范围撷取后，当视点范围内的地形模型块需要更新时，便删除VBO中已有数据，将新地形顶点数据存入VBO，算法过程如下：{……//如果客户端显卡支持VBOif(bSupportVBO){//可视范围撷取，并验证当前视点范围内地形顶点是否需要更新if(UpdateTerrain(TerrGrids)){//删除VBO中已有地形三角形和顶点数据DeleteTerrDataOfVBO(gl);//InsertTerrDataToVBO(TerrGrids);}DrawTerrByVBO();}else{//不支持VBO,则用瞬时直接模式绘制地形DrawTerrByImmediateMode();}……}5.4GPU直接编程技术5.4.1GPU计算特性1999年8月，NVIDIA的显卡—GeForce256上首先应用了GPU(GraphicsProcessingUnits)，它是显卡的“心脏”，相当于CPU在电脑中的作用，它决定了该显卡的档次和大部分性能。GPU所采用的核心技术有硬件T&L(TransformandLighting，多边形转换与光源处理)、立方环境材质贴图和顶点混合、纹理压缩和凹凸映射贴图等。近些年来，随着GPU性能的大幅度提高普及以及可编程特性的发展，人们开始将图形流水线的某些处理阶段以及某些图形算法从CPU向GPU转移。紧接着，人们又开始把GPU计算能力应用于其他领域，包括数据统计、图像处理等。微机的图形处理器具有很高的计算性能：2004年，NVIDIAGeForce6800ULTRA可达到峰值40G每秒的浮点数据处理，而IntelPentiumIV3.0GHz采用SSE指令集只能达到6G每秒的浮点数据处理。相对于CPU，其计算能力的优势主要表现在以下几个方面[41]：(1)并行性。这一功能主要是通过多个渲染管道和RGBA四个颜色通道同时计算来体现的，另外在一个时钟周期内可以同时获取两幅甚至更多幅纹理。顶点程序的多个渲染管道意味着一个时钟周期可以并行处理多个顶点，而对于子素程序同样如此。相对于并行机而言，图形卡提供的并行性虽然很弱，但它在十分廉价的基础上为很多应用提供了一个很好的并行方案，尤其是对于图形本身的应用来说。如图2.1可以看到它具有多个并行的顶点处理器和多个并行的子素处理器。(2)高密集的运算。由于图形卡内部的内存接口位宽大于CPU上的位宽，如GeForceFX的内存位宽达256位，显然高于CPU上32位的位宽，这样整个计算的带宽大大提高。GPU相对于CPU来说，更适应传输大块的数据，虽然CPU上有Cache可以加速整个计算过程，但CPU上的Cache相对于图形卡显存来说太小，一般只有64KB-1024KB，而现在的显存大多都在128MB以上，由此可见一斑。(3)减少了GPU与CPU的数据通信。尤其是当整个应用针对图形生成的时候，不再需要在CPU与GPU之间进行多次数据交换，从而可以将CPU解放出来做其他的事情。5.4.2基于GPU的通用计算当GPU的功能越来越强时，与图形有关的处理便自然而然地从CPU向GPU转移。最先转移的是最靠近应用程序的几何变换部分；其次是局部或特殊光照效果的计算和生成。当顶点级和子素级的编程功能越来越灵活时，图形本身的处理速度和灵活性都得到了前所未有的提高。这时，基于GPU的通用计算便应运而生了。基于GPU的通用计算(GeneralPurposeGPU，GPGPU)指的是利用图形卡来实现一般意义上的计算，而不单纯是图形渲染。本文关注的就是如何利用GPU来实现矢量、矩阵的基本代数运算，然后在这个基础上实现复杂应用问题的求解，如小波变换和矢量量化等。最初的GPU所提供的功能是三维图形和特效处理的硬件加速，而当今图形硬件设计上最明显的趋势是在图形处理器内提供更多的可编程性。图5-3显示了一个可编程图形处理器的流水线中的顶点处理和子素处理的过程[43]，图中深色的处理部件分别是可编程的顶点处理器和可编程的子素处理器，在初期的GPU中这两个处理器是不具备编程能力的。可编程顶点处理器和可编程子素处理器都是硬件单元，可以运行编写的程序(需要使用特定的编程语言)，从而实现要求的渲染效果。图5-3可编程图形流水线图5-3可编程图形流水线其中，顶点处理器操作在空间的几何点上，因而比较适用于除图形绘制以的几何操作类的应用上，而子素处理器由于是操作在像素一级的单元上，具有较大容量的“纹理”空间，可以模拟纹理数据及其操作，因而可以更广泛地用于各种通用计算，是GPU用于通用计算的最主要的平台。子素处理器可以用于二维、三维和四维浮点向量的向量数学操作，其中包括、减、乘、乘加、内积、最小值和最大值等。硬件对向量取反和移位的支持能推广向量数学指令来提供取反、减法和外积。同时能够提供向量比例除法和向正规化。子素处理器还支持纹理操作，使得处理器可以通过一组纹理坐标存取理图像，然后返回一个纹理图像过滤的采样[41]。如果想要对CPU进行编程，我们可以选择C++、Java等语台进行编写、调试、编译，同样人们已经开发出直接对GPU进行编程的语言，这类语言称为实时绘制语言，它可以方便用户书写各种不同功能的GPU绘制程序以及对其绘制程序提供控制，以使用户可以直接地调用GPU硬件的高级功能。关于这类语言的究工作，近年来具有较大影响的是[44]：OpenGLShadinglanguage，斯坦福大学的RTSL，NVIDIA的Cg，Microsoft的HLSL，其中前两种语言为当前GPU编程应用的主流，本研究采用的客户端渲染引擎JOGL都支持这两种编程语言。国内外学者将GPU用来做一些通常意义计算的例子很多，从图形输出流水线以外的非绘制处理，到碰撞检测[28，29]、偏微分方程数值求解[30]、代数运算[31]、优化计算[32]、运动规划、几何计算等。笔者认为：采用可编程GPU技术可以大幅地提高道路工程Web3D系统客户端三维场景的绘制效率，将客户端CPU从复杂的三维场景绘制运算中解放出来进行其它运算，因此将该技术运用于道路工程Web3D可以拓宽本研究的应用领域，如基于Web3D系统的可视化协同设计、三维空间道路路线平纵设计方案优化等等。第六章Web3D与WebGIS集成及道路工程信息查询第六章Web3D与WebGIS技术集成6.1概述与传统的桌面单机地理信息系统相比，WebGIS(网络地理信息系统)具有使用范围更广、可扩展性更强、维护更方便、对客户端硬件要求低等显著优点，是地理信息系统技术发展的热门方向，WebGIS自产生以后便被大量应用于Internet环境下的各种与空间位置相关信息的发布。随着技术的发展，WebGIS的应用领域几乎被扩展到GIS的各个方面。目前WebGIS已经被大量的应用于在资源、环境、防震减灾、城市建设、农业、交通、旅游、通讯、电力、教育、人口、海洋以及军事等领域。国内外对WebGIS的应用有着浓厚的兴趣，并且做了大量的研究，在理论和实践上都取得丰硕的成果图图6-1WebGIS应用实例a.面向公共服务b.面向行业应用从应用方向来说WebGIS的可分为两大类，一类是基于Internet的公共信息服务。这类WebGIS为公众提供交通、旅游、餐饮、娱乐、房地产、购物等与空间信息有关的信息。这一类的应用在最近几年发展很快，国内外都产生了很多成功的应用，其中较为典型的如GoogleMaps和Mapbar。图6-1a所示GoogleMap的即为面向公众服务的应用示例。另一类是Internet/Intranet下的具体行业应用的内部事务管理和查询，如城市管网、电力线、交通线路、安全监控等都是这类WebGIS的典型应用，，如图6-1b所示即为面向实时交通路况信息查询的WebGIS应用实例。这类应用的特点是需要在地图上添加和显示实时信息，将这种WebGIS技术与Web3D结合起来则可以为道路网络三维可视化提供更宏观的视角来进行信息展示和查询。WebGIS先后经历了CGI、ServerAPI、基于Plug-in/Activex、JavaApplet等实现技术。随着时间的推移，更多新的Web技术为WebGIS所采用。Web2.0的核心技术之一的Ajax随着GoogleMap的推出被引入到WebGIS领域。GoogleMap引发了WebGIS开发方式的变革，自此之后主流的WebGIS应用几乎都采用该方式实现，如国外的Yahoo!地图、微软LiveSearch地图，国内的51地图、灵图等均使用Ajax开发，显著增强了客户端的可用性和响应效率。但这些WebGIS应用主要是面向公众查询服务(即上文所述的第一类应用)，在服务器端都是基于WMS(WebMapService)地图服务，即服务器端预先生成多层地图的静态图片，并将每一层的图片分成不同的方格块(Tiles)，客户端通过Ajax技术调用这些静态图片。这种基于预先生成图片的WebGIS服务器端技术虽然可以使得客户端操作更加流畅，但对于像上文所述的第二类应用中需要在地图上快速添加复杂图元则显得无能为力。MapXtreme是上世纪末开始进入中国市场的MapInfo公司推出的一种WebGIS开发平台，该平台主要是面向具体的行业应用。它提供了两种开发模式以应对不同要求的应用：基于JavaApplet的瘦服务器端-胖客户端结构与基于.NET的胖服务器端-瘦客户端结构，这两种结构各有优劣，都有比较广泛的用户市场，两者的对比如表6-1所示。表6-1两种WebGIS结构对比瘦服务器端-胖客户端胖服务器端-瘦客户端适用规模中小型应用各种规模均可对客户端硬件要求低高逻辑处理位置服务器端大部分位于客户端逻辑处理能力高低操作流畅性一般较好更新和可维护性仅在服务器端客户端、服务器端地图格式栅格矢量/栅格本研究中，综合分析了系统需求后，笔者采用了基于ASP.NET胖服务器端-瘦客户端结构的MapXtreme作为道路网络三维可视化的宏观信息查询平台，并运用Ajax技术对其做了性能上的改进，将WebGIS与Web3D集成起来联动展示道路设计及建设的属性信息，远程用户可同时在二维电子导航图和三维交互式场景浏览和查询道路设计数据和工程建设信息。6.2基于MapXtreme的WebGIS平台构建6.2.1MapXtreme简介MapXtreme是MapInfo公司推出基于Internet/Intranet的地图应用平台，其地理信息功能逻辑处理核心是该公司著名的单机GIS工具-MapX。它采用标准的TCP/IP协议，通过HTTP进行文档和数据传输，在浏览器为标准的HTML语言，