cq9电子平台网站：数字地形模型LOD

　　 逐点插入算法  从构网过程来看，分割合并算法和三角网生长算法属于静 态剖分过程，在整个三角网形成过程中，新点的介入并不 会破坏已经形成的三角网。而逐点插入算法则是一种动态 的构网过程，新点的插入会导致已有的三角网进行改变。 该算法最早由Lawson在1977年提出，随后 LeeSchachter(1980)、Bowyer(1981)、Watson(1981)、 Sloan(1987)、Macedonio和Pareschi(1991)、Floriani和 Puppo(1992)、Tsai(1993)等人先后对其进行了改进。逐 点插入算法的基本过程为：

　　 规则格网，通常是正方形，也可以是矩形、三角形 等规则格网。规则格网将区域空间切分为规则的格网 单元，每个格网单元对应一个数值；  数学上可以表示为一个矩阵，在计算机实现中则

　　 离散LOD的基本原理是建立原始模型几个不同精度的几何 模型，每个模型均保持一定的细节层次，在渲染时会出现 视觉“跳跃”。为了从根本上解决离散LOD技术的缺陷， 1996年Lindstrom和Koller提出地形绘制的连续LOD概念， 但是在不同细节层次切换时仍然有所谓“poping”现象。  目前，比较著名的LOD算法有：基于TIN的层次结构的渐 进格网（VDPM，View-Dependent Progressive Meshes） 算法、实时自适应优化格网（Real-time Optimally Adapting Meshes）算法、基于Grid树结构的 GeoMipmapping几何多分辨率算法和四叉树(QuadTree) 算法。

　　 等高线模型表示 高程，高程值的集 合是已知的，每一 条等高线对应一个 已知的高程值，一 系列等高线集合和 它们的高程值一起 就构成了一种地面 高程模型

　　 等高线通常被存成一个有序的坐标点对序列，可 以认为是一条带有高程值属性的简单多边形或多边 形弧段；  由于等高线模型只表达了区域的部分高程值，往

　　 在地形平坦的地方，存在大量的数据冗余；  在不改变格网大小的情况下，难以表达复杂地形 的突变现象。

　　形记录的指针和它的两个顶点的记录的指针；也可 以直接对每个三角形记录其顶点和相邻三角形。

　　空间数据模型通过空间数据组织和空间数据库对空间对象及 其关系进行描述，对空间对象进行提取。空间数据模型有两 种分类方法： （1）从认知的的角度：分为基于对象（object based）的模 型、基于网络(network based) 的模型和基于场（field based ）的模型； （2）从表达的方式上：分为矢量数据模型、镶嵌数据模型和 组合数据模型。

　　形记录的指针和它的两个顶点的记录的指针；也可 以直接对每个三角形记录其顶点和相邻三角形。

　　 用数学方法来表达，可以采用整体拟合方法，即根 据区域所有的高程点数据，用傅里叶级数和高次多项 式拟合统一的地面高程曲面；  也可用局部拟合方法，将地表复杂表面分成正方形 根据有限个点进行拟合形成高程曲面

　　 四叉树是一个二维数据结构，由于四叉树模型与矩形格网 DEM坐标系有着天然的相似性，因此对于描述地形来讲， 它是很理想的一种数据结构。  QuadTree算法将整个地形区域看作四叉树的母节点，地 形母节点覆盖整个地形区域。树中的每一个节点都覆盖地 形中的一块相应的矩形区域。上层的节点涉及的采样点较 少，用其来表示地形时具有更高的绘制效率；但具有较低 的分辨率，地形表示的误差较大。底层地形的分辨率高， 误差小，但绘制效率低。在满足给定误差阈值的条件下， 动态地选择地形节点来实现对地形模型的连续多分辨率表 示。同时为了提高运算效率，要先对数据节点进行预处理， 计算每一个地形节点的误差精度，从而确定简化过程中节 点操作的执行顺序。

　　② 最小角最大准则 有很多种方法可以对三角形进行剖分，无 论怎样进行三角剖分，采样点的高程值都 是最准确的。就这个层面来看，无论怎样 剖分效果差别都不大，但是就其外观的自 然性而言，还是能比较出相对较好的一种 效果。

