（计算机应用技术专业论文）大规模地形多分辨率模型算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 逢形信息的可视化在地理信息系统、仿真系统、虚拟现实系统和三维游戏等 领域中占有十分重要的地位。随着遥感技术、卫星技术以及计算机技术的快速发 展，人们希望能够观察到更广阔更真实的地形，对地形的实对绘制提出了更高的 要求。本文着重研究大规模地形多分辨率模型算法，主要工作如下： 介绍了大规模地形实时可视化的应用背景。指出了提高其绘制效率的关 键在于设计出与场景规模基本不相关或弱相关的绘制算法。并且指出了三条提高 绘制效率的途径：可见面判别算法、层次细节技术以及基于图像的绘制技术。总 结了目前这一领域已有文献中所提出的若干技术路线。 叙述了层次细节技术的特征和类别，以及涉及到的一系列相关问题。探 讨了层次细节技术在大规模地形绘制中的应用地形多分辨率模型，列举和讨 论了有代表性的一系列算法。 提出了一个大规模地形数据实时绘制系统。该系统融合了地形多分辨率 模型和视域剔除快速算法。提出了一种新懿建形多分辨率模型实对生成算法，该 算法通过保守地估计简化后的近似网格的模型空间误差在屏幕空间的投影值，选 取恰当的分辨率，在降低模型几何复杂度的同时保证了简化模型的精度，并且在 计算和存储上均十分有效。通过视域四棱锥在x z 平面的投影三角形扫描算法，实 现了快速视域剔除。此外该系统还可以融合三角形条带化、几何过渡、纹理多重 映射等一系列方法，使得地形绘制的效率和质量更高。 应用c + + 和o p e n g l ，开发了原型系统。在p c 平台上，对较大规模的真实 地形数据进行了试验。试验结果证明本文提出的可视化系统是高效的，自皂够进行 大规模地形的实时可视化。 关键词大规模地形可视化；层次细节；多分辨率模型；视域剔除 西南交通大学硕士研究生学位论文 第1 i 页 a b s t r a c t v i s u a l i z a t i o no ft e r r a i ni n f o r m a t i o ni s p l a y i n g a k e y r o l ei n m a n y a p p l i c a t i o n ss u c ha sg e o g r a p h i ci a f o r m a t i o ns y s t e m ，s i r e a l a t i o ns y s t e m ，v i s u a l r e a l i t y a n d3 dg a m e s ，e t c w i t ht h er a p i d d e v e l o p m e n to ft h er e m o t es e n s e ， s a t e l l i t e t e c h n o l o g ya n dc o m p u t e rt e c h n o l o g y ，p e o p l ee x p e c tt oi n v e s t i g a t eo r v i e wl a r g e rt e r r a i nr e g i o n sw i t hf i n e rp r e c i s i o n ，w h i c hi n e v i t a b l yl e a d st ot h e r e a l t i m er e n d e r i n go fh u g et e r r a i nd a t a s e t t h i st h e s i se x p l o r e st h es t r a t e g i e so f r e a l t i m er e n d e r i n gf o r l a r g e s c a l et e r r a i n ，a n dt h ep r i n c i p a lc o n t e n ti nt h i st h e s i s i sa sf o l l o w ： s o m e a p p l i c a t i o nb a c k g r o u n d so ft h er e a l t i m er e n d e r i n go fl a r g e s c a l e t e r r a i nd a t as e ta r ei n t r o d u c e d i ti su n v e i l e dt h a tt h en a t u r eo ft h er e a l t i m e r e n d e r i n gf o rl a r g e s c a l et e r r a i ni st of i n do u ts u c hr e n d e r i n ga l g o r i t h m st h a th a v e n oo rl i t t l e d e p e n d e n c yw i t ht h en u m b e ro ft h et r i a n g l e si ns c e n e a n d i ti s p o i n t e d o u tt h a tt h e r ea r et h r e ef u n d a m e n t a l s t r a t e g i e s 幻a c c e l e r a t et h er e n d e r i n g p r o c e d u r ea sv i s i b l e s u r f a c ed e t e c t i o n ，l e v e lo f d e t a i la n d i m a g e b a s e dr e n d e r i n g s o m er e s o l u t i o n sw h i c ha r e p r e s e n t e d i nr e c e n t p u b l i c a t i o n s a b o u tt e r r a i n r e n d e r i n ga r es u m m a r i z e d t h ec h a r a c t e r i s t i c sa n dc l a s s e so fl e v e lo fd e t a i la r ed e s c r i b e d a sw e l la s as e r i e so fr e l a t e di s s u e s t h e a p p l i c a t i o nw i t h l e v e lo fd e t a i li n l a r g e - s c a l e t e r r a i n r e n d e r i n g i sd i s c u s s e d a n das e r i e so f a l g o r i t h m s a b o u tt e r r a i n m u l t i r e s o l u t i o nm o d e l i n gi nr e c e n ty e a r si se n u m e r a t e da n dd i s c u s s e d i nt h i st h e s i s ，as y s t e mf o rl a r g e - s c a l et e r r a i nr e a l t i m ev i s u a l i z a t i o ni s p r o p o s e d w i t h i n t h i s s y s t e m ，t h ea p p r o a c hi n t e g r a t i n g m u l t i - r e s o l u t i o n r e p r e s e n t a t i o n so ft e r r a i na n df a s tv i e wf r u s t u mc u l l i n gi sp r e s e n t e d an o v e l m e t h o df o rr e a l t i m em u l t i r e s o l u t i o n m o d e l i n g i s p r e s e n t e d i n o r d e r1 0 g u a r a n t e e t h e p r e c i s i o n o ft h em u l t i r e s o l u t i o nm o d e l e f f e c t i v e l y , t h e c o n s e r v a t i v ee s t i m a t i o no ft h ep r o j e c t e de r r o ri n s c r e e n - s p a c e i su s e da st h e c r i t e r i o nw h i c hi su s e dt oc h o o s ea na p p r o p r i a t el e v e lo fd e t a i l ，w h i c hc a nb e s t o r e da n dc o m p u t e de f f i c i e n t l y f u r t h e r m o r e ，af a s ts c a n n i n gi su s e df o rv i e w f r u s t u mc u l l i n gb a s e do nt h ep r o j e c t i o no ft h ev i e wf r u s t u mo nx z p l a n e t o 西南交通大学硕士研究生学位论文 第1 i i 页 f u r t h e ra c c e l e r a t et e r r a i n r e n d e r i n ga n di m a g eq u a l i t y ，t h es y s t e mi sa b l et o i n t e g r a t et r i a n g l es t r i p s ，g e o m e t r i c a lm o r p h i n ga n dt e x t u r em i p m a pa sw e l l a p r o t o t y p es y s t e m i s d e v e l o p e db yu s i n gc + + a n do p e n g la p i r e a l t i m ev i s u a l i z a t i o no ft w ol a r g e rt e r r a i nd a t as e t s i s i m p l e m e n t e do np c p l a t f o r m e x p e r i m e n t a lr e s u l t ss h o w t h a tt h ee f f i c i e n c yo f a l g o r i t h mi nt h i st h e s i s i s h i 【g h o nb o t h c o m p u t a t i o n a n d m e m o r y , a n dt h ea l g o r i t h mc a ns u p p o r t r e a l t i m ev i s u a l i z a t i o no f l a r g e s c a l et e r r a i n k e yw o r d s ：v i s u a l i z a t i o no f l a r g e s c a l et e r r a i n ，l e v e lo fd e t a i l ， m u l t i r e s o l u t i o nm o d e l ，v i e wf r u s t u m c u l l i n g 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景和意义 第1 章绪论 地球空间信息是人类探索和认识现实世界最基本的组成部分。地球空 间信息技术与生物技术和纳米技术起被认为是当今世界的三大新兴技术， 其在人们社会生活中的影响目益深远和广泛【“。随着遥感技术、卫星技术的 发展，使得获取高分辨率的数字高程数据以及影像纹理数据成为可能，因此 建立国家级乃至全球性的空问信息可视化系统已经成为各个国家及国际组 织的共识。 其中，最具代表性的是美国提出的“数字地球( d i g i t a le a r t h ) ”战略。美 国副总统g o r e 于1 9 9 8 年在美国加利福尼亚科学中心发表的题为“数字地球： 二十一世纪认识地球的方式”的讲演中指出“我们需要一个数字地球， 即一种可以嵌入海量空间数据的、多分辨率的和三维的地球的表示，可以在 其上添加许多与我们所处的星球有关的数据”1 2 j 。随着数字地球概念的提 出，各国政府纷纷把国家的数字化进程看作是国家发展战略的重中之重，是 增强国力不可或缺的一个环节。 目前我国的空间信息系统建设自9 0 年代以来步入快速发展阶段，在基 础环境数据库建设，推进国产软件系统的实用化、遥感和空间信息系统技术 一体化方面取得了很大的成绩。1 9 9 9 年1 2 月在北京成功召开了第一届国际 “数字地球”大会后，我国正积极推进“数字中国”和“数字省市”的建设， 2 0 0 1 年国家测绘局完成了构建“数字中国”地理空间基础框架的总体战略 研究。在已完成1 ：1 0 0 万和1 ：2 5 万全国空间数据库的基础上，2 0 0 1 年 全国各省市测绘局开始1 ：5 万空间数据库的建库工作1 3 j 。 地形信息作为地球空间信息最重要的组成部分，与人们的生活息息相 关。全球数字高程模型( d i g i t a l e l e v a t i o n m o d e l ，d e m ) 是描述地球形状的基 础数据之一，它对于正确显示三维地球，对全球数据进行分析决策都有着非 常重要的作用。然而，原始的文本数据对于普通人来说是抽象和枯燥的，如 果采用三维可视化的方法将这些数据显示出来，将帮助人们直观地观察全球 的地形变换情况，提高对二维或三维空间关系和空间问题的理解【4j 。可以说 地形数字高程模型数据的三维可视化对军事、仿真、规划、建筑、虚拟现实、 西南交通大学硕士研究生学位论文第2 页 土木工程和地球科学等学科都有非常重要的现实意义。 1 2 大规模地形场景简化的途径 采集到的地形数字高程模型数据通常用均匀采样的高度场来表示地形 表面，在图形学中一般用三角形网格来表示地形并进行绘制。三维地形模型 可视化的目的就是要根据视点位置和视线方向，快速逼真地由数字高程模型 数据模拟出三维地形的二维图像。 地形d e m 数据庞大的数据量和高度的冗余给大规模地形的处理与绘 制带来了非常大的困难。最精细的地形三角形网格是对最精细采样点的矩形 区域用对角线分割，形成两个三角形。构成地形的三角形数目随地形尺寸成 四倍增长，三角形数目与地形尺寸的比例关系如表1 - 1 所示： 表1 。1 地形尺寸与三角形数目关系1 5 1 地形尺寸三角形数目 1 ，0 2 4 1 ，0 2 4 2 ，0 4 8 2 ，0 4 8 4 ，0 9 6 4 ，0 9 6 8 ，1 9 2 8 ，1 9 2 1 6 ，3 8 4 1 6 ，3 8 4 3 2 ，7 6 8 3 2 ，7 6 8 随着计算机技术的发展，硬件技术得到了长足进步。然而，随着计算 机图形技术的实用化，需要构造更逼真、更精细的地形模型，使得绘制场景 的规模不断扩大。理论上，场景的复杂性是无限的，而任何硬件在单位时间 内的处理能力总是有限的。实时性效果要求帧频至少达到1 6 f p s ( f r a m ep e r s e c o n d ) ，若达到流畅的效果则要求2 4 f p s 以上，单纯依赖于硬件加速的快速 绘制技术，并不能满足实际应用对绘制速度的要求。此外，系统往往还要进 行光照处理、反走样处理及纹理映射等等，这就对实时绘制提出了更高的要 求，对硬件设备的要求也很高。所以，通过研究场景复杂性和人类视觉感知 规律等相关因素的内部联系，设计出与场景规模基本不相关或弱相关的简化 算法是必要的，也是必然的趋势。目前，大规模地形模型快速绘制的途径主 2 8 2 8 2 8 5 0 3 2 1 4 1 6 4 7 9 6 7 8 4 7 0 3 9 8 5 1 7 8 0 3 5 2 8 4 2 8 3 4 6 7 3 3 3 4 1 j 1 ， 2 西南交通大学硕士研究生学位论文第3 页 要有：可见面判别( s i b l e s u r f a c ed e t e c t i o n ，v s d ) 、层次细节技术r k v e lo f d e t a i l ，l o d ) 、基于图像的绘制等( h n a g eb a s e dr e n d e r ，i b r ) 等。所以，国 内外对大规模地形场景简化的研究热点主要是围绕这几个方面展开的。 1 2 1 可见面判别算法 可见面判别，即确定从某个视点出发场景中哪些表面可见的方法，是 图形学中基本而且十分重要的专题之一。目前已经有多种解决该问题的途 径，人们为不同的应用场合开发出了相当数目的算法。当为某个特定的应用 背景选择算法时，应考虑场景复杂度、待显示物体的类型等因素。这些算法 通常称为可见面判别算法，有时也称为隐藏面消除( h i d d e n s u r f a c er e m o v a l _ ， h s r l 算法，尽管判别可见面与隐藏面之间有细微的差别【6 】。 可见面判别算法的分类，通常是根据其处理场景时是直接对物体定义 进行处理还是处理它们的投影图像来分，这两种类型分别称为物空间算法和 图像空间算法。物空间算法通过对场景中各个绘制元素进行比较，从而最终 判别出哪些元素是可见的，常用的物空间算法有深度排序法：而像空间算法 则在投影平面上逐点判断各像素对应的可见面，常用的像空间算法有扫描线 方法、z 缓存器方法等。 作为三维可视化的最基本要求之一，目前的三维图形应用程序接口 ( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ，a e i ) 都具有消隐能力。但是图形a p i ， 包括o p e n g l 、d i r e c t3 d 、j a v a 3 d 等，都是在经过视图、投影变换以后才进 行消隐，这远远不能满足大规模地形可视化的实时性要求，因此有必要研究 基于物空间的快速可见面判别算法，对不可见元素在进行矩阵变换之前就进 行消除。 1 2 2 层次细节技术 l o d 模型是指对同一场景或场景中的物体，使用具有不同细节的描述 方法得到一组模型，供绘制时选择使用【1 1 。目的是在不影响画面视觉效果的 条件下，通过逐次简化模型的表面细节来减少场景的几何复杂度，从而提高 绘制算法的效率。l o d 的基本概念就是对场景中位于远处或不太重要的部 分使用较少的细节表示并进行绘制，这样对于一个较复杂场景而言，可以减 少所绘制场景的复杂度，并保证所生成的最终图像的质量损失在用户给定的 阈值以内，而生成图像的速度则能大幅度地提高。图1 - 1 是一个l o d 经典 例子兔子的l o d 模型，图1 - 2 示意了依据距离标准选取不同的l o d 模型 西南交通大学硕士研究生学位论文 第4 页 的例子。 图1 1 兔子能j l o d 模型【8 l 图1 - 2 根据距离选取l o d 模型 l o d 技术，大致可以划分为三个发展阶段；按照生成网格的形状可以 分为基于规则网格( r e g u l a rs q u a r eg r i d ，r s g 或g r i d ) 的算法和基于不 规则三角网格( t r i a n g u l a t e di r r e g u l a rn e t w o r k s ，t i n ) 的算法；按照简化方 法，可以分为自底向上的合并与自顶向下细分，以下分别给予介绍。 l o d 技术的发展阶段 l o d 技术的发展大致经历了三个阶段：离散l o d 模型、连续l o d 模 型和多分辨率模型，各阶段的特点如表卜2 所示。 西南交通大学硕士研究生学位论文第5 页 离散l o d 模型 一组具有不同复杂度和相似度的模型，同一模型各处具有相同 的细节层次水平，每一个模型对应一个细节层次，这些模型在绘制 前由简化算法生成。相邻层次间切换时伴有视觉上的突跳感 连续l o d 模型 多分辨率模型 同一模型各处具有相同的细节层次水平，没有显式的细节层次 存在，在绘制过程中，由相应算法自动生成 不同水平细节层次同时存在于模型的不同区域。没有显式的细 节层次存在，在绘制过程中，由相应算法自动生成 目前的研究热点集中在多分辨率模型上，也是本文主要的研究内容。 将不同区域具有不同细节层次的模型称为“多分辨率模型”( m u l t i r e s o l u t i o n m o d e l ) ，采用的是i e e e 可视化学术机构提出的分类名称。有些文献也将这 种模型称为“可变分辨率模型”( v a r i a b l er e s o l u t i o nm o d e l ) 、自适应l o d ( a d a p t i v el o d ) 等1 9 1 。多分辨率模型与连续l o d 模型之间并没有非常明确的 界限，因此也有许多学者将它们统称为连续l o d 模型。 g r i d 和t i n 圈圈固 a ) d e m 采样网格b ) g r i d 图1 - 3 地形网格的类型 1 0 按照生成网格的形状可以分为两类。一类是基于规则网格的，从d e m 采样网格出发生成规则的三角形网格，如图1 - 3b ) 所示；另一类是基于不规 则三角形网格的，由空间中离散的点与各自相邻近的点按照某种规则相连形 西南交通大学硕士研究生学位论文第6 页 成三角形的面片，如图1 3c ) 所示。规则网格数据存储位置能反映实际数据 的空间位置，可便利地生成多分辨率模型。t 矾模型描述效率高，但构造三 角网过程复杂，拓扑关系也非常复杂。 合并和细分 按照l o d 模型的生成方法通常可分为自底向上的网格合并与自顶向 下的网格细分二大类。自底向上的简化方法是从物体的原始精细模型出发， 通过删除或合并重要性较小的顶点和三角形来达到简化网格的目的。另一种 自顶向下的网格细分，它是从物体的一个原始简化模型出发，通过逐步加入 重要性较大的顶点与原模型逼近，从而实现网格的简化。 自底向上的方法计算量与输入的数据量成正比。自顶向下的方法的计 算量与输入无关，而与输出的数据成比例。目前几乎所有的简化算法都是自 顶向下的，因为输入数据与输出数据相比往往会增加几个数量级。 1 2 3 基于图像的绘制 基于图像的绘制技术通过一些预先生成好的图像来生成不同视点处的 场景画面 1 1 】。i b r 作为一种新的视觉建模方法，在不需要复杂几何模型的前 提下也能够获得具有高度真实感的场景表达，能够较好地解决三维建模过程 中模型复杂度与绘制的真实感和实时性三者之间的矛盾，大大简化了复杂的 数据处理工作。因此也被越来越多地用于各种虚拟环境的建立，特别是基于 图形和图像的两种建模技术被综合用于高度真实感的三维景观模型的创建【1 2 】。 1 。3 研究内容 本论文对大规模地形实时可视化技术进行了讨论，探讨了提高绘制效率 和质量的途径。具体所作的工作集中在三个方面： 视相关的地形多分辨率模型的构建与快速绘制算法； 适用于地形绘制的视域剔除快速算法； 大规模地形实时可视化的实现方法。 为了实现大规模地形的实时可视化，本文提出了一个有效的系统，结合 了地形多分辨率模型和视域剔除这两种主要的简化手段。试验结果证明本文 的算法是高效的，能够实现大规模地形数据实时可视化。 西南交通大学硕士研究生学位论文 第7 页 1 4 各章组织安排 论文按如下结构进行组织： 第一章中，介绍了大规模地形实时可视化技术的应用背景，探索了提 高其绘制效率和质量的基本途径。介绍了大规模地形可视化研究现状及热，r 蕈 技术。 第二章，介绍了地形实时可视化的相关技术：地形的数字表达、可见 面判别算法、多分辨率模型生成算法、纹理映射技术以及绘制时的加速技术。 同时总结了目前文献中所提出的若干技术路线，并列举和讨论了有代表性的 一系列算法。 笫三章，详细阐述了地形多分辨率模型的经典算法- - r o a m 算法、 g e o m i p m a p p i n g 算法及其改进算法，并且描述了r o a m 算法的数据结构和 算法流程。 第四章，提出了一个实现大规模地形实时可视化的系统，其在计算时 间和存储空间上都十分有效，并且易于实现。提出了一种新的地形多分辨率 模型实时生成算法，该算法在降低模型几何复杂度的同时有效地保证了简化 模型的精度。为了提高绘制效率，该系统融合了多分辨率模型、视域剔除、 三角形条带化等一系列方法，使得地形绘制的效率更高。叙述了算法的数据 结构和算法流程。 第五章，根据第四章的算法设计了原型系统，并对较大规模的真实地 形d e m 数据进行了试验。对试验结果进行了比较和分析。 结论部分对全文进行了总结并对未来的工作提出了展望。 西南交通大学硕士研究生学位论文 第8 页 第2 章地形可视化相关技术 大规模地形实时可视化是个复杂的问题，是多种不同技术的集成应用，涉 及到以下几个方面： 地形数据的表示与组织，数据的组织必须保证几何连续性和快速的数据 检索，以有利于实时调度； 视相关的地形l o d 模型生成算法，注意避免t 连接和裂缝； 对简化模型的有效的误差控制，即地形进行简化的判据： 快速高效的可见面判别； 大规模高分辨率的纹理映射； 快速的三角形条带化提高绘制效率。 在本章后面几节中将对这些问题展开详细讨论。 2 1 地形的数字表达 进入2 0 世纪中叶后，伴随着计算机科学、现代数学和计算机图形学等的发 展，各种数字地形表达方式也得到了迅猛的发展。借助于数字地形表达，现实世 界的三维特征能够得到充分而真实的再现【1 3 l 。 2 1 1 数字地面模型 1 9 5 8 年m i l l e r 和l a f l a m m e 提出了一个一般性的概念和理论：数字地面模型 ( d i 画t a lt e r r a i nm o d e l ，f f m ) ，即使用采样数据来表这地形表面，他们的原始定 义如下： 数字地面模型是利用一个任意坐标场中大量选择的已知盖，y ，z 的坐标点对 连续地面的一个简单的统计表示，或者说，d t m 就是地形表面简单的数字表示。 数字地面模型更通用的定义是描述地球表面形态多种信息空间分布的有序 数值阵列，从数学的角度，可以用下述二维函数系列取值的有序集合来概括地表 示数字地面模型的丰富内容和多样形式h 3 j ： 耳= 矗坼，0 ) ，t = 1 , 2 ，3 ，m ，p = 1 , 2 ，3 ，开 ( 2 - 1 ) 式中 k ，笫p 号地面点上的第t 类地面特性信息的取值 ，) 一第p 号地面点的二维坐标： 小一地面特征信息类型的数目； 栉一地面点的个数。 西南交通大学硕士研究生学位论文 第9 页 2 1 2 数字高程模型 在式( 2 1 ) 中，当m = 1 且，1 为对地面高程的映射， ，v ，) 为矩阵的行列号时， 式( 2 1 ) 表达的数字地面模型即所谓的数字高程模型。实际上，d e m 是d t m 中最 基本的部分，它是对地球表面地形地貌的一种离散的数字表达。 总之，数字高程模型d e m 是表示区域d 上的三维向量有限序列，用函数的 形式描述为： k ；( 互，x ，z ，) ，i = 1 , 2 ，l( 2 - 2 ) 式中 丑；，x 一平面坐标： z ：一( 互，誓) 对应的高程。 当该序列中各平面向量的平面位置呈规则网格排列时，其平面坐标可以省 略，此时d e m 就简化为一维向量序列钇；，i = l 2 ，n f 1 3 1 。 2 2 可见性剔除算法 在各种可见面判别算法中，可见性剔除算法是提高大规模地形实时绘制效率 的有效工具。可见性剔除算法通过在绘制前快速判断不可见的绘制元素，得到可 能的可见集，从而减少不必要的运算时间和存储空间。可见性剔除算法主要包括： 背面剔除( b a c kf a c ec u l l i n g ) 、视域剔除( v i e wf r u s t u mc u l l i n g ) 和遮挡剔除 ( o c c l u s i o nc u l l i n g ) 。 2 2 1 背面剔除与视域剔除 背面剔除和视域剔除算法较为简单，如图2 - 1 所示。 背面剔除算法，计算并判断绘制元素( 主要是三角形) 是否背离视点，如是 则不予绘制，否则应绘制。背面剔除算法可采用简单的点积方法，来识别法向量 指向视点相反方向的绘制元素。先计算绘制元素法向量和视线向量，再计算两个向 量夹角，如小于9 0 。，则为背面，应予易除。 2 0 0 3 年，s h e n gl i 等【1 4 】提出了一种针对地形t i n 模型的背面剔除算法。算 法的基本思想是，在预处理过程提取地形特征( 主要是山脊线) ，然后剔除掉不 可见的山脊线背面三角形。算法是基于这样的一个事实，在对于起伏剧烈的地形 表面( 如山区) ，在某一视点位置，位于山脊线背面的区域大部分不为视点所见。 视域剔除算法，通常采用的是绘制元素组的包围盒作为替代进行可见性判 断，如果包围盒位于视域四棱锥( v i e wf r u s t u m ) 之外，则其所包围的所有绘制元素 西南交通大学硕士研究生学位论文第1 0 页 都不可见。 视点 视域剔 j ，j _ _ ，_ _ ， _ 。一。一_ _ _ - i ，_ ? ? 。 图2 - 1 背面剔除与视域剔除 2 2 2 遮挡剔除 遮挡剔除技术主要避免绘制被场景内别的物体遮挡的绘制元素，如图2 2 所 示。 因为突兀和山峰很容易成为遮挡物，所以遮挡剔除算法对于像峡谷、山区这 样一些表面起伏剧烈的地形，可以在很大程度上减少需要处理的三角形。但是对 平坦的地形，遮挡剔除算法效率会降低。因此，遮挡剔除算法存在着一定的适用 范围。 视点 j ，- l 挡易u 除 - ，- i ，- 图2 - 2 遮挡剔除 西南交通大学硕士研究生学位论文 第1 1 页 2 3 地形l o d 模型 对于大规模地形这种范围很大、连绵不绝的场景，l o d 模型的生成与绘制 算法应具有如下特征【1 5 】： 在任何时刻，对网格的几何描述应该可以直接有效地访问，即有关多边 形和顶点的信息可以进行快速的空间索引： 网格几何的动态改变导致的重新计算，不应该对系统的性能有太大的影 响： 高频数据比如局部凸、凹性，或几何的局部改变，对地形l o d 模型的复 杂性不应该产生扩散的全局影响； 视觉参数( 包括，视点位置、视线方向、视域范围等) 的微小改变，对 复杂性仅有微小的改变，以便减小预测的不确定性，并允许维持恒定( 或接近恒 定) 的帧频； 算法应提供一种方法来控制误差，既确定由近似网格模型而引入的图像 质量的丢失程度。 2 3 ，1 基于t i n 的l o d 算法 不规则三角网通过从不规则分布的高程点生成的连续三角形面来逼近地形 表面。与规则网格地形模型相比，t i n 模型能用更少的空间和时间更精确地表示 更加复杂的地形表面。特别是当地形包含大量特征线如断裂线、构造线等时，t i n 模型能更好地顾及这些特征，从而更精确合理地表达地表形态。对于t i n 模型， 其基本要求有三点：1 1 1 1 n 是唯一的；2 ) 力求最佳的三角形几何形状，每个三角 形尽量接近等边形状；3 ) 保证最邻近的点构成三角形，即三角形的边长之和最小【1 3 j 。 在所有可能的三角网中，狄洛尼( d e l a u n a y ) z 角网在地形拟合方面表现最为 出色，因此常常被用于t i n 的生成。狄洛尼三角网为相互邻接且互不重叠的三角 形的集合，每一个三角形的外接圆内不包含其他的点【l 。图2 3 描述了欧几里得 平面上1 6 个点的狄洛尼三角网。 在绘制过程中，如果每一次视点改变都实时构建模型的d e l a u n a y 三角网格， 将使简化速度受到影响，从目前国内外出现的各种基于t i n 的实时多分辨率模型 建模方法来看，其基本思想都是避开复杂的三角网格重建过程，对t i n 进行预处 理，记录模型简化过程中的模型信息，在实时简化中利用这些已知的信息进行分 裂或归并，实现基于视相关的t i n 实时多分辨率模型【1 “。通常的做法是把一些不 重要的图元( 顶点、边或三角形) 从多边形网格中移去，图2 - 4 所示为典型的几 何元素删除简化算法。 西南交通大学硕士研究生学位论文第1 2 页 - - 一l 图2 - 31 6 个点集合的狄洛尼三角网【1 3 】 除 c ) 边折叠成一个庄 b 1 三角形删除 d ) 三角形折叠成一个点 图士4 基于几何元素删除三角网简化啊 1 9 9 6 年，h o p p e 提出了渐进网格( p r o g r e s s i v em e s h ，p m ) 的概念，首次较 好地解决了模型简化方法在实际应用中所遇到的问题，可以支持l o d 模型的实 时生成。p m 产生较好的目视效果，但是复杂的表面距离计算降低了它的运行速 西南交通大学硕士研究生学位论文第1 3 页 度。9 7 年h o p p e 在 1 7 基础上提出了视相关渐进网格1 1 8 m e wd e p e n d e n t p r o g r e s s i v em e s h ，v d p m ) 。9 8 年，h o p p e 在文献 1 9 1 中，将v d p m 应用到地形 绘制中，实现了大规模地形的实时漫游。算法首先将地形分为大块，对每块分别 采用递进网格预处理，然后依据记录的简化过程的信息，根据不同的视点实时生 成不规则三角网。但是该算法占用内存较大，而且效率较低。 p a j a r o l a 等 2 0 】提出的q u a d t i n 是一种将t i n 的优点和四叉树层次结构相结合 的算法。算法效率较高，所支持的输入数据既可以是不规则的点集，也可以是d e m 规则网格。 针对基于t i n 的地形l o d 模型建模，国内许多学割2 1 2 9 】也开展了一些卓有成 效的研究工作。 2 3 2 基于g r i d 的l o d 算法 目前应用较广的是基于规则网格的算法。这种基于规则网格的l o d 模型生 成算法一般具有如下特征： 数据一般以四叉树或者二叉树的层次结构进行组织； 简化算法相对比较简单； 已经有很多成熟的算法； 与不规则三角形网格相比较，规则网格更容易实现纹理映射。 l i n d s t r o m 等于1 9 9 6 年首次针对g r i d 提出了多分辨率地形模型实时绘制算 法，他的算法采用四叉树结构，自底向上递归合并三角形直到屏幕投影误差超出 阂值，得到最终的地形l o d 模型 3 0 】。他的算法思想为以后一系列地形l o d 模型 算法打下了基础。2 0 0 1 年，l i n d s t r o m 等在 3 1 1 6 0 又提出了基于外存( o u t o f - c o r e ) 的大规模地形可视化技术，使地形数据在自项向下细分的过程中安排数据在内外 存中调度。近期他又提出的s o a r ( s t a t e l e s so n e p a s sa d a p t i v er e f i n e m e n t ) 算法 【3 2 】，类似于先前的几种方法，在规则网格上采用基于视点的最长边剖分方法，自 顶向下逐步求精，每一帧均采用相同的步骤，并且把三角形条带化、视域剔除以 及几何过渡都集中在这一步骤，使得执行起来更为方便。 1 9 9 7 年，d u c h a i n e a u 等提出了r o a m 算法，自顶向下对地形表面进行递归 二叉剖分从而构造三角形二叉树。该算法利用两个剖分和合并优先级队列来控 制执行三角形的剖分和合并操作，避免了裂缝的发生，并且每一帧图像的绘制时 间只与发生变化的三角形的数目成比例。该算法被广泛应用于三维游戏中。 1 9 9 8 年，p a j a r o l a 3 4 1 提出了限制四又树算法。r j t t g e r 等【3 5 】很好地解决了地形 l o d 模型中的裂缝问题和连续帧之间顶点的突跳问题。2 0 0 0 年，c a s t l e 等p 刨在 3 4 的基础上，简化了细分的判定算法。 2 0 0 0 年，b l o w 【3 73 8 】对r o a m 算法做了重要改进，建议使用一个更为简单的 西南交通大学硕士研究生学位论文 第1 4 页 剖分判定规则，即每个三角形的剖分判定条件是一个球形等值面，当视点进入这 个球内时，三角形就剖分，否则三角形进行合并。 2 0 0 1 年，h a k l l 3 9 在r o a m 算法的基础上，提出的d i a m o n d 地形绘制算法， 采用四叉树结构，运用四个栈而不是优先权队列来驱动三角形的剖分和合并，算 法效率也比r o a m 算法高。 2 0 0 2 年，u l r i c h 4 0 l 提出了一种基于四叉树的算法c b u n l 【e dl o d 。该算法 是一种离散l o d 算法，c p u 负担轻，即使在视点快速移动时，c p u 的占用率也 不是很高。 2 0 0 0 午，b o e r l 4 “提出了几何多重分块( g e o m e t r i c a lm i p m a p p i n g ，g c o m i o m a p p i n g ) 技术，这种算法将类似于纹理多重映射的技术应用到了地形模型几何构 网上。2 0 0 3 年，l a r s e n 等【4 2 j 提出t 4 1 的改进算法，改善了裂缝的消除方法，通 过几何过渡解决了层次切换时所产生的突跳现象。 国外其他一些地形连续l o d 模型生成算法的研究工作还包括文献【4 3 4 5 1 等。 国内也有许多学者i s 1 0 4 ”5 9 】从事基于规则网格的地形连续l o d 模型生成算法 的研究，研究工作主要集中在基于二叉树和四叉树的算法上，许多算法还融合了 可见性判断等简化方法，使绘制效率得到了进一步的提高。 2 3 3 误差计算 在视相关的地形l o d 模型生成算法中，屏幕投影误差是建立l o d 模型的常 用标准。屏幕投影误差是生成的l o d 简化模型近似网格与原始精细网格间的模 型空间误差在屏幕空问上的投影。根掘文献 3 0 1 ，屏幕投影误差应该小于屏幕上 的4 个像素大小，否则就会在视觉上带来比较明显的差别。在细分过程中，当一 个块或三角形的屏幕投影误差大于要求的阈值时，需要对其进行细分；否则，不 必对其进行细分。 因为精确计算屏幕投影误差时间开销大，所以采用屏幕投影误差的估算值作 为选择分辨率层次的依据，如图2 5 所示，可以得到式( 2 3 ) ： e = 红瓦e 砀c o s , 6 ( 2 - 3 ) 式中 e一屏幕空间投影误差估算值；s 。一屏幕高度； e 。一模型空间误差； 口一视点的下视角； d ，一视点距误差计算点的距离； a 一视点的垂向张角。 西南交通大学硕士研究生学位论文第1 5 页 图2 - 5 屏幕投影误差的估算1 整理式( 2 3 ) 可得式( 2 4 ) ： 8 ；h! 堕壁笠- mf 2 4 ) 驴s 瓦面荔。石 弘4 式( 2 4 冲的前半部分仅视参数发生变化时改变，可以在预处理过程进行计算。 由式( 2 4 ) 可知，屏幕投影误差e 。与视点的下视角卢成反比，与视点到模型空 间误差e 。的距离d 。成反比。为简化计算，实际的算法采用最大屏幕投影误差法， 令芦：o ( 即视线总是平行于x z 平面) ，由此得到的一个保守的投影误差值，见 式( 2 5 ) ： 巳。上2 t a n ( o r 2 ) 。詈( 2 - 5 ) 由式( 2 5 ) 可知，e m 一定时，d 。越大，e s 也就越小，如用户指定的阈值为s ， 那么当d 。充分大时，其在屏幕上的投影误差g 。可以小于，从而可以将其忽略【5 5 1 。 2 3 4t - 连接和裂缝消除 在用三角形网格表达地形时，要注意避免t _ 连接。t - 连接就是指一个三角形 或多个三角形共享另外一个三角形的一条边的一部分。如果不避免t - 连接，就会 西南交通大学硕士研究生学位论文第1 6 页 产生“裂缝( c r a c k ) ”，图2 - 6 就是由于t _ 连接而产生的裂缝。为了消除i j 蟊蚕i 酉 缝，国内外学者们提出了各种解决方法。 图2 - 6t 连接和裂缝 以文献【3 4 为代表的四叉树l o d 算法，往往采用限制四叉树来消除裂缝。通 过限制四叉树相邻节点的层次差不超过1 层，大大简化了t _ 连接和裂缝的消除。 以r o a m 算法1 3 3 j 为代表的基于- - 3 l 树的算法，通过对三角形二叉树的一系 列强制剖分避免了t _ 连接和裂缝的产生。 文献【4 1 】采取在t - 连接发生处将高分辨率顶点强行拉向底边以达到闭合的方 法，这虽然解决了裂缝问题且不会带来额外的三角形，但对裂缝处地形的描述带 来损失并且会产生狭长的三角形。 文献 4 0 则提出了在可能发生裂缝的地方增加一个面的方法来填充裂缝的方 法。 2 3 5 几何过渡 图2 7 几何过渡 用l o d 模型绘制地形的时候，还有一个很