（计算机应用技术专业论文）大规模复杂地形模型的实时绘制技术研究.pdf

摘要 大规模地形的实时绘制技术是当前计算机图形学领域的一个研究热点，地形 的海量数据是进行地形绘制的瓶颈。如何有效地组织和简化地形数据，提高地形 实时绘制速度，是当前大规模地形实时绘制亟待解决的问题。 本文针对地形实时绘制技术当前的研究现状，围绕大规模地形模型的简化和 多分辨率模型的表示、数据的调度等问题进行了深入地研究从地形静态简化、 数据的分块预取、地形的视相关动态模型简化三个方面综合考虑，对大规模复杂 地形模型进行简化，实现大规模复杂地形模型的实时绘制。其研究内容及成果如 下： ( 1 ) 根据地形平坦程度，对地形原始模型进行基于自适应四叉树的静态简 化。并用静态简化后的模型代替原始模型进行后续的处理。 ( 2 ) 提出基于分块的数据预取算法，根据视点的移动，把在视线方向上、 下一帧中可能进入视域范围的结点数据预先调入内存。 ( 3 ) 根据视见体裁剪和动态误差的判断，确定最终参与场景绘制的结点及 其分辨率，对内存中已有的结点数据进行适当的分裂和合并，并进行地形的多分 辨率绘制。 实验结果表明，本文提出的算法能够有效地提高大规模复杂地形绘制速度， 基本满足大规模复杂地形实时绘制的需要。 【关键词】网格简化多分辨率模型数字高程模型自适应四叉树视相关数据调度 a b s t r a c t t h er e a l t i m er e n d e r i n gt e c h n i q u eo f l a r g e - s c a l et e r r a i nh a sb e e nap o p r e s e a r c h f i e l di nc o m p u t e rg r a p h i c s t h eh u g ed a t aq u a n t i t yl i m i t st h er e n d e r i n gv e l o c i t yo f t h et e r r a i n h o wt oo r g a n i z ea n ds i m p l i f ye f f e c t i v e l yt h et e r r a i nd a t ai st h eu r g e n t p r o b l e m t os o l v ei nt h ef i e l d t h ep a p e ra i m sa tt h ep r e s e n tr e s e a r c ho ft h et e r r a i nr e a l - t i m er e n d e r i n g , f o c u s e so nt h e f o l l o w i n gs e v e r a lp r o b l e m s ：l a l g e - s c a l et e r r a i ns i m p l i f i c a t i o n , m u l t i - r e s o l u t i o nr e p r e s e n t a t i o na n dt h ed a t as e h e d u l e c o m p r e h e n s i v e l yc o n s i d e r i n g t h et h r e ep a n s ：t h et e r r a i nm o d e l ss t a t i cs i m p l i f i c a t i o n , t h ed a t ap r e f e t c hb a s e d0 n s u b - b l o c k , t h ed y n a m i cm o d e lb a s e do nv i e w - d e p e n d e n t , t h ep a p e rs i m p l i f i e st h e m o d e lo f t h el a r g e - s c a l et e r r a i n , r e a l i z e st h er e a l - t i m er e n d e r i n go ft h et e r r a i nm o d e l t h er e s e a r c hr e s u l t sa l ea sf o l l o w s ： ( 1 ) t h ea u t h o rp r o p o s e dt h es m o o t hd e g r e eo f t h et e r r a i n , d e p e n d i n g0 1 1t h e s m o o t hd e g r e eo ft h et e r r a i n ；t h ea l g o r i t h ms i m p l i f i e st h et e r r a i nm o d e lb a s e do rt h e a d a p t i v eq u a d - t r e e t h ep a p e ru s e st h es i m p l i f i e d - m o d e lt or e p l a c et h eo r i g i n a lm o d e l ( 2 ) t h ea u t h o rp r o p o s e dt h ed a t ap r e - f e t c hb a s e do i ls u b - b l o c k d e p e n d i n g o nt h ev i e w p o i n t sm o v e ，w ei n p u tt h et e r r a i nn o d e si na d v a n c eo nt h ed i r e c t i o no f t h e s i g h tl i n ea n dp r o b a b l yi n t ot h er a n g eo f t h ev i e wi nt h en e x ts o 朗豫 ( 3 ) t h ep a p e ri m p r o v e st h ea l g o r i t h mt op r o d u c et h ed y n a m i cm o d e l ， d e p e n d i n g o nt h ec u to fv i e w - f i - u s t o ma n dt h ej u d g e m e n to fd y 衄n i ce r r o r , w ec a n m a k es u r et h en o d ea n di t sl e v e lo fd e t a i l ，t h e nw ec a ns p l i to rc o m b i n et h ev e r t e xo f t h en o d ei nm e m o r yc o r r e c t l ya n dr e n d e rt h et e r r a i n t h ee x p e r i m e n tr e s u l ti n d i c a t e s ：t h ea l g o r i t h m 啪e f f e c t i v e l yi m p r o v et h e r e n d e r i n gv e l o c i t y ；b a s i c a l l ys a t i s f yt h er e a l - t i m er e n d e r i n go f t e r r a i n k e yw o r d ：m e s hs i m p l i t i e a t i o n , m u l t i r e s o l u t i o nm o d e l ，d i g i t s lc i t a t i o nm o d d ，a d a p t i v eq u a d o u e e v i e w - d e p e n d e n t , d a t at r a n s l a t i o n 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意如不实，本人负全部责任。 论文作者( 签名) ：垂k 竭b 氍一 2 0 0 7 年月时日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ：忍巡芏2 0 0 7 年f 月护日 第一章绪论 第一章绪论 1 1 研究背景 地形作为自然界最复杂的景物之一。自古至今就与人类的生活息息相关，随 着计算机技术的发展，地形的实时绘制，已经成为计算机图形学的重要研究内容。 随着遥感等数据采集技术的发展，使得获取高分辨率的地形数据以及地形纹理数 据成为可能。目前地形数据动辄数以百万计的三角形面片，如果不做简化直接在 普通p c 机上进行实时绘制显然是不现实的，如何有效地组织地形数据和简化地 形模型，从而能够在普通p c 机上实现地形的快速漫游，是当前地形实时渲染技 术面临的巨大挑战。 随着地形范围的扩大、采样间隔的缩小，地形的数据量都会成倍的增加，从 而形成海量地形数据。因此，即使在当前计算机硬件得到了长足发展、主流图形 硬件的多边形处理能力也已达到每秒钟百万量级甚至千万量级的条件下，单纯依 赖于硬件加速进行地形的快速绘制，仍难以满足实际应用对绘制速度的要求。为 了从根本上解决地形绘制的问题，必须设计出一种地形实时绘制算法，能够在数 据量和绘制速度之间取锝一个平衡，这样才能有效地解决大规模复杂地形绘制的 实时性和逼真度之间的矛盾，实现大规模复杂地形的实时绘制。 目前三维地形的绘制技术基本上可以归纳为三类：基于真实地形数据的地形 绘制技术、基于分形的地形生成技术和基于衄恧拟舍的地形生成技术【。基于真 实地形数据的地形绘制技术f 2 j 是指利用真实地形的采样点，通过绘制采样数据模 拟地形表面。基于分形的地形生成技术【3 j 是利用分形几何所具有的细节无限和统 计自相似的典型特性，通过递归算法使复杂地形模型可用简单的规则生成。基于 曲面拟合的地形生成技术f 4 j 是根据控制点选择合适的曲面对地形进行拟合。 由于基于分形的地形生成技术算法的复杂性高。且没有与实际的真实地形、 地貌相联系，因此在应用上受到限制：基于曲面拟合的地形生成技术其曲面方程 及参数不易控制，且生成地形过于光滑，真实感较差，目前这种模型的应用还较 少。而基于真实地形数据的地形绘制技术能够通过剖分和合并的方法生成连续的 多边形网格，有利于计算机进行绘制，同时生成的地形也具有高度的真实感，所 以它已成为人们描述三维地形的主要手段【n 。 第一章绪论 数字高程模型d e m 是目前基于真实采样点的三维地形模型主要表示方法， 也是目前人们对三维地形实时显示算法进行研究的对象。 d e m 是由美国麻省理工学院c h a i r e sl m i l l e r 教授于1 9 5 6 年提出来的，其 目的是通过测量或其他技术手段获得地形数据，在满足一定精度的条件下，用离 散数字的形式在计算机中表示地形，并用数字计算的方式进行各种分析。在应用 中，d e m 是用一组由序数值阵列形式表示地面高程的一种实体地面模型是栅 格数据的一种。它与图像的栅格表示形式的区别主要是：图像是用一个点代表整 个像元的属性，而在d e m 中，格网的点只表示点的属性。点与点之间的属性可 以通过内插计算获得。 d e m 表现形式分为规则格网( g r i d ) 和不规则三角形格网( t r i a n g u l a t e d i r r e g u l a r n e t w o r k , t i n ) 。规则格网是一种结构简单、便于使用和管理的一种d e m 形式；t i n 是通过从不规则分布的数据点生成的连续三角面来逼近地形表面。由 于不规则网格的几何关系比较复杂，不便于数据的实时存取，而且基于不规则网 格的地形绘制算法多是一次性把地形数据全部载入内存，这显然不适合大规模地 形数据的实时绘制。因此，目前地形绘制大多是基于规则格网的d e m 。本文的 地形实时绘制算法也基于规则格网的d e m 的。 由于规则格网表示的地形d e m 是按照矩形网格对实际地形均匀采样而来 的，如果地形范围较大而采样问隔较小，就会造成地形模型数据非常庞大，因此， 必须对地形模型进行适当的简化，以满足人们对地形实时绘制的要求。 所谓三维地形的简化【l j 是指在保持模型对地表描述有一定逼真度和精确度 的前提下，尽量减少模型的复杂度，取得模型复杂度、地形逼真度和精确度之间 的折衷，简化的结果为用少量的点和面来表达原始的地形。 1 2 国内外研究现状 在模型简化中一个重要的技术就是细节层次模型技术( l e v e lo fd e t a i l ， l o d ) ，l o d 的思想是：为每个物体建立多个分辨率不同的模型，使用时根据条 件进行选择。l o d 技术改变了“模型越精细图像质量越好”的片面观点，通过 对模型复杂度进行综合评定，在绘制时用一定的算法为各个物体选择适当的细节 模型，从而使图形显示在保证恒定帧频率的前提下最大程度地提高视觉效果。 尽管l o d 技术为模型简化提出了新的思路，但该技术只是适用于物体或小 2 第一章绪论 范围地形的简化，对于大范围的地形仍不能产生令人漫游的效果，原因是模型的 建模机理与现实生活中人们观察大规模地形的原理还有着很大的差别吼l o d 技 术的特点是同一模型的各处均具有相同的细节层次，而实际地形场面宏大，延绵 不断，人们在观察距离视点较近或曲率大( 地表细节特征) 的区域时，需要较高 的细节层次表达，而离得远或较平坦的区域用粗略的细节层次表示即可。为此， 人们开始研究用不同的细节层次来构造一个地形场景，这就是目前人们普遍关注 的三维地形多分辨率实时显示模型。 多分辨率模型( m u l t i r e s o l u t i o nm o d e l , m r m ) f 钉的基本思想是用不同的 l o d 层次构造或近似表示场景，其中与视点距离不同的区域可以有不同的分辨 率，并随着视点位置的不同做相应的调整，对于有突出特征的地表区域根据地表 起伏程度的不同而采用不同的细节层次。 对于多分辨率模型的构建问题，国内外的学者提出了很多算法，其中很多算 法都取得了成功的应用。如l i n d s t r o m 6 m $ 1 提出了将受限四叉树三角剖分的方法 用于网格地形模型的实时多分辨率显示他采用基于屏幕空间的误差度量算法和 有效的场景裁剪方法来实现地形的视点相关多分辨率显示：d u c h a i n e a u 等人在 1 9 9 7 年提出了“实时优化自适应网格”( r e a l - t i m e o p t i m a l l y a d a p t i n g m e s h e s ， 简称r o a m ) 算法网，但r o a m 算法是针对规则网格的三角形二叉树的动态网 格表示法；徐青等提出了基于t i n 的自适应分块思想，把传统的分割合并法和 三角形生长法合并在一起，并给出了相应的地形简化过程1 1 0 1 】。h o p p e 1 2 1 1 3 提出了一种整体网格优化算法，算法建立了比较复杂的全局能量优化方程；后来 在原有的算法基础上又提出了基于边折叠的渐进网格优化方法；i s l e r 使用边折叠 和三角形折叠操作来实时生成简化模型；r e n a t o 对地形数据的分页管理和实 对存取技术进行了有益的研究1 蛔，但在他的算法中，只对一较小规模的地形数据 进行了实验；j o n a t h a n 对r o a m 算法作了重要改进1 1 7 1 f 司；国内在这方面也开展 了一些卓有成效的工作 2 9 h 4 2 1 。 尽管目前地形模型简化算法很多，但普遍存在的一个闯题是算法简化准则所 考虑的信息量单一，因而导致简化效果不理想，容易造成地形的失真；另外有些 算法本身过于复杂，计算量大，难于达到实时。 虽然近年来计算机的硬件发展速度很快，c p u 的主频越来越高、图形加速 器也在不断发展，但我们也应该看到在实际应用中需要处理的数据量往往比硬件 第一章绪论 可以处理的数据量大一个或多个数量级。当数据量大到不能一次全部装入内存 时，单纯的多边形简化技术也无济于事。解决闯题的唯一途径就是采用数据调度， 将多边形简化与数据调度相结合以实现大规模地形的实时渲染1 1 9 l 。 在实际漫游过程中，人们在某一视点位置观察场景时，往往只能看到整个地 形很小的一部分，大部分场景相对于菜一视点位置来说是不可见的，因此，在地 形的绘制过程中，只要把视点可见范围内的数据调入内存即可满足当前视点的场 景绘制要求。地形数据调度的任务就是根据视点的位置，将视点附近区域的数据 调入内存，尽量满足当前视点位置的场景绘制要求【嘲。 不同的地形模型数据构建方法采用不同的数据调度方法。在l i n d s t r o m 的地 形绘制算法中f 9 】【1 0 j f i l 】i ，用四叉树结构对她形进行规则划分，采用隔行隔列采样的 方式构建基于四又树的层次模型。在绘制过程中，视点移动时，根据视见体裁剪 和用户允许的屏幕误差判断出最终参与场景绘制的结点，再去读取需要的结点数 据，然后进行场景的绘制。该数据调度方法容易造成场景绘制的不连续，在漫游 过程中容易出现停滞现象；在h o p p e 提出的基于分块的层次累进网格 ( p r o g r e s s i v em e s h e s ，p m ) l j5 】f j 6 j 【l 刀算法中，在地形模型的简化过程中记录了高程 点的简化情况，在系统启动绘制程序时，首先把最粗略的地形模型调入内存，根 据视点的移动，判断参与场景绘制结点的细节层次，调入高程点的简化信息，对 内存中已有的模型数据进行适当的点分裂和边合并操作，从而达到当前视点位置 的场景绘制要求。该算法的计算较为复杂，在大规模地形的绘制过程中难以达到 实时要求；在d u c h a i n e a u 等人提出的“实时优化自适应网格”( r o a m ) 算法1 1 2 】 中，利用分裂和合并队列对高程点数据进行控制，且该算法能够利用相邻两帧场 景问的相似性，减少调度的数据量，但是维护分裂和合并队列需要花费大量的计 算时间 目前，对于大规模地形数据模型的组织方法还处于研究阶段，还没有一个成 熟的、可普遍适用的方法。虽然人们提出了不同的处理模型，但这些模型仍不尽 完善，因此如何将地形模型数据的动态调度与地形模型的简化技术结合起来，实 现大规模地形的快速绘制是当前国内外学者正努力解决的问题，也是本文对其进 行研究的原因所在。 4 第一章绪论 1 3 本文研究内容及成果 本文对地形模型的简化和实时渲染技术进行了有益的探索，针对大规模复杂 地形模型的特点，从地形静态简化、数据的分块预取、地形的视相关动态模型简 化三方面综合考虑，对大规模复杂地形模型进行简化，实现了大规模复杂地形模 型的实时绘制，其主要研究内容及成果如下： ( 1 ) 根据地形平坦程度对地形模型进行基于白适应四叉树的静态简化。并 用静态简化后的模型代替原始模型进行后续的处理。 ( 2 ) 提出基于分块的数据预取算法。根据视点的移动，把在视线方向上、 下一帧中可能进入视域范围的结点数据预先调入内存。 ( 3 ) 根据视见体裁剪和动态误差的判断，确定最终参与绘制的结点及其分 辨率，对内存中已有的结点数据进行适当的分裂和合并。进行地形的多分辨率绘 制。 1 4 本文组织结构 本文由以下五章和参考文献组成。这五章的内容是： 第一章 绪论。介绍了本文的研究背景、研究现状及研究内容。 第二章基于自适应四叉树的地形静态简化。总结当前地形静态简化的研 究成果，提出了基于地形平坦程度的衡量标准，对基于自适应四叉树的地形静态 简化算法中的关键技术分别作了详细的论述，给出了本章算法的数据结构设计流 程和实验结果。 第三章基于分块的数据预取。根据视点的移动，基于分块的数据预取算 法对下一个可能的视点位置进行推测，然后由下一个视点的可能位置，对在视线 方向上且下一帧中可能进入视域范围的结点数据进行基于分块的预取，在本章 中，对预取结点的范围、次序和预取调度程序启动的时间等问题进行了深入地探 讨。 第四章基于自适应四叉树的视相关动态模型生成。根据视点等相关因素 对自适应四叉树进行视见体的裁剪，得到参与绘制的结点链表，并根据设定的屏 幕允许误差，对已经调入内存的结点数据进行适当的分裂和合并，选取合适的模 型进行场景绘制。给出了本章算法数据结构设计、流程和实验结果。 5 第一章绪论 第五章总结和展望。对本文的研究内容及成果进行了总结，并指出在大 规模复杂地形实时绘制方面有待进一步研究的问题。 6 第二章基于自适应职叉辫的地形静态简化 第二章基于自适应四叉树的地形静态简化 由于采样点问隔的缩小、地形地势较平坦等因素，造成采用规则格网表示的 地形d e m 中有大量的重复数据，因此必须对地形模型进行离线的静态简化，从 而能够在满足视觉要求的前提下，有效地减少需要处理的数据量，提高实时绘制 的速度。在本章中，首先对已有的地形静态简化算法进行了归纳和总结，重点介 绍了d u c h a i n e a u 和l i n d s t r o m 提出的地形简化算法，然后提出了基于自适应四叉 树的地形静态简化算法，并对其中的关键技术进行了详细论述。 2 1 典型的简化算法 目前而言，地形的静态简化算法按照所采用的数据结构主耍分为两类：采用 二又树结构的地形静态简化算法和采用四叉树结构的地形静态简化算法。其中采 用二叉树结构的地形静态简化算法以d u c h a i n e a u 等提出实时优化适应性网格 ( r o a m ) 算法【刁为代表；采用四叉树结构的地形静态简化算法以l i n d s t r o m 提出 的受限四叉树多分辨率模型为代表【9 l 【1 0 l 【l l 】。 在d u c h a i n e a u 等提出的实时优化适应性网格( r o a m ) 算法中，采用基予三 角形二叉树的数据结构，使用分裂、合并两个优先级队列和基于视点的误差定义 公式来动态更新三角形格网，开发了帧间连贯性、视见体裁剪和三角形条带绘制 等技术来加速地形的显示。在构建多分辨率模型时，r o a m 算法首先把整块地 形作为根接点，然后将原始的地形模型剖分成两个等腰直角三角形，这两个三角 形分别作为根结点的两个子结点，对每个三角形进行递归剖分直到得到满足精度 要求的三角形为止，根三角形为二叉树的最高层次，最小尺寸的三角形为二叉树 的最底层次，该层显示效果最精细。由此形成基于= 叉树层次结构的多分辨率模 型。 在l i a d s t r o m 提出的受限四叉树多分辨率模型算法中，采用规则四叉树层次 结构对地形模型进行划分。该算法采用的模型数据组织方法是：在船7 平面按离 散取样间隔厶x 和4 y 进行取样，地形表面用对称三角形网格来表示，用三角形 可表示的最小网格为基本网格，有3 3 个高程点，后继较细的网格通过2 * 2 的划 分来实现。( 2 n + 1 ) + ( 2 n + 1 个高程点的格网组成一个块，一系列那样的块覆盖整个 地形区域。最高分辨率的块包含该块所覆盖区域内的所有原始数据点。一个稍低 ， 第二章基于自适应四又树的地形静态简化 分辨率的块( 仍包含( 2 “+ 1 ) ( 2 “+ 1 ) 个高程点) 通过对4 个高分辨率每隔一行或一列 丢弃一个高程点而获得。这样不同分辨率的块可用四叉树的层次结构来组织模 型。除叶子外每个结点有四个孩子。根接点覆盖整个地形块，具有最低的细节层 次，叶子结点具有最高的细节层次。 在l i n d s t r o m 的地形绘制算法中，对地形模型进行规则四叉树划分时，只是 将地形数据直接划分成大小相等的块进行处理；在简化数据时，采用隔行隔列的 方法对高程点数据迸行采样，导致实时绘制时，计算量和内存消耗巨大；用这种 方式获取的较粗略模型没有很好地保持模型的局部细节特征，容易引起较大的视 觉误差。 树是地形绘制中经常采用的数据结构。在本文中，采用四叉树作为基于自适 应四叉树的数据结构来表示地形，是因为用四叉树表示地形有许多优势1 2 0 1 ：第一， 采用四叉树结构可方便地对地形进行分块和细分；第二，采用四叉树结构可方便 地实现地形表面的纹理映射；第三，采用四叉树结构能够降低地形整体的表示时 间。 本文在深入研究和总结前人算法的基础上，对地形模型的静态简化算法进行 了改进，提出了基于自适应四叉树的地形静态简化算法，该算法能够根据地形的 平坦程度对地形模型进行自适应的简化，从而能够较好地保持地形的局部细节特 征。 2 2 基于自适应四叉树的地形静态简化算法 基于自适应四叉树的地形静态简化算法的思想是：首先按照完全四叉树自顶 向下对地形d e m 进行划分( 每个四叉树结点覆盖地形中相应的区域，子结点覆盖 的区域是其父结点覆盖区域的四分之一) ，并对四叉树的各结点迸行编码；然后 依据误差测试公式自底向上计算所有结点的静态误差，根据地形的平坦程度衡量 标准，对每个地形块内的高程点数据进行自适应的简化，降低各叶子结点区域的 复杂度，并对相对平坦区域的相邻地形块进行块的合并，去掉一些叶子结点，在 自适应的静态简化过程中保持d e m 的拓扑结构。 地形模型静态简化结束时，生成地形原始模型基于自适应四叉树层次结构的 地形简化模型，同时生成相应于自适应四叉树结构简化模型的自适应四叉树结 构。在后续的处理中，本文用简化后的自适应简化模型代替原始模型，不再使用 0 第二章基于自适应四叉树的地形静态简化 原始模型。 2 2 1 地形的四叉树划分 本文中，地形绘制采用的地形d e m 是一种规则格网模型，它使用二维数组 表示地形，数组中的元素为格网上高程点的高程值，或高程点相关属性的值。一 般地，d e m 数组的表示形式为： f l o a td e m n m a x r o w n m a r c o q 其中，n m a x r o w 和n m a x c 0 1 分别表示该地形在经度和纬度方向上的采样点 数。给定n m a x r o w 和n m a x c o l 的值，则d e m n m a x r o w n m a x c 0 1 的值就为该 处的高程值。 由于d e m 的地形表示与树型数据结构具有天然的一致性，因而可以用四叉 树结构对其进行表示，基于白适应四叉树的地形静态简化算法对地形的划分过程 为：首先将整个地形区域作为四叉树的根结点，即四叉树的第0 层，涉及地形场 景的4 个角的高程点；其次将整个地形块按照地理区域进行四等分，构成四叉树 的第l 层结点，即根结点的四个子结点，每个子结点覆盖的地理区域为其父结点 的四分之一；继续对第l 层的各个四叉树结点进行四等分，构成四叉树的第2 层 结点，每个结点所覆盖的地理区域为第1 层结点覆盖地理区域的四分之一。依次 递归划分下去，直到最底层叶子结点所覆盖的区域达到设定的块的尺寸为止。 如图2 1 ，四叉树中的每一个结点覆盖地形中的相应区域，其中，根结点c d 覆盖整个地形区域，涉及地形的四个角的高程点。结点o ，o ，o ，o 为根 结点岛的四个子结点，c j ，o ，o ，q 分别q 的l ，4 区域，c j ，a ，o ， o 的分辨率高于白的分辨率。 c i 白 白 c i ( 幻对根节前篷行四书盼( b ) 根节点和四个子节点的关系 图2 1 地形的四叉树划分 由于地形子块内部分辨率的一致性，相同分辨率时分块尺寸越大。则需要绘 9 第二章基于自适应四叉树的地形静态简化 制的高程点数量越多，导致绘制速度下降；分块尺寸越小，则四叉树结构越庞大， 导致绘制阶段的实时性下降。因此，必须选择合适的分块大小以达到最好的性能。 2 2 2 结点的编码 为了能够在系统绘制阶段迅速查找烈每个结点的邻接结点和父子结点，必 须对四叉树的各结点进行编码。在基于自适应四叉树的地形静态简化算法中，算 法在对地形进行四叉树划分时，同时对所有四叉树结点进行编码。结点的编码要 能够准确直观地表达结点问的空间关系，结点问的空问关系主要有两个方面( 6 1 ： 一是细节层次关系，体现在一个分辨率较低的结点与四个分辨率较高的子结点之 间的“父子”关系及这种关系的传递；二是同一层结点的相邻关系，表达同一细 节层次的结点之间的空间邻接关系。结点编码的好坏对于最终的绘制速度有着重 要的影响，定义结点编码的原则既要使编码能够充分体现结点间的空间关系，又 要使编码规律明显，便于结点定位，避免复杂的查找过程【1 6 1 。 根据以上讨论，在基于自适应四又树的地形静态简化算法中，所采用的编码 规则如下： 结点每剖分一次就增加两个比特，其中o o 表示左上子结点；o l 表示右上子 结点；l o 表示左下子结点；l l 表示右下子结点如图2 2 所示。根结点的编码 为空，假设根结点所在的层次为0 ，则第一层各个结点的编码分别为0 0 ，o l ，1 0 ， l l ；第二层的编码为：0 0 0 0 ，0 0 0 i ，0 0 l o ，0 0 l l ，o 1 0 0 ，0 1 0 1 ，0 1 1 0 。0 1 1 1 ，l o o o ， 1 0 0 1 ，1 0 1 0 ，1 0 1 1 ，1 1 0 0 ，1 1 0 1 ，1 1 1 0 ，i i i i 。依次类推。直至形成完整的四叉 树结点编码，如图2 3 m 加 “ 图2 2 四叉树结点的编码 1 0 第二章基于自适应四叉树的地形静态简化 o o o omg o l o n m0 1 1 0 “i l a ol i i i oi i i i 图2 3 四叉树结点的编码示例 2 2 3 地形平坦程度的衡量标准 在对地形进行四叉树划分后，算法对各个地形子块内的高程点数据进行自适 应的静态简化，由于地形d e m 模型中常常存在大量重复的数据，特别是在地形 较平坦时，数据的重复现象尤其明显。因此，在地形模型的静态简化阶段，必须 设计一种地形平坦程度的衡量标准，对地形的平坦程度进行衡量，从而有效地减 少数据量。 在地形较平坦的区域，d e m 高程点的高程值会相等或者接近。因而，在本 小节中，通过判断d e m 高程点的高程值是否相等或者接近的方法来判断地形是 否平坦。如图2 4 所示，d e m 的高程点a 1 1 ，田? ，a 2 t a 2 2 围成d e m 模型中的一 个小块，如果高程点a 1 1 a 1 2 幻，a 2 2 的高程值相等或者四个高程点的高程值之 差在设定的阈值内，则本文认为由高程点口小a 小a 2 t 、锄构成的这- 4 , 块是平 坦的。 a u r 勘 图2 4 判断d e m 模型中小块的平坦度 本文给出以下形式化的描述，设a ，j 口小a 2 t ，a 2 2 为d e m 模型中相邻的四 第二章基于自适应四叉树的地形静态简化 个高程点，艿为用户设定的地形平坦程度阈值，日为高程点a l l ，a 协a 2 t ，以2 的最大高程差值，则 ，胆m a x a l l - a 1 2 i 、i a l 2 , - a 2 1 l ，i a 2 t - a 2 2 i ，f 川，p j i h 艿 ( 2 1 ) 当d e m 模型中相邻的四个高程点满足公式( 2 1 ) 时，那么本文认为该四个高 程点构成的小块是平坦的 2 2 4 块内基于平坦程度衡量的高程点删除 人们在观察地形时，在地形较平坦的区域，只要较少的高程点就可以满足人 们的视觉要求，而在地形较崎岖的区域，需要较多的高程点才能满足人们的视觉 要求正是基于这一现象，本文根据上小节中提出的平坦程度衡量标准对地形模 型进行自适应的简化，提出了块内基于平坦程度衡量的高程点删除的自适应简 化，从而在保持d e m 规整性的前提下，达到减少模型高程点数量的目的 基于平坦程度衡量的高程点删除的简化过程为：在进行第一遍扫描时，按照 2 2 3 中给出的地形平坦程度衡量标准，算法对地形d e m 模型进行隔行隔列的扫 描判断，判断每一个由四个高程点构成的d e m 小块是否平坦，扫描过程中记录 每个小块的扫描判断结果。第一遍扫描结束时。根据扫描结果对判断为平坦的地 形小块进行以下操作：用该小块的其中一个高程点代替该小块。用一个高程点代 替一个小块要遵循的原则是：对于奇数行奇数列的小块，用其左上高程点的高程 值代替；对于奇数行偶数列的小块，用其右上高程点的高程值代替；对于偶数行 奇数列的小块，用其左下高程点的高程值代替；对于偶数行偶数列的小块，用其 右下高程点的高程值进行代替。如图2 5 所示。 ( 1 ) 原始d e m 小块( ”奇数行奇数列的小块 第二章基于自适应四叉辫的地形静态简化 ( c ) 奇数行偶数列的小块( d ) 偶数行奇数列的小块( c ) 偶数行偶数列的小块 图2 5 用小块中的其中一个高程点代替小块 在用其中一个高程点代替一个小块时，为了保持d e m 规则网格的规整性， 需要做一下判断：如果相邻的四个小块中，两个相邻的小块可以进行替代操作， 而另外两个相邻的小块不能进行替代操作，或者相邻的四个小块中，只有一个小 块不能进行替代操作。如图2 6 所示，这两种情况下如果直接进行替代操作，将 无法保持d e m 的规整性，因此，必须对这两种情况进行限制。 “霄千町一亿的莰 n 1 青三十町国亿一囊 图2 6 替代简化过程中出现的破坏d e m 规整性的情况 本文给出的解决办法是：将小块的各边界的中点加入图2 6 中没有保持 d e m 规整性的两种情况在进行处理后，如图2 7 ，依然保持了d e m 的规整性。 图2 7 图2 6 经过处理后的拓并结构 有了前面所述的替代规则，则第一遍扫描结束时，可能的扫描结果如图2 8 所示， 第二章基于自适应四叉树的地形静态简化 田口 a)f” 图2 8 第一遍扫描的可能结果 在第一遍的扫描结果上。本文算法根据平坦程度衡量继续对地形数据进行第 二遍的扫描，第二遍扫描时的跨度为第一遍扫描时跨度的两倍，则根据替代准则， 第二遍的扫描可能的结果如图2 9 所示。 国凌i 问i 眦手块 c 再两个司栅化子块“ 青三个可简化子块曲育四个可越化子墟 圈2 9 第二遍扫描的可能结果 在第二遍扫描结果的基础上，继续进行第三遍的扫描，扫描的跨度是第二遍 扫描跨度的两倍。依次递归，在前一遍扫描的基础上继续迸行扫描，扫描的跨度 是前一遍扫描时跨度的两倍。直到一遍扫描完毕没有可以简化的块为止。此时， 一个地形子块的自适应静态简化结束地形，继续进行下一个地形四块的自适应静 态简化。直至所有的叶子结点全部进行自适应简化完毕。 在对倒数第二层结点进行静态简化时，算法设定平坦程度的衡量标准为2 6 ， 即为其子结点所在层次阈值的两倍。按照块的替代准则和判断条件，在对叶子结 点自适应静态简化的基础上进行自适应的静态简化。依次递归，父结点的简化阈 值为其子结点简化阈值的两倍，直至根结点 1 4 第二章基于白适应四叉树的地形静态简化 在删除高程点时。需要注意的是在简化过程中必须保持d e m 模型网格的规 整性，简化过程中，只有当一个块的中心点存在时，边的中点才能存在。如图 2 1 0 给出了中心点和边中点的依赖关系。 图2 1 0 简化过程中结点的依赖关系 2 2 5 块问基于平坦度衡量的块合并 当同属于一个父结点的四个子结点内高程点的高程值之差小于子结点所在 层次设定的静态简化阈值，即满足子结点所在层次的地形平坦程度的衡量标准， 则认为这样的四个子结点是可以合并的，由父结点代替子结点，删掉四个子结点。 为了保持一定的地形细节特征，父结点代替子结点时，父结点中高程点的简化阈 值为予结点所在层次的简化阈值。 对整个四叉树结点进行检查，对符合合并要求的四叉树结点予以合并，在进 行块的合并过程中，块的叶子结点数量会相应地减少合并完毕，地形d e m 的 静态简化结束。生成了基于自适应四叉树的地形简化模型如图2 1 l 所示，如 果对地形模型进行完全四叉树的简化，则基于四叉树的地形模型简化的叶子结点 共有1 6 个t 而对地形模型进行基于自适应四叉树的地形模型简化后，其叶子结 点只有8 个。 图2 1 i 基于自适应四叉树的简化模型示例 测试完所有的四叉树结点后，地形d e m 的自适应静态简化结束，至此，所 第二章基于自适应四叉树的地形静态简化 形成的基于自适应四叉树的静态简化模型中，根结点的分辨率为地形模型的最粗 略表示，四叉树的叶子结点构成了地形模型的最精细表示。 2 2 6 结点的静态误差 在对地形进行绘制时，需要建立一个误差判断准则来决定是否对结点继续分 割。该误差判断准则与地形本身的粗糙程度相关，即在地形起伏比较大的区域有 较高的细节程度，而在平坦的区域则有较低的细节程度。 在基于自适应四叉树的地形简化算法中，考虑用结点内高程点高程的最大差 值作为结点的静态误差。它的数值越大表示这个结点表示的地形越粗糙，在地形 绘制过程中，在某一视点位置时，相对于平坦的结点，较粗糙的结点常常需要分 辨率更高些。由于结点的静态误差在其后的处理中不发生变化，所以。在静态简 化过程中事先计算好结点的静态误差，保存在四叉树的结点内。定义霄为结点 的静态误差，即结点的粗糙程度，则 置= m a x a h a h 为结点内高程点的最大高程差值 ( 2 2 ) 在地形的绘制过程中，对于经判断在视域范围内的四叉树结点，必须根据其 静态误差确定最终参与场景绘制的分辨率。假定c 为设定的屏幕允许误差，在 判断一个结点的分辨率是否适合于当前的视点位置，有公式( 2 3 ) l 2 3 2 算法流程 ，高程点的坐标值和商程值 ，高程点的光照强度 本文提出的基于自适应四叉树结构的地形静态简化算法，通过对高程点进行 自适应的静态简化生成简化模型，该算法能够较好地保持地表模型的局部细节特 征，同时保持了d e m 格网模型的规整性，保证了地形模型的完整性。 算法详细流程如下： 步骤1 ：读入初始网格模型数据，自上而下对原始地形模型进行完全四 叉树划分， 同时生成完全四又树各结点的编码。 步骤2 ：对四叉树划分后的每个叶子结点进行第一遍的扫描，按照2 2 3 中给出地形平坦程度的衡量标准，对地形模型中符合平坦标准 的高程点数据进行判断，按照2 2 4 中的替代准则和判断条件进 行判断，完成第一遍的扫描简化。 步骤3 ：在第一遍扫描简化的基础上，继续进行第二遍的扫描，扫描跨 度为第一遍扫描时的两倍，根据替代准则和判断条件进行第二 遍的简化 步骤4 ：继续对结点中的高程点数据进行扫描，直至没有符合条件的高 程点数据，该四叉树结点的自适应简化结束。计算结点的静态 误差，存储在该四叉树的结点中。 步骤5 ：继续对下一个四叉树结点进行基于高程点删除的自适应静态简 化。跳至步骤2 第二章基于自适应四又树的地形静态简化 步骤6 ：对四叉树中的全部结点简化完毕后，测试四叉树的各个结点， 判断是否能够进行块的合并，对能够进行合并的块，删去四个 子结点。用父结点代替子结点。 步骤7 ：对四叉树的全部结点测试完毕，生成基于自适应四叉树的地形 静态简化模型。 2 3 3 试验结果及分析 作者在p i v3 0 g 、内存l g 的计算枧上应用v i s u a lo h6 0 和o p e n g l 实现 了本章提出的算法，对一个2 5 7 x 2 5 7 的地形网格模型进行了测试。如图2 1 3 ( a ) 所示，原始模型合有6 6 0 4 9 个高程点，通过本文算法的自适应简化，四叉树所有 叶子结点的高程点构成了原始模型自适应简化后的简化模型，如图2 1 3 ( b ) 所示， 得到了含有2 2 3 6 8 个高程点的简化模型从图2 1 3 中可看出，本文算法在保持 了模型的拓扑结构和局部细节特征、边界等形状特征的同时，大大降低了模型的 复杂度。 ( a ) 输入原始地形嗣格模型( 2 5 6 x 2 5 6 ) 1 9 第二章基于自适应四叉树的地形静卷简化 ( b ) 静态简化后的四叉树叶子结点 图2 1 3 原始模型和简化后模型的比较 作者对原始模型的绘制速率和简化后所有叶子结点生成的模型绘制速率进 行了比较，实验数据如表2 1 所示。 表z l 原始模型和所有叶子结点生成的简化模型的绘制速率比较 三角面片数目( 个)绘制速率( f p s ) 地形规模 原始模型简化后模型原始模型简化后模型 1 2 9 x 1 2 91 6 6 4 l8 6 5 54 25 5 2 5 7 x 2 5 7 6 6 0 4 92 2 3 6 82 9 3 7 5 1 3 x 5 1 3 2 6 3 1 6 91 4 7 2 8 62 02 5 2 4 本章小结 为了充分体现地形的细节特征，d e m 模型产生了大量冗余数据，同时d e m 网格模型的精度往往超出用户所需要的精度。因此，为了提高交互漫游过程中地 形场景的渲染速度，需要对地形模型进行简化。本章详细讨论了基于自适应四叉 树结构的地形静态简化：首先自上而下地对地形模型进行完全四叉树划分。然后 自下而上地根据地形的平坦程度对每个子块内的高程点进行自适应的简化，依据 误差判断准则去掉一些叶子结点，使各叶子区域的复杂度降低，从而生成地形的 第二章基于白适应四叉树的地形静态简化 自适应四叉树层次结构。与其他算法相比。本章采用基于自适应四叉树的地形模 型静态简化方法能较好地保持原始地形模型的拓扑结构和细节特征 2 1 第三章基于分块的数据预取 第三章基于分块的数据预取 大规模复杂地形涉及大量的数据，而计算机的内存资源和计算能力相对有 限，这种矛盾决定了不可能将大规模地形的数据事先一次性调入内存，而必须根 据当前