（水利水电工程专业论文）大范围三维地形实时显示研究.pdf

华中科技大学硕士学位论文 摘要 大范围三维地形显示能够将自然界中的真实地形地物仿真显示出来，用户可以比 较直观地获取各种信息，因此各个领域都有较广泛的应用。 大范围地形由于其数据量很大，在实时显示的时候，系统需要进行的数据处理量 大大超过系统硬件的处理能力。要想建立一个比较实用的系统，必须对软件算法进行 改进和采用优化模型，将实时显示时系统需要处理的数据降低到系统硬件可以承受的 范围。这其中比较有代表性的是l o d 技术。 l o d 技术就是在三维地形实时显示时所采用的细节省略( d e t a i le l i s i o n ) 技术， 也就是系统生成地形时基于一定的准则采用不同分辨率的地形模型。它的发展经历了 离散l o d ，连续l o d 和多分辨率l o d 三个阶段。 当前，各种虚拟现实开发环境所采用的主要是离散l o d 模型。以业界比较成熟 的v e g a 为例，由于v e g a 较好的利用了基于s g i 工作站的p e r f o r m e r 类库，地形的三 维显示速度较快，并且由于将大量的构建系统所需要的功能集成为v e g a 的模块，使得 利用v e g a 开发系统较为便利。但是由于离散l o d 模型自身的不足，使得地形模型数 据较大而系统的实时显示效果不理想。 本文正是针对通过软件技术的改进以建立大范围三维地形实时显示系统的思想， 对大范围三维地形实时显示实现进行了有益的研究。本文在对三维地形生成原理研究 的基础上，提出了自己的基于多分辨率l o d 模型的改进算法。并提出了具体的进行 敏感区域识别，三角形网格构建，以及进行模型顶点重要度计算和实时处理所需要的 数据结构、处理过程和计算方法。通过验证，本算法能够较好地提高地形显示的速度， 并且由于算法所采用的技术移植性较好，因此本算法能够很好好的与v e g a 技术结合提 高三维地形显示的效果。 关键字：大范围三维地形，三维地形显示，层次细节模型，多分辨率显示，虚拟纹理 华中科技大学硕士学位论文 a b s t r a c t l a r g e s c a l et e r r a i nr e p r e s e n t i n gc a ns i m u l a t et h er e a lt e r r a i nf o rt h e u s e lt h eu s e r c a ne a s i l y g e tm a n yk i n d so fi n f o r m a t i o n i t i sau s e f u l w a yf o rt h e u s e rt o g e tt h e i n f o r m a t i o na b o u tt e r r a i n i ti sb e i n gw i d e l yu s e di nm a n yf i e l d l a r g e s c a l et e r r a i nh a st h ec h a r a c t e r i s t i co fh a v i n ga b u n d a n c ed e n s e d a t a s ot h ew o r kt o r e n d e rt h et e r r a i no nr e a l - t i m ei sb e y o n dt h ea b i l i t yo ft h eh a r d w a r e f o rb u i l d i n gag o o d s y s t e mt od i s p l a y t h el a r g e - s c a l et e r r a i n ，w em u s ta m e l i o r a t ea n do p t i m i z et h et e r r a i n r e n d e r i n ga l g o r i t h m t or e d u c et h en u m b e ro ft h ed a t aw h i c ht h es y s t e mm u s td e a l 谢m t of i t t h eh a r d w a r e a n d u s i n gl e d m o d e li sa i m p o r t a n tw a y l o di st h et e c h n i q u eo fd e t a i le l i s i o ni n3 - dt e r r a i nr e n d e r i n g t h es y s t e mu s e st h e d i f f e r e n tm o d e l s ，w h i c hh a v ed i f f e r e n ts o l u t i o n ，b ys o m ec o d e t h i so p t i m i z e d t e c h n i q u eh a s b e i n gd e v e l o p e d i n3s t e p s ：d i s p e r s el e d ，c o n t i n u o u sl e d ，m u l t i - s o l u t i o nl o d t o d a ym a n y v i s u a lr e a l i t y d e v e l o p i n g s o f t w a r eu s i n g d i s p e r s el e d b y c a s eo f v e g a , v e g a u s i n gt h ep e r f o r m e rb a s e do ns g ih a r d w a r e ，s ot h e3 - dt e r r a i nc a r lw e l lr e n d e r i n g ，a n d m a n y f u n c t i o n si nb u i l d i n gt h es y s t e mo f l a r g e - s c a l et e r r a i nr e p r e s e n t i n ga r ei n t e g r a t e da s t h em o d u l e si nv e g a s ot h eu s e rc a n r a p i d l yd e v e l o p t h es y s t e m b u tf o rt h ed e f i c i e n c yo f d i s p e r s el o d s o t h ee f f e c to f t e r r a i n d i s p l a y i n gi sn o tg o o d t h i sp a p e rh a st h er e s e a r c hi ne s t a b l i s h i n gal a r g e s c a l et e r r a i nr e p r e s e n t i n gs y s t e mb y t h ew a y s o f o p t i m i z i n g t h er e n d e r i n ga l g o r i t h ma n d u s i n go p t i m i z e d m o d u l e t h i sp a p e rh a s r e s e a r c h e di n l a r g e s c a l e t e r r a i nr e n d e r i n ga l g o r i t h mb a s e do nt h er e s e a r c h i n go nt h e p r i n c i p l eo ft h e 3 - dt e r r a i nd i s p l a y i n g a n dt h i s p a p e re x p o s eao p t i m i z e dt h et e r r a i n r e n d e r i n ga l g o r i t h mb a s e do nl e d ( 1 e v e lo fd e t a i l ) b a s i n gt h ea l g o r i t h mb e i n ge x p o s e d ， t h i sp a p e rr e p r e s e n t st h ed a t as t r u c t u r e ，t h es t r a t e g ya n dt h ef o r m u l af o rr e c o g n i z i n gt h e s u s c e p t i v i t yr e g i o n ，b u i l d i n gt h et r i a n g u l a ri r r e g u l a rn e t ，a n dc o m p u t i n gt h ei m p o r t a n c eo f t h ea c m e b yv a l i d a t i n g ，t h ea l g o r i t h mc a na c c e l e r a t et h e3 - dt e r r a i nr e n d e r i n g ，a n dt h e a l g o r i t h mc a ni n t e g r a t e w i t ht h ev e g a k e y w o r d s ：l a r g e - s c a l e3 - dt e r r a i n ，3 - dt e r r a i nr e p r e s e n t i n g , l o d ( 1 e v a lo fd e t a i l ) ， m u l t i - r e s o i n t i o nr e p r e s e n t i n g ，v i r t u a lt e x t u r e l i 华中科技大学硕士学位论文 1 绪言 1 1 引言 地形，是地貌和地物的统称，地貌是地表面高低起伏的自然形态，地物是地表面 自然形成和人工建造的固定性物体【2 1 。 在过去，由于科学技术的水平较低，人们只能通过米堆或者土堆来近似地模拟地 形，这种方式只能大略地表达地形的特征和彼此之间大概的相对位置。随着欧洲工业 革命的开始，科学技术有了很大的提高，地图学开始出现，地图开始成为人们描述地 形的工具。但是这种方式主要表达了地形的二维信息，通过不连续的等高线来反应地 形高程信息，人们获取信息不方便，信息量也较少。上个世纪六十年代以后，随着电 子计算机技术的发展，电子地图开始出现，同时随着计算机图形技术的发展，地形的 二维重建在计算机上得以实现。 进2 , j k 十年代以后，随着电子技术的发展，电子计算机的性能水平得到了很大的 提高，中央处理器的运算速度和信息存储设备的存储容量得到了很大的提高，其存储 器能实现将大型文件映射至内存的能力，使得许多较为复杂的应用可以通过计算机进 行处理，并且由于许多专用的处理芯片( 例如图形处理芯片) 投入应用，使得许多比 较复杂的特殊运算不需要通过c p u 完成，这样就大大提高了计算机系统对图形处理 的速度，计算机仿真技术得到了很大的提高，通过计算机显示三维地形成为可能。 三维场景仿真技术是近几年计算机图形学领域中发展起来的一种高度逼真地模 拟人在自然环境中视、听、动等行为的人机交互技术。它在实时仿真领域，如飞机汽 车驾驶训练、战场作战模拟等具有重要的应用。这些系统皆涉及大规模复杂虚拟地表 模型的动态生成。 大范围地形三维显示就是将计算机存储或者计算出来的三维地形数据，借助计算 机仿真技术，以三维的方式在输出设备上进行显示。将大范围三维地形显示在计算机 上具有很强的应用价值，例如将大范围三维地形显示与地理信息系统相结合，将三维 华中科技大学硕士学位论文 l j $ # i l r i i _ _ _ _ i i 地形显示与地理信息系统强大钓数据管理和处理功能相结合，通过地形显示将地理信 息系统所管理地形地物数据通过计算机屏幕逼真地显示出来，并在其上附加系统数据 挖掘或决策过程产生的结果，铋及用户要求的查询结果。这样使得使用者可以比较直 观的获得系统希望提供的各种信息，了解系统实时进行处理的结果。提高了系统的应 用性。 由于大范围地形三维显示提供的信息简单、直观、易于接受，符合入们的获取信 息的习惯，系统交互性强，因此在相当多的领域中得到了应用，尤其是应用于与地形 相关的专业技术性管理，如土地资源，矿产资源，交通运输，生态环境，防灾减灾， 水电建设，建设规划，邮电通信，安全生产，国防军事等可视化表达的技术性管理方 面。 在我国，大范围三维地形研究虽然受到技术条件和研究经费的制约起步较晚，但 近年来发展也十分迅速。一些研究机构和高等院校也对此进行了较深入的研究，有相 当数量的在建和已完成的地理信息系统、数字城市等系统在显示应用上采用了大范圉 地形三维显示。 1 2 系统应用存在的问题 当前，虽然我国有很多的科研机构和高等院校进行了有关大范围地形三维显示的 研究，也有相应的应用系统投入了使用。但总体来看，系统应用成果并不突出。 虽然得益于高速发展的c p u 和专用图形处理器，使得现今的图形工作站性能得到很 大的提高，但是大范围地形显示中地形起伏变化大地形复杂度较大，地形数据量较 大。硬件系统的性能距离地形仿真的需求仍相当遥远。换句话说，当前图形生成的速 度相对于通常大范围三维地形的规模来说仍存在楣当大的差距。铡如，在华中科技大 学水电与数字化工程学院所承接地数字襄樊项目中，襄樊市1 6 0 平方公里的面积，地 形数字化后的数据达到4 0 0 0 g ，并且其中有相当比例韵是空间数据，如此大量的数据 是不可能在显示时进行实时处理的。由于硬件系统的能力不能满足系统功能需求的发 展，虽然可以通过一定的数据压缩、降低系统一定的性能来实现大范围三维地形实时 显示，但是能够满足这样的要求的硬件系统也是价格昂贵的高端图形工作站。因此只 2 华中科技大学硕士学位论文 一t = _ 2 日_ 目_ i _ _ 目_ _ t = _ _ _ _ - _ 口_ # l l _ - _ _ z _ _ 有通过软件架构的改进，采用优化模型和算法，减少系统需要实时处理的数据量，加 速图形生成。 图形加速技术也是随着人们对三维地形实时显示的研究不断深入而不断有新的 发现。首先，在现实中人们在自然环境中所看到的景物，只是整个地形中很小的一部 分，而有相当多的地形地物是不在我们的视线内或者是看不到的，由此首先产生了消 隐和裁剪处理以及地形分块调入技术。消隐和裁剪也就是将在视线内出现的地形地物 中背向观察者的、应该被挡住看不见的一部分模型去掉，只保留可见部分。这项技术 现以广泛应用于三维地形生成技术中，甚至有些硬件厂商已将相关处理集成到硬件 中，通过硬件来实现该技术。地形分块技术就是将系统地形数据分成若干个小地形， 在实时显示的时候根据观察者的位置，相应的调入观察者视线相关的地形，这项技术 比较有代表性的就是m u l t i g e n p a r a d i g m 公司推出的视景驱动软件v e g a 所应用的a o i 技术。它将数据分成若干个小块地形( 在v e g a 中称为区域) 并设定以观察者视点为 圆心的圆周( 在v e g a 中称为a o i ( a r e a o f i n t e r e s t ) ，即兴趣区域) ，在实时显示时随 着视点的移动，系统动态的调入这个圆周所触及到的所有小块地形进行显示，避免了 将所有的地形调入系统进行显示处理。 此外，在生活中，我们都知道，当我们远眺时，对于远处的景物，我们看得并不 是很清楚。同样，在计算机三维显示中，这些景物在计算机屏幕上的投影所占用的象 素是非常少的，构成其模型的每个三角形的投影就更少了，甚至多个三角形被投影到 同一个象素中，同样许多纹理象素也可能被压缩到一个图像象素中，因此这些模型细 节是否需要全部显示对于提高系统显示效果没有什么影响。由此我们可以通过对地形 模型精度和纹理映射分辨率的调整来降低实时显示时需要进行的处理。首先，在纹理 映射中引入了m i pm a p p i n g 技术，它的思想是：在多分辨率的地形模型中运用多分辨 率的纹理影像，并根据视点的变化选择不同分辨率的纹理。它把一幅大纹理影像分割 成一系列长和宽都为2 的指数幂的小块影像。在多边形距离观察者较近的时候贴较高 分辨率的纹理，较远时贴低分辨率的纹理。降低分辨率的方法是将原纹理分辨率缩小。 为了计算的简便通常是将原纹理按2 的幂次方不断的缩小。如果原来的纹理是8 x 8 的 则其m i p m a p 为4 x 4 ，2 x 2 ，1 x 1 。以至于产生一个对应于同一多边形的纹理倒金字塔。 华中科技大学硕士学位论文 在实时显示时，当进行纹理映射时选择可以覆盖该多边形的分辨率最小的纹理数据进 行映射，通过这种方法降低系统负载。m i pm a p p i n g 技术也是一项发展的比较成熟的 技术，同样现在有些硬件提供商也将这项技术集成到硬件系统中，可以通过硬件来实 现相关功能。 另外就是产生了l o d ( 1 e v e l o fd e t a i l ) 技术。所谓l o d 技术，就是在三维地 形实时显示时所采用的细节省略( d e t a i le l i s i o n ) 技术。这项技术由c l a r k 于1 9 7 6 年 提出，其基本思想是：如果用具有多层次结构的物体几何描述一个场景，即场景中的 物体具有多个模型，其模型间的区别在于细节的描述程度，那么实时显示时，就可以 使用细节较简单的物体模型来提高显示速度。由于采用l o d 技术可以大量减少大范 围三维地形实时显示时系统需要处理的数据量，代表了三维地形实时显示加速技术的 发展方向，有许多的学者投入了大量的精力在这项研究中，当然由于地形显示技术较 为复杂，要想找到很好的解决方案还需要进行更多的工作。这也是本文主要的研究方 向。 1 3 研究意义 通过前文所述，我们可以知道大范围三维地形实时显示对系统硬件的性能有很高 的要求，在我国由于高端图象处理服务器的价格非常昂贵，不是一般系统应用能够采 用的，大范围三维地形实时显示在我国当前的应用范围并不是很广泛。为了降低系统 应用对于硬件的依赖，我们只有从软件架构、模型设计和采用优化算法入手，减少 系统实时运行时需要进行的各种处理，降低系统运行时的硬件负载，从而降低大范围 三维地形实时显示应用对于硬件系统性能的苛求。这样就能使得更多的企业和科研机 构能够负担建立大范围三维地形实时显示应用所投入的费用，提高这项很有应用价值 的应用系统在我国的应用范围，为我国的经济建设和社会发展做出应有的贡献。 1 4 论文的主要内容 本文共分为5 章，内容安排如下： 第一章，在介绍大范围三维地形实时显示的应用价值、当前系统应用遇到的问题 4 华中科技大学硕士学位论文 一目j j t 日_ i 目_ i l _ _ - _ _ 目_ - _ 目_ i 目_ t = _ _ _ _ _ e _ 自_ 和三维地形生成加速方法的基础上，介绍了本课题研究的目的和意义，以及本论文的 主要内容。 第二章，介绍了当前进行大范围三维地形实时显示所支持的数据格式、三维地形 的生成方法，以l o d 技术为例介绍了当前三维地形实时生成的加速算法。 第三章，在对现有三维地形多分辨率l o d 技术的比较分析之下，本文提出了基 于三角形网格的多分辨率l o d 模型算法，该算法基于地形模型中的敏感区域，利用 地形模型简化中三种常见变化对原模型进行简化同时计算顶点的重要度，并依据重要 度建立地形模型的有序递减网络，并给出了在实时显示中如何利用有序递减网络进行 多分辨率l o d 显示的算法和策略。 第四章，针对第三章所提出的l o d 算法，本文经过研究给出了具体的进行敏感 区域识别、三角形网格构建、顶点重要度计算、构建有序递减网络以及实时显示时的 处理方法和计算公式，并对顶点重要度计算的公式进行了合理的化简，避免了求解复 杂矩阵地特征值和特征向量。最后给出本算法的验证结果及结果分析。 第五章，对全文进行了总结，对下一步的工作提出了建议。 华中科技大学硕士学位论文 l = j l 目- l $ _ = l l j _ _ _ j 目- _ i _ _ e 目j 口目；# = l d g = _ _ l _ 目_ _ i r , m l 目目# 2 大地形三维显示及优化技术 三维显示首先要解决的是如何将地形显示在计算机当中。本章将着重说明三维地 形的数据和如何通过这些数据进行三维显示以及现在对三维地形实时显示所采用的 优化技术。 目前，通过计算机显示三维地形主要分为两种情况。 一是根据地学图形数据的精确描述。来进行真实地形的仿真，如根据地形特征参 数生成地形，这些特征参数包括高程、最大，最小高程及其位置、高程标准差、相关长 度、地形粗糙度等。这种地形的生成通常是在给定一定的地形特征或地形参数条件下， 通过模拟符合地形的统计特征的随机过程，即用计算机自动生成符合要求的真实的三 维地形。 二是模拟自然场景中的地形，常用于具有真实自然视觉效果的虚拟环境中。这种 方法不需要针对某个特定地区的地形来进行仿真，而是希望可以灵活地生成不同特征 的地形以满足不同的需求或者是为保证整个虚拟环境的真实感，因此，这种方法评价 的唯一标准是视觉上的接受能力。 当前系统应用主要基于第一种情况。 2 1 地形数据的来源及格式 前述第一种情况是对自然界中的真实地形进行仿真再现，具有更加实际的意义， 进行这类仿真的时候需要对实际地形进行各种方法的测量，获得比较精确地形数据， 再存于不同的数据格式，通过一定的算法在计算机系统重再现实际地形。 获取地形数据，开始人们是进行野外测量，利用野外测量仪器，实地选择地形特 征点、线作为采样点，测量其大地三维坐标，获得地形数据，但是这种方式费时费力。 随后，人们通过将地形图扫描成数字图象，经变换纠正后利用专业软件自动或半自动 化将其转换为矢量数据，获得地形数据。现在由于航空摄影测量技术的发展，人们通 过航拍并进行相应处理，可以大范围的获取比较精确的地形数据。数字摄影测量方法 以成为现代最为主要的获取地形数据的技术方法。 6 华中科技大学硕士学位论文 广义来说数字三维地形的数据源分为矢量型数据和栅格型数据，矢量数据一般 分为点、线、面3 类，都包含点数、属性和坐标串。其主要指等高线矢量、地形特征 点线矢量、地物要素矢量以及用线框和离散点阵表示的d e m 。栅格数据主要指纹理 图像数据和用纹理方式表示的d e m 。矢量型d e m 的数据组织形式分为g r i d ( 规则格 网) 和t i n ( 不规则三角网) 两种。 在数字三维地形中常用到的地形数据格式如下： ( 一) 等高线数据 等高线数据其实就是我们常用的地图，我们现在常用的地图上地表高度相同的点 连成一环线直接投影到平面形成水平曲线，而不同高度的环线不会相合，这种数据非 常原始，而且对地形的描述非常不精确，但是很多其他格式的地形数据由等高线数据 矢量化而来，它是用二维手段表示三维物体的常用方法。 ( 二) 格网数据 格网数据也称为g r i d 型数据，是一种于x y 平面等间距排列地面点x y z 三维坐标 的数据形式，简单的说就是在规则矩形网格点上给出该点的地表高程值，也称为高度 场。其优点是组织结构简单，能比较方便的从矢量化地图、经过处理的航拍照片中得 到，算法处理速度快，适用于表现起伏变化平滑的地形；缺点是遇到平缓地形时会产 生大量冗余数据，表现起伏变化剧烈的地形时要靠缩小格网间隔才能达到精度，但因 此会成倍的增加数据量。 ( 三) 三角两数据 三角网数据也被称为t i n 型数据，地面点x y z 三维坐标的排列完全等同于原始采 样的离散点，它不但含有地面点x y z 三维坐标，而且含有三角网格网的拓扑信息，能 够保持原始采样数据的精度，描述地形细致而合理，适用于表现起伏变化剧烈的地形， 特别是城市三维景观的表现，但t i n 型d e m 的数据结构较为复杂，在一定程度上影 响了算法的处理速度。三角网地形数据通常由格网地形数据转化得到。 ( 四) 格式数据 所谓的格式数据也就是基于一定的格式标准和构成规范的地形数据，格式数据的 使用有利于数据的广泛使用和系统模块化，现在比较常用的是基于o p e n f l i g h t 规范的 华中科技大学硕士学位论文 以m 为扩展名的地形文件。此外还有基于v r m l 语言的可用于w e b 显示的以w r l 为扩展名的地形文件。他们都来源于原始的地形数据。 ( 四) 纹理数据 在三维地形生成中，我们基于地形数据，通过一定的地形生成算法，生成出来的 其实只是一个由大量线段构成的可以反映地形起伏的框架。但是，在真实世界中，每 一个地形、地物除了有自己一定的形体外，都有自己的构成材质。 在三维地形仿真中，我们通过一定的方法将纹理数据映射到三维地形中，使得生 成的地形更加逼进自然。纹理数据其实就是常用的图片，较为常用的是位图。纹理映 射( t e x t u r em a p p i n g ) 是通过将数字化的纹理图像覆盖或投射到三维景象表面，从而 为物体表面增加表面细节的过程。 2 2 三维地形的生成方法 早期生成三维地形主要是基于曲面来生成，它是利用常用的参数曲面如b e z i e r 曲面、c o o n s 曲面、有理b 样条曲面，通过插值、曲面拟合来生成所需要的三维地形。 如用于散乱数据进行插值或拟合，形成曲面并用图像或图形表示出来的技术。曲面不 需要作分段线性近似，仍可以保证相邻面的斜面的斜率连续性，因此比较灵活。这 种方法采用计算机几何的方法，表现地形的准确度并不高，此外由于其数学计算的复 杂性，对于复杂场景来说，计算量较大，不适用于大范围三维地形的重建【1 4 】。 现在比较常用的三维地形构建方法是基于地形数据，以此为输入，经过某种数学 算法的处理，得到一个表现地表几何形状的模型，这一过程就是地形的建模过程。其 结果也就是在计算机中重建的三维地形。 基于地形数据生成三维地形的基本过程如下： ( 1 ) d e m 构模。将d e m 子网格分为面要素，以便作填充和图像映射。 ( 2 ) 透视投影变换。根据视点、视角、视场和三维图形大小等参数建立d e m 结点与三维图像点之间的透视关系。 ( 3 ) 建立光照模型或进行纹理映射。由透视投影关系逐点计算每一象素的颜色 和灰度，使模型能逼真地反映地表明暗和颜色的变化。 华中科技大学硕士学位论文 ( 4 ) 消隐和裁减。利用消隐算法处理三维图形被遮挡处，将落入屏幕之外的图 形裁减掉【4 j 。 d e m 构模和纹理映射是使数字三维地形具有“直观性”的重要步骤。通过构模 使d e m 格网具有封闭“面”的特征，纹理贴图则是将这些封闭面表现象素填充和r g b 图像映射，达到不同程度的仿真效果。 通常的建模方法可划分为两大类：规则三角网方法，即c d c 方法，或称为格网 方法，不规则三角网方法即t i n 方法，也称为三角网方法。 格网法显示地形的原理是在格网数据中通过相邻点的三维坐标进行几何内插，从 而重建地形表面。不规则三角网采取的是一种“原汁原味”的方法，其显示原理是通 过许多小三角面片来逼进地形表面，它几乎完整的保留原始数据按照某种原则将采样 点直接连成网，建立起模型。不过需要注意的是，如何选择点来组成三角面片将决定 显示的三维地形的逼真度，如果选择不当，将产生很多狭长的三角形，形成尖锐的地 形，产生较大的失真。虽然现在有很多基于三角网法的算法，但是大多采用了d e l a u n a y 三角形，即采用符合d e l a u n a y 原则构建三角网。 格网法这样重建的地形较为平滑，当数据量较小时，地形失真较大，而三角网法 由于不需要内插，因此很好的保持了原始数据点的精度。 三角网的数据量比格网的数据量要大很多，但是在显示的角度上看，由于现在多 数三维显示设备显示的速度只与模型三角面片的数量有关，而与三角形的大小无关， 而且由格网地形简化为三角地形的时候三角面片的数量还会减少。因此，采用三角网 格可以提高显示速度。当模型对精确度要求不高的时候，应更多的使用方格网模型， 以充分利用其算法相对简单、模型规范的特点。否则就要应用不规则三角网，其最大 的优点是：在采样数据密集、并分布合理的前提之下能够精确地再现地形。 近来，出现了一种不规则格网生成方法，它是基于四叉树的结构，用链表和指针 结构来表示地形高程。图2 - 1 分别给出了这几种方法所构建的地形模型。 9 华中科技大学硕士学位论文 ；= e = # # = = ； i g 目i _ i 。l i p j 1 _ d 4 _ _ _ 4 _ _ 鞭；黔i 复，1 、 + ，- 1 8 ， e ：o l 4 尊q q t 基于尊i 融船口地，l b 基于不规则三角网方法生成的地，l e 基于规则格网方法生成的地形d 基于不规则格网生成的地形 雷2 - 1 数宇准萄橇墼的表示 2 3 三维地形优化显示技术 由于大范围三维地形显示要求图形生成速度达到实时。而计算机所提供的计算能 力往往不能满足复杂三维场景的实时绘制需要，因而研究人员提出多种图形生成加速 方法。我们在第一章中已经介绍了多秘方法，本节主要说明l o d 技术。 l o d 技术的提出可以追溯到1 9 6 7 年，c l a r k 】认为当物体覆盖屏幕较小区域时， 可以使用该物体描述较襁的模型，并给出了个用于可见面判断算法的几何层次模 型，以便对复杂场景进行快速绘制。在1 9 8 2 年，r u b i n 1 2 】结合光线跟踪算法，提出了 复杂场景的层次表示算法及相关的绘制算法，从而使计算机能以较少的时间绘制复杂 场景。c r o w 【1 3 】用一个实例说明了同一物体采用不同的l o d 模型所具有的优点。 l o d 模型研究的发展主要分为离散l o d 模型、连续l o d 模型和多分辨率l o d 模型这几个阶段。 一直到九十年代前半期，研究的工作主要集中在离散l o d 模型的生成及实时显 示方面。离散l o d 模型方法就是离线生成多个离散的不同细节层次的模型，实时显 l o 华中科技大学硕士学位论文 示时，根据当时的条件进行选用，这些条件包括地形整体距视点的距离远近、投影后 地形在图形空间所占象素面积的大小以及光照强弱等，交互过程中，对于每个特定的 场景，只需要选择一个合适的l o d 模型进行渲染即可。由于不同l o d 模型之间在拓 扑结构上互不相关，因此这种离l o d 技术有一个明显的缺点，即在实时显示中，不 同l o d 模型之间进行切换时，在视觉上会引起明显的突跳感。 为了从根本上改变离散l o d 技术存在的上述问题，九十年代中期出现了连续 l o d 模型。所谓连续l o d 模型是指一种紧凑的模型表示方法，从这个表示中可以生 成任意多个不同分辨率的模型，从而实现模型的连续显示。这种技术一般通过迭代运 算进行各种操作，其中包括删除点，折叠边或网格中的一个三角形等，从而得到简化 的三角形网格，这就隐含地定义了一个被简化模型的不同细节水平的层次结构。每个 后继的l o d 与前一个l o d 相比，只有在删除点、边、三角形附近的局部区域有差别。 这种方法的优点是两个前后相继l o d 模型的差别相对较小，进行模型切换时，只会 引起视觉上非常微小的变化，不易察觉。 在地形简化中使用这些技术，这时所产生的地形各处分辨率相同，且各区域的细 节层次水平与视点和地表局部具体特征无关。由于地景一般场面宏大，绵延不断，只 有那些距离视点近的和变换曲率达的区域才需要较高的细节层次，以保证一定的形状 精度和真实感。因此为了进一步减少数据量，考虑用不同的分辨率来表示地景的不同 区域。 我们将不同区域具有不同细节层次的模型称为“多分辨率模型”。它的基本思想 是用不同l o d 构造或近似表示地景，其中对局部分辨率依赖视点变化的地景模型， 距视点不同距离区域的细节层次水平可以不同，并且随着视点的移动作相应的变化； 而对于依据地表特征变化的模型，在突变和缓变处采用不同的细节层次。这样即可在 没有视觉损失的前提下，加快大面积地景的渲染速度，并且满足所需的图象质量要求。 根据上述思想，场景的不同部分必须从多个l o d 模型中获取，即前景和突变区域从 高细节版本中获取，背景和平坦区取自低细节版本【3 1 0 这几年在全世界范围内形成了对多l o d 自动生成技术的研究热潮，并且取得了很 多有意义的研究结果。1 9 9 1 年，d e h a e m e r l 2 9 1 利用自适应递归方法，提出了基于规则 华中科技大学硕士学位论文 四边形网格表示物体的简化多边形网格的方法；在1 9 9 2 年，s c h r o e d e r 【3 0 】提出了基于 顶点移去的网格简化算法。g r e g l 3 1 】给出了基于网格重新划分的多边形网格模型简化方 法。1 9 9 3 年，h o p p e l 3 2 蟪出了一种整体网格优化方法，它包括网格匹配过程和网格简 化过程。r o s s i g n e c ”】使用多分辨率近似法自动生成物体的简化模型，该方法并不保持 原有模型的拓扑结构；1 9 9 4 年，h a m a n n 3 4 】给出了一种基于三角形移去的模型简化方 法。1 9 9 5 年，h e 3 5 1 使用信号处理方法来消除模型的高频细节，从而得到简化模型。 e c k l 3 6 荆用小波变换把多面体模型表示为多分辨率形式，由此可生成一系列连续的多 l o d 模型。1 9 9 6 年，c o h e n l 3 7 1 使用内外两个包络网格来控制简化过程，该方法可保持 模型的拓扑结构。k a l v i n l 3 8 1 利用面片合并方法来自动生成物体的简化模型。h o p p e t ”l 基于网格优化方法，提出了累进网格的概念以及生成方法，该方法搜索平面区域和特 征边，使用边折叠操作来完成简化功能。l i n d s t r o m l 4 0 】对规则网格表示的地形模型提出 了一种实时连续l o d 绘制方法，在三维地形仿真中得到成功应用。r o f l 抽- d 1 4 1 1 针对非 常复杂的场景，使用区域合并操作来进行模型简化，该方法根据与原始形状的几何偏 差度量进行边合并。g u e z e i c t 4 2 l 提出了一种误差可控的模型简化方法，边折叠操作与 r o n f a r d 所用的边折叠方法类似，而误差控制方法则与c o h e n 所用的方法类似。x i a 4 3 1 提出了一种动态的、与视点相关的多边形网格模型简化方法。a l g n r i t “l 使用一聚类过 程来确保简化操作仅在某些区域进行，聚类是通过查找特征边和平面区域来完成的。 在1 9 9 7 年，h o p p e l 4 5 对累进网格进行扩展，形成对任何网格都适用的且与视点有关的 累进网格。g a r l a n d l 4 6 1 使用二次误差度量来控制表面网格的简化，该方法可快速产生 高质量的近似模型。 国内近几年也开展了一些卓有成效的研究工作【1 9 , 2 0 , 2 1 , 3 2 。例如，文献【1 9 1 提出了一 种基于特征角准则的多面体简化方法，算法适用于对网格进行少量的删减。文献f 2 0 】 提出一种基于快速形成近平面的简化算法，算法具有保细节、保真和快速等优点。文 献1 2 1 对基于重新划分的网格简化算法进行改进，简化了分布点的操作。文献1 2 2 1 提出了 基于三角形二叉树和动态三角形链表结构的规则地表模型的简化新方法，这种算法基 于规则三角形网利用二叉树进行多分辨率显示，取得了一定的效果。 虽然现在对多分辨率l o d 技术研究已经有了相当的成果，但是主要是基于格网 华中科技大学硕士学位论文 地形生成方法，由于格网地形与原始地形相比，由于方法原理所限制失真较大，而基 于三角形生成方法的模型与原始地形相比失真较小，但相应优化算法处理较为复杂。 由于多分辨率l o d 模型在实时显示的时候受到的制约条件过多，模型负载度较 大，显示效果要求较高，现在还没有一个很好的对于各种情况都适用的理想多分辨率 l o d 模型算法出现，还有待于广大学者投入更多的精力去发掘它。 1 3 华中科技大学硕士学位论文 3 多分辨率l o d 算法 上一节我们提到了多分辨率l o d 模型，由于其在地形中不同地区可以产生不同 分辨率的地形模型，在保证一定分辨率的要求下，大大降低了系统所需要绘制的模型 多边形数量，降低了系统在实时显示时的负载，应该说这项技术代表了地形简化的方 向。 m u l t i g e n p a r a d i g m 公司推出的视景软件开发环境v e g a 是当前业界较为常用的三 维地形显示系统开发软件，由于其较好的利用了基于s g i 工作站的p e r f o r m e r 类库， 地形的三维显示速度较快，并且由于将大量的构建系统所需要的功能集成为v e g a 的 模块，使得利用v e g a 开发系统较为便利。但是v e g a 在地形简化方面仅仅提供了基于 离散l o d 地形简化技术，它是通过预先再地形模型中对同一地区存储多个不同分辨 率的地形模型，在实际使用中通过静态节点基于视点与模型的距离来调用不同分辨率 的模型，这样一方面增加了地形模型的数据量，另一方面由于离散l o d 不同分辨率 模型间的切换是突变的，使得实际显示效果不理想，虽然v e g a 提供了a o i 技术对地 形数据进行分块调度，但是相对而言数据量还是很大，如果在v e g a 系统中能够使用 多分辨率l o d 模型技术，一方面在实时显示中地形模型的分辨率逐渐变化，另一方 面通过l o d 技术降低系统负载，那么对系统性能的提高会有很大的帮助。 由于多分辨率l o d 模型需要根据视点在地形中的位置，在不同的区域选择不同 分辨率的模型，并且模型分辨率的变化程度是很细微的，它的变化也是渐变的，这样 就给模型算法提出了很高的要求。 一个理想的多分辨率表示算法应具有以下性质： 1 近似网格应尽可能保存原模型的拓扑性质。 2 近似网格中的顶点是原模型中的顶点的子集。也就是说，在多分辨率表示中没 有引入新的顶点，这个性质非常重要。因为这样做可以在绘制中直接使用原有 的顶点性质，如法向、纹理等。 1 4 华中科技大学硕士学位论文 3 具有连续性。视点的变化不会导致模型复杂度的大变化。更准确的说对于视点 的任意充分小的变化，模型中三角型的数目的变化量最多为l ，这个性质将会 避免在动态显示中出现跳变现象。 4 算法提供一种方法让用户较容易地控制生成由多分辨率模型生成的图像的质 量f i 】 虽然现在有很多的研究学者提出了自己的多分辨率l o d 模型算法，但是他们大 多数是基于格网生成方法的，例如二叉树法和四叉树法。由于格网数据分布规则，容 易根据顶点的分布来选择分辨率增加时需要添加的点。但是格网生成法本身有一个先 天不足就是它是在格网数据中通过相邻点的三维坐标进行几何内插，从而重建地形表 面，这样就不可避免的降低了模型的精度，在一定程度上改变了地形模型的拓扑特征， 要保证精度就需要加入大量的点。而三角形网格由于是基于三角形面片来逼进地形表 面，可以较好的保证地形拓扑特征，保证地形的精确程度。图3 - i 中给出了一个三角 格网地形简化的示例。其中，图3 l ( a ) 所示的是原始的d e m 数据。这是一个湖的地形， 可以注意到湖中心的一个岛。此地形数据共有1 5 4 ，2 2 4 个顶点。图3 - i ( b ) 所示的是 大约使用了0 5 的( 7 7 1 个) 顶点作为输入进行逼近的效果。图3 - 1 ( c ) 所示的是大约 使用了1 的( 1 ，5 4 2 个) 顶点作为输入进行逼近的效果。图3 1 ( d ) 所示的是大约使用 了5 的( 7 7 1 1 个) 顶点作为输入进行逼近的效果。比较一下图3 - 1 ( a ) 和图3 一l ( d ) 可 以看出，我们只需要大约5 的顶点个数就可以比较好的模拟整个地形。因此应用三角 形网格在多分辨率显示中可以比较好的保证地形特征。 c a ) 华中科技大学硕士学位论文 ( c )( d ) 图3 - i三角格网地形简化示例 当然由于三角形格网构网较为复杂，在整个地形中进行多分辨率显示现在还没有 很好的解决方法。但是我们可以看到在实际地形中，地形中起伏较大的地区并不是连 贯整个地形，而这些地区又往往代表了整个地形的特点，是观察者比较关心的区域。 同时对这些区域的显示处理也往往占用了系统较多的资源。我们可以称这些区域为敏 感区域。因此本文就此提出一种基于三角形格网的对地形中敏感区域在保证一定拓扑 特征的情况下进行实时多分辨率l o d 显示的算法。 由前面叙述可知，对于一个确定物体或者地形，用于描述它的三角面片越多，三 维形体的细节被描述的就越多，理论上当三角面片的数量无限大时所构建的三维形体 就与真实形体相同，反之，当三角面片数量减少的时候，则形体的分辨率降低。而三 角面片的数量增减可以通过顶点分裂和合并完成，并且分裂可以是合并的逆过程，由 此我们可以建立一个对于三维模型的有序递减网格，在实时运行中当顶点按照顺序进 行分裂和合并时，模型分辨率也相应的变大和变小。 3 1 透视原理 要进行多分辨率l o d 显示，我们需要处理视点与模型的距离与分辨率的关系。 为了建立视点参数与所选择的分辨率之间的直接关系，即通过模型与视点之间的距离 来选择满足一定用户精度的近似模型，我们首先来考察透视变换的基本原理。 1 6 华中科技大学硕士学位论文 图3 - 2 透视变换的基本原理 如图，视点的张角和屏幕的边长为a 和l ( 可假定为常数) 。被投影线段的长度 为l ，视点与该线段中心的距离为d ，且该线段与屏幕平行。显然，此时线段在屏幕 上的投影长度最长，设其为t ，我们可以得到如下公式： r ：! ：墨! 墨刚1 2 x t g 曼d 2 其中九为物体空间中单位长度占屏幕上的象素数。因此，对于一条特定的边，距离越 长，t 也越短。选择e 为用户控制的精度值，也就是说，当三维模型中一条边离视点 的