（计算机应用技术专业论文）基于lod技术的地形渲染方法的研究.pdf

学位论文版权使用授权书 本学位论文作者完全了解重迭整电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重麽邮电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 寸耠 导师繇岛波 签字魄叫年月，伯签字日期砂7 年 月f 7 日 ：00玑k毋和群磐警 = 兰互曼兰兰蠹誊= 羔：慧羔篓：二= = = 二兰州= 妒兰= f 、? 。? ”唑再“曩：多i 磊? 裂i j j j l “，孓崎j i 孵z j w j 量” 一矗氨t ，：；i 疏量t 芝站_ 曲。互! ：点- + z 叩新；。矗赫二。： 重庆邮电大学硕士论文 摘要 摘要 层次细节( l o d ，l e v e lo fd e t a i l ) 技术的研究是随着三维可视化技术 的不断发展而开始的。c l a r k 最早提出了层次模型的概念，层次模型的自 动建立过程被称为模型简化。此后出现了大量的模型简化算法，目的在 于有效降低每一帧绘制多边形的数量。l o d 技术一直是图形学里的热点 问题之一。它在g i s 、飞行模拟器、v r ( v i r t u a lr e a l i t y ) 系统、视频游戏 以及数字地球里有重要的作用，尤其在大规模地形可视化中发挥着巨大 的作用，它可以有效地缓解地形数据的海量性与计算机处理速度和网络 带宽的有限性的矛盾。 随着应用领域的不断扩展和新技术的出现，尤其是计算机运算速度 和存储能力的大大提高以及高精度扫描测绘手段的出现，有效地对模型 进行简化的应用需求使得层次细节技术面临着新的挑战，对数字模型进 行层次细节划分的研究具有重要的意义。 l o d 技术的核心就是模型的简化技术，在过去的三十多年的时间里， 已经出现了很多基于数字高程模型( d e m ，d i g i t a le l e v a t i o nm o d e l ) 的简 化的方法，但就满足实时漫游的要求来看，还是远远不够的。本文着重 研究基于四叉树的层次细节技术，主要的工作有：介绍了l o d 技术的应 用背景，总结并评述了l o d 技术的特点、研究现状、研究意义及其分类， 分析研究了基于网格的大规模地形数据实时可视化的相关技术问题，例 如数据的存储和调度、可见性剔除、背面剔除、轮廓保留、模型生成算 法以及误差计算方法。并在现有技术的基础上改进了一种有效的基于四 叉树的l o d 算法。该算法采用基于视点的l o d 技术，结合粗糙度的评 价算法，高效快速地对节点进行渲染和分割，并很好地解决了t 型裂缝 问题。 最后在v c + + 6 0 平台上开发了原型系统。在p c 平台上，对较大规 模的随机地形数据进行了仿真实验。实验验结果证明本文使用的算法具 有更高的地形绘制效率，能够进行大规模地形的实时绘制。 关键词：层次细节，四叉树，数字高程模型，大规模地形可视化 棼“、矗毫肾健t零 重庆邮电大学硕士论文 a b s 仃a c t a b s t r a c t 1 kr e s e a r c ho fl o di sc o m i n g 谢mn l ed e v e l o p i n go f 圮廿玳e 碰m e n s i o n a l v i s u a l i z a t i o n c l a r kp u t 缅w a r dn l ea l g o r i t h l no fl e v e lo fd e t a i l ( l o d ) m19 7 6f o r 曲e f i r s tt i i n e 1 1 l e 卸t o m 撕ce s t a b l i s h m e n to ft 1 1 em o d e l i s 甜s oc 甜l e dm o d e ls i m p l i 丘c a t i o n 1 1 l e r ea r em a n yk i n d so fm o d e ls i i n p l i f i c a t i o na 1 9 0 r i t h m sw t l i c ha r eu s e dt 0 川u c et l 圮 n m b e r so fm ep o l y g o 必i ne v e r ) r 舭n c l o di sah 0 卸0 tf o rd i s c u s s i o ni i lc o i n p u 衄 g r a p l l i c s i ti sp l a y i n gak e yr 0 1 ei nm 锄ya p p l i c a t i o 璐s u c h 弱g i s ，n y i n gs i i 肌l a t i o n s y s t e n l v i r t u a lr e a l i 劬v i d e og 锄e sa n dd i g i t a le a r i l l e s p e c i a l l yi nv i s u a l i z a t i o no f l a 玛e s c a l e 删玛i tc o u l d n d e rl a r g e - s c a l et e 础i i lam u c hm o 聆e m c i e n tw a y w i t l lm ec i e v e l o p r n e mo f 枷：wt c c l l i l o l o g ya 1 1 d 血ee x t e i l d i i l go fn e wa p p l i c a t i o n a r e ao fl o d ，e s p e c i a l l y 也ei i l l p r 0 v e m e n to fa ：b i l i 够o fc o m p 毗e r so p e r a ! t i o n 觚d 咖r a g e a n dn l eo c c l l r r e n i c em o d 锄m e a 璐o fs c 锄i l i l l ga n dm a p p i n gt e c 城q u e s ，g r e a tc 蹦l e n g e b a sp u tf o r w 矾i i l 舭r e a r c ho fs 抽1 p l i 研n gm el o dm o d e l t h es t i l d yo f l o di s b e c o m i l l gm o r e 觚dm o r ei n e a i l i n g 觚r e c e n t l y ，n l ec o 他t e c l l l l o l o g yo fl o di ss i m p l i f i c a t i o nn l e t h o d i nn 伧p a s tn l i 啊y e 嬲，a l a r g em l m b e ro fm e 越岱k 嘲甜o nd i g i t a ld e v a t i o nm o d e lh 嬲b e e np r o p o s e d b u tn l e s t i l lc 趾ts a t i s 匆t h ed e m a n do fr e a lt i n l er e n d e f i n g 1 1 1 i sd i s r t a t i o nm a i l l l yd i s c u s s e s 龇m 砒o d so 儿o db 邪e do nq l l a d - 仃e e p 血c i p a lc o 籼o fm ed i s s e 僦i o n 妇l u d e ： s o m e 印p l i c a t i o nb a c k g r o m l d so fl o d ，“sf e a ：t u r e s ，c u n - e n t 陀s e a r c hs t a _ t u s ，s i g l l i 6 c a i l c e a 1 1 dc l 雒s i f i c a t i o n ，m er e la t i 耐m e m o d so fl a r g et e m l i i ld a t a ss t o r a g ea r l dm a i l a g c m e n t ， v i s i b i l 毋c u l l i n g ，b a c k f k ec u l l i n g ，c o n t o l l rr e s e r y i n g 觚dt h em e t i l o d so f 锄r c 咖p u t i n g a 盘e rt l l a t ，锄e m c i e n tl o da l g 耐廿l i nb 嬲e d0 nq u a d - 骶e 嘶di sp r o p o s e d t t 坨2 i 1 9 0 r i l n lm a k e 伽lu so fv i e w - p o i n tb 弱e dl o da l g o r i 廿1 i n 觚dr o u g l l n e s sl e v e l j u d g 堍i i 酬d ，r e n d e 血ga n dd i v i d 啦也en o d ei i lae m c i e n t 、a y 1 1 1 i sa l g o 棚吼a l s o c a l la v o i dt l ：屺t i c r a c k ap r o t o t ) ，p es y s t 锄i sd e v e l o p e db y 惦i n gv c + + 6 0 r e a lt i m ev i s u a l i 脚i o no f o n el a 玛et e r r a i l ld a ：t as e t si si m p l 锄e n t e do np cp l a t f o r m e x 雕d m e n t mr e s u l t ss h o w 廿l a t l ea l g o r i t l l mi i lt h i sm e s i si sm o r ee 伍c i e n ta n d 跚p p o n sr e a l - t i i n ev i 刚i z a l i o n0 f l 锄翟6s c a l et e 力盈i 1 1 k e ，rw o r d s ： l e v e lo fd c t a i l ，q 啪d 舭e ，d e m ，、，i s u a l i z a t i o no fl a 玛e - a l et i m a i l l 重庆邮电大学硕士论文 目录 目录 摘要? i a b s n 锨n 。i i 第一章绪论”1 1 1 研究背景及研究内容1 1 2 国内外研究现状3 1 3 论文的预期目标和工作内容5 1 4 论文结构5 第二章地形实时绘制的加速技术7 2 1 数据的存储与调度7 2 1 1 基于内存的海量数据存储方法7 2 1 2 基于外存的海量数据的高速调度8 2 2 多层次细节模型1 0 2 3 几何数据的高效表示1 1 2 4 地形实时可见性加速技术1 2 2 4 1 地形可见性概述1 2 2 4 2 通用加速方法1 4 2 5 本章小结1 6 第三章地形三维可视化中的l o d 技术实现的相关方法1 8 3 1 基于视点的l o d 生成方法1 8 3 2 快速动态渲染的方法2 0 3 2 1 直接双循环渲染算法2 0 3 。2 2 视觉三角形算法2 0 3 2 3 递归算法“2 l 3 3 本章小结2 2 第四章基于规则格网l o d 算法设计2 3 4 1 算法的总体设计思想2 3 4 2 相关研究2 4 4 3 算法介绍2 5 4 3 1 基本思想2 5 4 3 2 数据存储2 7 i v 二篓篓竺之0 7 。冀簟冀攀竺? “h4 “鞴葡谳i 孤子荔嚣i ，簖? ：，。j 嚣嚣蔬露麓，篡“冀箸：盛蕊藏褫蕊露瑟浮雩鬻繁粉糍 麓? 拳訾- = 。器! 掣“弦西- ；- 睁? 秭1 嗵i 二? ；t 南* 西、簪* 矗j 2r ：“i i ；吣? f ? ；? j 玉二帚，。z ，i 。j ，：x 一 ，。 一 ， 一 ， 一j ? i 重庆邮电大学硕士论文 第一章绪论 第一章绪论 1 1 研究背景及研究内容 1 9 9 8 年，美国副总统g o r e 在美国加利福尼亚科学中心发表的题为“数 字地球：二十一世纪认识地球的方式一的讲演中指出“我们需要一个数 字地球，即一种可以嵌入海量空间数据的、多分辨率的和三维的地球的 表示，可以在其上添加许多与我们所处的星球有关的数据【l 】。随着遥感技 术，卫星技术的发展，使获得高分辨率的数字高程数据以及影像纹理数据 成为可能。获得空间数据已经不再是“数字地球刀建设的障碍，但如何使 这些数据真正变成一个虚拟地球却存在很多技术问题，大规模地形可视化 就是其中之一。传统的地图是用单一分辨率的各种地图符号来标志地面上 的各种物质，但是我们在真实的世界中观察各种事物的时候，反映在我们 脑中的景象并不是如此。随着计算机技术的发展，软件工程师们希望把我 们获得的海量空间数据在计算机中如同真实的世界一样通过输出设备展 现在人们面前。这是个非常令人神往的想法，但是当前的计算机还没有如 此强大的处理能力，我们目前只能近似地实现实时可视化或达到某种精度 的三维可视化。 大规模的地形可视化是研究数字高程模型( d e m ) 的显示，简化和仿真 等内容的学科，它属于计算机图形学的范畴。为了根据原始数字高程采样 点的疏密程度不同可以采用不同的数据处理策略，研究人员提出了l o d 技术。c l a r k 最早提出了层次模型的概念【2 】，该层次模型的自动建立过程被 称为模型简化。此后出现了大量的模型简化算法，目的在于有效降低每一 帧绘制多边形的数量。l o d 技术的研究是随着三维可视化技术的不断发展 而开始的，该技术一直是图形学里的热点问题之一。它在g i s 、飞行模拟 器、v r 系统、视频游戏以及数字地球里有重要的作用。现在三维可视化 技术是在继承二维可视化技术的基础上发展起来的，由于二维地理信息系 统将实际的三维事物采用二维的方式表示，具有很大的局限性，大量的多 维空间信息无法得到利用。三维g i s 的研究不是对二维g i s 的简单扩展， 而是从空间模型分析到空间数据库的结构直至三维数据的可视化，都必须 进行系统的研究。许多研究者已经开发了三维g i s 的原型系统，使得三维 g i s 技术在矿产资源管理、数字城市等领域得到应用，如加拿大 重庆邮电大学硕士论文 第一章绪论 n e w b r u n s w i e 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 e v i r t u a l g i s 模 块，能在实时三维环境下，提供g i s 分析和实时三维飞行方式的访问和漫 游。还有许多其它一些模拟实验系统，其研究集中于三维可视化和虚拟现 实功能方面。 在地形可视化领域，模型简化算法必须满足两个基本要求1 3 j ：第一是 要满足原始地形数据的精度要求，地形的简化模型必须能够真实反映原始 地形；第二是要具有良好的可视化效果，消除由于模型简化引起的裂缝、 尖锋和锯齿现象，保证地形模型的空间连续性。在现实世界中，随着观察 者的视点和视线方向的不同，观察到的场景也会发生变化，因此视点相 关的l o d 算法成为近1 0 年来研究的热点。在视相关的l o d 模型中，地 形场景的同一帧通常具有不同水平的细节层次，也称该模型为多分辨率模 型。视点相关的l o d 算法通常在地势较复杂、视点较近的地区使用较多 的多边形描述，而地势平坦、视点较远的地区则用较少的多边形描述， 从而实现实时优化的多分辨率模型。 恰当地选择细节层次模型能在不损失图形细节的条件下加速场景生 成。提高系统的响应能力。目前模型简化方法主要研究的问题主要有以下 四类【4 】： 第一类是基于物体的空间位置关系在一些特定的情况下，场景中一部 分几何形体是不被观察者所看到的，图形系统在这种情况下不再绘制这部 分物体；物体到观察者的欧式距离越远，能被观察到的精细的细节部分就 越少，这就意味着选择较粗糙的细节层次来表示物体不会对显示的逼真度 产生大的影响。因此，可以去掉这些细节的绘制。 第二类是基于人眼的视觉特性，人眼辨识物体的能力随着物体尺寸的 减小而减弱，因此，可以根据物体的大小选择不同的细节层次。而且，人 眼辨识物体的能力随着物体远离视域中心而减弱，视网膜对中心的物体 细节的分辨能力较强，因此，可将显示的场景分为具有较精细细节层次的 中心部分和外围部分；还可以根据眼睛的焦距来为焦距区域前面或后面的 物体选择不同的细节层次。 第三类是基于物体的运动特性，运动物体相对观察者的速度决定了人 2 jili 1 2 国内外研究现状 如何设计并建立一个有效的模型简化系统已经成为一个热点和难点。 在国外，有众多的研究机构、大学和公司进行该技术的研究，基于已有的 几种模型的主要的算法有以下几种【5 】 1 r o s s i g n a c 和b o r r e l 的多面体简化算法，算法分4 个主要步骤： 赋予各项点以权值，给物体特征变化较大处的点( 特征点) 以较大 的权值； 根据物体的复杂程度、相对大小等因素把物体所占空间划分为多 个立方体单元； 计算位于立方体单元中各顶点的代表点： 把位于同一个立方体单元中的点用其代表点代替，把产生的退化 多边形移去。 这种算法本质上是一种信号处理方法，相当于对多面体所表示的景物 重新采样。基于原多面体的拓扑结构和采样点可重建产生一新的、保持原 多面体一定层次细节的模型。该算法的优点在于它适用于任意类型的输入 模型，甚至可以是一些不构成网格的多边形集合。另外它也是一种非常有 效的快速简化方法。其缺点在于不保持原模型的拓扑结构，因而所产生模 型的视觉效果不佳，而且，其近似误差也不可控制。 2 s c h r o e d e r 的顶点删除法，其基本思路是指定一个最小的距离阈值， 如果模型中某顶点到由该顶点定义的平均平面的距离小于该阈值，则删除 该顶点，并采用递归循环分割法对删除顶点后遗留的空洞进行三角剖分， 通过调整距离阈值大小可生成层次化模型。s c h r o e d e r 算法分为以下几个主 要步骤： 重庆邮电大学硕士论文 第一章绪论 计算三角形网格中每个给定顶点的局部几何和拓扑特征，并对顶 一点分类； 如果点到平均平面的距离小于给定的近似误差值，就删除这个顶 点；， ， 对删除顶点后留下的空洞进行局部三角化： 重复上述操作，直到三角形网格中无满足上述条件的点为止。 s c h r o e d e r 算法计算量小，时间复杂度为线性，有很好的保细节特性， 能保持拓扑结构，简化模型的顶点为原始模型顶点的子集。但是，由于算 法采用局部近似误差质量，无法从整体上对简化后的模型与原始模型间的 误差进行度量，在多次迭代后误差会积累，从而影响简化模型的质量。 3 t u r k 的重新布点法，基本思路是指定一个新模型所包含的顶点数， 首先将这些点布置在曲面上，原则是面积大的多边形内多布一些点，曲率 变化大的多边形内多布一些点，新点集合中可以包含原模型中的点；第二 步生成由新旧顶点共存的网格，即将新点插入到原模型中，修改原模型网 格；最后删除模型中不在新点集中的顶点，得到由新布点集合中的顶点组 成的简化模型。通过调整新模型中的顶点数，可以生成层次化模型。这种 方法仅适用于光滑曲面，且简化模型中引入了新点，涉及到平面旋转或投 影，计算量和误差都较大。 4 视点依赖的场景简化算法，对实时绘制来说，一个好的场景简化 算法应实时地随着摄像机取景的不同而简化场景几何。视点依赖的场景简 化算法的基本步骤一般是： 将景物空间剖分成一系列子空间，按每一子空间对顶点的包含关 系将传统的场景几何组织成一个庞大的顶点树； 通过动态查询树结点生成简化场景模型； 加入场景简化标准，通过两个操作( 收缩节点到一个代表顶点以及 展开代表顶点恢复原来几何) 完成场景简化。 视点依赖的场景简化算法则具备以下特点： 一般性：能处理任意类型模型，如边界封闭和开放的多面体网格 等： 自动性：场景模型简化是全自动的，无需人工干预： 动态性：根据当前摄像机的取景方位及摄像参数，自动决定是否 对景物进行简化，并生成简化模型。 4 | 重庆邮电大学硕士论文 第一章绪论 1 3 论文的预期目标和工作内容 l o d ( l e v e lo f d e t a i l ) 技术，即层次细节技术，指根据物体模型的节点 在显示环境中所处的位置和重要度，决定物体渲染的资源分配，降低非重 要物体的面数和细节度，从而获得高效率的渲染运算。是三维可视化技术 中将人们模糊意识与电脑的数字意识联系在一起的技术。它是运用人们的 模糊比例尺概念，将远近不同具有不同细节层次的各种对象生动形象的运 用数字在电脑中以可视化的技术展现给人，让人感觉另一个接近的“真实 的世界 。 我的主要设计方案是在原有的基于视点的l o d 技术的扩展，设计一 种可应用于地形漫游的节点简化方法。现有的方法主要是根据视点距离的 简化和地形的粗糙程度的简化，我的工作是在原方法的基础上提出一些改 进，然后试图找出一些新的适合实际需要的简化条件。 本课题的具体研究内容包括： ( 1 ) 在收集、整理和消化国内外最新数字高程模型的简化技术；首先介 绍海量地形几何数据的存储技术与调度技术，根据调度技术与数据的重组 与排序相关，对数据的排序技术进行了详细的研究。接下来研究了当前几 种三角网的简化技术，包括递进格网简化技术、基于顶点删除的简化技术、 基于最大独立点集的简化技术。对l o d 技术中的基础算法可见性剔除算 法做了深入的探讨，包含了隐藏面移走技术、背面剔除技术、对误差的计 算，本文也做了简要的介绍。在最后，对加速绘制三角形的基本算法作了 深入的探讨。在此基础上，设计出满足实时漫游需要的简化算法； ( 2 ) 在w i n d o w sx p 操作系统开发环境下用v i s u a lc + + 6 0 作为开发平 台实现该算法，完成应用程序的设计与编程工作。 1 4 论文结构 本文共分六章，各章的内容安排如下： 第一章为绪论，介绍了论文的研究背景，包括基于数字高程模型的 l o d 技术的国内外研究发展状况、研究内容，对课题的研究目标和内容也 做了阐述。 ， 第二章将首先介绍实时绘制中的各种通用的加速技术，并重点介绍基 于各种实时可见性加速的计算方法。室外地形是特殊的虚拟环境，针对地 篓篓篓璧竺翌篡篓零兰零! 繁麓霹鞲麓霉哆臻露磁瑟巧黑孽曩瀚露溺紫雾惹纛瓣纛囊蠹鬻鬻翳鬻器蔫雾慕蕊甄露雾蚕霉焉 = ：釜毯二：羞= = ：j 翌三：! = = 羔羔盖竺妻兰篓妻竺兰! 二蠹董乏一嘶墨诹一，= 譬囊冀掌。叠最蔓恐壶型? 生甄2 逝臻二恐箍- 亟玉二出面：；池：。：；：。? “ 重庆邮电大学硕士论文 第一章绪论 形的多分辨率建模方面的技术多种多样，我们将详细介绍几种典型的有代 表性的地形l o d 算法。 第三章，详细阐述了基于规则格网的l o d 技术，并对这些算法进行 了比较和分析。 第四章在总结前人的基础上，设计了一种新的计算l o d 节点粗糙程 度的方法，并根据粗糙度的大小来选择节点的细节层次。 第五章根据第四章的算法设计了原型系统并对较大规模的真实地形 d e m 数据进行了试验。对试验结果进行了比较和分析。 第六章总结本文所做的工作，并探讨了进一步的研究方向。 6 重庆邮电大学硕士论文第二章地形实时绘制的加速技术 第二章地形实时绘制的加速技术 在地形的实时绘制中，由于场景的几何复杂度、照明效果计算的困难 度以及三维数据转换成二维数据庞大的投影计算，通常会遭遇到下面两个 问题：虽然计算机硬件处理三维数据显示的速度进步很快，但若只以传统 的显示技术和算法，基本上仍无法达到视觉上所需的交互式显示速度与高 质量的需求；现今处理物理光线和照明效果，无法仿真真实的光学现象， 因此表现出来场景与物体的精致程度，显示效果并非完美。一般说来，这 两个问题一直是计算机图学领域的研究中心，是为了让虚拟场景与物体在 视觉显示上有模拟真实世界的效果而不断努力的目标。为了使显示画面逼 真，通常可以采用纹理映射、或者是整体光照明等技术来达成。而为了加 速三维物体模型的显示速度以期达到实时绘制的要求，可以采用诸多的方 法以及这些方法的有效组合，最终目的是尽量避免由绘制通道造成的整个 显示流程的瓶颈，提升绘制速度。 2 1 数据的存储与调度 在l o d 技术中，海量数据的存储方式对于数据的快速调度以及减少 存储量等起着非常重要的作用。现在根据海量数据的存储位置可分为基于 内存的海量数据存储方法和基于外存的海量数据的存储方法【6 1 。 2 1 1 基于内存的海量数据存储方法 对于海量数据的存储，一种方式是对海量数据进行分类存储，即采用 层次的结构进行存储，对相同层的数据存储在一起。这样根据一定的规则， 在进行实时调度时，可以快速的取出数据进行显示。另一种方式就是对地 形数据进行简化处理，采用一定的简化方法，对简化后的数据进行组织。 现在的数据组织一般采用树结构【7 1 ，如二叉树、三叉树、四叉树等方式。 在树中，一般使用节点的误差作为关键字，以便实时处理。 7 ，“”尊琢磁；i 霉搿i ：乏霹嚣冒嚣：嚣r 端弼誓：嚣：髫：蚕罗4 霸；嚣4 澎嚣获“乏：焉戳墨妻爵：紧镶焉曩蠹蛩爱曩焉豢慧鼍蹶蠢篡j 熏爱鼍蠖謦雾嚣磁j 疆器骧麓雾鬻 曼竺釜三：兰芝曼三二三篓堂参”乎鼍爿一巍：嵇j + “而r ：? 魄。二z i 西，；+ ，睁z 一葛卉赫赫邯：愚矗：j 河i 。二? ，撕，弧_ 二二劬。一- 。五杯，z 城j ；：= 。蕊五，盈。孟。五二龇二二一三 重庆邮电大学硕士论文 第二章地形实时绘制的加速技术 2 1 2 基于外存的海量数据的高速调度 基于地形的几何连续多分辨率层次细节模型的实时动态构网方法，根 据当前的视点位置和相邻帧的视点连贯性对地形进行简化。但是当简化后 的地形数据量仍超出内存的容量时，就必须考虑把数据存储在容量更大的 外存上，而外存的读取非常慢，成为实时绘制的一个瓶颈。显然，设计一 个有效的文件存储方式，对大规模地形的绘制具有非常重要的意义。 l i n d s r t o m 提出了一个基于外存的地形实时绘制框架，即数据调度由 操作系统来执行，使用操作系统的文件映射，建立文件与内存之间的映射 关系，在w i n d o w s 下使用m a p v i e w o 行i l e 函数。但当数据超出了操作系统 的文件映射( 或虚拟内存) ，则需要设计数据调度算法，更有效地在快速的 内存和较慢的外存( 例如硬盘) 之间进行数据交换。 基于外存的算法和数据，关键在于利用数据的局部连贯性，以避免重 复的，频繁的数据调度，减少输入输出的花费。外存的数据高效调度，归 结为数据的重组和排序，即建立地形网格顶点的一种有效排序，使他们在 硬盘上的排列方式具有很好的局部性，并且与三角形构网的方式一致，这 样在实时构网时能快速地访问数据。因此，重组后数据需满足物理地址上 的相邻的数据具有几何上的局部连贯性，同时在构网的过程中，能有效地 计算顶点的索引，以便在剖分的过程中能迅速地获取所需要的顶点信息。 数据的重组和排序可分为规则格网式的排序和不规则格网的排序。 1 规则格网的排序 j 大规模矩形网格的数据重组织在地形可视化、三位数据体绘制以及矩 阵运算中，都有着广泛的应用，其重点在于保证数据访问时的局部性。尽 管在几何计算和科学可视化领域中，不断有新的算法出现，但它们在执行 时都需把二维以及多维数据映射到一维数组，使得一维数组中的相邻数据 在空间中具有很好的局部性。 二维或多维空间填充曲线不仅可以保证遍历空间中的每个数据点，而 且填充曲线局部区段内的数据点在空间分布也是相邻的。因此空间填充曲 线常选作空间数据重组的排序方式，著名的h i b l e n 曲线就是一种经典的空 间填充曲线，如图2 1 所示。 近来，l a w d e r 采用了几种空间填充曲线来有效地存储和快速获取多维 数据。b a l m e l l i 使用z 型填充曲线有效地表示网格的四叉树结构，并能快 速计算相邻结点以及具有共同父结点的其他结点的索引，可用于地形绘制 以及自适应网格逐步求精。 8 ：霉警鞲鬻嚣；3 ；i 鞲；荔麓嚣惹霉臻露焉；甄嚣瑟鼍奎毫蒙器豸零戆嚣霉。甄嚣i i 警蒙孑j 篡妻謦瑟爱誊誊荔甍妻雩鬻甓鬻曩雾黎髫零篡雾零琴瑟箩譬季繁鬻瑟瑟琴嚣瑟瑟雾i i ：需 ：苎! 苎重篓翌! ! ! 凄妻耋二耋i 曼黑箩里簟i 西t 一；一并弦轨p ，毋。j 。- ；j i ：嘉：磊一? i 强* 譬；一：t ；二a j ：。而：i 。，。i ：毒? = 警墨。i ：羔；o 。量叠。：t ：，疽，姥壶二二= 兰二妄二笠上立珏i 二j 。盎址曲五。二矗。矗盎二；五。五。溢。j 重庆邮电大学硕士论文 第二章地形实时绘制的加速技术 ! | 鳃羔 图2 1h i b l e n 曲线 图2 2 给出了z 型填充曲线的四叉树排序。四叉树的z 型填充曲线用 来加速矩阵操作也是十分有效的。 图2 2z 曲线 p a s c u c c i 把单一分辨率数据变换到多分辨率的数据排序，该排序方式 采用自顶向下，由粗往细的顺序排列网格顶点，在三维体数据的可视化中 是一种十分有效的数据组织方式。l i n d s r t o m 和p a s c u c c i 在地形的可视化 中采用了三种数据结构，并给出了有效的顶点索引。第一种是隔层四叉树， 该方法把地形网格在由粗往细的剖分过程中按层次分为白色四叉树和黑 色四叉树两种，每种均为一棵完全的四叉树。这种黑白隔层表示顶点的方 式利用四叉树的编码，根据父子结点关系推导出顶点索引号，但是这种算 法增加了6 6 的顶点，导致数据的存储量的增加。 2 不规则格网的排序 不规则格网的排序一般采用扫描方式来排序，这样的排列有利于格网 的三角化与分块。另一种方法就是对数据进行分类，如山、平地、河流、 湖等，然后根据其拓扑关系，采取相邻对象存储在一块，以便快速调度， 一般来说，每个对象都有一个中心点来作为对象的索引标志，这样在实时 可视化时，就根据索引标志来快速判断是否调度该对象的数据。这种方法 采取自然分类，可以避免人工生成的一些裂缝。但是这种方法对每个对象 的边界不好确定，并且对于如丘陵这样的地区不好分类。因此，对不规则 格网的排序，主要采用规则格网的排序方法来排序，这样算法实现起来比 较容易。总的来说，虽然可以通过操作系统的虚拟内存来映射数据文件， 9 重庆邮电大学硕士论文第二章地形实时绘制的加速技术 、 把数据调度的工作交给操作系统来管理，但是当需存储的数据超出了虚拟 内存的容量，并且操作系统没有针对特定的数据进行优化装载时，就需要 设计算法来加速数据的调度。为了实现数据的实时调度，可以采用数据预 装载和实时装载两个线程来并行调度地形数据，使数据调度能更好的适应 可视化的要求。 2 2 多层次细节模型 多层次细节技术是一种应用到计算机显示上的技术【9 】，白1 9 7 6 年被 c l a r k 提出以来，这门技术对于加快图形显示有着重要的贡献。它的基本 思想是：如果描述场景使用具有多层次结构的物体，即可视作场景中物体 具有多个不同分辨率的模型，以不同程度的分辨率来区别，那么实时显示 时，可依照实际需要更换不同的模型来提高显示速度。复杂的场景往往会 包含大量较小的物体，而这些物体在远离视点时几乎不可见，如果一个物 体距离视点很远，其显示结果在画面上只占小小的几个像素，用很复杂的 多边形模型去处理确实是很不值得的。在实时应用程序中，为获取较高的 帧速率，常常要牺牲掉那些微不足道的场景细节，用较低细节的模型去呈 现远离视点或偏离视点的物体，并不会带来视觉效果上的损失。复杂的物 体可以使用层次细节技术进行简化。细节越少，则用来表示物体的多边形 数目就会越少。而运行阶段层次细节的选择一般都是依据视点与物体之间 的距离、场景部分的重要性或者用户所期望的绘制时间而确定。可见性信 息甚至可以支配层次细节的选择。多层次细节模型建构的技术依其建构时 间可分为静态与动态两类。动态多层次细节模型技术是在执行时间( r u n t i m e ) 根据视点的所在位置，实时建构出不同细节的多边形模型。因此，也 称为视点相关多层次细节模型( v i e w d e p e n d e n tl o d ) 。静态多层次细节模型 是利用预处理产生不同细节的多边形模型，储放在内存空间。当显示时， 再根据当时的视点位置取用适合于显示的细节模型，此后若视点改变再切 换成不同细节的多边形模型。这种多层次细节模型的建构因为与视点的位 置不存在依赖关系，所以就称为视点无关多层次细节模型 ( v i e w i n d e p e n d e n tl o d ) 技术。 1 离散层次细节( d i s c r e t el o d ) 所谓离散层次细节模型是一组具有不同几何复杂度和不同细节的模 型，每一个模型对应一个细节层次，这些几何模型的表示和构造在绘制时 l o 重庆邮电大学硕士论文第二章地形实时绘制的加速技术 由简化算法生成。在不同细节层次之间切换时，离散层次细节模型容易导 致跳跃现象( p o p p i n g ) 的问题，为解决该问题，可以通过不同层次之间的模 型连续混合运算消除，但是同时模型混合会占用额外的计算开销。 2 连续层次细节( c o n t i n u o u sl o d ) 连续层次细节模型是指对物体实时地进行一系列基本简化操作的方 法，而简化操作是基于当前视点位置的。连续层次细节技术在地形绘制之 中非常重要，在地形场景中靠近观察者的部分需要使用较精细的网格剖分 而较远处的部分则可以使用相对粗糙的模型表示。典型的模型简化方法有 h o p p e 提出的递进网格算法( p r o g r e s s i v e m e s h ) 。通过一系列的边折叠( e d g e c o l l a p s e ) 操作获得逐渐简化的三角形网格。当每一条折叠时，其附近顶点 的位置移动到新的位置以便能够更好地表示物体的形状。边折叠的逆操作 为点分裂( v e r t e xs p l i t ) 。通过点分裂过程，一个最粗糙的简化模型可以逐渐 恢复成原始模型。不同l o d 层次之间的几何过渡技术可以实现变化的顶 点位置之间的平滑连接以避免点分裂或者边折叠时跳跃现象的产生。 2 3 几何数据的高效表示 将物体的几何表示组织为便于图形卡硬件使用的方式是一种常用的 提高绘制性能的技术。优化几何表示的组织结构能够节省大量的g p u 上 的变换和光照( t r a n s f o r m a t i o n & l i g h t i n g ) 计算，并且降低c p u 和图形硬件 之间带宽的占用。几何数据的有效组织进行加速可以被应用到大部分多边 形或者三角形表示的场景。 任何多边形模型都可以转换成三角形的集合【1 0 】。相互邻接的三角形共 享一条公共边和两个顶点。如果三角形被各自独立地送至图形硬件进行绘 制，共享的顶点数据就需要执行的重复冗余的运算，并且相同的数据还被 传送至少两次以上。降低这些额外开销的一个方法就是把彼此相邻的三角 形构建成三角带。首先，把第一个三角形的三个顶点放至s t r i p 之中，然后 将其余的三角形顶点依照相邻顺序依次放至s t r i p 中，每个三角形只需要加 入一个顶点。缺省条件下，在s t r i p 中彼此相邻的顶点都构成了连接两个相 邻三角形的公共边。如果连接规则( 顶时针或者逆时针顺序) 需要发生改变， 则可以使用s w a p 命令交换顶点顺序，或者重新将某一个顶点放入s t r i p 之 中。三角形扇可以看作是三角带的一种退化形式，只是其中所有的三角形 都共享一个公共顶点。以三角带或者三角形扇形式存储在顶点缓存( v e r t e x 重庆邮电大学硕士论文第二章地形实时绘制的加速技术 b u f f e r ) 中通常被称为广义三角形网格。 2 4 地形实时可见性加速技术 2 4 1 地形可见性概述 可见性的计算对计算机图形、计算几何、计算机视觉、智能机器人、 远程通讯定位以及其他一些研究领域都十分重要。我们研究的重点是可见 性在计算机图形学中实时绘制方面的作用。可见性算法在计算机图形学中 的只要目的是用于判定在一个三位场景之中哪一些表面或者物体是可见 的。这些可见性算法归结为可见面或者可见物体的判定问题，b e r g 进行了 有关计算几何方面的可见表面判定的理论性研究。可见面( 线) 判断的另外 一种表达方式就是隐藏面和隐藏线消除问题( h i d d e ns u r f a c er e m o v a l ) 。 可见性是与以三维图像生成为目的的绘制技术紧密相关的。通常绘制 技术又分为两大部分：实时绘制和真实感绘制。在实时绘制技术中，每一 幅图像的生成时间是由所期望的帧速率严格控制的，对应实时绘制的最广 泛使用的可见性算法是z - b u f i f e r 算法【1 1 】。而真实感绘制的终极目标就是要 进行光线与物体之间相互作用的精确模拟，以得到与人类观察的自然现象 几乎相同的图像效果，而不在乎时间耗费的长短。对应真实感绘制的最主 要可见性算法是r a ys h o o t i n g 算法，用于计算沿发射光线方向可见信息的 计算。在可以预期的将来，这两种绘制技术将会融为一体，能够实时绘制 出非常逼真的图像，这是图形学追求的至高境界。 可见性剔除技术十分有助于遮挡稠密的场景的绘制，在这样的场景 中，只有较少的一部分物体相对于观察者可见。而室内建筑场景的漫游以 及室外大规模地形场景或者城市场景的漫游恰恰符合稠密遮挡的情况。可 见性计算按照其实施的时间阶段的不同，可以分成离线可见性计算和在线 可见性计算两种，而按照可见性判定的方式又可以分成f r o m r e g i o n 和 f r o m p o i n t 可见性两种，这两种方式其实又是紧密相连的，离线可见性大 多采取基于f r o m r e g i o n 的判定方式，而在线可见性又大多采取基于 f r o m - p o i n t 的判定方式。 离线可见性计算1 1 2 ( o 衄i n e ) 是指预先计算可见性信息的方法，而在线 ( o n l i n e ) 可见性计算是指在实时应用程序的运行阶段动态生成可见性信息 的方法。离线技术通常把场景分成一些观察单元，对每一个观察单元都计 重庆邮电大学硕士论文第二章地形实时绘制的加速技术 算出一个潜在可见物体集合。在应用程序运行阶段，根据观察者所在的观 察单元，这些预先计算好的可见性信息指出场景那些物体是有可能相对于 视点可见，并绘制这些物体。而最终的像素级的可见性由硬件实现的 z - b u f f e r 算法来完成q 在线可见性计算技术并不预先处理可见性信息，而是在程序执行阶段 实时对每个更新的视点计算物体集合。另外一些在线技术可以实时计算出 一个视点及其临近区域的物体集合，使得在连续的几帧之内不需要重新计 算，以节省可见性计算的消耗。大部分在线可见性计算都是解决基于 f r o m p o i n t 可见性问题，也就是可见性是相对于单独一个给定的视点而确 定的。相反，大部分的离线可见性计算都是解决基于f r o m r e g i o n 可见性问 题，该可见性信息是相对于给定区域之内的任意视点的。 随着计算机性能的不断提高，人们对显示图像质量的期望值也就越 高，用户希望能够与非常复杂的场景进行交互，同时场景绘制的图像质量 要尽可能高，实时应用程序中所期望的图像的刷新频率至少是3 0 h z 以上。 实时绘制需要达到至少三个目标：每秒更多的帧数目、更高的分辨率以及 更真实