（计算机应用技术专业论文）大规模地形的快速几何绘制与实时纹理映射技术研究.pdf

中国民航大学硕士学位论文 摘要 随着计算机性能的日益提高，人们开始不满足于缺乏生动表现力的二维地图 而转向三维地形；随着遥感技术、卫星技术以及如今测量技术的不断发展，人们 又开始不满足于小规模的三维地形而转向三维的“数字地球。如今，大规模三 维地形在飞行仿真、地理信息系统以及三维游戏都有着非常重要的应用，因此如 何有效地组织大规模三维地形数据、如何快速而真实地绘制地形便成为一个非常 重要的研究问题。 本文所说的大规模是指地形几何数据与纹理数据之和超出当前普通p c 机内 存容量( 2 g b ) 的一种规模。针对大规模三维地形本文实现了一个有效的可视化 框架：将地形数据分为几何数据与纹理数据分别进行处理，地形几何数据来源于 数字高程模型( d e m ) ，而纹理数据则来源于遥感图像，对几何数据与纹理数据分 别进行多分辨率组织，并且根据一定的误差测度，选取适当的分辨率进行绘制， 主要贡献包括以下几点： 1 、在地形几何数据连续l o d ( 层次细节) 模型的构建方面，本文首先将原 始地形进行分块并进一步将每一地形块划分成若干个三角形，再将这些三角形组 织成二叉树的结构，然后根据误差测度的结果调度相应的三角形简化算法以便根 据当前视点位置及方向动态调整当前帧地形的多分辨率层次。在三角形简化算法 方面，本文实现了基于指针的简化算法以及基于编码的简化算法，并将两种算法 与经典r o 创算法进行了比较。 2 、在o u t o f - c o r e ( 基于外存的) 数据调度方面，本文采用了基于外存的数 据重组以及基于多c p u 的数据预取策略来实现o u t o f - c o r e 数据调度。基于外存 的数据重组在预处理阶段对原始地形数据进行重组并存放于外存中；基于多c p u 的数据预取策略实现了数据预取线程以及绘制线程调度到独立的c p u 上运行的 方法，提高了c p u 使用率及数据调度的效率。 3 、在大规模地形的实时纹理映射方面，首先对每一个地形块的纹理数据在 外存中建立其多分辨率的组织结构，然后在o u t o f - c o r e 数据调度的预取过程中预 取下一帧可能落在视域内的低分辨率纹理数据，最后是将纹理数据映射到几何三 角形上。 本文的可视化框架将地形的几何数据和纹理数据都进行了多分辨率组织， 其特征是尽管数据规模远远超出内存容量，但是系统仍然能对大规模地形进行快 速的绘制。 度 关键字：大规模地形，几何绘制，纹理映射，l o d 技术，o u t o f - c o r e 数据调 中国民航大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , p e o p l ep r e f e rt h r e e - d i m e n s i o n a l t o p o g r a p h i c a lm a pt ot w o d i m e n s i o n a lw h i c hl a c ko fv i v i dp e r f o r m a n c e a l o n g w i t h t h ed e v e l o p m e n to fr e m o t es e n s i n gt e c h n o l o g y , s a t e l l i t et e c h n o l o g y , a n dm e a s u r e m e n t t e c h n o l o g y , p e o p l eb e g i nt on ol o n g e rs a t i s f yw i t ht h es m a l l - - s c a l e dt h r e e d i m e n s i o n a l t e r r a i nb u tt op r e f e rl a r g e - s c a l e dt h r e e d i m e n s i o n a lt o p o g r a p h ya st h e ”d i l g i t a le a r t h ” t o d a y , l a r g e s c a l et h r e e - d i m e n s i o n a lt e r r a i ni sp l a y i n gk e yr o l ei nm a n ya p p l i c a t i o n s s u c ha sg e o g r a p h i ci n f o r m a t i o ns y s t e m s ，f l i g h ts i m u l a t i o na n d3 dg a m e s s o ，h o wt o o r g a n i z el a r g e - s c a l e dt h r e e - - d i m e n s i o n a lt e r r a i nd a t ae f f e c t i v e l y , h o wt or e n d e r i n g t e r r a i nr a p i d l ya n dv i v i d l yh a sb e c o m eav e r yi m p o r t a n tr e s e a r c hq u e s t i o n s t h ep a p e rp r o p o s eaf r a m e w o r kf o re f f e c t i v ev i s u a l i z a t i o no fl a r g e s c a l e d t h r e e d i m e n s i o n a lt e r r a i n ，o u rt e r r a i nd a t aw i l lb ed i v i d e di n t og e o m e t r i cd a t aa n d t e x t u r ed a t a ，g e o m e t r i cd a t ag e t sf r o md i g i t a le l e v a t i o nm o d e l ( d e m ) ，a n dt e x t u r e d a t ag e t sf r o mr e m o t es e n s i n gi m a g e ，b o t hg e o m e t r i cd a t aa n dt e x t u r ed a t aw e r e m u l t i r e s o l u t i o no r g a n i z e d ，a n db a s e do nt h ee r r o r so nt h es c r e e n ，w ec a ns e l e c tt h e a p p r o p r i a t er e s o l u t i o nt or e n d e r i n gt h et e r r a i n ，t h em a j o rc o n t r i b u t i o no ft h i sp a p e ra s f o l l o w s ： 1 b u i l d i n gl o d m o d e l sb a s e do ng e o m e t r i ct e r r a i nd a t a t h et e r r a i ni sd i v i d e d i n t od i f f e r e n tb l o c k sa n df u r t h e rd i v i d e di n t om a n yt r i a n g l e st ob u i l db i n a r yt r e ed a t a s t r u c t u r e t h ep a p e rp r o p o s et h et r i a n g l eb i n a r yt r e es i m p l i f ya l g o r i t h mb a s e do no u r c o d i n ga p p r o a c h ，t h et r i a n g l es i m p l i f ya l g o r i t h mi st h ec o r eo fb u i l d i n gl o d m o d e l s i no u ra l g o r i t h m ，e a c hn o d eo fb i n a r yt r e ei se n c o d e d ，a n dw ec a l c u l a t et h ec o d i n go f e a c hn o d et h a tw en e e di na c c o r d a n c ew i t ht h ef o r m u l ao fo u rp a p e r t h ea l g o r i t h m e l i m i n a t e st h et r a d i t i o n a ls t r u c t u r eo ft h eb i n a r yt r e et h a tv i s i t sc h i l d r e no rn e i g h b o r s b a s e do np o i n t e r s ，w h i c hs a v e sl o t so ft i m ea n ds p a c e 2 d a t as c h e d u l i n gf r o mo u tm e m o r y t h ep a p e rr e o r g a n i z et e r r a i nd a t ai n e x t e r n a lm e m o r yf i r s t ，t h e no p e nu pas e p a r a t et h r e a df o rs c h e d u l i n gd a t a ，w h i c hu s e s m o d e mc o m p u t e r st w oc p uf e a t u r e ，d a t as c h e d u l i n gt h r e a da n dt h em a i nt h r e a dw e r e a s s i g n e do nt h e i ro w nc p u ，a n dw es y n ct h et w ot h r e a d sb a s e do ne v e n tt om a k ea b e t t e ru s ef o ro u ts c h e d u l i n gt h r e a d 3 t e x t u r em a p p i n gf o rt h el a r g e - s c a l e dt e r r a i n t h ep a p e rb u i l dm u l t i r e s o l u t i o n s t r u c t u r ef o rt e x t u r ed a t ai ne x t e r n a lm e m o r y , t h e np a g et h el o wr e s o l u t i o nt e x t u r e d a t ai n t om e m o r ya h e a do fr e n d e r i n g ，a tl a s tw em a po u rt e x t u r ed a t at ot h et r i a n g l e s i i 中国民航大学硕士学位论文 i nt h i sp a p e r , o u rf r a m e w o r km u l t i r e s o l u t i o no r g a n i z e dt h eg e o m e t r i cd a t aa n d t e x t u r ed a t a ，a n dt h ef e a t u r eo ft h ef r a m e w o r ki st h a ta l t h o u g ht h es i z eo fd a t af a r b e y o n dt h es c a l eo fm e m o r yc a p a c i t y , t h es y s t e mc a ns t i l lr e n d e r i n gt h et e r r a i n r a p i d l y k e y w o r d s ：l a r g e s c a l e dt e r r a i n ，g e o m e t r yr e n d e r i n g ，t e x t u r em a p p i n g ，l o d t e c h n o l o g y , o u t o f - c o r ed a t as c h e d u l i n g i i i 中国民航大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得中国民航大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：寻牛日 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权中国民航大学研究生部办理。 研究生签名：导师签名：之堇幽堡日 中国民航大学硕士学位论文 第一章绪论 1 1 研究背景及研究目的和意义 本文源于国家自然科学基金项目“民航飞行视景的真实感与快速绘制研究y 基金编 号：6 0 5 7 2 1 6 9 ) ，主要研究飞行视景中大规模地形的快速几何绘制与实时纹理映射技术。 三维地形作为飞行视景中不可或缺的组成部分，其绘制的速度与真实感对民航飞行 视景 具有重要的影响，本文即是研究大规模三维地形的快速几何绘制与实时纹理映射 大规模是指地形几何数据与纹理数据之和超出当前普通p c 机内存容量( 2 g b ) 的一种 规模，快速几何绘制目的是为提高三维地形的绘制速度，而实时纹理映射目的是提高三 维地形绘制的真实感。 当前国内外出现了越来越多的飞行模拟软件小至p c 机上运行的飞行模拟游戏， 大至为飞行员提供飞行训练的专业飞行训练器，快速真实的地形绘制都在其中具有非常 重要的作用。 2 0 0 6 年1 0 月，微软发布了f l i g h t $ i m u l a t o rx ，即微软模拟飞行1 0 ，这款飞行 模拟软件主要专注于民航飞行的模拟，模拟飞行软件中超过2 4 0 0 0 个机场、真实的飞行 距离、不同材料的反射光泽都在其中完美的呈现出来。为了给用户呈现尽可能逼真的世 界，飞行模拟本身有一大部分就是关于地面场景的，包含大量不同的地形，如山脉、河 流、湖泊、森林、城市、公路以及从虚拟驾驶舱看到的其他特征。为尽可能逼真的渲染 地面场景微软飞行模拟游戏使用的大量真实世界地理数据来源于a r c g i s ，这些数据中 包括向量数据和光栅数据。向量数据的例子如公路、跑道、电力线、溪流和海岸线的中 心线，也有用来描绘出公园、高尔夫球场或者机场的外框；光栅数据例如海拔高度栅格、 航空成像、陆地和水体分类以及季节数据。图1 - 1 是微软模拟飞行1 0 中的场景画面： 图1 - 1 微软模拟飞行1 0 ) 中的场景画面 2 0 0 5 年，中国研制出了具有自主知识产权的“空中客车a 3 2 0 虚拟飞行训练器”。 飞行训练器是为飞行员飞行训练提供的专业设备，飞行模拟训练就是要给飞行员构建一 1 中国民航大学硕士学位论文 个虚拟的“真实”环境，主要分两部分：首先是机器环境，即飞机座舱、设备等：其次 是外部环境，主要指自然条件、地理条件等。在机器环境方面，对飞机运动、动感( 如 加速度、座椅抖振等) 的模拟是比较关键的技术；对飞机设备( 主要是座舱中的仪表、操 作设备和综合显示系统) 的模拟也比较重要；外部环境模拟是目前研究的重点。透过模 拟座舱看窗外，为了能看到空中、地面自然景色和地理环境的变化，需要用到三维可视 飞行环境数据库，这种虚拟的三维飞行环境数据库是运用地理信息系统( g i s ) 三维动态可 视化仿真、场景建模和图形图像处理等技术，集成数字化高程、卫星遥感影像、实体纹 理、文化特征等数据源而生成的。它可以再现真实环境中的自然地形地貌( 山川、河流、 森林、海洋、天空等) 和人文景观( 城镇建筑物、桥梁、公路、铁路、机场等) ，同时提供 雨、雪等多种气象条件下的昼夜景象，创造一种几近真实的立体环境。外部环境模拟可 以为参训人员提供多种飞行条件下较为逼真的飞行视觉和临场感觉，提高训练质量和参 训人员对飞行环境的认知效率。 除此之外，大规模地形在地理信息系统、模拟驾驶以及网络游戏等领域都具有重要 的意义，例如g o o g l e 公司提供的g o o g l ee a r t h 采用的3 d 地图定位技术能够利用g o o g l e m a p 上的最新卫星图片使用户在3 d 地图上搜索特定区域，放大缩小虚拟图片，然后形 成行车指南。与此同时，2 0 0 6 年微软公司也发布了v i r t u a le a r t h3 d 产品，v i r t u a le a r t h3 d 基于m i c r o s o f tl i v e 搜索引擎是微软公司l i v e 服务中的一个地图服务，可以用3 d 的方 式浏览地球上的任何一个地方。 由此，三维地形技术已经渗透到了计算机的众多方面，与人们的生活也息息相关。 1 2 面临问题及技术现状 大规模地形在众多领域里都有如此重要的应用。然而大规模地形场景的实时绘制却 面临着两个非常困难的问题： 一是原始几何模型庞大的数据量远远超过了系统的实时处理能力，例如微软的模 拟飞行1 0 中包含了整个地球的地形数据，其原始数据源非常巨大，达到太拉( t b ， 1 t b = 1 0 2 4 g b ) 级别的容量，进行有损和无损压缩后的容量也有近1 0 g b 。由于当前普 通p c 机的内存容量在2 g b 左右，如果我们忽略压缩技术，想让广大的游戏玩家在自己 的p c 机上尽情享受这款游戏便成了天方夜谭。 标准地形文件一般是采用正则网格来表示地形的高程值，而在图形学中则一般采用 三角形网格作为地形几何绘制的基本图元，也就是说外存的正则网格地形数据在送到图 形显示硬件显示时要转化成三角形图元。当我们将每一个最精细的地形网格矩形区域用 对角线分割，就形成了图形显示硬件绘制所需要的三角形，因此地形的三角形个数随地 形尺寸成四倍增长；另一方面由于标准地形文件只包含高程信息，而送往图形显示硬件 进行显示三角形的每个顶点都需要三维的信息，因此假设每个采样点高程值占用4 b y t e 的存储空间，则每个三角形将占用3 6 b y t e 的存储空间。地形规模与三角形数目以及所需 2 中国民航大学硕士学位论文 存储空间关系如表1 1 所示。 表1 1 地形规模与三角形数目以及所需存储空间关系 地形尺寸三角形数目( 个)所需存储空间( b y t e ) 1 0 2 4 奉1 0 2 4 2 ，0 9 7 ，1 5 2 7 5 4 6 m 2 0 4 8 2 0 4 88 ，3 8 8 ，6 0 8 3 0 1 9 8 m 4 0 9 6 * 4 0 9 6 3 3 ，5 5 4 ，4 3 2 1 2 0 g 8 1 9 2 事8 1 9 2 1 3 4 ，2 1 7 ，7 2 8 4 8 3 g 1 6 3 8 4 1 6 3 8 4 5 3 6 ，8 7 0 ，9 1 2 1 9 3 2 g 3 2 7 6 8 幸3 2 7 6 8 2 ，1 4 7 ，4 8 3 ，6 4 8 7 7 3 0 g 二是与地表模型相对应的地表纹理更加重了交互实时绘制的难度，在飞行仿真中为 了更真实的显示地形，需要利用纹理映射技术来增加地形的真实感。飞行仿真中的地形 纹理一般采用卫星图像，利用单张高分辨率的纹理数据给纹理映射造成的困难类似于庞 大的几何数据，主要体现在纹理数据的存储及传输问题。 一般说来，纹理数据存储在主内存当中，当需要将其映射到某一几何表面时，纹理 数据通过图形总线送入图形处理硬件中。目前，几乎所有支持纹理映射的图形处理硬件 都在其硬件系统中设置了纹理内存来缓存纹理数据以提高纹理映射的效率。当纹理数据 的规模大于纹理内存的容量时，图形处理硬件将无法缓存全部纹理数据，每一次纹理映 射时都需从主存中传输部分纹理数据，因而图形总线传输带宽成为纹理映射的时间效率 瓶颈。特别地当纹理数据规模超过了主内存时，纹理数据将不得不存放在外存中( 如硬 盘设备) ，此时外存与内存之间数据调度速度也将构成一个瓶颈。值得注意的是外存与 内存之间数据调度的速度远远低于内存与显存之间数据调度的速度，通常在数量级上相 差1 0 0 - - 1 0 0 0 倍。 针对上面两个主要问题，国内外研究人员分别从各自的重点提出了相应的解决办 法，归纳起来大致可以分为三类： 第一类是对地形几何结构建立多分辨率模型，层次细节模型( l e v e lo fd e t a i l s ，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 s ，t i n s ) ；另一类是将地形建模成规则网格( r e g u l a r s q u a r eg r i d ，r s g ) ，由于本文只针对规则网格模型，因此在这里不讨论非规则网格的 多分辨率模型方法。 对于规则网格，早期的研究工作主要集中在离散l o d 模型的生成及简化工作，1 9 9 6 年l i n d s t r o m 在1 9 9 6 年首次提出了c l o d ( 实时连续层次细节) 算法【l j ，使得研究工作 转为连续l o d 模型的多分辨率组织结构方面。该方法自底向上实时生成连续细节层次， 在连续细节层次生成过程中使用顶点依赖型关系消除裂缝。 3 中国民航大学硕士学位论文 另一个具有里程碑意义的事件是d e c h a i n e a u 在1 9 9 7 年提出了r o a m ( 实时自适应 动态网格) 算法【2 1 ，算法使用两个优先队列来驱动三角形的分裂与合并。队列中三角形 按单调的权值进行排序，从而保证在若干步简化和细分之后得到一个最优的三角形网 格。2 0 0 0 年，b l o w 对r o a m 算法做了重要的改进【3 1 。抛弃了r o a m 算法中根据视点 计算误差的方法，改为根据误差函数对每个顶点预先计算一个包围球，当视点进入包围 球的范围内，就加入该顶点，否则就不加入，而各个顶点包围球有树状关系。 l i n s t r o m 在2 0 0 1 年及2 0 0 2 年连续发表论文【4 ，5 1 ，提出了s o a r 算法，类似于以前的 几种方法，在规则网格上采用基于视点的最长边剖分方法，自顼向下逐步求精，每一帧 都采取相同的步骤，并且把三角形条带化、视域剔除，以及地形的几何过渡都几种在这 一步中，使得执行起来更为方便。在该文中还提出了o u t o f - c o r e ( 基于外存) 的可视化 框架，能够实现大规模地形的实时绘制。 采用l i n s d r o m 的系统框架，2 0 0 3 年g e r s t e r 提出了一种新的剖分判断的规则1 6 j ，由 于顶点的层次嵌套包围体不仅在计算基于视点的误差时要使用，在进行视域剔除时也要 使用，该包围体的精确程度直接影响构网后三角形的数目，所以该文提出了更为紧致的 层次包围体。把物体的包围盒分解成水平和垂直方向两部分，在垂直方向使用了垂直方 向包含所有子结点的测度，并且保证这种包围盒具有嵌套关系，在水平方向，构建了一 种八边形体的包围盒，对剖分顶点作了紧致的包围。 2 0 0 6 年，李胜等提出了一种新的基于受限法向锥的误差计算方法【7 】，使得模型简化 具有轮廓保持性和光照保持性。算法使用离散层次细节技术并结合连续层次细节，当生 成网格包含三角形数目相当时，该方法比传统基于几何误差的简化更加符合地形场景漫 游中人的视觉感知规律。 第二类是o u t o f - c o r e 数据调度，o u t o f - c o r e 数据调度，即基于外存的数据调度，是 为解决三维模型规模爆炸性增长【引，远远超出当前计算机内存容量，无法一次性调入内 存这一问题而发展起来的技术。许多学者从不同方面取得了重大的技术成果。 在外存多分辨率组织方面，有些学者采用了外存多分辨率技术1 9 0 1 ，即在预处理的 时候，对模型建立多分辨率组织结构并将其存放在外存中，但是构造外存多分辨率层次 结构是非常耗时的工作，因此实现了将模型分为若干可以并行构造的子块交给多台主机 并行处理的方法【1 1 1 2 1 ，加快了构建多分辨率结构的速度。 在内外存数据调度方面，外存多分辨率结构在进行交互绘制时只能放在外存上，内 存中主要存放的是绘制当前帧需要的数据以及一些预取数据。除了重复利用内存缓冲中 的数据外，其它所需数据从外存中按需调入。系统大多自己的算法显式地管理内外存数 据交换1 1 3 1 4 1 5 1 ，大多使用最近最少使用原则来尽量提高内存缓冲命中率，数据调度都是 以操作系统数据调度单位页面作为单位来进行的。数据调度在大部分系统中会交给 专门的一个甚至多个线程来与其它计算并行进行，减少了等待所需数据带来的时延【1 们。 大部分系统在发现需要的数据不在内存中时，并不等待数据的调度，而是在当前内存中 已有数据中挑选最接近的来代替，以减少延迟时间【1 7 l 。 4 中国民航大学硕士学位论文 在预取方面，预取技术指预测哪些数据是绘制下一帧马上要用到的，提前将它们调 入内存以其进一步提高内存数据命中率，有的文献预取当前帧的活跃前端的父亲、孩子 结点的数据旧，考虑到前后帧视点的相关性，这种预取策略的命中率较高，但由于视点 突变情况失效。 在多线程并行方面，大部分地形漫游系统利用两个线程并行工作【1 3 1 6 ，1 7 1 ，一个负责 数据管理，包括内存中存放的数据，和外存交换数据等；另一个负责计算，包括层次细 节管理、发出数据调度指令或者修改共同的缓冲区进行通信。 第三类是实时纹理映射技术，在纹理映射方面目前使用最为广泛的地形纹理管理和 调度技术有纹理裁剪方法【1 8 】和纹理树方法【1 9 j 。 纹理裁剪提供了硬件支持的机制来解决使用大纹理的问题。纹理裁剪将原始图像作 为纹理最底层，高一层的纹理为低一层纹理大小的1 2 ，形成一个金字塔形的纹理层。纹理 裁剪并不将全部纹理载入显存，每一层剪切同样大小的区域载入显存，随着每一层纹理分 辨率的减小，每层剪切区域包含的图像区域占该层全部纹理的比例的大小逐层的扩大，当 剪切区域大小大于某层大小则该层都保存在显存中，剪裁区域由视点位置确定。 纹理树是一种四元树( q u a d t r e e ) 结构，子节点的纹理精细度是父节点的一倍，通常采 用纹理树的大地形漫游算法其三角形网格也采用同样的四元树结构，这种方式可以实现 对大型三维模型的变分辨率表示， 1 3 总体方案概述 本文大规模地形漫游系统框架如图1 2 所示： 图1 2 大规模地形漫游系统框架图 整个系统主要涵盖三个方面：几何数据连续l o d 模型的构建、o u t o f - c o r e 数据调 5 中国民航大学硕士学位论文 度以及实时纹理映射部分。下面对本文的技术方案做一个概括的介绍。 在地形几何数据连续l o d 模型的构建部分，主要研究如何将地形几何映射为内存 中的三角形二叉树模型，以及如何根据视点位置及方向的变化动态调整三角形二叉树模 型。 首先对原始地形用等间隔的水平分割线及竖直分割线分成若干个相同规模的地形 块，并在地形块内将每一个最精细的采样点的矩形区域用对角线分割，得到若干个三角 形；其次是将每一地形块内的三角形组织成二叉树的结构；再次是选取一定的误差测度 以决定二叉树中的三角形结点分裂为高分辨的结构还是合并为低分辨率的结构；最后是 实现具体的分裂合并算法。 在o u t o f - c o r e ( 基于外存的) 数据调度部分，本文主要采用了两种方法用来实现 o u t o f - c o r e 技术，即基于外存的数据重组方法和基于多c p u 的数据预取方法。 在基于外存的数据重组中，地形数据在预处理阶段被组织成适合内外存之间数据调 度一种分辨率结构；而在基于多c p u 的数据预取策略中，开辟两个线程，一个线程用 于数据预取，另一个线程用于绘制显示，并将两个线程调度到独立的c p u 上运行方法， 以便提高c p u 使用率及数据调度的效率。 在大规模地形的实时纹理映射部分，主要研究纹理数据的多分辨率组织以及如何将 纹理快速的映射到三角形的问题。 首先我们按照几何数据的分块方法将纹理分成同样规格的若干纹理块，并将每一个 纹理快的纹理数据在外存中建立多分辨率的组织结构，然后在o u t o f - c o r e 数据调度技术 的预取过程中预取下一帧可能落在视域内的低分辨率纹理数据，而高分辨率纹理只有在 真正需要的时候才从外存调度到内存，最后将调度到内存中的纹理数据纹理到几何三角 形匕。 1 4 本文主要工作与论文组织结构 本文主要工作是实现了大规模地形的可视化绘制框架，框架分为三个主要部分：地 形几何数据连续l o d 模型的构建、o u t o f - c o r e 数据调度以及实时纹理映射。在地形几 何数据连续l o d 模型的构建部分主要研究了三角形简化算法，并用基于指针和基于编 码两种方法加以实现；在o u t o f - c o r e 数据调度部分中主要完成了外存地形数据进行重组 以及基于多c p u 的数据预取策略；在实时纹理映射部分主要完成了纹理的多分辨率组 织以及预取策略在纹理调度方面的实现。 第一章是本文的绪论部分。主要介绍了大规模地形绘制的应用背景，指出了大规模 地形绘制面临的技术问题以及技术现状，同时也介绍了本文的总体设计方案以及论文的 组织结构。 第二章主要研究了地形几何数据连续l o d 模型的构建方法，首先介绍了构建连续 l o d 模型的整体方法，然后针对其核心算法三角形简化算法，介绍了基于指针的 6 中国民航大学硕士学位论文 三角形简化算法以及基于编码的三角形简化算法，最后是本文的视域裁剪方法。 第三章主要研究大规模地形的o u t o f - c o r e 数据调度问题，首先介绍了预处理阶段中 对外存中的数据进行重组的方法，然后介绍了本文的数据预取策略。 第四章主要研究了大规模地形的实时纹理映射技术，在这一章里首先介绍了本文的 纹理多分辨率组织方法，然后介绍了数据预取技术在预取纹理数据时的方法。 第五章是本文的总结和展望部分，在这章里首先总结了前面各章节中的工作，然后 说明了本文的不足之处以及今后的工作计划。 7 中国民航大学硕士学位论文 第二章地形连续l o d 模型的构建 当地形模型的数据量远远超过了系统的实时处理能力时，庞大的数据量与计算机有 限的计算能力就形成了尖锐的矛盾，解决这一问题的方法是对地形模型进行多分辨率组 织。即构建其连续l o d 模型， 2 1 节介绍了本文地形连续l o d 模型的构建方法；在接下来的两节中详细介绍了本 章的研究重点：三角形简化算法，这是构建地形连续l o d 模型的核心过程；2 2 节是基 于指针的三角形简化算法，2 3 节是基于编码的三角形简化算法；2 4 节是两种算法的比 较；在2 5 节中介绍了视域裁剪算法；2 6 是实验部分。 2 1 地形连续l o d 模型的构建方法 本文在地形连续l o d 模型的构建大致分为四个主要的过程：首先是对原始地形进 行分块并将每一地形块划分成若干个三角形；其次是将每一地形块内的三角形组织成二 叉树的结构，我们称之为三角形二叉树；再次是选取一定的误差测度确定当前的分辨率 层次；最后是调整分辨率层次变化的具体操作三角形简化算法。 2 1 1 原始地形的分块 在地形连续l o d 模型构建的第一步中我们首先要对原始地形分块并将每一地形块 划分为若干个三角形。 在地形绘制中，一般采用均匀采样的高度场( d i g i t a le l e v a t i o nm o d e l ，简称d e m ) 来表示地形表面，许多标准的文件格式都用正规网格来表示地形表面的高度场，如吉奥 公司的d e m 文件格式、a r c i n f o 公司的b i l 文件格式等。 对于大规模地形，由于其数据量远远超出内存大小，无法一次性载入内存因此一个 自然的想法就是将地形分割成若干个地形块，而每一个地形块再细分成若干个三角形。 利用一组等间隔的水平及垂直分割线，就可以将地形分割成若干个等大小的地形块，在 地形块内将每一个最精细的采样点的矩形区域用对角线分割，就会将地形块分割成了若 干三角形。如图2 1 所示。 8 中国民航大学硕十学位论文 l ： 原始地形分成若干块 每一块地形块细化成若干三角形 图2 - i 地形分块与细化为若干三角形示意图 例如：对于( 锄+ 1 ) ( 知+ 1 ) 大小的超量模型，对网格按照一定粒度( 加+ 1 ) ( 2 m + 1 ) 进行分块，分次调, k p 4 存，整个地形被分为2 k 2 k 个等大小的块，其中七玎一朋，分块 的边界相重叠。 2 1 2 三角形的剖分与合并方法 在将地形块内的三角形组织成三角形二叉树结构之前，我们需要知道三角形剖分与 合并的方法。 按照上述方法得到的地形三角形结构只是最精细分辨率的地形三角形结构，如果我 们要构建地形的l o d 模型，就需要对三角形进行剖分与合并，从而形成多分辨的地形 层次结构。 就三角形的剖分与合并的方法对于规则网格而言，各个文献中基本一致，只是在 方法的具体实现中会有一些差异，将在2 1 6 中介绍。 连接直角三角形的直角顶点和斜边中点将直角三角形分裂成两个小的直角三角形， 我们称之为三角形的剖分，剖分的逆过程，即用父三角形取代两个子三角形时我们称之 为三角形的合并。剖分与合并过程如图2 2 所示： 分裂 2 1 3 地形的三角形表示基础 合并 图2 2 三角形剖分与合并过程 在将地形块内的三角形组织成三角形二叉树结构之前，我们还需要对三角形二叉树 9 中国民航大学硕士学位论文 结构中的术语做一下定义： 有文献对建立的l o d 模型表示成右则三角形二叉树【2 0 1 ，本文的表示法类似于此， 但是添加了更多的概念，定义如下： 直角三角形的左直角边、右直角边与斜边：直角三角形直角所对的边为直角三角形 的斜边，其余两条边为直角三角形的直角边，如果其中一条直角边以直角顶点为轴沿逆 时针方向旋转9 0 度恰好到达另一条直角边的位置，则该直角边称为左直角边，另一条直 角边称为右直角边。 直角三角形的左孩子与右孩子：连线直角三角形的直角顶点与斜边中点，将直角三 角形分成两个小的直角三角形，这两个小的直角三角形称为原三角形的孩子三角形，其 中以左直角边为斜边的孩子三角形称为原直角三角形的左孩子，以右直角边为斜边的孩 子三角形称为原直角三角形的右孩子。 直角三角形的左邻居、右邻居与斜邻居：与直角三角形共用左直角边的三角形称为 该直角三角形的左邻居；与直角三角形共用右直角边的三角形称为该直角三角形的右邻 居；与直角三角形共用斜边的三角形称为该直角三角形的底邻居。 2 1 4 三角形二叉树的构建 这是本文构建地形几何数据连续l o d 模型的第二步，将地形块内的三角形组织成 一种二叉树结构，即三角形二叉树。 在三角形二叉树构建方面，不同文献按照不同表示法或按照不同的填充序列构建自 己的二叉树结构；如按照自顶向下对三角形进行排序 2 1 ，三角形编号按照s i c r p i n s k i 填充 曲线进行排列；或者采用了h i l b c r t 曲线构建二叉树结构【2 1 1 ，并按照其曲线顺序对二叉 树结点排列，本文基于2 1 2 节的定义并为辅助后面的简化算法按照如下的方式构建三 角形二叉树： 本文构建三角形二叉树的方法是：首先把地形块的四个角点组成的正方形作为二叉 树的根结点，然后连接正方形的对角线将正方形分成两个直角三角形，构成二叉树根结 点的两个左右孩子结点，继续连接每一个直角三角形的直角顶点和斜边中点将直角三角 形分裂成两个小的直角三角形，我们将这两个小的直角三角形作为原直角三角形的两个 左右孩子结点，如此不断分裂直到分裂到地形最精细的采样点就可以将一个地形块组建 成一个二叉树结构，二叉树结点的编号按照层次遍历的顺序，这样二叉树的根结点构成 地形的最粗糙分辨率描述，而二叉树的叶结点则构成地形块的最精细分辨率描述。这一 过程如图2 3 所示： 1 0 中国民航大学硕士学位论文 2 1 5 误差测度 冈滕震 图2 - 3 三角形二叉树的构建 本文构建地形几何数据连续l o d 模型的第三步是选取一定的误差测度以便动态调 整三角形二叉树结构。 在地形连续l o d 的构建过程中，误差测度是一个评定标准，其误差值决定了在当 前误差下三角形要进行剖分还是进行合并。本文在误差测度方面采用物体空间的简化误 差以及屏幕空间的简化误差作为误差测度标准f 2 2 1 ，但是采取了不同的误差测度方法。 物体空间的简化误差：在数字地形模型中，用简化网格和原始网格在垂直方向的高 度差来衡量物体空间的简化误差。对于本文的三角形模型，取直角三角形斜边中点计算 高度与其在原始网格中理论高度的差值作为该三角形的物体空间简化误差。公式如2 - 1 。 = d 一 ( 2 1 ) 其中z m 甜表示直角三角形斜边中点的计算高度值，z 。神表示直角三角形斜边中点在 原始网格中的理论高度值。 屏幕空间的简化误差：在数字地形模型中，用视点e 到顶点i 的距离来衡量屏幕空 间的简化误差。对于本文的三角模型，取直角三角形斜边中点与视点的三维空间上的距 离作为该三角形的屏幕空间的简化误差。公式如2 2 所示。 d = o 。i d 一) 2 + ( y 。耐一y 。，) 2 + ( 乙甜一z v i e w ) 2 ( 2 - 2 ) 其中( x 。耐，y 。耐，乙耐) 为三角形斜边中点的三维坐标，o 订。，y 咖，z v i e 。) 为视点的三维坐 1 1 中国民航大学硕士学位论文 标。 本文在地形连续l o d 模型的构建中综合准则一与准则二， 准则计算公式为公式2 3 。 | k n d 得出本文三角形的剖分 其中，厅为三角形的物体空间误差，d 为三角形的屏幕空间误差， 对于某一三角形来说有如下的剖分准n - s 1 辛对三角形进行剖分 己劬潮) 表示p 的左孩子结点的编码，c o d e ( p - r c h 泌) 表示= p 的右孩子结点的编码，c o d e ( p ) 表示p 结点的编码，则有如下关系： c 麓。答二篇r c h 浆洲c o d e ( 砷p ) 竺1 ： 如俾一谢) 一 p a r e n t ) 表示p 结点的父亲结点的编 码，则有如下关系： c o d e ( p 一 p a r e n t ) 一c o d e ( p ) 1 ( 2 - 6 ) 规则三：如果一个结点是其父结点的左孩子结点，则分为两种情况：如果其父结点 的右孩予结点的左孩子结点的编码在m a p 结构中存在，则该结点的左邻居结点的编码即 1 9 中国民航大学硕士学位论文 为其父结点的右孩子结点的左孩子结点的编码，否则为其父结点的右孩子结点的编码： 如果一个结点是其父结点的右孩子结点，也分为两种情况：如果其父结点底邻居结点的 左孩子结点的左孩子结点的编码在m a p 结构中存在，则该结点的左邻居结点的编码即为 其父结点底邻居结点的左孩子结点的左孩子结点的编码，否则为其父结点底邻居结点的 左孩子结点的编码。 我们用c o d e ( p 一 l n e i ) 表示p 结点的左邻居结点的编码， 用 c o d e ( p 一 p a r e n t 一 r c h i l d 一 l c h i l d ) 表示p 结点父结点的右孩子结点的左孩子结点 编码，用c o d e ( p 一 p a r e n t 一 r c h i l d ) 表示尸结点父结点的右孩子结点编码，用 c o d e ( p 一 p a r e n t 一 p b a s e 一 l c h i m 一 l c h i l d ) 表示p 结点父结点底邻居结点的左孩 子结点的左孩子结点的编码，用c o d e ( p 一 p a r e n t 一 p b a s e 一 l c h i m ) 表示p 结点父结 点底邻居结点的左孩子结点的编码，则有如下关系： 如果p 结点是其父结点的左孩子结点，则有 。，。，、f c o d e ( p 一 p a r e n t - r c h i m - l c h i l d ) ，矿( c o d e e m a p ) c 0 比p 一 胤) 2 c o d e f p 一 p 口r e n t - r 饧i l d ) ，出e 、7 i一 p 口 饧) ，出 如果p 结点是其父结点的右孩子结点，则有 (