结合分形的多分辨率ＬＯＤ地形建模简化技术研究

摘要：文章介绍了多分辨率LOD地形及分形地形建模技术的相关理论和研究技术，在深入研究地形建模和简化的典型算法的基础上，提出了结合分形的多分辨率LOD地形建模简化技术。

关键词：分形地形；多分辨率；LOD地形；地形建模

中图分类号：TP391文献标识码：A文章编号：1009-2374（2009）07-0005-02

一、多分辨率LOD地形的概念

（一）地形模型的几何描述

本文所讨论的地形是有一定的要求的，首先地形必须是一方形区域，且大小必须为（2n+1）×（2n+1），采样点均匀的格网。通常采用高度图来保存地形模型数据，由于地形模型的规则性，只要按二维顺序保存地形的高度数据，然后在需要时根据二维到三维的映射就可以很容易地得到三维数据。

（二）多分辨率连续地形生成

在图形硬件处理中，对几何模型的渲染最后都转换为对三角形的渲染，因此多分辨率连续地形生成就是要根据视点位置和地形的起伏程度生成不同细节层次的地形三角形网格，并尽量使三角形网格的生成简单、避免冗余，以减少不必要和重复的图形渲染，提高效率，增强实时性。但是由于地形三角形网格在生成中不同的细节层次之间必然要出现层次上的差异，因此就会出现裂缝（Cracks）和T型头（T-Junctions），这就使地形变得不连续，如图1所示。因此，为了保持地形网格的连续性，多细节层次地形简化的一个关键就是要消除裂缝。消除裂缝就是要保证在不同细节层次的相邻块的层次之差不能够大于1。

二、多分辨率地形的表示过程

表面多分辨率表示和绘制的典型处理步骤如图2所示。图中椭圆框中的内容是各种形式的“数据”，而矩形框中的内容总表示“处理”。

整个框图分为两部分。第一部分建立多分辨率表示，它通常是一个离线步骤，即作为非实时的预处理。该部分读取输入数据，进行必要的初始化预处理之后，按照一定的算法产生对输入表面的多层次（多分辨率）表示结构，每一个层次具有不同数量的面元，是对输入表面的某种程度的逼近。第二部分是可视化部分，它往往是一个循环。每次循环都是先读取约束绘制的条件（如观察位置、误差门限、输出面元数量），然后通过遍历上述多分辨率表示结构，为不同的子区域选取适当分辨率的表示。不同的选取算法所得到的结果的表示形式不尽相同：有的得到多边形网格，即可直接用于绘制当前一帧图像;有的则不是网格形式，还需要进一步生成网格，然后方可用于绘制。

三、多分辨率地形的基本特征

表面的多分辨率表示方面的研究主要集中在多分辨率表示的构造策略和构造方法上。不同的策略和方法导致不同的模型。我们从模型的基本特征上来认识表面的多分辨率表示。多分辨率模型的基本特征包括：面元形状、数据结构形式、细节管理方式、层次结构类型、构造途径、误差测度等。

（一）面元形状

对表面的表示总是以网格来逼近的。网格的每一个网孔称为一个面元。面元的形状是一个多边形，大多数情况下为三角形，也有四边形、六边形等其他形状。以三角形为面元对表面实现网格化逼近被称为表面的三角化（Triangulation）。三角化网格中的面元有的是任意三角形，有的是直角三角形，还有的是等边三角形。面元是任意三角形的网格被称为不规则三角化网络（TIN），每个面元三角形相似的网格称为非TIN网格。

（二）结构形式

表面的多分辨率表示可看作是对输入表面的一系列网格近似。每个近似表示的逼近程度不同，称为具有不同层次的细节。将这些近似表示结构起来的方式有两种：一种是离散的序列结构，另一种是有机的层次结构。序列结构的多分辨率表示不需要复杂的数据结构，它就是在不同的k个离散分辨率上产生一个对象的k个模型，并保存起来。绘制该对象时，基于某些准则（如距离），从这组模型中选取某个即可。

（三）细节管理方式

细节层次的管理有显式LOD和隐式LOD两种模式。在显式LOD下，网格表面序列中的每一个都显式地满足给定的逼近误差条件;而在隐式LOD模式下，在同一个网格表面上不同部分的逼近误差可能有较大差别。尽管网格表面序列是由粗略到精细，但不能保证其中接续的两个网格表面之间有指定数量的精度提高，而面元数量的增加却可以控制。可以从隐式LOD的模型获得显式LOD的模型。

（四）层次模型的类别

