（计算机软件与理论专业论文）基于格网划分的地形lod算法优化研究.pdf

河海大学硕士研究生论文摘要 摘要 长期以来，地理信息系统资料的分析解释成果局限于二维静态表达方式，它 绘人们直接、完整、准确地理解与感受成果所反映的地表地形地貌情况造成了困 难，也限制了资料的充分利用。科学计算可视化技术的发展为利用g i s 资料分 析解释成果、重建地表三维模型创造了条件。 本文针对当前地形三维可视化及其实时绘制技术的研究现状，在吸取三维计 算机图形学、科学计算可视化、虚拟现实的先进理论和技术成果的基础上，围绕 地形三维可视化及其实时绘制技术中的地形简化、层次细节、三维真实感地形生 成等核心技术内容展开讨论与研究，提出了一种基于地形四叉树实时构建地形多 分辨率模型的优化算法，该算法采用分块分层的思想。首先将大规模高程数据进 行分块，然后对块内数据按照分辨率的大小分层存储，并给出一种与视点相依赖 的对地形节点误差进行评价的方法，在网格的生成中只使用一次四叉树遍历，从 而大大提高了渲染速度。 作者结合参加水利部科技创新项目“引江济太三维模拟系统”的经验体会与 实践以本论文的理论研究成果为基础开发了一个三维可视化系统。系统具有数据 输入与预处理，地表三维模型的计算机重构，三维模型的实时动态简化与多分辨 率表示等功能。实验表明所提出的方法高效可行。 关键词三维可视化，虚拟现实，细节层次模型，四叉树，视相关 基子辖厨划分的地形f ，0 d 算法优化研究 a b s t r a c t f o ral o n g 石m ep a s t ，a l lo ft h ci m e r p r e t a t i o nr e s u l t s 舶mg i sd a t ah a v eb e e n d i s p i a y e d o rm a p p e db yh 捌n gr e s o r tt o2 da n ds t a t i c a p p r o a e h t h a c r c a t e s d i m c u l t yf o rp e 叩l et ot e l li m m e d i a t e l ya 1 1 dp o s i t i v c l yw h a tt h eo v e r a nr e s u l t sm e a i l s a b o mt h et e r r a i ns u r f a c e ，a i s o ，m er e l e v a n ti f o n a t i o no b t a i n e dc o u i dn o tb eb r o u 曲t i n t oi t s 砌ip l a y t h et e c h i l i q u eo f v i s u a l i z a c i o ni ns c i e n t m cc o m p 谢n gp a v e s4w a yt o r e b u i l d3 dt e r r a i nm o d e lu s i n gt h ei n t e r p r e t e dr e s u l to fg i sd a 诅 t 王i s h e s j sf o c u s e so nt h e 1 1 e o r c t j c a ja n d 田e t h o d 0 1 0 西c a ls t u d i e si n 吐l es e v e r a l s u b t o p i c s ：3 dt e r r a i nv i s u a l i z a t i o na n dr e n d e r i n g ，t e h a i ns i i n p l m c a t i o n ，l o d ( l e v e l o fd e t a i l ) ，a 1 1 dm u l t i r e s o l u t i o nt e r r a mr e p r e s e n t a t i o n t h e s es t u d i e sa r eb a s e do nl o t s o fa d v 锄c e dr e s u l t so f3 dc o m p u t e rg r 印h i c s ，s c i e m i f i cc o m p u t 撕o nv i s u a l i z a t i o n ， a n dv i 咖a l r e a l 时aq u a d 廿e e _ b a s e do p t i i n i z a t i o na l g o r i t h m f o r d y n a m i c a l l y g 。n e 豫矗o nc o n t 血u o u sl e v e l so fa 百v e nc o m p e xj a n d s c a p ei n 玛8 lt i m 。j sd e v e k p e d i nt h i sa l g o r i t l l m ，a nm o u g h to f p a n i t i o n i i l gm et e r r a i nb o ms p a t i a l l ya n dr e s 0 1 u t i o n ” i sa p p l i e d i tf i r s tp a n i t i o n st h el a r g ed e md a t ai m o s o m es m a l l e rs u b - b l o c k sa j l dm e n s t o f e sm ed 如i nr e s o l u t i o no r d e ri ne a c hs u b - b i o c k ，t h ev i e w d e p c n d e n td y n a i i l i c n o d ee r r o re v a l u a t i o nm e t h o di sa l s op r 叩o s e d r e n d e r i n gs p e e di sg r c a t i yi m p r o v e d b yu s i n go m y o n eq u a d n e e 妇v e r s a li nm e s hg e n e m t i o n a t1 a s t ，b a s e do nt h er e s e a r c h e dr e s u l to ft 1 1 ea b o v ep r o b l e m a t i cs i t u a 缸o n ，t l l e 1 f e e d i m e n s i o n a l v i s u a l i z a t i o n s y s t e m h a sb e e ne s t a b l i s h e d c o m b i i l i n g谢m e x p e r i e n c ea n dp r a c n c ei nm ei t e mo f “3 d d y n 锄i cs i m u l a t i o ns y s t 锄( d e r i v a t i n g t h ew a t e f 丘d mc h a n 西i a n gt o1 越h ul a l ( e ) ”1 1 1 es y s t e mh a st h e s e 劬c t i o n s ：d a t ac a n b er e c e i v e da n dp 咒t r e a c m e n t ，出r e e d i m e n s i o n a 王v i s 啦i i 2 a t i o na 1 1 dd y n a r n i c a 呈d i s p i a y o f t e r r a i n ，m r e e d i m e n s i o n a lm o d dr e a l 一t i m ed y n a m i c s i i l l p l 讧i c a t i o n a 1 1 d m u l t i r e s 0 1 u t i o nr c p r c s e n o n e m p i r i c a lt e s t ss h o w 山em e t h o di sr o b u s t ，a r l df 瓠t k e y w o r d s 3 d v i s u a l i z a t i o n ， v i m “ r e a l 崎， l e v e lo fd e t a i l ， q u a d t r e e ， e w - d e p e n d e n t i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均己在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 叠盘一 口。年b 月7 日 l 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) 垒聋。【，年( ) 月 目 河海大学硕士研究生论文第一章绪论 1 1 引言 第一章绪论 随着计算机技术及空间技术的迅猛发展，地形三维可视化及其实时绘制是当 前计算机图形学、虚拟现实、g i s 等领域的热点研究问题。可视化是指利用计算 机图形学、图像处理技术和虚拟现实技术，将事物的发展变化过程转换为更易被 人们理解的图形图像的形式显示出来，并能进行交互处理的理论、方法和技术。 而实时绘制技术是指以足够的帧率在计算机上动态交互的生成和显示图形、图像 画面的理论和方法，它是保证可视化技术中图形、图像画面能否动态交互的关键 技术。这样，地形兰维可视化及其实时绘制技术是指在计算机上对数字地形模型 ( d i g i t a lt e r r a i n m o d e i s ) 中的地形数据实时地进行三维逼真地显示、模拟仿真、 简化、多分辨率表达等内容的一项技术。场景模型趋于多样化、复杂化是复杂几 何环境中造型数据的重要特点。 要让计算机所绘制的场景达到实时变化取决于两点：一是所采用的计算机平 台具有很高运算速度；二是所绘制的几何目标要尽量简单，通过减小计算量的方 法来增加实时性能。众所周知，所有的计算机图形制作系统的制图能力都是有限 的。在一定的帧频下，每帧所能绘制的原始几何模型( 三角形) 数是有限的。因 而，降低模型复杂度是实现复杂场景实时绘制与漫游的关键所在。于是，在虚拟 现实的视景仿真中，为提高视景生成的效率，达到视景充分实时绘制的要求，采 用场景简化技术，以减少绘制多边形的数量，提升渲染速度是现在研究的热点。 1 2 技术背景 本课题是在地形三维可视化项目背景上提出的。地形三维可视化是研究未来 地理信息系统中众多复杂的信息并以人们最能接受和最直接的方式表现的理论 和技术。当前的地理信息系统主要是处理数字式的地图，大部分是静态的二维地 图。在数字地球研究中，用户不仅对传统的静态地图、电子地图感兴趣，更需要 对地理现象的演化过程进行可视化和动态分析、动态模拟。复杂的静态地图，不 管是印在纸上还是显示在屏幕上，都不能满足用户的要求，他们希望一个动态的、 三维可视化的、交互的环境来处理、分析、显示他们的多种地理数据，这对三维 基于格网划分的地形l o d 算法优化研究 地形可视化及其实时绘制也提出了更高的要求。由于研究对象的范围大、复杂度 高，因此首先必须研究大规模复杂场景的简化与显示技术，在此基础上建立和实 现三维场景显示漫游系统。 1 2 1 三维数据场可视化技术 可视化( v i s u a l i z a d o n ) 在没有成为信息技术专业术语之前，仅是形象化的 一般性解释，它是指人脑中形成对某件事物( 人物) 的图像，是一个心智处理过 程，促进对事物的观察及概念的建立等。随着科学技术的迅猛发展，可视化被赋 予了新的含义。 科学计算可视化( s u a l i z a t i o ni ns c i e n t i cc o m p u t i n g ) 是发达国家在2 0 世纪 8 0 年代后期提出并发展起来的一个新的研究领域。科学家们不仅需要分析计算 机得出的计算数据，而且需要了解在计算过程中数据的变化，这些都要借助计算 机图形学及图像处理技术。因而“将图形和图像技术应用于科学计算是一个全新 的领域”。近年来，科学计算可视化又扩展到工程计算可视化及测量数据可视化。 实现科学计算可视化具有多方面的重要意义。它可以广泛应用于气象学、石 油勘探、计算流体力学、分子生物学、医学教育与医疗、有限元分析等领域。它 是发现和理解科学计算过程中各种现象的有力工具；它可以大大加快数据的处理 速度，使目前每日每时都在产生的庞大数据得到有效的处理：它可以在人与数据、 人与人之间实现图像通信，而不是目前的文字通信或数据通信；它还可以使人们 对计算过程实现引导和控制，通过交互手段改变计算依据的条件并观察其影响。 总之，科学计算可视化将极大地提高科学计算数据的处理速度和质量，实现科学 计算工具和环境的现代化。 科学计算可视化的核心则是三维数据场的可视化。( 见图1 1 ) 图1 1 可视化技术的三层结构模式 河海大学硕士研究生论文 第一章绪论 三维数据场可视化的对象是三维数据，三维数据中的每个数据元至少有相应 的空间坐标属性。三维数据场可视化研究的主要内容包括规则数据场可视化、不 规则数据场可视化、散乱数据场可视化及矢量数据场的可视化等。就其可视化算 法来说，可划分为两大类：面绘制和体绘制。 1 2 2 虚拟现实技术 虚拟现实( n u a lr e a l i t y ，简称v r ) 技术是产生于本世纪六十年代的一项 高新技术 1 】。广义地讲，它是一种人类可视化地与计算机和极为复杂的数据进 行交互操纵的技术。狭义地讲，虚拟现实是一种人机界面。它是多门学科的综合， 所涉及的学科有计算机视觉、图形与图像处理、自动控制、人工智能：计算机网 络、计算机通讯等等。在虚拟环境中，用户看到的是全彩色主体景象，听到的是 虚拟环境中的卢音，手或身体的其它部分可以感受到虚拟环境反馈给他的作用 力，由此使用户产生一种身临其境的感觉。亦即人以自然的方式来感受计算机生 成的虚拟世界。 其基本特征可以用一个如图1 2 的三角形来表示：第一个特征是沉浸，让参 与者有身临其境的真实感觉；第二个特征是交互，v r 的交互特性主要是通过使 用虚拟交互接口设备实现人类自然技能对虚拟环境( r t u a le n v i m n m e n t ，简称 v e ) 对象的交互考察与操作；第三个特征是构想，从图形角度来说，传统的计 算机图形学强调了三维场景在屏幕上的二维显示，虚拟现实技术则强调三维图形 的立体显示。 图1 2 虚拟现实技术特征 基于格两划分的地形l o d 算法优化研究 尽管虚拟现实技术出现仅仅短短的三十多年，但是它在社会许多领域的广泛 应用使这项技术具有了强大生命力。当然目前v r 还有许多软硬件的技术和理论 不成熟。但是随着计算机硬件设备处理能力的不断提以及人们对虚拟现实技术研 究不断的深入，虚拟现实的技术会越来越成熟。未来的虚拟世界表现得更加真实、 客观，而且虚拟现实系统低廉的价格使它走进千家万户，成为人们生活中的一部 分。出色的虚拟现实系统使人们的工作更加轻松、安全和高效，使人们的生活变 得更加丰富多彩。可以这么说，二十一世纪是虚拟现实技术广泛普及的世纪。 1 3 研究现状 地形景观模型的三维可视化及漫游是g i s 、虚拟现实、游戏、仿真等的关键 技术已成为近年来的研究热点，取得了卓有成效的进展，目前最主要的简化技 术大致可以分成两类，分别简单介绍如下： ( 1 ) 可视范围撷取( v i e wc u u i n g ) 指绘制前先将不在视点可视范围内的多边形模型予以去除，当绘制时，就只 将位于视点可视范围内的多边形模型，交给负责渲染管道( r e n d e rp i p e l i n e ) 工 作的硬件处理。 因为考虑到人类视角大小的限制，当观看一个场景时，在人眼视角外的物体 是看不到的：也就是说，若能够在绘制之前，即将看不见的场景部分去除，而不 加以绘制运算也不会对正确的绘制结果造成影响。如此，降低渲染管道系统处理 的多边形数量，可有效的增进绘制速度。使用可视范围撷取的方法，通常会先以 球体边界( b o u l l d i n gs p h e r e ) 或方形边界( b o u n d i n gb o x ) 的方式对整个场景做 简易的分割动作，然后再测试球体边界或方形边界是否完全在可视范围外。若是， 则球体边界或方形边界覆盖的多边形则可快速的全部去除：若否再交由硬件来执 行更细致部分的可视范围撷取。 ( 2 ) 细节层次模型( l e v e lo f d e t a n ( l o d ) m o d e i i n g ) 上面介绍的技术在减少绘制多边形的数量，也就是在渲染画面时，先把视觉 范围外或确定看不到的多边形去除然后才绘制其余的多边形。这样的做法加快 了实时绘制的速度，但是场景中若有许多复杂的物体模型，需要处理的多边形数 量还是太庞大，依然是达不到互动绘制速度的需求。于是，使用多边形化简技术 4 河海大学硕士研究生论文 第一章绪论 的细节层次模型就显得非常重要了f 2 1 。 在场景渲染时，如果一个物体距离视点很远，其显示结果在画面上只占很小 的几个像素，用很复杂的多边形模型去处理确实是很不值得的。因此，使用较低 精度的模型去呈现远离视点或偏离视点的物体，视觉效果上没有什么损失，但是 给予渲染管道系统的负担却有很大的差别。基于这个想法，因而产生了细节层次 模型的技术。 目前通常有两种方法构建l o d 模型，其中一种是静态的l o d 技术 3 6 ，即 将d e m ( d i g i t a le 1 e v a t i o nm o d e l ) 数据做成多个精度不同的层次，漫游时则根据 视点的位置调用不同层次的数据；另外一种是实时动态的l o d 生成技术 7 1 0 】， 即一次将d e m 数据读入计算机内存，然后在三维场景中漫游时，可根据视点位 置实时地调整网格的层次。但对于大规模地形数据，它们都有固有的缺点，静态 l o d 模型存储空间要求大，不同分辨率之间切换比较生硬，不便于分辨率相差 太多；与视点相关的动态l o d 模型由于动态简化的复杂计算而加重c p u 负担， 出现显卡等候c p u 数据的情况，严重影响绘制速度，并且在执行实时l o d 操作 时，需要读取较多的数据到内存。 为了使得到的场景具有比较高的真实感，除了加入光照投影等技术之外，纹 理映射技术也是其中的一个重点。将真实世界得到的照片或图片作为纹理图映射 到建立的场景原始模型中，可以得到效果更逼真的三维图像。 1 4 本文的工作和组织结构 1 4 1 本文的工作和目标 本文针对当前地形可视化的研究现状，在分析了现有地形简化算法的基础 上，提出了一种基于地形四叉树实时构建地形多分辨率模型的优化算法和纹理映 射方案，并结合本人所参与过的引江济太动态模拟这一项目的设计和开发过程设 计了一套完整的针对大规模复杂场景的三维重建与漫游方案。针对场景规模大的 特点，首先将大规模高程数据进行分块，然后对块内数据按照分辨率的大小分层 存储，并给出一种与视点相依赖的对地形节点误差进行评价的方法，在网格的生 成中只使用一次四叉树遍历，从而大大提高了渲染速度。 基于格网划分的地形l o d 算法优化研究 其中主要的研究范围是集中在与视点相关的多分辨率模型的可视化系统，内 容包括下列几项预计完成的目标： ( 1 ) 实时的绘制 通常要保持绘制图像的视觉品质，又不影响到交互式绘制的速度，就要做到 有限时间内选取到最佳化的多层次细节模型。最佳化多层次细节模型的意义包含 两点：第一，是多层次细节模型的投影误差能够小于预设的上限；笫二，是多层 次细节模型的多边形数量能够达到最少。我们希望能在规划的时间内完成建构最 佳化多层次细节模型的步骤，利用缩短多层次细节模型建构的时间，来提升绘制 速度。 ( 2 ) 几何连续的多层次细节模型 除了实时的绘制之外，使用者若想获得较逼真的显像，还要考虑多层次细节 模型是否能够符合几何连续的情形。通常具有高度值的地形资料经过三角化程序 后，建构好的多层次细节模型可能在相邻区闻连接的地方产生t 交点 ( t _ j u n c t i o n ) ，如果是采用这种不理想的多层次细节模型就会在绘制的视觉效 果上出现破洞( c r a c k s ) 现象。 ( 3 ) 可供使用者选择或调整的误差控制 这是一个具有高度弹性的机制，使用者可配合绘制系统的硬件效能选择适合 该设备的绘制误差，使得多层次细节模型的地形可视化系统能够提供符合使用者 需求且最适合的绘制速度与图像品质。这种友善的接口设计，是希望地形可视化 系统能够在不同的硬件设备下，发挥最大的绘制功效。 ( 4 ) 地形地表贴图 贴图是要表现地形细部的特征，希望藉由地形细节贴图的变化，把山、河等 常见的自然景观或人造建筑物表现出来，做到高品质的视觉仿真。 1 4 2 论文的组织 论文共分五章，主要内容如下： 第一章绪论。主要介绍地形三维可视化及其实时绘制技术概念，所包含的 技术背景、当今研究现状、本文研究内容、目标和论文的组织。 第二章相关研究。主要介绍l o d 的起源，算法分类和主要算法，其中重点 6 河海大学硕士研究生论文 第一章绪论 介绍了基于地形场景绘制的典型算法和各算法的优缺点。 第三章基于四叉数l o d 简化算法。重点阐述针对大规模复杂场景这种特殊 对象本文所提出的基于四叉数的分块分层简化算法，并给出一个与视点相依赖的 度量标准。 第四章三维地形可视化的实现与分析。作者利用通过o d e n g l 结合v i s u a l c + + 开发了一套适用于大规模三维地形可视化的实验系统，本章对该系统中所采 用的开发工具和具体实现方法进行介绍与分析。 第五章结论与展望。总结本文的工作，提出今后需要进一步研究的问题。 基于格网划分的地形l o d 算法优化研究 第二章相关研究 本章首先介绍了关于l o d ( 细节层次模型) 的基础知识，然后从多边形场 景和复杂几何模型的应用角度对简化算法进行比较并对几个典型算法进行了重 点介绍和分析。 2 1 场景简化的提出 基于几何造型的视景生成技术是一种传统的图形生成技术，主要涉及动态建 模和三维图形显示，为保证三维图形的快速生成，必须降低复杂度。实时显示就 是要求图形显示速度必须跟上视点移动速度，消除迟滞现象。当场景很简单，例 如仅有几百个多边形，要实现实时显示并不困难，但是，为了得到逼真的显示效 果，视景中往往有上万个多边形，有时多达几百万个多边形，这就对实时显示提 出了很高的要求。降低场景的复杂度和选择合适的成像算法是关键。 ( 1 ) 选择合适的成像算法 亮度描述的是光线在模拟物体表面的一个像素点反射后的强度，并被观察者 看到。逼真图形的生成算法，图形学中大都采用光线跟踪等算法，但它们的开销 都较大。不是本文的重点，不作介绍。 ( 2 ) 降低场景的复杂度 随着科学技术的进步，在计算机图形学、计算机辅助设计技术、计算机动画、 地理信息系统等领域内所构造和使用的模型，越来越复杂。例如，一幢建筑物模 型，室内的设备等，达到2 0 0 万个多边形。前面我们讲到的，用高精度d e m 数 据构造出的地形模型具有近3 0 0 万个多边形( 三角形) 。模型复杂程度的提高， 对计算机的存储容量、计算速度、传输速率均提出了很高的要求。 人们往往认为，可以利用高档计算机来处理、存储复杂的模型，如使用计算 速度高、存储容量大、图形功能强的图形工作站等。虽然这是有效的办法，但不 能完全解决问题。首先随着应用需求地发展，模型复杂程度的增长几乎是无限的。 机器的性能提高了，模型的复杂程度也会增加。其次，高档计算机需要大量的投 资，非一般用户所能承受。因此，如何利用中档的计算机，特别是微机来处理复 杂的几何模型，是近几年来的热门话题。特别是虚拟现实技术的出现，对复杂模 型的实时动态显示提出了更为迫切的要求。因此，在利用性能较高的计算机的同 河海大学硕士研究生论文第二章相关研究 时，人们提出了多种技术和算法，力求更有效地解决复杂模型的处理、存储、传 输和绘制的问题，其中，一个非常有效的方法就是采用l o d ( 细节层次模型) 降低场景的复杂度，即降低图形系统需处理的多边形数目。 2 2l o d 的概念 在计算机图形学的应用领域中，物体模型多采用多边形网格来描述。描述场 景中的多边形数目越多，所绘制的图像质量就越高，但是绘制速度也就越来越慢， 从而形成了一对矛盾。一般说来，图形绘制速度与模型中的多边形数目成反比。 尽管图形绘制系统的性能在近几年有明显提高，但是总会有一些场景太过复杂， 不能实时绘制。尤其在场景漫游中，要实时绘制的复杂场景可能要包含上百万个 多边形。这种情况下，必须采用必要的简化技术，来降低复杂度，以谋求场景真 实性与实时性的协调。为场景提供不同的l o d 描述就是控制场景复杂度和加速 图形绘制的一个非常有效的方法。l o d 模型技术在复杂3 d 场景的快速绘制、飞 行模拟器、3 d 动画、交互式可视化和虚拟现实等领域得到广泛应用。 l o d ( l e v e lo f d e t a i l ) ，最初是为简化采样密集的多面体网格物体的数据结 构而设计的一种算法。由于稠密的采样点为三维景物数据的存贮、传输及绘制带 来了极大的困难，所以，许多硬究者试图通过顶点合并方法将这种复杂多面体网 格进行简化。这就是l o d 的雏形。 l o d 技术在不影响画面视觉效果的前提条件下，通过逐次简化景物的表面 细节来减少场景的几何复杂性，从而提高绘制算法的效率。该技术通常对每一原 始多面体模型建立几个不同逼近精度的几何模型。与原模型相比，每个模型均保 留了一定层次的细节。当从近处观察物体时，采用精细模型，而当从远处观察物 体时则采用较为粗糙的模型。同时，在两个相邻层次模型之间形成光滑的视觉过 渡，即几何形状过渡，以避免视点连续地变化时两个不同层次的模型间产生明显 的跳跃。这样，计算机在生成场景时，根据该物体所在位置与视点间的远近关系 不同，分别使用不同精细程度的模型，避免了不必要的计算，既能节约时问又不 会降低场景的逼真度，使计算的效率大大提高。 l o d 简化多边形的目的，不是为了从初始模型中移去粗糙的部分，而是为 了保留重要的视觉特征来生成简化的模型，其理想的结果应是一个初始模型序列 9 基于格网划分的地形l o d 算法优化研究 的简化 i i 】，这样简化模型才可以应用于不同的实时加速。为了实现连续帧的绘 制，l o d 简化方法必须均衡考虑模型的细节度和绘制速率。 2 3l o d 典型算法 l o d 算法发展到现在，已经产生了很多经典的算法。现把它们分为一般几 何模型和地形场景模型分别阐述，并从大规模地形绘制的角度对他们的优缺点进 行了分析。 2 3 1 基于l o d 几何模型绘制 在虚拟实境的应用软件中，目前处理一般几何模型所使用的多层次细节模型 技术，大都是先为同一物体准备多个不同精度的几何模型，然后再依据视点和物 体的距离，动态地选用适当的精度模型。这种多层次细节模型的技术虽然耗费内 存空间，但是由于制作上相当简单，并可直接加快物体的绘制速度，因此普遍地 被整合在实时绘制的系统之中。 在此节中，主要介绍两种一般多层次细节模型化简的方法与优缺点，分别为 边线折迭法( e d g ec o l l a p s i n g ) 和顶点丛集法( v c r t e xc l u s t c r i r 曙) 。 2 3 1 _ 1 边线折迭法 边折迭法中最有代表性的是h 叩p e 提出的累进网格法 1 2 】，也是引起人们普 遍关注的l ，0 d 简化方法，该算法把连接两个顶点的边线折迭在一起，最后只用一 个顶点来表示，而原先与此边线相连接的顶点就用新的边线连接到新的顶点。此 新的顶点可以是原来顶点的其中一个或不同于边线两端顶点的任何新顶点，如图 2 1 所示。这种边线折迭的方式，每一次化简最多可以使几何模型减少一个顶点 和两个三角形。 河海大学硕士研究生论文第二章相关研究 图2 1 边线缩减的模型化简 在h o p p e 的研究中定义e n e r g yf u n c t i o t r e ( m ) 代表模型m 的状态，利用 e ( m ) 函数最终必定会收敛的性质，来停止边线折迭的动作，以求得尽量在不 改变几何模型形状的前提下，用最少的顶点或三角形表示原始模型。 理论上，边线折迭法的好坏可由定义的成本函数来评估，采用不同边线折迭 的成本函数，就会得到不同精度的几何模型。站在主观的立场，是很难断定哪一 种的几何模型才是最佳化，但如果以考虑几何特征保留与拓朴架构调整的问题 时，选择最短边线来折迭并不能使原始模型的几何特征得到良好的维持：若是以 三角形法向量的变动为误差的方式比较能维持原始模型表面起伏和锐边或锐角 的几何特征，但是可能使得多层次细节模型化简的程度受到限制。此外，新顶点 的选择如果只限于折迭边线两端的顶点，将无法调整几何模型的拓朴架构。因此， 新顶点产生的选择，能否由折迭边线上扩张到三维空间中适当的一个邻近位置亦 非常的重要。 边线折迭法的优势是每一次边线折迭运算皆会对应到一个反运算顶点 分裂( v e n e xs p l i t ) ，所以只要依序记录每边线折迭与顶点分裂的步骤，则可 用边线折迭达到几何模型的粗糙化和用顶点分裂达到精细化的目的，如此即完成 了渐进式模型的制作。但是，以边线折迭法制作而成的渐进式模型，因为粗糙化 或精细化的资料太过于琐碎，而使得多层次细节模型的转换过于缓慢，所以较为 不适用于实时显示的应用中。 2 3 1 2 顶点丛集法 顶点丛集法的多层次细节模型化简方式( 也叫做顶点聚类法) ，基本上可视 为是一种对几何模型的顶点重新取样的方法 1 3 1 5 】。如果三维空间中许多接近的 基于格网划分的地形l o d 算法优化研究 顶点投影之后几乎是围绕在同一个像素附近，则这些顶点很直接的就可以只用一 个代表顶点来取代，不但可以使得几何模型的复杂度降低，对于输出的品质效果 也并不会有太大的影响。顶点丛集法就是利用这种观念化简原始模型的：一般做 法上，先将原始模型的方形边界( b o l l i l d i n gb o x ) 做均匀的空间分割( u n j f o 瑚 s d a t i a ls u b d i v i s i o n ) ，使得模型占据的空间分成好几个小细格( c e l l ) ，然后再 每个小细格中选择一个最具代表性的顶点以替代同细格内的其它顶点，最后把所 有代表小细格的顶点重新三角化，获得复杂度较低的几何模型。如此，依据方形 边界分割小细格的大小，就可以制作各种精细度的几何模型。 顶点丛集法将均匀分割之后细格内所有的顶点，用一个同样位于细格内的顶 点来代替，因此可以保证每一个顶点位移的距离绝不会超过细格大小的2 倍。 但往往会因为小细格是均匀分割的缘故，导致化简后几何模型的顶点分布密度亦 趋近均匀，将使得原始模型的几何特征保留效果不佳，可能造成较大的形状失真。 然后，顶点丛集法在简化模型时，因为小细格代表点的取样不受限于原始模型的 拓朴架构，加上顶点取样后可弹性的重新连接，因此自然地具有调整拓朴架构的 功能。 2 3 2 基于l o 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 ，t i n ) 与 规则格网系统( r e g u l a rs q u a r eg r i d ，r g s ) 两种。另外，又依据多层次细节模 型建构时机与建构时考虑因素的不同，区分成与视点无关的地形多层次细节模型 技术( v i e w _ i n d e p e n d e n tl o dm o d e l i n g ) 和与视点有关的地形多层次细节模型技 术( v i e w d 印e n d e n tl o dm o d e l m g ) 。以下先分别说明这四类地形模型的建构 技术与优缺点。 2 3 2 1 与视点无关的地形多层次细节模型 f a l b y ( 1 6 】采用四种不同顶点分布的密度来构建四种不同精度的几何模型，分 别是距离1 2 5 m 、2 5 0 m 、5 0 0 m 和1 0 0 0 m 。在决定选用哪一精细度的几何模型前， 先把1 0 0 0 m 见方的区域平均分割成田字形，接着再细分成更细的四个阶层，因 此此块地形区域就可以用阶层式的四叉树( q u a d t r e e ) 来表示。在显示时，只要 河海大学硕士研究生论文 第二章相关研究 可视范围内的所有区域皆能找到相对应适当的多层次细节模型，就完成了地形模 型的构建。 当然，这样的多层次细节模型有几项明显的缺点，第一因为顶点平均分布的 关系，所以并不能表现出重要的地形特征：第二不同精度模型相连接的区域会因 为顶点取样的不一致而出现破洞的现象。 b e r g 提出每一个层级( l e v e l ) 的地形顶点皆采用d e l a u n a yt r i a n g i 】l a t i o n 的方 式，以构建一个具有阶层性质的多层次细节模型 1 7 。首先原始资料的顶点所形 成的集合是，由计算得到一个最大的不相依子集合( a m a x i i i l a l i n d e p e n d e n t s u b s e t ，o ，而下一层级的集合是_ 等于一，0 ；然后再根据_ 求出。l 、， 以此类堆到，、k ；直到集合的顶点个数少于事先定义的数目为止。因此， 把每个层级的顶点集合、气、口l 三角化就可以得到精度不同的几何 模型，d t ) 、d t _ ) 、口、d t ) 。因为d t _ ) 与d t i + 1 ) 之间相差一个顶点集合，：，所以自然就形成了阶层式的架构，如图2 t 2 。 d t ( 蝣 + c o a s t e n d t ( 鞲d 图2 2 阶层式的多层次细节模型 该方式首先将d e l a u n a yt r i a n g u l a t i o n 方法应用到地形模型的建构上，此外， 在建构多层次细节模型的同时，根据场景边界( b o r d e r ) 上的顶点以及表现地形 特征( 如山峰、河流、矿坑等) 的顶点不能包含于，集合( 即将要移除顶点的集 t 合) 的限制，此做法不但可以成功表现的地形特征，而且还可以把不同精度的几 何模型顺利连接在一起，仍旧维持空间性的连续( s p a t i a lc o n t i n u i t y ) 。 h o p p e 也提出渐进网格模型来解决地形不同精度模型转换的不连续现象。渐 进网格模型由一个简化到最粗糙的几何模型( b a s em e s h ) 和一连串的精细化模 型所组成。渐进式网格模型的动作可以用图2 t 3 的有限状态机制来表示，最粗糙 的几何模型记为m 。，表示了这各渐进网格模型的最低精细度， “经过一次精 基于格厨划分豹地形l o d 算法优化研究 细化( r e f i n e ) 运算q 之后得到精细度模型肘1 ，m l 的粗糙化( c 。a r s e n ) 运算c l 则是将几何模型的精细度由吖l 变回m o 。依此类推，而哆经过t 十1 之后得到 m f + l ，经过0 得到哆一la 如果m o 经过n 次经细化之后可以得到最精细的原始 模型，也就是说它的精细度有n + 1 个状态，我们称这个渐进网格模型有n 个 层次( l “e 1 ) 。 r 1r 2 r i r i + 1r 抛 r n c 1 c 2 2 c n 图2 3 渐进模型示意图 这个算法的优点在于可以生成连续细节层次，支持模型的累进传送和有选择 的简化，并且还考虑到模型上纹理信息的处理。 但是，这类与视点无关的地形多层次细节模型有几项共同的缺点，例如需要 大量的内存来存放各种不同精细度的地形模型；而且也无法根据视点位置与距离 局部性的调整多层次细节模型；最严重的问题是因为内存容量的限制，不可能建 构足够多的精细度模型，所以当精细度切换时，突然跳动的显示情形将使得视觉 效果很不逼真。因此现在一般的做法大都将花费在资料存取的时间转移到动态建 构地形资料的多层次细节模型上，如此不但可以建构较为理想的几何模型，又可 以改善不同精度之间切换的问题。 2 3 2 2 与视点有关的地形多层次细节模型 l i n d s t r o m 提出化简地形模型与视点相关的误差计算方法 1 8 】。它们首先根据 地形顶点所在周边地势的垂直高度变化定义每个顶点的高度差( d e l 诅v a l u e ) ， 之后将顶点的高度差投影到屏幕坐标系统上，如果高度差投影( d e l 扭s e g m e n t p r o j e c t i o n ) 小于给定的误差容许值( t o l e r a n c e ) ，则此顶点就可以化简，而几何 模型会因此顶点的化简将两个较小的三角形合并成一个大三角形，以产生地形资 料的多层次细节模型。 这种多层次细节模型建构的方法不但有考虑地形顶点的重要性，同时还考虑 河海大学硕士研究生论文 第二章相关研究 了几何模型在视觉上的效果( 例如视点方向正好面向山的斜坡，则斜坡上的地形 顶点之垂直变化的几何特征，就显得较不重要了) ，所以可以用较精确的多层次 细节模型达到比较高品质的图像显示。不过，由于必须对大量的顶点实时计算高 度差的投影值，另外还得支持各种顶点选取情况的几何模型，所以会因为实时运 算需求的负载过重而使得效率变差。 l i n d s t r o m 使用四叉树阶层式的数据结构纪录每分区( b 1 0 c k ) 的地形顶点， 采由下往上的策略化简高度差投影在给定误差容许值内的地形顶点，同时提出分 区性多层次细节模型化简( b l o c k l o d _ r e d u c t i o n ) 算法，有效率的应用显示画 面间的共效性可以快速达到大量的化简不需要选取的地形顶点。另外，在构建地 形的多层次细节模型方面，首先提出具有规则性与对称性的三角化方式。不但不 ， 需要海量存储器空间的多层次细节模型，而且可根据给定的规则步骤，迅速取得 符合显示的几何模型。因此，实时构建与视点相关的地形多层次细节模型的困难 度就获得解决了。然而，l i n d s 缸o m 并没有提供解决多层次细节模型切换造成显 示跳动( p o p p i n g ) 的方法，以及解决精度不同的相邻区间所造成图像破洞现象 的具体方案。 之后，h o p p e 【1 9 】以边线折迭化简法、渐进式网格模型和与视点相关的多层 次细节模型的建构方法为基础，设计出可根据视点调整地形顶点选取的机制，然 后再依照渐进式网格模型定义的运算，找到符合显示的几何模型。值得一提的是， h o p p e 加入执行时间几何形变( r u n t i m eg e o m o r p l s ) 的功能，使得不同精细度的 几何模型转换较为流畅，以此获得显示画面时间上的连续效果( t e m p o r a l l y c o m i n u i t y ) 。可是由于纪录几何形变复杂规则以及采用渐进式网格模型处理地 形资料所需的内存空间实在可观，虽然他们提出o u t p u l - s e n s i t i v e 的资料结构可 以减少内存需求，但对于大规模的地形资料而言，依然还是有严格的限制存在。 2 3 2 3 不规则三角网格架构 地形的多层次细节模型采用不规则三角网格的架构，主要着眼点是在代表地 形区域的几何模型弹性较高f 2 0 - 2 3 。采用不规则三角网格建构的地形模型，可以 弹性地增加或移除动态的地形顶点，或者依照不同方式的几何连接( 或称为三角 化) 可以适当的调整地形模型的拓朴结构，因此，往往可以用较少量的三角形数 目表示出较为理想的地形全貌或局部特征。但是产生不规则三角网格模型的算法 基于格网划分的地形l o d 算法优化研究 通常需要较久的计算时间，不然就是无法满足实时调整多层次细节模型的需求 【2 4 2 5 】。然而，h o p p e 应用渐进式网格模型的概念使用预先处理( p r e p r o c e s s i n g ) 制作地形的多层次细节模型，之后再根据视点的改变而动态调整显示所需的几何 模型，成功地完成不规则三角网格的多层次细节模型的实时绘制。 事实上，采用不规则三角网格架构制作的地形多层次细节模型，无法直接提 供使用者变更某块地形区域需要的几何模型，如在游戏或军事训练仿真器上的爆 炸效果，使得地形资料的原始模型需要变形。另外，如果加上不规则三角网格架 构的多层次细节模型本身不具规则性的缘故，将使得地形表面上物体的处理( 如 建筑物、树木、道路等) 或物体与地形模型的碰撞检测( c o l l i s i o nd e t e “o n ) 格 外困难、没有效率，主要的理由还是因为由此种架构制作的几何模型缺乏系统性 的空间组织( s p a t i a lo r g a i l i z a t i o n ) 。 2 3 2 4 规则格网系统 使用规则格网系统制作而成的地形模型若从二维平面上来看，将发现顶点与 顶点连接的方式具有明显的规律性。首先，规则方格系统有两个显而易见的特色： 第一，几何模型的顶点都会出现在格子点( g r i dp o 恤t s ) 上；第二，由顶点连接 而成的三角形皆是以等腰直角的形式呈现。其次，规则格网系统对比不规则三角 网格架构的特点是在多层次细节模型的建构过程中，具有较快的运算速度及较简 洁的数据结构。不过