　　 格网DEM的另一个缺点是数据量过大，给数据管 理带来了不便，通常要进行压缩存储； DEM数据的无损压缩可以采用普通的栅格数据压缩 方式，如游程编码、块码等；

　　多分辨率LOD的基本思想是：用不同的LOD表示 一个三维场景，LOD级别取决于可视区域与视点 的关系，并随着视点移动更新各个区域LOD的级 别。多分辨率LOD在地形应用中分为规则格网和 不规则格网两种，国内外学者对此都进行了深入 研究，相关文献很多，相对而言，规则格网LOD 技术较为成熟。从提出LOD应用于地形三维可视 化到现在，其研究发展大致分为离散LOD（DLOD， Discrete LOD）、连续LOD（CLOD，Continuous LOD）和多分辨率LOD（MRLOD地型模型，MultiResolution LOD）。

　　 第一步，读入TIN模型，并建立顶点与三角形的邻接关系；  第二步，根据顶点与三角形的邻接关系，计算每个顶点和 每条边的误差；  第三步，根据边误差建立边误差链表，并从小到大排队；  第四步，从边误差表中误差最小的边开始，依次进行收缩， 同时建立顶点层次树结构，并按顶点误差大小依次排列；  第五步，根据视点的位置依次判断顶点树中的顶点误差是 否超出给定的阈值，若是，则对该顶点进行分裂操作；否 则，进行顶点合并，同时更新顶点层次树结构；  第六步，重复第五步，直到满足要求为止。

　　镶嵌数据模型的基本思想是：可以用相互连接在一起的网络 来覆盖和逼近空间对象。数字高程模型通常用于刻画具有连 续变化特征的空间对象，目前最典型的应用就是通过连续网 格单元来实现地形曲面的模拟，应归类于基于场的镶嵌数据 模型.

　　当地形数据呈规则分布或由格网DEM向TIN转换时，其三角 剖分与不规则数据域的三角剖分有很大的差异。由于规则格 网分布采样数据的特性，对其进行三角形剖分可以有两类方 法： （1）直接对角线）Delaunay三角剖分法

　　Delaunay三角网  ① 空外接圆准则  Delaunay三角形外接圆内部包含其它点的性质被用作从一 系列不重合的平面点建立Delaunay三角网的基本法则。 Delaunay三角形由三个相邻点连接组成，这三个相邻点对 应的Voronoi多边形有一个公共的顶点，这个顶点同时也 是Delaunay三角形外接圆的圆心。在进行Delaunay三角 形剖分的过程中，每一个三角形都要经过空外接圆检测， 目前常用的计算方法是计算三角形外接圆的圆心和半径， 然后计算圆心和其他点的距离，通过距离和外接圆半径的 比较进行判断，这种判断方法的计算包含了开方、除法、 平方等复杂的运算。

　　 线模式：等高线是表示地形最常见的形式。其它的 地形特征线也是表达地面高程的重要信息源，如山脊

　　第一步，定义包含所有数据点的初始包容盒，并 对该包围盒进行初始三角剖分。形成矩形包容盒 的方法是找出数据域的坐标极值点，然后用这些 点形成包容盒。 第二步，对所有数据点进行循环（设当前处理的 数据点为P），在已经存在的三角网中，查找包 含P点的三角形t，将P与t的三个顶点相连，形成t 的三个初始三角剖分，再用LOP算法对初始三角 剖分进行优化处理。 第三步是对外围三角形进行处理。

　　渲染海量三维几何数据需要大量的计算机资源， 很多时候已经远远超出了目前图形设备的承受能 力，解决超大规模数据问题成为三维场景实时绘 制的最大瓶颈。图形硬件GPU的飞速发展极大地 提高了图形渲染的效率，但是对于海量数据而言 仍是不堪重负。若不应用LOD技术对数据进行分 层多级显示很难实现地形的实时可视化。多分辨 率LOD算法不仅能简化数据，还能使视觉效果更 接近真实。