根据其组织几何信息的方式，多分辨率表面的层次模型可分为两类：一类是基于面元层次的模型，一类是基于顶点层次的模型。面元层次模型是较为传统的多分辨率表示模型，这种模型着重描述不同细节层次的网格面元之间的关系。优点是便于在对表面做近似描述时保持其拓扑结构。基于这种模型发表的多分辨率表示及可视化的算法较多。面元层次模型可进一步分为两个子类：层次子分模型和金字塔面元模型。这两种模型最先是由DeFloriani和Puppo针对地形表示提出的。后来DeFloriani还提出了一般面元层次模型“多重三角化”（Multi-Triangulation），并指出，现有多分辨率模型都可理解为多重三角化MT的特例。

顶点层次模型是按照不同逼近程度的近似表面中顶点之间的关系来构造层次的。层次中的每个节点对应一组顶点，即一个节点的所有子节点所表示的顶点则是在作更精确的近似时用来替代本节点所对应的顶点的。每个节点都可存贮它所对应的误差度量。由于仅有顶点信息不足以确定网格，所以还需要有保存如何形成网格的信息。可视化时，选取了适当的简化表示后，还要作“生成网格”的处理。

（五）层次的构造顺序

从构造多分辨率表示的各个层次的先后顺序来看，已发表的算法可以分为两类方法：一类是求精法（refinement），另一类是简略法（decimation）。求精法是从对输入表面的一个最粗糙的近似网格开始，迭代地插入一个或多个顶点或面元到网格中，从而增加网格的细节，直到使网格符合所要求的最高近似精度。简略法则是从输入表面的一个最精确的近似网格（甚至就是输入模型本身）开始，然后迭代地通过删除顶点、缩减边线或面元等方法来简化网格，直到获得允许的最粗表示。

（六）误差测度

多分辨率层次模型中的每一个近似网格与输入表面之间存在偏差。如何度量这种偏差，有多种方法。从度量范围上看，有局部误差和全局误差。局部误差是指近似网格的顶点或面元与输入表面之间的偏差；全局误差是指整个近似网格与输入表面之间的偏差。从度量的尺度上看，有的采用欧氏距离，有的是用Hausdorff距离，有的用映射距离，还有采用诸如曲率等高次误差测度。在许多面向可视化的层次模型中，通常采用屏幕空间的误差测度以及一些如颜色、纹理等非几何特性的方法。

四、简化约束条件

到目前为止，地形可视化方面已建立了多种地形模型简化约束条件。多分辨率模型中按离散LOD方式选取简化表示时，会导致切换LOD时在画面上产生视觉“跳变”，并导致很难调节帧速率，这在要求恒定帧速率的应用中是不可取的。因此，在可视化阶段，最主要的约束简化的条件是“视野相关的简化（View-dependent Simplification）”，即要求实时地基于观察者的视点位置等自适应地简化对象的表示，只要满足指定的允许误差。这种方法以连续LOD方式选取简化表示，可以克服上述问题。

构建多分辨率表示的过程是以不依赖于视野的方式离线进行的，为了支持可视化时依赖于视野来选取简化表示，一方面要求在两个过程（建模和选取）中都采用同样的简化操作，另一方面要在模型中保留可供计算与视野相关的误差测度的信息。这样在可视化阶段才能通过一些预定的简化操作（如顶点消去、边收缩等）和指定误差选取出与视野相关的简化表示。

Lindstrom等人率先将视野相关的简化技术用于地形的实时绘制。Duchaineau等以及Hoppe等相继发表了类似的用于地形可视化的算法。这些算法的基本简化操作是顶点消去。Hoppe还采用边收缩操作将简化技术推广到具有任意拓扑结构的不规则网格上。Luebke和Erlkson提出了一种基于层次的数据结构，运用顶点聚合操作完成与视野相关的简化的处理框架。

约束简化的另一个条件是误差门限。在可视化阶段的简化中，这一门限通常是用户在屏幕空间指定，而简化算法往往是先计算简化表面的几何误差，然后将该误差投影到屏幕空间与用户指定的门限比较。

帧速率也是约束简化的一个条件。用户指定帧速率等价于限定了每个简化表示的三角形面元的数目，尽管这种对应关系是与平台有关的。

五、结语

本文首先介绍了多分辨率LOD地形的相关概念、理论和特征，随后在研究数字地形模型及分形理论后，提出一种新的地形建模方法，即利用DEM数据生成地形框架，运用分形理论生成细节。框架生成过程中采用层次细节简化技术简化地形，提取大致描绘地形总体形状特征的数据，再运用分形理论进行细节绘制，并结合视点变化提出新的面片可见性判别方法。

作者简介：蒋军荣（1974－），男，广西全州人，永州市勘测设计院工程师，研究方向：测绘。