（地图学与地理信息系统专业论文）基于视点的金字塔实时地形渲染算法的研究.pdf

中国农业大学硕士学位论文 摘要 摘要 3 dg i s 中近些年来一个热点问题就是3 d 地形渲染算法的研究，目前主流的地形渲染算法有 l i n s t o r m 9 6 、l i n d s t o r m 2 0 0 1 、r o a m 、p m ，但这些算法都是通过c p u 计算，用最优化的三角形 来表达地形，逐点计算l o d 。实现这样的算法必须达到豫个条件，足够大的内存和足够快的c p u 。 如果地形数据量很大，内存不足以装载这些数据，而c p u 的处理速度又不能在足够短的时间内 处理完所有这些数据，那么这些算法就不再适用。 本文主要提出了一种大数据量地形渲染算法，该算法相对简单，是一个基于静态的l o d 很 有效的地形渲染技术。与其它的更复杂的算法则相反，目的不是获得最优化的三角形，而是尽量 通过增加三角形吞吐，来减少c p u 使用率。当然，l o d 还是需要的，但是要在一个非常粗泛的 水平上。本文的做法就是，依赖视点相关的l o d ，但不是对每个顶点去做，而是对于比较大的 块几何体。首先通过对l i n d s t o r m 9 6 、l i n d s t o r m 2 0 0 1 、r o a m ，c h u n kl o d 等地形渲染算法的进 行深度剖析，然后利用了c h u n kl o d 地形分块渲染思想，把l i n d s t o r m 9 6 的思想融合到c h u n k l o d 算法之中，但是由于c h u n k l o d 裂缝处理有缺陷，本文摒弃了其裂缝处理的方法，提出了 一种新的处理裂缝的方法。最终本算法实现了海量地形数据的实时渲染。 关键词：地形，金字塔，渲染，3 dg i s 中国农业大学硕士学位论文a b s t r a c t a b s t r a c t 3 dt e r r a i nr e n d e r i n ga l g o r i t h mi so n eo fh o t t e s tp o p u l a rp r o b l e m si n3 dg i sa r e ar e c e n ty e a r s t h e r e r es o m em a i na l g o r i t h m sl i k el i n s t o r m 9 6 、l i n d s t o r m 2 0 0 1 、r o a m 、p me r e b u ta l lo f t h e ma r e c a l c u l a t i n gv i ac p u ，u s i n go p t i m u mt d a a g l e s ，p h a s i n ge a c hp o i n tt oc a l c u l a t el o d i no r d e rt o i m p l e m e n tt h e s ek i n d so fa l g o r i t h m sw eh a v et oh a v ea d v a n c e dm e m o r ya n dc p uw h i c ha r eh u g ea n d f a s t e n o u g h ) o t h e r w i s e ，i fm e m o r yc a l l th o l da l lt h ed a t ao rc p uc a n tf i n i s hc o m p u t i n gf a s te n o u g h ， t h e s ea l g o r i t h m sw i l lf a c es e r i o u sp r o b l e m t h i sa r t i c l ew i l li n t r o d u c ea l la l g o r i t h mt od e a lw i t hm a s sd a t a r e l a t i v et oo t h e ra l g o r i t h m s ，o u r m e t h o di ss i m p l e i ti sav e r ye f f e c t i v et e r r a i nr e n d e r i n ga l g o r i t h mb a s e d0 ns t a t i cl e d o nt h ec o n t r a r y t ot h eo t h e rc o m p l i c a t e da l g o r i t h m s t h i sm e t h o dd o e s n tt a r g e ta to p t i m u mt r i a n g l e s i tt r i e st or e d u c e c p uu s a g eb ya d d i n gf r e q u e n c yo ft r i a n g l e si na n do u t o fc o u r s e ，w es t i l ln e e dl e d ，b u ti nav e r y r o u g hl e v e l t h i sm e t h o di s ，d e p e n d i n go nv i s i o nr e l a t o dl o d ，n o tf o c u so ne a c hv e r t e x ，b u tf o rb i g g e r g e o m e t r i c a lo b j e c t t oa p p l yt h i sa l g o r i t h m ，w ef i r s ti n v e s t i g a t eo t h e rt e r r a i nr e n d e r i n ga l g o r i t h m s d e e p ly ，s u c ha sl i n d s t o r m 9 6 ，l i n d s t o r m 2 0 0 l ，r o a m ，c h u n kl e de r e t h e nw e u t i l i z e dc h u n kl o d a n di n t e g r a t el i n d s t o r m 9 6i n t oc h u n kl o d b u tc h u n kl e dd o e s n tm a n a g ec r a c k i n gw e l ls ow e d i s c a r d e dc h u n kl o d sc r a c k i n ga n dp u tf o r w a r dan e wm e t h o dt od e a lw i t hc r a c k i n g t h r o u g ha l lt h i s ， f i n a l l yw ei m p l e m e n t e dt h i sn e wa l g o r i t h mt om a n a g em a s sd a t at e r r a i nr e n d e r i n ge f f i c i e n t l ya n de a s i l y k e yw o r d ：t e r r a i n ，p y r a m i d ，r e n d e r ，3 d g i s i i v9 3 8 2 6 7 独创性声明 本人声明所呈交的论文是我个人在导师指导卞进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得中国农业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名时问：沙占 关于论文使用授权的说明 年1 只l r 日 本人完全了解中国农业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。同意中国农业大学可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名：? m 导师签名： 帆伊6 年 日 好 时间：z o - 考- ( m ；l x 这些块彼 此相互重叠一行和一列。也就是说每个块的边与它相邻块的边共享。首先把块按2 * 2 分组然后 除去一些行和列，组成一个新的大块。这个新的大块在面积上与组成它的四个子块面积上相等， 但由于大概有3 1 4 的点被去掉了，所以分辨率较低。这种处理一直这样递归下去，最后只有一个块。 最后的这个块包含完整的地形，但分辨率非常低。这些块阻四叉树的结构组织最低分辨率在树 的根节点，分辨率最高的块为处于叶子上的结点1 6 j 。 粗略化一 ，、 h 、， 精细化 图2 - 34 个3 * 3 的块合并成一个新的块，白色的点被删除，形成一个分辨率较低的块。 2 2 2 基于点的精细简化 精细的简化基于斜边的二分，二分一个等边直角三角形，只要从斜边的中点到顶点添加一条 直线，形成两个小的等边直角三角形。但是，在这个算法里，斜边二分的过程是逆行的，在斜边 的中点被去掉，两个小三角形合并成一个大的三角形。在小三角形a e d 。d e b 和三角形b f d ，d f c 合并之前，三角形a d b 和三角形b d c 不能合并。所有的三角形都有层次关系，在子的三角形合并 之前，当前三角形是不能合并的。 5 2 2 3 l o d 选择 g 图2 - 4 三角形合并示意图 c 一个顶点是否从层次结构中移出，主要决定于移出这个点后，地形渲染到屏幕上的误差有多 大。这个在屏幕上造成的误差与设定的误差极值比较，如果误差比极值大，这个点就不能被移出。 几何误差的计算，就是顶点到新三角形斜边的距离。可以图2 5 ： 图2 5 顶点b 和b 点的误差6 b 之问的关系 决定一个点是否耍移除，不是依靠它的几何误差有多大，而是它的屏幕误差。屏幕误差则 是几何误差投影到屏幕上后的误差。l o d 块的粗略选择是先查找最大的误差值，然后决定是否需 要一个更低的分辨率块。当l o d 算法执行后，两个相邻的块可能分辨率不同，这样就会在共享边 的地方出现裂缝，如下图，( a ，a ) ，( b ，”和( c ，c ) 共享相同的点。但我们不能确保顶点d 位于a b 边上， 也不能保证e 在b c 上。 6 中国农业大学硕士学位论文 第二章当前地形渲染算法介绍 c ， ，。 圈2 - 6l i n d s t o r m 9 6 中的裂缝问题 l i n d s t o r m 在块与块之间建立顶点依赖来解决裂缝问题。 。圈。豳 豳鬻蒸 善蕤k 糕 八 冷 = 1 ) 。如果我们的地形数据不满足( 2 n + 1 ) + ( 2 n + d 这样的大小，我们可以把我们的数据 切分成若干块这样大小的数据。 我们在预处理地形时，主要有两步，数据的分块处理以及块内的l o d 数据的生成。 3 3 1 数据的分层与分块 分块处理比较简单，主要按照四叉树的层次来分，如图3 - 5 。 图3 - 5 四叉树分层示意图 本算法将数据首先分成很多层，每层的地形范围都一样大，只是精度不同。接着把每层的数 据按四叉树结构分成块，在这个过程中只需要知道我们需要的细节层数l 。分块的原则主要采 f f l l i n d s f o r m 9 6 的思想“i 。如图3 6 所示： 2 l 三量邕型型曼墅生兰燮奎第三章基于视点的金字塔实时地形渲染算法 粗喀化 一一、q 、一一 精细化 图3 6 分块示意图左边是高分辨率右边的图是减去白色点的低分辨率圈 3 3 2l o d 数据的生成 在l o d 算法中，主要采用l i n d s t o r m 9 6 的算法的思想，使用等腰直角三角形的斜边二分。但 我们是在渲染前对每个块进行l o d 处理。而不是在渲染时进行l o d 处理。我们在渲染之前把不同 分辨率的l o d 都计算好。 首先要确定一个最大几何误差值6 ，这个值也就是我们看最清晰的画面时所能接受的误筹。 如果一个地形我们分为1 0 层，也就是说在第9 层时分辨率最高，画面最清晰，这个时候的几何误 差不超过6 ，如果是上一级，也就是第8 层，那么它的几何误差不超过26 第7 层几何误差不超 过46 依此类推。 皿+ 1 ) = 8 m 心( 3 - 2 ) 在计算每个点的误差时，我们采用的是l i n d s t o r m 9 6 的思想，也就是使用斜边二分的思想，但 在实现中，我们总是想把我们的表面映射到一个正方形上，而不是一个三角形。很直观，可以通 过把2 个三角形的斜边放一起构成一个正方形，也可以把4 个三角形直角边放一起，形成正方形。 我们选择后一种，现在，这样生成的矩形可以被递归的细分到任意可能的深度。然后递归计算每 个三角形斜边的误差，实际上也就是每个点的误差。除了三个顶点。 其实我们在计算时，并不存储屏幕误差值，而存储的是哪个层可以接受这种误差；所以我们 存储的是每个点能接受的层数。这样做的一个好处就是能节省一定的内存。因为误差的范围很大， 而层数是有限的，也就是说层数的值的大小不会很大。所以我们只需要很少的字节用来存储层数。 计算层的公式为： l e v e l = f l o o r ( 1 l 0 9 2 ( 64 - 0 5 ) i )( 3 3 ) 公式3 3 中6 为屏幕误差，我们对每个点做完误差处理后，我们根据点的误差来确定块状的误 差。我们取最大点的误差为点所在块的误差。 例如，我们针对一个2 0 4 9 * 2 0 4 9 的地形，我们切分成8 层，我们在程序中就是0 至7 层。给定一 个接受的j l 何误差1 ，也就是说我们在分辨率最大的层( 第0 层) 接受的误差不超过1 个单位。那么上 2 2 主垦查些查兰硕兰三兰| 苎堡垒兰 第三章基于视点的金字塔实时地形渲染算法 一级( 第l 层) 的误差不超过2 个单位。我们计算出每点的误差，如果这个误差值为1 0 ，我们可以 得知这个点可以在第4 层( 接受小于1 6 误差) 的被忽略，因为第3 层可以忽略小于8 个单位误差。换 句话说，如果误差为1 0 ，也就是说可以被第4 第5 ，第6 ，第7 层忽略，这样，我们可以把所有的 点能接受层数计算出来。我们计算出每个点的误差后，因为我们最后渲染是在块的基础上完成的。 所以我们必须把每个块能接受的层计算出来然后把这个值赋给中心点也就是中心点能接受的 层数。 几何数据的生成，主要是通过递归来完成，从项节点递归到叶子节点。对于每个节点我们 主要分为块数据的处理和与这个块相关的四条边的数据的处理。 块数据的生成：首先生成第7 层的数据，因为第7 层是最顶层。首先写入一些头数据，块文件 的数据结构为 s t r u c th e a d i n tc h u n k i n d e x ；块的索引 i n te a s t i n d e x ，n o r t h i n d e x ，w e s t i n d e x ，s o u t h i n d e x ；四个子节点的索引 u n s i g n e dc h a rl o dl e v e l ；所在的层数 s h o r tx i n d e x 。z i n d e x ； 块在该层中的位置 s h o r tm i nv ，m a x _ y ； 该块的最小高程以及蛙大高程 i n tm e s hp o s ； 三角网数据的位置 头文件写完后，我们开始生成几何数据，为方便裂缝的处理裂缝，我们在生成几何数据时， 依然采用的是四叉树递归然后根据每个点能接受的层数。我们生成静态几何三角形数据。 我们将把网格数据写到指定位置。然后把三角形条带的点依次写入磁盘，便于显卡顶点数组 扩展的使用；头文件实际相当于一个索引，目的是为了提高访问顶点速度。 我们在选择图形库时，选择的是o p e n g l ，o p e n g l 和d i r e c t 3 d h ：较起来，最大的个长处就 是其扩展机制。硬件厂商开发出一个新功能，可以针对新功能开发o p e i 1 g l 扩展，软件开发人员 通过这个扩展就可以使用新的硬件功能。所以虽然显卡的发展速度比o p e n g l 版本更新速度快得 多，但程序员仍然可以通过o p e n g l 使用最新的硬件功能。而d i r e c t 3 d m j 没有扩展机制，硬件的新 功能要等到微软发布新版d j r e c t x 后才可能支持。 预处理数据的文件数据结构 字节数 数据类型 说明 文件头 4b y t e sc h a t”几c 0 ” 2b y t e s s h o r t 文件版本号 4b y t e sf l o a t 分辨率最高时能接受的误差 4b y t e s f l o a t 顶点的扩大倍数 4b y t e s i n t 最小分辨率时的几何级数 4b y t e s i n t 数据块的数目 每块的头 4b y t e s i n t 当前块的索引 4 b y t e si n t 右方向子块的索引 4b y t e s i n t 下方向子块的索引 4b y t e si n t 左方向子块的索引 4b y t e si n t 上方向子块的索引 1b y t e u n s i g n e dc h a r该块所在的层数 2 b y t e ss h o f t 该块的x 坐标 2 b y t e ss h o r t 该块的y 坐标 2b y t e s s h o n 最小的高程值 2b y t e ss h o r t 最大的高程值 4b y t e sj n t 网格的地址 2b y t e s u n s i g n e ds h o r i 顶点的数目 顶点信息 2b y t e ss h o r tx 2b y t e ss h o r ty 2b y t e ss h o r tz 2b y t e ss h o r t 忽略该点时的误差。 4 b y t e s i n t 顶点索引数目 2 b y t e ss h o r t顶点索引 4b y t e si n t 三角形的数目 纹理数据我们主要模仿m i p m 印p i n g 的方法t 与m i p m a p p i n g 不同的是，我们是在磁盘上存储这 些不同分辨率的纹理块，而m i p m a p p n g 是在程序运行时在内存中存储不同分辨率的块。 3 4 裂缝 与块相关的边数据的生成。处理块的边的目的就是为了裂缝的处理。一般的l o d 算法都会出 现裂缝问题，图3 7 是没经过处理的裂缝。 中国农业大学硕士学位论文 第三章基于视点的金- 7 塔实时地形渲染算法 圈3 7 椭圆处出现裂缝 裂缝，也称之为t 连接，p 连接是指一个三角形或多个三角形共享另一个三角形一条边上的 一部分，也就是相邻地形块的分辨率不一致时，在它们的边界交界处会出现裂缝上图椭圆形里 的就是一个t _ 连接。一个好的地形算法，是需要消除t - 连接的。一般消除裂缝的方法主要有以f 几种处理方法。 3 4 1 裂缝处理方法一 第一种方法我们可以在不同分辨率的关键点处加线，如图3 8 。 圈3 - 8 椭圆处的块加了很多细线 中国农业大学硕士学位论文 第三章基于视点的金字塔实时地形渲染算法 这样相邻的网格可以相差任意级精度。如图3 - 9 椭圆体内的正方形。 貊曝除吨 l g 湫x | ) l 6琵l 受 泛d z _ 沫盔溅h | ) ( i x ；黼孤 歹 黼猢鼹 w x 一 嚣翼礤雾| i ) 蚓强x k p 钰g 受p 藁 n 歹 阱 兴 絮盼e 驳 溪集箔圈黝 x 躅3 - 9 椭圆处表示分辨率相差的分辨率可以任意级 这种方法实现起来非常简单，但是在块与块的边界处由于分辨率过离，会产生很多不必要的 细小的三角形，限制了绘制速度。 3 4 1 裂缝处理方法二 第二种方法，就是在地形块的周围加上一圈垂直的“裙边”，如图3 1 0 所示，以消除裂缝。 图3 1 0 左图表示两种分辨率之间出现的裂缝，右图表示添加裙边裂缝消除了 c h u n kl o d 使用了一项被称为裙子( s k i r t i n g ) 的技术。s k i n i n g 基本的意思是，在m e s h 的边缘， 有一些额外的向下延展的三角形，这些三角形可以有效的隐藏裂缝。然而，就算这样t 必须小心 中国农业大学硕士学位论文第三章基于视点的垒字塔实时地形渲染算法 图3 11 加裙边时的渲染效果图 的选择裙子的长度，因为长的裙子将会降低填充率。如图3 - 1 1 所示。 上图表示的是可以看到块与块之问靠裙边来实现处理裂缝的效果。实际上靠裙边来解决裂 缝，并不是真正的解决裂缝。因为如果裙子的长度选择不合适依然会有裂缝出现，还有就是如 果裂缝过大，用裙边会看见明显的“台阶”。所以依赖裙边解决裂缝不是一种理想的解决方法。 3 4 3 裂缝处理方法三 这里本文提出一种新的处理裂缝的方法。 由于只要三角形的数量能在显卡接受的范围内，我们可以靠多输出一些三角形来解决裂缝。 看图3 1 2 ： 图3 1 2 处理裂缝效果图 中国农业大学硕士学位论文 第三章基于视点的金字塔实时地形渲染算法 我们使用不同分辨率的共享边上的所有点都保留，不被移除，这样处理起来非常简单。不需 要复杂的运算，缺点就是块与块的边界处分辨率偏高，使显卡负担有所增大。但只要三角形的数 量在显卡接受的合理范围内，就整个算法来说，对帧率影响很小。 3 5s d l 与l o d 数据结构 3 5 1s d l 简介 为了使场景的渲染能脱离操作系统平台本身的限制，我们采用了跨平台的s d l 多媒体库。s d l ( s i m p l ed i r e c t m e d i a l a y e r ) 是一个跨平台的多媒体支持库。其中包含了对图形、声音、游戏杆、 线程等等的支持，目前可以运行在许多平台上，其中包括xw i n d o w 、xw i n d o ww i md g a 、l i n u x f r a m e b u f f e r 控制台、l i n u xs v g a l i b ，以及w i n d o w sd i r e e t x 、b e o s 等等。 因为s d l 专门为游戏和多媒体应用而设计开发，所以它对图形的支持非常优秀，尤其是高 级图形能力，比如a 1 p h a 混和、透明处理、y u v 覆盖、g a m m a 校正等等。而且在s d l 环境 中能够非常方便地加载支持o p e n g l 的m e s a 库，从而提供对二维和三维图形的支持。使用s d l 的好处就是可以使我们的程序很方便的移植到其它平台上。所以在这里我们不使用传统的 w i n d o w sa p t ，而是采用s d l 平台。 3 5 2l o d 的数据结构 首先我们需要合理的数据结构。渲染地形，我们不可能把整个网格文件加入内存，因为数据 文件本身就很大。我们可以把网格文件的头文件载入内存( 也就是索引文件) 因为头文件几乎 包含了除数据本身以外的所有信息，包括各个数据块的关系，以及数据在磁盘的实际位置，便于 后台线程高效定位读取几何数据和纹理数据。 下面是处理索引的类结构。 c l a s s j l c _ l o d _ t r e e p u b l i c ： j l c _ l o d _ t r e e ( s d l _ r w o p s + s r c ，c o n s tt q t + t e x t u r e _ q u a d t r e e ) ； - - j l cl o d _ t r e e o ； v o i ds e t _ p a r a m e t e r s ( f l o a tm a xp i x e l e n o r , f l o a tm a x _ t e x e l s i z e ，f l o a ts c r e e n _ w i d t h ，f l o a t h o r i z o n t a l _ f o v _ d e g r e e s ) ；，设置一些扔始化参数 v o i du p d a t e ( c o n s tv e c 3 & v i e w p o i n o ；当试点移动时，更新数据。 i n t r e n d e r ( c o n s t v i e w _ s t a t e & v r e n d e r o p t i o n so p 0 ；膻染出结点 v o i dg e t _ b o u n d i n g _ b o x ( v e t 3 * b o x _ c e n t e r , v e c 3 * b o x _ e x t e n 0 ；艉取包围盒的大小，以及中心 点。 u i n t l 6 c o m p u t e ，i o d ( c o n s t v e c 3c e n t e rc o n s tv e t 3 & e x t e n tc o n s tv e c 3 & v i e w p o i n t ) c o n s t ； ， 十算几何l o d 获取要提取的数据 i n t c o m p u t e ，)_texture l o d ( e o n s tv e c 3 & c e n t e rc o n s tv e c 3 & e x t e n tc o n s tv e c 3 & v i e w p o i n tc o n s t ； ，计算纹理l o d 定位纹理的位置。 v o i ds e t u s e - j o a d e r _ f l u v , a d ( b o o lu s e ) ；i 蹬置线程是否该启动 数据： l o d _ c h u n k *r e _ c h u n k s ；，磁盘上的数据 i n tmc h u n k sa l l o e a t e a ；数据块的块数 i n tmt r e e _ _ d e p m ；块数据 f l o a t m e r r o r l o d m a x ；f l 从数据文件中 f l o a t m _ d i s t a n c e _ l o d m a x ；，最大l o d e 离 f l o a tm _ t e x t u r e _ d i s t a n c e l o d m a x ； f l o a t m _ v e r t i c a l _ s c a w ； f l o a t mb a s ec h u n kd i m e n s i o n ； i n tmc h u n k _ c o u n t ； i o d _ c h u n k m _ c h u n k _ t a b t e ； c o n s tt q t + m _ t e x t u r e _ q u a d t r e e ； c h u n kt r e ei o a d e r * ml o a d e r ；，线程指针。 ； 图3 1 3 程序运行的金字塔块，颜色越红，表示细节越高，颜色越绿，表示分辨率低。 3 6 数据的渲染 当我们拥有了预处理的几何地形数据以及纹理数据后，我们剩下的工作就是如伺调度这些数 据，实时渲染出地形场景。 3 6 1 利用显卡扩展渲染 在3 d 图形应用程序中所有的模型都是几何圈元来表达，而几何图元最终都是以顶点的形式描 述，因此顶点数据的处理效率直接影响到图形渲染速度。g ln vv e r t e xr a n g e 和 g l n v f e n c e 这两个扩展的目的就是通过利用o p e n g l 顶点数组来获得极高的顶点处理速率， 甚至是在c p u 缺乏必须的数据传输宽带来维持顶点引擎处理顶点的速率。按照一般的原理，如果 只是传输顶点数据的索引到图像硬件，同时通过直接内存访问( d i r e c t e dm e m o r y a c c e s s ，d m a ) 方 式让硬件自己访问实际的定点数据，c p u 就能够维持较高的顶点处理速率，但当前的o p e n g l 顶 点数组功能存在语义上的限制使得这种方法的实现存在很困难。因为对于o p e n g l 从顶点数组 中抽取顶点数据和应用程序更新内存中顶点数组数据，o p e n g l 定义的顶点数组功能规定了一个 相当严格的一致性模型。 o p e n g l 规定：在b e g i n 和e n d 执行中对顶点数组数据的改变将会影响到对在同一个 b e g i n e n d 代码段按照非连续方式执行的函数a r r a y e l e m e m 的调用。即一个在顶点数据变化前的 a r r a y e l e m e n t 用实际将会存取到变化了的数据，而一个顶点数据变化后的a r r a y e l e m e n t 调用则会存 取到最初的原始数据。当e n d 回( 包括d r a w a r r a y s 和d r a w e l e m e n t s 调用的隐式返回) 之前，实际的顶 点数据必须完全传递给o p e n g l 。这个严格的一致性模型使我们不能简单地传递顶点元素的索引 给硬件，让硬件获取顶点数据。显然。解除一致性模型的制约和界定顶点数组数据绘制的范围是 快速、高效传输o p e n g l 顶点数组的关键所在。因此，n v j e r t e x 是为了解除一致性模型的限制，它提供了一个机制来延迟顶点数组元素的绘制，允许g p u 通过直 接内存访问获取顶点数据，实现快速、高效的顶点数组传输。o p e n g l 的客户端仅需要传递顶点 索引到硬件，而硬件可以在客户端的地址空间外通过内存直接访问方式直接存取索引指向的实际 顶点数据，以便硬件在应用程序完成需要顶点数据的几何图元的传送后，能真正地从客户端地址 空间中绘出顶点数据”“。 o p e n g l 顶点数组功能的第二个问题是无法从a p i 喇 什么内存区域的顶点可以被访问，且 o p e n g l 的顶点数组大小没有限制，任意指向有效顶点数据的顶点索引都是一致的。这就使得顶 点内存直接访问引擎绘制数据很难因为它们潜在地可以从o p e n g l 客户端地址空间的任何地方 进行绘制。而n v - v e r t e x - a r r a y - r a n g e , f f 展指定了顶点可被绘制的o p e n g l 客户端地址空间的范围。 在顶点数组范围外访问任何数组元素的顶点索引都被视为未定义的。这就允许硬件在限定的 o p e n g l 客户端地址空间范围内进行内存直接访问，也使得内存直接访问引擎的执行可以被追踪。 g ln vv e l t e x a r r a y 具有真正加速顶点数据的能力但是它的内存是有限的，且没有提供一 个高效的方法重用内_ 存r a n 。g e 而通常g p u 的读和c p u 的写都是同一块内存，这就必须有一个同步机制 来保证g p u 在内存被熏写之前完成数据的读取。当前o p e n g l 的同步手段非常薄弱：g l f l u s h 只是l 止 命令在一个有限的时间单元内执行，但不能保证立即执行，同步性很弱；而g l f i n i s h 延迟c p u 的执 行直到所有等待执行的g l 命令执行完毕，它是一种强制而笨拙的方法。与之相比，g l - n v - f e n c e 扩展提供了一个粒度更为精细的g l 命令同步执行机制。它能够执行命令流中的一个子集，可以确 定一个命令是否己经执行完毕。它i a t f e n c e 的概念至1 o p e n g l 命令流中。一旦一个f e n c e 插入 到命令流中，它就可以对给定的条件( 一般是它的执行条件) 进行查询。而且应用程序也可以请求 部分的执行( f i n i s h ) ，这样，在f e n c c 前面的所有命令将会被强制执行直到控制被返回到调用过程。 中国农业大学硕士学位论文 第三章基于视点的金字塔实时地形渲染算法 这种新的机制允许在宿主c p u 和g p u 之间的同步，它们可以访问同一资源( 如内存) 。与n vv e r t e x a r m y _ r a n g e 扩展的联合使用可以决定什么时闻己从顶点数组中获取顶点信息一旦一个f e n c e 测试 为t u r e 或者完毕，在f e n c e 前面的所有顶点索引取出保证了与之对应的顶点数据内存可以被安全地 修改【1 6 】。 3 6 2 视锥裁减系统 l o d 算法是基于视点的，因为在距离视点远的地方选择分辨率低的数据距离视点近的地方 我们选择分辨率高的数据。当然，我们首先耍获取视点的位置，以及方向，然后根据视点来计算 出视点的可视范围，视野范围外的场景我们可以忽略，不需要考虑。我们仅仅考虑视野范围内的 场景。 如图3 - 1 4 ，照相机相当于人眼，人的眼睛在看东西时，必须有一个何时的范围，物体离入眼 太近或者太远。都看不清楚，所以人眼可见范围是在近距离平面和远距离平面之间构成的视锥内。 囤3 1 4 透视投影视锥躅 那我们如何判断哪些点在我们的视锥里呢，理解平面方程a x + b y + c z + d = o 向量( 曲，c ) 为平面 法向量，也是平面的正方向。将点的三维坐标代入平面坐标方程，可以判断这个点在面里+ 还是 在面的正方向或者负方向上。所以我们很容易判断一个点是在我们的视锥内还是在视锥外( 只要 将这个点带入构成视锥的六个平面方程) 。 jk 法蝮 7 正面 r l霄面 图3 1 5 平面与法向量 3 l 中国农业大学硕士学位论文第三章基于视点的金字塔实时地形渲染算法 当然，我们不可能测试每个点，这样会非常消耗时间，我们可以把每个块里的点用一个包络 立方体包围起来，也就是我们寻找一个大的立方体，把每块的点都包含在这个立方体里，这样我 们只需要判断这个立方体里的几何数据是否需要渲染。这样可能会出现三种情况，包围体在视锥 内，包围体与视锥相交，视锥在包围体外( 如图3 1 6 ) 。我们只需要渲染与视锥相交的和在视锥 体内的包围体的几何数据。这样我们在渲染块时，我们就不需要考虑在视锥体外的块了。我们根 据块到视点的距离来决定调取哪些块。 3 , 6 3 请求队列与缓存队列 圈3 1 6 视锥裁减 渲染时，把需要读取的块放入队列( 请求队列) ，把上一帧的块放入另外一个队列( 缓存队 列) 。 我们在读取块时，我们把需要读取的块的放入请求队列，这里我们只要放入块的索引即可， 这样后台线程很容易在磁盘上定位到顶点数据。当然，我们再获取新的一帧前，我们不能把上一 帧数据完全释放，因为一般情况下，我们很多时候都是在一个场景周边漫游，这样，我们就不必 重复从磁盘上读取数据，而只要读取缓存中的数据即可。所以我们需要建立一个缓存队列专门 用来存取刚刚用过的一些数据，来起一个缓存的作用。 后台线程从请求队列中获取要渲染得数据块，知道要读取的块后，首先从缓存队列中查找是 否有需要请求的块，如果有，则直接重复利用。如果没有，则从磁盘上读取。我们对纹理的处理 跟几何数据非常类似。 3 7 小结 本算法主要是针对大场景设计。可能在细节处理上不及一些优秀的算法，但在处理大数据量 的地形方面，却能很流畅的运行。主要在于我们提前已经把l o d 网格已经完成。在运行时后台 线程只需要根据索引寻找所需要调用的金字塔哪个层的哪些块。在测试中我们使用1 g 的几何 数据和纹理数据作为测试，帧率达到3 3 f p s 。一般达到3 0 帧左右，画面就非常流畅。 中国农业大学硕士学位论文 第四章结论与讨论 4 1 结论 第四章结论与讨论 本文主要提出了一种基于在金字塔切分的3 d 地形渲染算法借用了c h u n kl o d 地形分块渲 染思想，把l i n d s t o r m 9 6 的思想融合到c h u n kl o d 算法之中，但是由于c h u n kl o d 裂缝处理有 缺陷，本文摒弃了其裂缝处理的方法，而是用了共享边上的点都保留的方法。最终该算法实现了 海量地形数据的处理。该算法优点如下： l 、低c p u 消耗，甚至当视点移动很快时候。由于该算法没有在运行时构建网格所以在运行 时不需要进行l o d 的计算，我们c p u 只需要不断的检索加载网格数据就可以了。所以c p u 的 消耗非常少。 2 、支持动态磁盘数据读取，以及支持较大地形数据的渲染。由于内存是有限的，我们又要 处理超过内存大小的数据量，所以我们必须建立动态磁盘数据读取机制。 3 、支持g b 级的数据量，使用1 g 左右的几何数据和纹理数据进行测试时，f p s 达到3 0 以 上所以我们实现了大数据量的几何数据处理。 4 、纹理l o d 与几何l o d 是统一的。在一般的地形渲染算法中，纹理都是不会进行处理的， 而在该算法中。由于支持大纹理，所以不可能一次性把纹理加载到内存中，所以纹理必须也要做 相应的切割。 4 2 讨论 该算法的值得探讨的地方： 1 、本算法必须要进行数据的预处理，目的是为了减少实时运算量。该算法实质上增加了廊 用复杂度。有必要强化预处理的自动化程度。 2 、该算法是一个静态l o d 算法，细节的层数有限。容易出现画面的突然跳跃。可进一步在 运行时通过插值等方法减少跳跃感。 综上，该算法是一个能运行大数据量，为了预处理地形数据，预处理之前需要一个层数的值 所以地形的细节不能最大限度的增加或者减少，造成细节处理不是足够的好。在以后的工作中有 待改进。 中国农业大学硕士学位论文 第四章结论与讨论 图4 i7 0 0 md e m 怀柔水库数据3 d 渲染效果 图4 27 0 0 md e m 怀柔承库数据3 d 渲染效果 参考文献 【l 】c a m e r o ne l l u m d a t as t r u c t u r e sf o r3 dg 1 s ，e n g 0 6 6 1p r o j e c tr e p o r t ( m i n o rp r o j e c t ) g d e p a r t m e n to f g e o m a t i c se n g i n e e r i n g ，t h eu n i v e r s i t yo f c a l g a r y , 1 9 9 9 2 】c a m e r o ne l l u m i n t e g r a t i n go b j e c t ，t e r r a i n ，a n dt e x t u r ed a t ai nu r b a n3 dg i s ，e n g 0 6 6 1 p r o j e c tr e p o r t ( m a j o rp r o j e c t ) i r 】d e p a r t m e n to fg e o m a t i c se n g i n e e r i n g ，t h eu n i v e r s i t yo f c a l g a r y , 1 9 9 9 【3 孙敏论三维地理信息系统讲义w w w v g e l a b o r g 【4 张健挺，万庆地理信息系统集成平台框架结构研究遥感学报1 9 9 9 1v o l ( 3 ) 【5 k i n g o a ll e e ”e m l k d d e di m a g ec o d i n g a l g o r i t h m ” 【6 】p e t e rl i n d s t r o m ，d a v i dk o l l e r , w i l l i a mr i b a r s k y , l a i t yfh o d g e s ，n i c kf a u s ta n dg r e g o r ya t u r n e r ”r e a l - t i m e ，c o n t i n u o u sl e v e lo fd e t a i lr e n d e r i n go fh e i g h tf i e l d s ” i n s i g g r a p h9 6c o n f e r e n c ep r o c e e d i n g s ，p p 1 0 9 一1 1 8 ，a u g1 9 9 6 【7 m a r kd u c h a i n e a u ，m u r r a yw o l i n s k i ，d a v i de s i g e t i ，m a r kc m i l l e r , c h a r l e sa l d r i c ha n dm a r kb m i n e e v - w e i n s t e i n ”r o a m i n gt e r r a i n r e a l - t i m e , o p t i m a l l ya d a p t i n gm e s h e s ”p r o c e e d i n g s o f t h ec o n f e f e n c eo nv i s u a l i z a t i o n 9 7 ，p p 8 1 - 8 8 ，o c t1