（大地测量学与测量工程专业论文）基于不规则三角网的lod研究.pdf

第1 章绪论 1 1 研究背景 随着科学技术的发展，二十一世纪的到来标志着数字时代的到 来。美国“数字地球”战略的提出标志着一个新的科学世纪的来i 临。 美国副总统g o r e 于1 9 9 8 年在美国加利福尼亚科学中心发表的题为 “数字地球：二十一世纪认识地球的方式”的讲演中指出“我们需 要一个数字地球，即一种可以嵌入海量空间数据的、多分辨率 的和三维的地球的表示，可以在其上添加许多与我们所处的星球有 关的数据”【1 】。为在二十一世纪抢占科技战线的堡垒，各国纷纷提 出了自己的数字化的国家发展战略并投入大量的资金和技术来攻克 该领域内的各类难题， 在“数字地球”中，作为构成该地球的基础数据一一地理空间 数据，曾一度被人们认为是最难获取的数据。然而，随着遥感技术、 卫星技术的发展，使获取高分辨率的数字高程数据以及影像纹理数 据成为可能。现在，人们获取空间数据的手段已经从曾经的单一化 接触式测量来获取数据到多方位、多渠道的获取。例如我国的空间 信息系统建设自9 0 年代以来步入快速发展阶段，在基础环境数据库 建设，推进国产软件系统的实用化、遥感和空间信息系统技术一体 化方面取得了很大的成绩。1 9 9 9 年1 2 月在北京成功召开了第一届 国际“数字地球”大会后，我国正积极推进“数字中国”和“数字 省市”的建设，2 0 0 1 年国家测绘局完成了构建“数字中国”地理空 间基础框架的总体战略研究。在已完成1 ：1 0 0 万和l ：2 5 万全国 空间数据库的基础上，2 0 0 1 年全国各省市测绘局开始1 ：5 万空间 数据库的建库工作p “。 、 尽管空间数据的获取已经不成为“数字地球”建设的瓶颈，但 是如何使这些数据真正变成一个真正的“虚拟地球”却是要面对许 多的技术攻关，其中的一项便是空间数据的可视化。g i s 作为“数 字地球”的支撑技术之一，已经有近三十年的历史。现在，对于空 问数据的二维可视化已经发展成熟，人们可以利用二维数据来进行 各种空间的计算。但是这与真正的“数字地球”相去甚远，于是 各种空间的计算。但是这与真正的“数字地球”相去甚远，于是 亘壹奎涌大多硕士研究生学位论文第2 页 在近十几年，人们开始在二维可视化技术的基础上寻找真正的三维 甚至多维信息的可视化，这样就可以用电脑世界中虚拟地球真实的 再现我们共同居住的地球。 在可视化技术发展方面，人们对比例尺的概念一直保持着很谨 慎的态度。在我们的头脑里，从开始就习惯接受单一分辨率的各 种地图符号来标志地球上的所有物质。但是，在人眼里。我们在真 实世界中收到的数据却并非如此，雨是概念性的数据，即非精确定 位性的数据。用数学的观点，就是采用的是模糊系统来描述进入人 眼中的对象。因此研究计算机可视化地球的科学家们尝试着用计算 机中的精确数字来描述人们肉眼中豹模糊世界概念。之所以要研究 这类问题，这与计算机发展速度和人们获取空间数据的速度跟不上 有着密切的关系。当今世界，人们动辄就可以获取数以兆计的空间 数据。要把这些海量数据在计算机中如同真实世界一样展现在人们 面前，供人们自由实时浏览，对于当前的计算机技术来说是无法达 到的。当前的计算机还没有能力处理海量数据的实时可视化。所以 科学家们就思考着如何用人们的模糊意识和电脑中的数字意识联系 在一起。在三维可视化方面，这是首先要解决的闯题。 l o d ( l e v e lo fd e t a i l ) 技术，即层次细节技术，是三维可视化 技术中将人们模糊意识与电脑的数字意识联系在一起的技术。它是 运用人们的模糊比例尺概念，将远近不同具有不同细节层次的各种 对象生动形象的运用数字在电脑中以可视化的技术展现给人，让人 感觉另一个接近的“真实的世界”。 1 2 研究意义 l o d 技术的研究是随着三维可视化技术的不断发展而开始的。 现在三维可视化技术是在继承二维可视化技术的基础上发展起来 的，因此他脱离不了比例尺的限制。由于二维地理信息系统将实际 的三维事物采用二维的方式表示，具有很大的局限性，大量的多维 空间信息无法得到利用。三维g i s 的研究不是对二维g i s 的简单扩 展，而是从空间模型分析到空间数据库的结构直至三维数据的可视 化，都必须进行系统的研究。许多研究者已经开发了三维g i s 的原 型系统，使得三维g i s 技术在矿产资源管理、数字城市等领域得到 西南交通大学硕士研究生学位论文第3 页 应用，如加拿大n e wb r u n s w i c k 大学的k a v o u r a s 和m a s r y 在1 9 8 7 年就开发了用于矿产资源评估和开采的三维g i s 原型系统。德国 r o s t o c k 大学、s t u t t g a r t 大学等研究机构目前正联合研究三维g i s 在数字城市模型中的应用，他们对城市的空间对象进行了分类和表 示，建立了数字城市模拟系统，对城市基础设施( 包括房屋、道路、 绿地等) 可方便地进行查询、分析和显示。一些商用g i s 系统中， 也加入了三维g i s 模块，如e r d a s 公司的i m a g i n ev i r t u a lg i s 模 块，能在实时三维环境下，提供g i s 分析和实时三维飞行方式的访 问和漫游。还有许多其它一些模拟实验系统，其研究集中于三维可 视化和虚拟现实功能方面。首先，由于地形数据的海量特点，三维 地形的实时浏览，除了对计算机浏览端的硬件提出了很高的要求外， 而且对网络的带宽也是沉重的负担。因此，研究三维海量地形数据 的实时浏览技术，成为目前宽带网上的商业应用的迫切需要1 2 “。其 次是高精度的扫描测绘手段为复杂物体基于多边形网格表示的三维 几何建模提供了新的高效手段，但由于采样精度高，由此建立起的 三维模型的复杂程度远远超过了当前计算机实时的图形处理能力。 如何降低这些模型的复杂度，减少图形系统需处理的多边形数目， 实现实时交互，已经成为计算机图形学研究中的一个重大课题【4 ”。 第三，虚拟现实的提出标志着在计算机领域的一个新的领域的开拓， 但是要实现真正的虚拟现实，需要攻克的难关很多，其中可视化技 术就是一个。而在可视化方面，如何采用最好的建模方法，使系统 中出现的画面更加逼真，更贴近现实是很重要的问题。一方面，为 了准确的逼真，人们最初想用尽量多的多边形来绘制现实中的对象， 然而这就产生了一个海量数据的可视化问题。第四，计算机动画是 计算机图形学和艺术相结合的产物，它给人们提供了一个充分展示 个人想象力和艺术才能的新天地。目前，计算机动画已经广泛应用于 影视特技、商业广告、游戏、计算机辅助教育等领域。在计算机动 画设计中也要涉及到一个问题，就是逼真表现对象问题。同样，这 也会产生海量数据实时可视化问题。最后在军事中，三维可视化技 术也得到了广泛的应用，但是，在战场环境模拟仿真时，由于需要 将环境的各方面表现出来，就不得不使用海量的多边形来绘制，这 也产生了计算机处理海量数据实时可视化的问题。 西南交通大学硕士研究生学位论文第4 页 总之，在当前的多个领域里，都会遇到海量数据实时可视化问 题。在当前计算机技术无法满足海量数据处理的情况下，人们不得 不把问题转化为海量数据的无损信息压缩下的可视化问题。一方面， 在数据可视化的时候，要达到一定的帧速，才能满足实时的要求， 但同时绘制的画面又需要保真。为此，人们选择了一种折中的办法， 就是在当前的技术下对帧速和画面的保真性进行一个平衡。即在不 损失画面视觉效果的情形下，保证画面的连续性。为达到这种效果， 层次细节技术就提出来了。 层次细节技术的提出不仅在理论上突破了人们的比例尺概念， 同时在实际应用得到了广泛的证明。如上所述三维可视化对军事、 仿真、虚拟现实、地球科学等学科都有非常重要的现实意义。 本文主要研究基于不规则格网的层次细节技术。在这方面，作 者认为在当前规则格网研究比较流行的情形下，它也有着十分重要 的作用。首先，世界本是不规则的，采用不规则格网来描述不规则 的世界合乎自然逻辑，同时也减少了许多冗余数据。其次，规则格 网不过是不规则格网的特例。由一般到特殊是研究自然世界不变的 真理。通过对不规则格网的层次细节技术研究，可以掌握理解人眼 中的无比例尺是如何形成的，这对于研究未来机器人如何接受自然 界对象将起到关键作用。同时，对不规则格网的研究，也是对数据 内在的特性研究，是充分利用数据内在的关联性。这是规则格网技 术没有利用到的。 综上所述，本文研究不规则格网的层次技术是海量不规则地形 数据可视化技术里的基础技术，具有一定的现实意义。 1 3 基于不规则格网的l o d 技术的分类 不规则格网的l o d 技术研究已经有三十多年的历史，在过去的 三十多年，随着计算机技术的发展，人们对基于不规则格网的l o d 技术的看法也不断的发展。下面根据不同的分类依次介绍该类技术 的研究现状。 1 3 1 根据不规则格网的发展历史来分类 根据不规则格网的l o d 技术的发展历史来分，它可以分为静态 亘鲢通六芋题士研究生学位论文 第5 页 的l o d 技术和动态的l o d 技术。 1 静态的不规则格网的l o d 技术：在计算机发展的初期，由于 存储数据技术的不完善，在存储数据上人们力图寻找一切可能来减 少数据的存储，因此发展起来了l o d 技术。静态的l o d 技术，即与 视点无关的l o d 技术，它是通过对数据进行预先处理，根据需要产 生几种一定的比例尺的模型。在实时显示时，依据一定的误差规则， 调入相应比例尺的模型进行显示。静态l o d 技术主要是以不规则格 网为主，因为不规则格网本身产生的数据量很少，满足早期的存储 要求，而规则格网则是数据过于庞大，无法适应当时的存储技术。 静态的不规则格网的l o d 技术方法简单，算法很容易实现，但是应 用却并不广泛，其根本原因就是在实时显示时没有连续性，因此产 生了视觉上的“跳跃”现象。 2 动态的不规则格网的l o d 技术：针对静态l o d 技术产生视觉 上“跳跃”的原因，人们根据视觉原理，开始研究基于视点的l o d 技术，即动态l o d 技术。简单的说，动态l o d 技术是依据视点的不 同，对输入的数据进行动态的处理，以产生具有不同尺度的数据显 示在屏幕上，达到视觉上的效果。动态l o d 技术实现了真正的实时 显示，但是动态l o d 技术由于数据的实时调度和实时处理，对于现 代的一般的计算机来说，调度和处理数据的时间过长，影响了数据 实时显示时的帧速。因此，人们不得不在计算机显示速度和数据处 理后的精度上做一定的平衡，以便找到一个合理的结合点。在动态 l o d 技术中，针对不规则格网的研究很少，其主要原因是不规则格 网的动态构网难度很大，同时在调入数据时需要一次性的全部调入， 这也增加了调度数据的时间。 1 3 2 根据不规则格网的数据结构类型来分类 目前研究的不规则格网的l o d 技术所采用的数据结构大致有三 种【6 ： 基于点状的数据结构：最简单的方法就是构建一个样本函数 的近似连续，即以一个带权的重构来构建一个点集，该法不 提供清晰的数据结构，通常用于那些通过函数来获取几何数 据的算法。另一种重构技术是产生一个k 维区域的镶嵌。在 西南交通大学硕士研究生学位论文第6 页 这样的镶嵌中，样本点的函数值为了达到样本函数的部分近 似，通常沿体元线形插入。 基于三角形的数据结构：基于不规则三角形格网的l o d 模 型的数据结构可分成清晰数据结构和模糊或暗含的数据结 构。在清晰的三角形数据结构中所采用的方法是直接在模型 中描述三角形。而模糊或暗含的数据结构则是不编码三角 形，只有一个操作的过程描述，通过该过程描述产生l o d 模型，如边折叠或点插入点移走。 基于四面体的数据结构：该类型的l o d 技术是以四面体为 基本的描述空间对象基元，通过对空间进行不规则的四面体 割分，它采用视相关树对空间直接依赖关系进行编码，这种 编码大大提高了该类l o d 技术的存储效率。 1 。4 本文的工作 本文对不规则格网的l o d 技术进行了讨论，将探讨提高数据存 取效率和地形可视化的途径。具体工作有以下几方面； 研究不规刖格网的l o d 的关键技术：首先介绍海量地形几何 数据的存储技术与调度技术，根据调度技术与数据的重组与 排序相关，对数据的排序技术进行了详细的研究。然后探讨 了t i n 的快速生成技术，包含点扩张算法、径向扫描算法、 基于凸壳技术的t i n 快速生成算法。接下来研究了当前几种 三角网的简化技术，包括递进格网简化技术、基于顶点删除 的简化技术、基于最大独立点集的简化技术。对l o d 技术中 的基础算法可见性剔除算法做了深入的探讨，包含了隐藏面 移走技术、背面剔除技术、遮挡剔除技术，这里主要研究了 隐藏面移走技术，包含深度排序技术和对象空间技术。对误 差的计算，本文也做了简要的介绍。在最后，对加速绘制三 角形的基本算法，三角带化算法作了深入的探讨。 分析并评速了当前已经成熟的几种l o d 算法：这几种算法是 基于点状数据结构的算法、静态不规则格网技术、q u a d t i n 以及超块q u a d t i n 技术。针对这几种算法，作者对其数据结 构，简化效率、存储效率、计算时间以及显示质量等方面做 堕蜜窑夔盔堂塑主塑塞兰堂焦笙塞茎：夏 了比较和分析，最后并得出了不规则三角网的l o d 技术需要 遵循的一般原则。 改进一种适合大规模不规则格网地形数据的l o d 算法：该算 法是基于超块四叉t i n 算法设计思想上设计的，它采用基于 凸壳的快速t i n 生成方法作为三角化方法，同时利用点删除 插入算法来进行动态三角化。实现海量地形数据的实时多分 辨率浏览。首先，在数据预处理阶段，首先对数据进行排序 分块，并记录各块的中心及包围矩形。然后对各块数据进行 数据分类，将重要的地形特征点、线以特殊点的方式存储。 然后采用基于凸壳的t i n 快速生成技术，对数据进行三角化， 在此基础上计算每个点的重要度。接着，采用四叉树结构来 存储并排序数据，以便实时时充分利用。在实时阶段，采用 多线程技术，一个线程进行数据装载，一个线程进行数据的 实时简化计算，一个线程用于实时绘制。对于数据装载，需 根据视点移动速度及其视觉范围进行装载。对于实时简化计 算，充分利用帧之问的连贯性，采用近似公式进行快速计算。 在三角化时，采用t i n 快速生成法以减少计算时间。对于实 时绘制，则会考虑帧与帧之间的连续性，采用延迟技术进行 绘制，以保证帧速的一致。 对提出的算法进行试验分析：对本文改进的算法进行了实 验，包含对其简化效率、误差阙值的选择、以及背面剔除和 遮挡、三角形条带技术。在实验数据的基础上分析了执行效 果所产生的原因。 1 5 论文结构组织 论文的结构组织是按如下结构进行的： 第一章，介绍了基于不规则格网l o d 技术的研究背景及研究意 义，简要介绍了当前不规则格网的分类。 第二章，介绍了基于不规则格网的地形实时绘制的几种关键技 术：海量地形几何数据的存储和调度技术；可见性的剔除算法；轮 廓的保留技术；t i n 的快速生成；不规则格网简化技术：误差计算 及选择；三角带化技术。 亘目重童湮大掌硕士研究生学位论文第8 页 第三章，详细阐述了基于不规则格网的l o d 技术的经典算法一 一基于点状数据结构的算法、静态不规则格网技术、q u a d t i n 以及 超块q u a d t i n 技术，并对这些算法进行了比较和分析。 第四章，在总结前人的基础上，提出了一种可保留特征点的不 规则格网的l o d 技术，其在计算时间和存储空间上都十分有效，并 且易于实现。 第五章，根据第四章的算法设计了原型系统，并对较大规模的 真实地形d e m 数据进行了试验。对试验结果进行了比较和分析。 第六章，对全文进行了总结并对未来的工作提出了展望。 西南交通大学硕士研究生学位论文第9 页 第2 章不规则格网l o d 的关键技术 不规则格网的l o d 的关键技术包括：数据的存储与调度、t i n 的快速生成技术、不规则格网的简化技术、可见性剔出技术、轮廓 保留技术、误差计算技术、三角带化技术、几何过渡、纹理压缩技 术等。限于本文主要研究的内容，因此只对前面几种技术作分析与 探讨，而几何过度和纹理压缩技术，本文将不做深入探讨。 2 1 海量数据的存储与调度 在l o d 技术中，海量数据的存储方式对于数据的快速调度以及 减少存储量等起着非常重要的作用。现在根据海量数据的存储位置 可分为基于内存的海量数据存储方法和基于外存的海量数据的存储 方法40 1 。 2 1 1 基于内存的海量数据存储方法 对于海量数据的存储，一种方式是对海量数据进行分类存储， 即采用层次的结构进行存储，对相同层的数据存储在一起。这样根 据一定的规则，在进行实时调度时，可以快速的取出数据进行显示。 另一种方式就是对地形数据进行简化处理，采用一定的简化方法， 对简化后的数据进行组织。现在的数据组织一般采用树结构，如二 叉树、三叉树、四叉树等方式。在树中，一般使用节点的误差作为 关键字，以便实时处理。 2 1 2 基于外存的海量数据的高速调度 基于地形的几何连续多分辨率层次细节模型的实时动态构网方 法，根据当前的视点位置和相邻帧的视点连贯性对地形进行简化。 但是当简化后的地形数据量仍超出内存容量对，就必须考虑把数据 存储在容量更大的外存上，而外存的读取非常慢，成为实时绘制的 一个瓶颈，显然，设计一个有效的文件存储方式，对大规模地形的 绘制，具有非常重要的意义。 l i n d s t r o m 提出了一个基于外存的地形实时绘制框架，即数据调 度由操作系统来执行，使用操作系统的文件映射，建立文件与内存 耍膏变通大学硕士研究生学位论文第l o 页 之间的映射关系，在w i n d o w s 下使用m a p v i e w o f f i l e 函数。但当 数据超出了操作系统的文件映射( 或虚拟内存) ，则需要设计数据调 度算法，更有效地在快速的内存和较慢的外存( 例如硬盘) 之间进 行数据交换。基于外存的算法和数据，关键在于利用数据的局部连 贯性，以避免重复的。频繁的数据调度，减少输入输出的花费。 外存的数据高效调度，归结为数据的重组和排序，即建立地形 网格顶点的一种有效排序，使他们在硬盘上的排列方式具有很好的 局部性，并且与三角形构网的方式一致，这样在实时构网时能快速 地访问数据。因此，重组后数据需满足物理地址上的相邻的数据具 有几何上的局部连贯性，同时在构网的过程中，能有效地计算顶点 的索引，以便在剖分的过程中能迅速地获取所需要的顶点信息。 数据的重组和排序可分为规则格网式的排序和不规则格网的排 序。 1 规则格网的排序 大规模矩形网格的数据重组织在地形可视化、三位数据体绘制 以及矩阵运算中，都有着广泛的应用，其重点在于保证数据访问时 的局部性。尽管在_ 几何计算和科学可视化领域中，不断有新的算法 出现，但它们在执行时都需把二维以及多维数据映射到一维数组， 使得一维数组中的相邻数据在空间中具有很好的局部性。二维或多 维空间填充曲线不仅可以保证遍历空间中的每个数据点，而且填充 曲线局部区段内的数据点在空间分布也是相邻的。因此空间填充曲 线常选作空间数据重组的排序方式 s a g a n l 9 9 4 】，著名的h i l b e r t 曲 线就是一种经典的空间填充曲线( p a r a s h a r l 9 9 7 】【i e b e l 9 9 9 】 n i e d e r m e i e r l 9 9 7 】图2 1 给出了初始几步网格顶点的索引号。 l ：卜_ ：i ! l ：li ：；lh hihhl 菡卜h + _ + d 图2 1h i b e r t 曲线 近来，l a w d e r 采用了几种空间填充曲线来有效地存储和快速获 亘鲢道大堂硕士研究生学位论文第1 1 页 取多维数据( l a w d e r ，2 0 0 0 ) 。b a l m e l l i 使用z 一型填充曲线有效地表 示网格的四叉树结构( b a l m e l l i ，2 0 0 1 ) ，并能快速计算相邻结点以及 具有共同父结点的其他结点的索引，可用于地形绘制以及自适应网 格逐步求精。图2 2 给出了z 一型填充曲线的四叉树排序。四叉树 的z 一型填充曲线用来加速矩阵操作也是十分有效的( f r e n s ，1 9 9 7 ) 。 ：j 黼：j 图2 2z 型填充曲线 p a s c u c c i 把单一分辨率数据变换到多分辨率的数据排序 ( p a s c u c c i ，2 0 0 1a ) ，该排序方式采用自项向下，由粗往细的顺序排列 网格顶点，在三维体数据的可视化中是一种十分有效的数据组织方 式( p a s c u c c i ，2 0 0 1 b ) 。l i n s d r o m 和p a s u c c i 在地形的可视化中采用了 三种数据结构，并给出了有效的顶点索引( l i n s d r o m ，2 0 0 2 ) 。第一种 是隔层四叉树，该方法把地形网格在由粗往细的剖分过程中按层次 分为白色四叉树和黑色四叉树两种，每神均为一棵完全的四叉树。 这种黑白隔层表示顶点的方式利用四叉树的编码，根据父子结点关 系推导出顶点索引号，但是这种算法增加了6 6 的顶点，导致数据 的存储量的增加。 2 不规则格网的排序 不规则格网的排序一般采用扫描方式来排序，这样的排列有利 于格网的三角化与分块。另一种方法就是对数据进行分类，如山、 平地、河流、湖等，然后根据其拓扑关系，采取相邻对象存储在一 块，以便快速调度，一般来说，每个对象都有一个中心点来作为对 象的索引标志，这样在实时可视化时，就根据索引标志来快速判断 是否调度该对象的数据。这种方法采取自然分类，可以避免人工生 成的一些裂缝。但是这种方法对每个对象的边界不好确定，并且对 于如丘陵这样的地区不好分类。因此，对不规则格网的排序，主要 采用规则格网的排序方法来排序，这样算法实现起来比较容易。 总的来说，虽然可以通过操作系统的虚拟内存来映射数据文件， 西南交通大学硕士研究生学位论文第1 2 页 把数据调度的工作交给操作系统来管理，但是当需存储的数据超出 了虚拟内存的容量，并且操作系统没有针对特定的数据进行优化装 载时，就需要设计算法来加速数据的调度。为了实现数据的实时调 度，可以采用数据预装载和实时装载两个线程来并行调度地形数据， 使数据调度能更好的适应可视化的要求。 2 2t l n 的快速生成技术 t i n 的快速生成对于不规则格网的实时绘制将起到关键作用。 在当前，有几种生成算法，一种是点扩张算法，一种是径向扫描算 法，还有就是基于凸壳技术的三角网快速生成算法。 2 2 1 点扩张算法 点扩张算法，也叫生长算法 4 4 1 ，他就是首先将数据排序，以数 据矩阵的前面两点作为起始点，根据点到直线的最小距离原则，选 择距离该边最小的点作为构建三角网的下一点，根据同样的原则对 生成的两边分别扩张，直到所有点被加入到三角网中，同时，在三 角网的生成后要进行三角网优化处理，其优化原则，一般采取摄大 化最小角原则，即在由两个相邻三角形构成四边中，两个三角形的 最小角应该最大的。这种算法速度较慢，并且优化处理在全区域内 进行，导致优化时间过长。 2 2 ，2 径向扫描算法 径向扫描算法【3 9 】，如图2 3 所示。设离散点个数为n 。第一步， 任取一个点( 设为0 点) 作为基准点，计算其余的n 1 个点和它的连线 的方向，以方向角的大小进行排序。第二步，连接o 点和其余的n - 1 个点，并把相邻的点连接起来，形成最初的扇形三角网。第三步，从扇 形边的任一点开始，以一定的方向( 顺时针或逆时针) 进行凹边连接， 如图2 3 所示，以p 点为起点( 当前点) ，沿逆时针方向搜索下一个点 s 和再下一个点q ，如果q 点在线段ps 的前进的方向的左侧，当 前点改为s ，从s 点继续向前搜索；如果q 点在线段ps 前进方向 的右侧，则连接pq ，生成一个新的三角形，再往下搜索，r 点在p q 的右侧，连接pr ，又生成一个三角形，下一个点t 在pr 的左侧， 当前点改为r ，从r 点继续向前搜索，直到把外边界变成凸多边形 亘禽i 窒道盘堂硬研究生学位论文第1 3 页 为止。第四步，利用局部优化算法，把第三步生成好的三角网进行 优化，得到最优的三角网。 笾笾婢镀 第一步 第二步第三步 第四步 图2 3径向扫描步骤 2 2 3 基于凸壳技术的快速三角孵生成 基于凸壳技术的快速三角网生成方案【5 0 】，该技术的出发点是完 全不考虑三角形的优化性，只考虑联结而成的三角网的所有三角形 是合理三角形，具体如下：首先对所有的点按扫描方式加以排序， 生成有序点集合s ，然后以有序点集合s 的点g 为着眼点( 对于集合 s 中的任意点g ，设在集合s 中点g 以前的所有有序点构成的子集为 k ，并且子集k 已经联结成了三角网和获得了凸壳) ，在子集k 的凸 壳中寻找能够与点g 构成合理三角形的凸壳边，进而组成三角形， 并且构造点g 加入后点集( k ，g ) 的新的凸壳，该过程不断进行直到所 有的点都成为三角形的顶点，即完成了点集s 的三角网联结。 2 。3 三角网简化技术 三角网的简化不仅与网的结构有关，而且还与三角网代表的空 间数据有关，如果三角网代表的是一个地表模型，则它的简化与三角 网顶点的高程值有关。根据这种相关性，可将简化算法分为二类，一 类是与三角网的顶点的属性值有关，一类则无关。下面提供三个简 化算法，算法一和算法二属于第一类，算法三属于第二类。算法一：基 于h o p p e f l 0 1 的思想，相邻点合并。如果相邻的两个点高程值差和两 点的距离都在给定的范围内，则对这两个点进行合并，即删除两个 点，加入一个新点，加入的点的位置和高程值为原两个点的平均。 根据给定的高程值差和两点的距离范围可以控制简化的程度，也可 匿蜜窑运盔堂塑主墅塞生堂焦熊塞蔓! j 戛 模型m = m “通过一系列边折叠( e d g e c 0 1 l a p s e ) 操作渐进简化为基网格 m o ，即 m = m “竺奴一m ”1 竺! 吐哼 曼! b m o 兰! 屿m o 通过其逆变换点分裂( v e r t e x s p l i t ) 操作可将基网格m 渐进细化为 原始网格m o ，即 m = m ”灿射”1 型k q 型! 生专m o 显! 屿m o h o p p e 把( m ，( e c o l 。1 ，e c o l 。2 e c o l o ) 称作物体的递进网格表示。 由e c o l 操作集合可构建网格的合并树，即所谓层次结构。由该层次 结构根据视相关准则选择合适的元操作集合f 边折叠或点分裂) 的子 集，即可进行网格的视相关简化和细化。初始e c o l 操作集合的选择 及其顺序是非视相关的，学者们提出各种选择初始e c o l 操作集合的 准则，如x i a 和v 缸s h n e y 基于边的长度选择初始操作集合，限制条 件是同一层的边折叠操作的影响域互不重叠。如h o p p e 所述，这会导 致不必要的深树。h o p p e 放宽了边折叠操作的限制，如图2 5 所示，只 要被插入面或删除面f l 和f r 的邻居f o 、f l 、f 2 、f 3 为活动面( 存在于 当前网格中的面) ，则元操作被认为是合法的。h 0 p p e 是基于点建立的 图2 5基于边结构的合法元操作变换 二叉树点层次结构，研究发现，由于点层次结构的叶子结点不包含元 操作所需的任何信息，因此，可以基于元操作建立二叉树层次结构， 这样能够节省近一半空间。根据顶点曲率的大小确定点的重要度，按 西南交通大学硕士研究生学位论文第1 6 页 点的重要度和边的长度选择初始的e c o l 集合，建立元操作层次树。在 整体简化过程中，应先简化重要度小的边，每个顶点有一系列相关联 的边，选取其中一条最短边作为候选折叠边。为了建立较为平衡的操 作层次树，减少操作的依赖性，需要在三角网范围内均匀地选择折叠 边。为此，对点进行网格管理，落在同一网格内的点按其重要度大小 用双向指针串起来。点的重要度越小，则越在网格链表的前端，该点对 应的候选折叠边越早进行折叠。在进行简化时，根据视锥体准则、 背面准则以及屏幕投影误差准则进行边折叠合点分裂。由于点分裂 是边折叠的逆向操作，因此点分裂的顺序必须与边折叠得顺序准确 相反。 关于递进格网算法的更多细节，请参阅p r o g r e s s i v e m e s h e s ( h u g g u eh o p p e ，1 9 9 6 ) 。 2 3 2 基于顶点删除算法的t i n 简化 一般情况下，顶点删除算法主要应用于建立离散的格网l o d 模 型。当初始模型为t i n 模型时，对于给定的数据点集，需要建立的 则是一个层次化的三角形网络结构j 而顶点删除简化算法的实质就 是根据原模型的精度要求，通过用数量较小的大三角形代替数量较 多的小三角形从而相应减少模型中三角形的数量，以获得不同复杂 层次的同一场景的三角形网格，该算法中顶点被删除的条件必须同 时满足：自由度小于给定值：重要度小于某个预先定义的值：相邻 点组中没有顶点被删除这三个条件。 2 3 3 基于最大独立点集的简化技术 张锦提出了一种t i n 构造方法【3 l 】，就是最大独立点集法构造地 形层次结构，它是采用自底向上的方法，使用d e l a u n a y 三角形序列 来构造层次树，层次越高，地形表示越粗糙。从最低层次的t i n ， 通过一定的法则，去掉一些点，得到高层次的t i n ，循环操作就可 以得到一个层次t i n 。在最开始构造底层t i n 时，在选择最大独立 点集时，需对特征点标记，以便不被删除。该方法最大的缺点就是 只能依次构造层次三角形，不能跳跃层次。同时，寻找最大独立点 集也是耗时的。有鉴于此，他在l u e b k e 的层次动态简化方法基础上 耍直窑道盔堂巫主塑塞生堂焦垒塞蔓；! 基 图2 8背面别除例子 2 4 4 遮挡剔除技术 遮挡剔除是用于剔除绘制区域内被高耸地物或地貌遮挡的对 象，以便加快绘制速度。在该类技术中，要解决的关键问题是如何 快速剔选这些高耸的地物地貌，以便快速准确的剔除该类对象周围 被遮挡的对象。一个最好的方法就是将地形进行聚类分析，然后进 行分类存储，并建立不同类的对象之间的拓扑关系，并在此基础上 对临近对象设置遮挡视线阈值，以便在实时绘制时快速判断。 2 5 轮廓保留技术 大规模地形的轮廓，即特征线，含有大量的可视化信息，因此 在实时显示时具有很重要的作用。针对地形而言，有两种方法可以 用于不规则格网的l o d 技术中。一种是预先提取特征线，然后实时 插入到不规则格网中：另一种方法便是实时探测保留技术。即在构 建不规则格网的时候，采用一定的探测原理，对特征点、线进行识 别别进行标志保留。采用第一种方法的时候，可以对特征点线和非 特征点线进行区分对待，即采用不同的误差机制来简化他们。例如， 可以对特征点、线的误差阙值设置时增大( 相对于非特征点、线) ， 即提高了特征点、线的相对重要度，这样就可以有效的保留了这些 重要的特征点、线。第二种方法原理简单，通常采用三角形法向量 来进行判别，如果其法向量方向在9 0 度上的某个很小的阚值内，则 亘蜜至逗大学硬士研究生学位论文 第2 6 页 第3 章几种基于不规则格网的l o d 算法 在本章中，将介绍当前几种常用的基于不规则格网的l o d 算 法。主要有以下四种：基于点删除的l o d 算法；基于静态t i n 的 l o d 算法；基于h y p e r b l o c k q u a d t i n 的算法；基于独立点集的l o d 算法。首先会对这几种算法进行介绍，然后分析各自算法的优点与 缺点，最后作出总结，阐述基于不规则格网算法应当遵循的几条原 则。 3 1 基于点删除的不规则格网的l o d 算法 l o d 模型的建立，首先要面队模型简化问题。模型筒化算法中 最直观的方法就是顶点删除简化算法【4 。顶点删除的过程实质是根 据对原模型逼近精度的要求，相应地减少模型中三角形数目，即用 数量较少的大三角形来取代数量较多的小三角形，从而可获得不同 复杂层次的同一场景模型的三角网描述，见图3 1 。 “) 街化前 图3 1顶点删除示例 顶点删除简化算法主要用于建立离散的网格l o d 模型。一般而 言，对于三角彤格网，不同层次模型的三角形之间不能进行层次描 述。从图3 1 可以看出，虽然不能用细节较高的几个三角形取代细 节较低的一个三角形，但可以用细节较高的一组三角形取代细节较 低的一组三角形。因此对于一个t i n 格网，遍历所有的顶点，删除 西南交通大学硕士研究生学位论文第2 7 页 可满足条件姿捣栈臻羿氢型翼阿姐朔；到节相应的主级别乖子级别 静刁豫j 澎鬻美望鼎蔫瑾堪遵燃嘏埋撩r 氍誊汀立j j 巯耕肚铂砷努 黔蛔萌兰贻；塑型于缎烈龆款i 琵懈戡雕鞠疑蛆键够苷一椰钓妇 薛辨! 鞭鞭“鹾惦精媸酗。的曲趟葬鞴氡钔f j 蔫盔塔淄拦鞋笺 臣，嬷臻嬲嗣”b 捕薰尊秤署薹疆鬣学露， 鋈；萎薹鋈警薹囊i 蚕萎娄品肇囊蚕 和1 ：5 万这三个主级别，则从上向下查找到的主级别应 该为1 ：5万) ，读取该级别上相应场景范围的t i n 数据并进行渲 染。 在该算法的实现中，为了很快的产生t i n 模型，同时也为了保 持接边一致，它采用了均匀分块的办法，对于t i n 的生成则采用逐 点插入的办法。在实时构网时，为快速生成t i n ，快速判断插入点 所在位置，将矩形区域进行“虚分块”。在插入每个三角形时，获取 该三角形的最小外接矩形，并获取该外接矩形内包含的虚块，判断 每个虚块与该三角形的位置关系，如果二者相交，则向该虚块中添 加该三角形。同时针对d e l a u n a y 构网使用的频繁，也设计相应的优 化算法。针对模型块的拼接，为达到快速目的，在块边界处设置公 共插值点。在地形t i n 模型分辨率评价函数使用上，采用下面公式 计算地形t i n 模型使用的分辨率： 土 c( 3 1 ) d 其中，d 为视点到观察点的距离，c 为一个可调节的因子，c 越 大，地形细节越多，反之则越少。 3 3 基于h y p e r 引o c k - q u a d t l n 的算法 超块四叉t i n 算法( h y p e r b l o c k q u a d t i n ) 【1 7 1 是一种视相关算 法，它是采用块选择，目标是充分利用块选择的快速性和使用预先 计算好的三角带。三角带是基于块数据结构。 3 3 1 超块构建 超块a d t i n 文件作为输入，遍历 x 西南交通大学硕士研究生学位论文第3 2 页 i n tn u m s t n p 【1 6 ； i n t + s t r i p 【1 6 】； f l o a te f r o r ： ) 每个超块层的基本的和扩展的三角化都存储在这种数据类型 中，十六种三角带构造( 基本的外加十五种扩展的构造见图3 3 ) 在 构造过程中生成并阻三角带的形式存储( 长度存储在n u m s t r i p 中) 。 字段误差包含了属于对应的基本构造层中的节点的最大的几何近似 误差。 3 3 3 超块四叉t i n 的绘制 1 超块和基本块层的选择：在视锥体内的超块选择，超块树是自顶 而下递归遍历。每个节点的边界球用来执行视锥体测试。从每个 视锥体金子塔面到边界球中心的距离被计算和边界球半径比较。 如果大于边界球半径，那么该节点的任何子孙节点和超块都位于 视锥体外，于是该节点被去掉。当一个超块选中后，层误差投影 到屏幕上并与给定的屏幕容许误差相比，最小层投影误差比允许 误差要小。 2 基本块层的调整：一旦超块层选中后，这个阶段中，如果临近层 次差异超过一层，则通过增加低层临近超块来去除裂纹。 3 扩展块层的选择；在这点上，超块层是被设置了，基本形状也是 假定了的。最后的调整采用扩展边界形状表( 图3 3 ) 来保证跨 超块之间的自由裂缝的三角化。 廉_ 寓_ 离 a ) 超块和基本块层的选择b ) 基本块层的调整c ) 扩展块层的选择 图3 4超块四叉t l n 的绘制 亘童銮夔盔兰塑主壁窒生堂焦迨窒蔓i ：夏 姗8 馘 匐吣 c ) 图3 5 绘制阶段和超块的屡转换 有关超块四叉 t i n的细节过程，请参阅 h y p e r b l o c k q u a d t i n ：h y p e r b 1 0 c kq u a d t r e eb a s e dt r i a n g u l a t e d i r r e g u l a rn e t w o r k s ( l a rior ，2 0 0 3 ) 3 4 基于独立点集的l o d 的算法 3 4 1 理论 基于独立点集的l o d 的算法f 2 3 】的层次理论是这样的：我们以层 次地形的全分辨率地形作为开始。为了从一个层次转向另一个层次， 粗糙层，大量的非临近点从地形中移走，并且地形进行从新三角化。 由于重新三角化仅仅是一个局部操作，当三角网抽取时，地形可以 在不同的部分采用不同的层次细节进行描述。 3 4 2 描述 我们的层次包括两个结构：三角形和多边形。三角形简单的包 含三个角数据点。一个三角网是由一系列三角形形成的。多边形对 于其自身覆盖同样的区域包含两列三角形：一列为指向子三角形， 超一露 一团渤囚盟一魏 亘里变通盎堂耍研究生学位论翻 g 目崮 贰匠 誓； 氍和新翻朝昊茧葡肇旨翼醐黧j 壤娃鳙酗孽酥惑重 鋈邋壤匾。墨氆噻藩蹲罐融埕蔫瑗埠蠕雌塔霪二丽苫鲻鬟意糖箍猫 。：鬓。鬈藕j 誊： ：蒸：麓：i 蒸；! 簇j j 纛。j 纛j? 誉。蓥j 一黪j瓣雾萋藜? 熹l 一莓而可瞄将翼忍鬟翼i 薹i 囊薹塞耋；氟 鹱薹鬟蚕篓蓁吃! 簪稚翔钧 膳翻稀：俐粤气嘲嫩驾情国晦阵反 比 ，与视点到模型空间误差p ，的距离d 。成反比。为简化计算，实际 的算法采用最大屏幕投影误差法，令卢= o ( 即视线总是平行于x _ z 平面) ，由此得到的一个保守的投影误差值，见式2 3 ： 铲 高罢 协3 ， 由式( 2 3 ) 可知，e 一定时，d 。越大，e ，也就越小，如用户指定 的阈值为s ，那么当以充分大时，其在屏幕上的投影误差p ，可以小 西南交通大学硕士研究生学位论文 第37页该区的一个更高层。 请注意p i ( v ) 的子层与父层在其可以产生的地方可以超过不止 层的差异。当所有的i i 中的点都重新移走了，其对应的多边形也就 已经建立起来了，一个建立过程也就完成了。然后，该步通过在一 个新的三角网中选择一个新的独立点集来重复直到没有点可以选 择。下图表明了上面例子的层次的完全构建过程。圆圈标志了下一 步要移走的点，虚线是插入的新边。 3 5 算法分析 图3 1 0屡次构建例子 3 s 1 数据结构分析 基于点删除的算法中有节点和三角形两种数据结构。对于节点 数据结构，它可以直接获得顶点周围邻强焉噬臻鹌确勤醐驰刊，m 稠1 措陶昏跖；三角形数量垂岜 副誊型蓥i 拍嚣戳辩翳貂醐氙 鞫拦驰磐；心羔演魂椎送毒嚏傅肾噬。鼍 噎谚i 确的簧不红装砸 璃滢强薹骟髓蚂一 形含有相 同数量的最小邻近三角形时，算法就向它的邻居的邻居的前一层寻 找并选择最小化度数的方向，如果又存在一个带子，就任意选择。 西南交通大学硕士研究生学位论文第3 8 页 块数据在文件中的酋地址，然后再存储各块的数据。对于每块的数 据，首先定义了块所在的矩形，然后是记录该块的数据量大小，接 着存储该块的数据，最后是索引量大小和索引的详细记录。块数据 结构有利于快速读取原始数据，并且可以采用索引来快速找寻原始 数据的位置。在具体三角化时，它的数据结构和点删除有些相似， 但比点删除的数据结构要好，这是因为在三角形的数据结构中，它 定义了三角形的最小外界矩形，这对于在实时绘制时进行三角形的 快速剔除具有重大的意义。 基于超块四叉t i n ( h y p e r b l o c k q u a d t i n ) 的算法中，有树、 超块和信息层三种数据结构。综合分析，该数据结构采用了包围球， 可以进行快速剔除，另外，采用了超块，有利于数据的快速读取。 基于独立型箕夥螽紊璧善荐嘎豫蝎噬憾琊鼍旧曜耀滢；琴殳搿慨 剞稻啪剡艇降鬲；若龇戬鑫翟但强掣南曲州热鲫静戳坠￥娶。百型 接蟹垦药旦誉蜀誊黧裂；婺习热氍溢揖鲢瓢；罐篡理灞澹蟛提m 妊掰懿醺担i 攀舍盔括毕去璺矗列热强殚搿曙：坛蒸引端坐野 捌矧戳剖型陧曜豫黼穗噬啜崾州强j ! = g j i 辇善型儡罂矮 塔咒馨型尘季舌望态型；醛黧鳇 锄魍r 对嚣蔫咏i 矗强漏 强矍攀蠹扎蝶稚嫦鲥懿辩翘些；西包含了隐藏面移走技术、背面剔除技术、遮挡 剔除技术，这里主要研究了隐藏面移走技术，包含深度排序技术和 对象空间技术。对误差的计算，本文对一般的原理作了介绍。在最 后，对加速绘制三角形的基本算法，三角带化算法作了 x 西南交通大学硕士研究生学位论文第3 9 页 据量。存储量最大是静态t i n 的l o d 算法，因为该算法存储了大量 的不同分辨率的数据。 在数据读取方面，基于静态t i n 的l o d 算法和基于超块四叉 t i n ( h y p e r b l o c k q u a d t i n ) 的算法居于优先地位，因为这两种算 法都采用了分块技术，这对于海量级的数据读取无疑有绝对的优势。 丽超块四叉t i n 的算法还将数据进行了分类处理，这更进一步提高 了数据的读取速度。至于基于点删除和独立点集删除算法，由于没 有考虑这方面的因素，只能针对少量数据的读取。 在数据简化效率方面，简化率最高的是静态t i n 的l o d 算法，该 算法是人为设置简化率，与地形数据的属性无关。最差的是基于独立 点集的算法。他在相邻层次问的简化效率不超过2 0 。 最后，在实时显示质量与效果方面，超块四叉t i n 算法是最好 的，它考虑到了分块后的快速接边。对于静态t i n 的l o d 算法，它 存在视觉跳跃现象，同时它额外的增加了分块边界点，以求接边一 致。而对于独立点集的删除算法，显然是存在视觉跳跃现象的，同 时独立点集删除未考虑特征点不能删除，这也影响了绘制出来的图 象的真实性。至于点删除算法