（计算机应用技术专业论文）三维分形地形的研究与实现.pdf

摘要 地形是自然界中具有复杂特征的景物之一。三维地形的建模和显 示技术，在很多颁域中部有重要意义，同时也是计算机图形学的重要 研究内容。 分形几何学是近年来新兴的一门学科。分形在计算机图形学领域 有着重要应用。其中的分形布朗运动( i b m ，f r a c t a lb r o w n i a nm o t i o n ) ， 为描述地形表面提供了有效的数学模型。以分形布朗运动为基础来构 造地形的相关数据可以较好地体现出地形这一具有复杂特征的自然 景物的特点。 三维分形地形的显示需要涉及到投影变换，消隐处理，光照处 理，色彩合成等计算机图形学的相关知识和技术，选择合适的相关处 理方法。并构成具体的算法来实现，可以使显示出的三维分形地形具 有较好的真实感。 分形布朗运动在三维地形中主要用于生成地形的数字高程模型 ( d e m ，d i g i t a le l e v a t i o nm o d e l ) ，这是三维地形的数据基础。对于 投影变换，消隐处理，光照处理，彩色合成等内容的实现，可以选用 计算机图形学中的一些成熟的技术如z - b u f f e r 技术，p h o n g 光照模型 等。在具体实现过程中，需要将各种技术有效结合，才能得到满意的 效果。同时，还应当采取适当的方法，使所编制的三维分形地形生成 和显示软件具有良好的交互性。 目前，基于分形的三维地形生成与显示技术正处在发展阶段，一 方面，有效实现三维分形地形生成和显示的方法已经存在。另一方面， 原有的方法还有需改进的方面。同时。围绕三维分形地形生成和显示 这一问题，又不断有新的技术出现。 关键词：三维地形，分形，中点位移法，数字高裎模型 a b s t r a c t t e r r a i ni so n eo ft h em o s tc o m p l e xob j e c t si nt h en a t u r e t h e t e c h n i q u e so fg e n e r a t i o na n dv i s u a l i z a t i o nf o rt h r e e d i m e n s i o n a lt e r r a i n a r eb o t hi m p o r t a n tt o o l sf o rm a n yr e a l m sa n di n t e r e s t i n gr e s e a r c hf i e l di n c o m p u t e rg r a p h i c s f m c t a lg e o m e t r yh a sb e e nan e wr e s e a r c hf i e l di nr e c e n ty e a r s t h ef r a c t a l b r o w n i a nm o t i o n ( f b m ) p r o v i d e se f f e c t i v em a t h e m a t i c sm o d e l ，w h i c hh a si m p o r t a n t a p p l i c a t i o ni nc o m p u t e rg r a p h i c s t h ed a t ao ft e r r a i nf e a t u r e so b t a i n e du s i n gf b m m e t h o d sc a l lr e f l e c tc o m p l e xc h a r a c t e ro f t h en a t u r a l v i s u a l i z a t i o no ft h r e e d i m e n s i o n a lf r a c t a lt e r r a i ni n v o l v e sal o to f k n o w l e d g ea n dt e c h n i q u ei nc o m p u t e rg r a p h i c s ，s u c ha ss h a d o wt r a n s f o r m a t i o n ， h i d d e nh a n d l i n g ，i l l u m i n a t i o nh a n d l i n g ，c o l o rs y s t e m i z a t i o ne t c s u i t a b l em e t h o da n d c o n s t i t u t e a l g o r i t h m s f o rt h r e e d i m e n s i o n a lt e r r a i nv i s u a l i z a t i o ni s c r i t i c a l t h e nt h et h r e e d i m e n s i o n a lf r a c t a lt e r r a i nt h a td i s p l a y e dw i l l b eh i g hs c e n eo fr e a l i t y i nt h i s p a p e r ，f r a c t a lb r o w n i a nm o t i o n i su s e dt oe s t a b l i s ht h ed i g i t a l e l e v a t i o nm o d e l ( d e m ) o ft h et h r e e d i m e n s i o n a lf r a c t a lt e r r a i n t h e d i g i t a le l e v a t i o nm o d e l ，i nt u r n ，c o n s i s t s t h ee s s e n t i a ld a t at o c h a r a c t e r i z et h r e e - d i m e n s i o n a lf r a c t a lt e r r a i n i nt h er e n d e r i n gp r o c e s s ， c o m b i n a t i o no fm a t u r et e c h n i q u ei nc o m p u t e rg r a p h i c s ，s u c ha sz b u f f e ra n d p h o n gi l l u m i n a t i o nm o d e l ，c a nb eu s e dt o r e a l i z es h a d o wt r a n s f o r m a t i o n ，h i d d e n h a n d l i n g ，i l l u m i n a t i o nh a n d l i n g a n dc o l o r s y s t e m i z a t i o n t h e s o f t - w a r e f o r t h r e e d i m e n s i o n a lf r a c t a lt e r r a i ns h o u l dh a v eg o o du s e ri n t e r a c t i v e f u n c t i o n p r e s e n t l y t h ef r a c t a lb a s e d v i s u a l i z a t i o nt e c h n i q u ef o rt h r e e - d i m e n s i o n a l t e r r a i ni sd e v e l o p i n g w h i l es o m ep r a c t i c a lm e t h o d sh a v ea l r e a d yb e e nc o n s t r u c t e d ， t h e i re f f i c i e n c ya n du s a b i l i t ys t i l ln e e dt ob ei m p r o v e d keyw o r d s ：t h r e e d i m e n s i o n a lt e r r a i n ，f r a c t a l ，m i d p o i n td e f l e c t i o n a l g o r i t h m ，d i g i t a le l e v a t i o nm o d e l 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：釜塞笠细衅年f 月2 ；日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 。锋一 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交燕授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签冬：盟 勘口争年月鸟目 硕士论文三维分形地形的研究与实现 1 引言 1 1 课题的意义和目的 真实感图形1 2 】的生成算法一直是计算机图形学的重要内容，而在 真实感图形显示中，自然景物的模拟又是最具挑战性的课题之一，因为 自然景物不仅形状千姿百态，而且很多是实时变化的，其算法十分繁琐 复杂，很难用一种常规的方法来描述。因此，自然景物的建模与绘制便成 为计算机图形学中的一个研究热点和难点。与其它自然景物相比，地形 自身的特殊性在于：其一，空问范围大、视野广。例如在飞行训练的模拟 中尤其需要一个广视野的虚拟场景。其二，地形表面细节的复杂性。地 表的起伏具有很大的随机性。三维地形的可视化技术【3 】在地理信息系统 ( g i s ) 、测绘学、地图学等领域有着广泛的应用。近年来，虚拟现实( v r ) 、 数字地球、科学可视化等崭新的研究方向不断产生和发展，地形作为一 种自然界中具有复杂特征的事物，是以上学科的重要研究内容。 三维地形的可视化除了用到大量的计算机图形学的知识外，还可以 从新的领域中得到支持。分形理论是近年来新兴的一个学科，利用分形 理论中的相关知识，可以很好地实现对自然界景物的建模，例如l 系统 【4 】可以模拟植物的生长，迭代函数系统1 4 】可以模拟云、烟、海水等。分 形布朗运动是已经被证实的描述地形的最有效模型之一。利用分形布朗 运动构造三维地形的数学模型，再使用计算机图形学中的投影变换，消 隐处理，光照处理，彩色合成等技术实现地形的显示是三维地形可视化 的有效方法。经此方法生成的三维分形地形可以具有较好的真实感，是 对复杂的自然界事物进行模拟的良好范例。 本课题的主要目的是以分形布朗运动【2 l 【3 】【4j 为工具构造三维地形 的数字高程模型【3 1 ( d i g i t a le l e v a t i o nm o d e l ，简称d e m ) ，然后在此模型 的基础上选用适当的投影算法，消隐处理，光照处理，色彩合成等技术 实现三维分形地形的可视化，并使显示的三维地形具有较好的真实感。 同时本课题还对图像存储方式，分形云图模拟，分形地形绘制软件的交 互性等相关内容进行一定的讨论。 硕士论文三维分形地形的研究与实现 1 2 国际国内研究状况和进展 三维地形可视化技术与地理信息系统( g i s ) ，虚拟现实【2 l 等新兴学 科有密切关系。同时，分形几何学1 “2 1 f 3 1 【4 l 作为一门新兴学科也引起了 越来越多的研究学者的注意，分形几何学与三维地形可视化的结合产物 一一三维分形地形可视化已经成为计算机图形学，分形图形学，虚拟现 实，科学可视化等领域的重要研究方向。近年来，很多自然科学基金项 目的研究内容都与此有关，关于三维分形地形的科技论文也越来越多， 在三维分形地形的生成与显示方面不断有新的研究成果出现。1 9 6 8 年，m a n d e l b r o t 和v a n n e s s 提出了一类一维高斯随机过程，称为“分维布 朗运动”( f r a c t i o n a lb r o w n i a nm o t io n ，简称f b m ) 。由于f b m 很好地描 绘了许多自然现象，所以，许多学者便开始尝试利用f b m 方法来模拟真实 感地形。目前，分形布朗运动是已经被证实的描述地形的最有效模型之 一口 研究人员对于三维分形地形的研究的重点有以下几个方面： 1 对于使用分形布朗运动构造数字高程模型的方法进行改进，使 之更具有现实世界中地形的特点； 在这方面，已经有了泊松阶跃法( p o i s s o nf a u l t i n g ) 、傅立叶滤波法 ( f o u r i e rf i l t e r i n g ) 、中点位移法( m i d p o i n td i s p l a c e m e n t ) 等具体的实现方 法，其中的中点位移法是最常用的方法。同时针对原有算法的缺点，也 有一些改进方法被提出。 2 改进消隐处理，光照处理等技术，使显示的三维分形地形更有 真实感： 这方面也是计算机图形学中真实感图形生成的重要研究内容，新的 实现消隐处理，光照处理的技术，例如光线跟踪算法等已经被提出并不 断成熟。使显示的图形具有更好的真实感也是计算机图形学的一个研究 目标。 3 提高三维地形绘图软件的人机交互能力。 三维地形绘图软件除了可以进行三维分形地形的绘制外，还应提供 较好的交互性，例如：软件使用者更改观察角度或光照角度后，所显示 的三维地形也应有相应的变化。这方面的研究在军事，航空等领域具有 重要的意义。 2 硕士论文三维分形地形的研究与实现 1 3 论文各部分主要内容 论文第一章概要介绍分形地形研究的意义，目前国内，国际对这一领 域的研究状况和进展，以及本课题研究所要达到的目的。 论文第二章介绍三维地形建模的方法，包括对分形布朗运动的介绍 和基于分形布朗运动构造地形特征数据的算法，重点是用于地形建模的 中点位移法。 论文第三章介绍三维地形显示的基本过程和在已经获得地形特征 数据的基础上进行地形显示时所要处理的投影变换，消隐处理，光照处 理，彩色合成等关键问题，以及解决这些问题时可采用的方法。 论文第四章在第二章、第三章所做研究的基础上针对具体问题，如 数字高程模型生成、消隐处理、光照处理等提出确定的解决方案，如z 缓冲方法、p h o n g 光照模型等，并给出具体算法，以实现有真实感三维分 形地形的显示。 论文第五章针对传统的三维分形地形的实现方法中可能出现的问 题和需要解决的部分问题提出改进方法并进行相应的讨论。 论文第六章给出了在前几章所作研究的基础上使用v is u a lb a s i c 语言开发出的三维分形地形生成与显示软件各部分功能的演示效果。 论文第七章对于本论文所研究的三维分形地形生成与实现这一问 题进行了总结和展望。 硕士论文三维分形地形的研究与实现 2 三维分形地形建模基础 在进行三维地形显示之前，必须提供有效的方法来获取能够正确 体现地形特征的数值信息。这就是地形建模所要研究的问题。 在地形特征的数值信息中，数字高程模型( d i g i t a le l e v a t i o n m o d e l ，简称d e m ) 是体现地形特征的主要数据。数字高程模型，可理 解为在三维地形中，不同位置的点所对应的高度值。具体处理时，有以 下两种情况【3 j ： 1 如果所进行的研究工作是针对现实存在的某区域的地形信息， 这时d e m 数据的获取主要有以下三种途径： 野外实地测量； - 航空航天摄影测量： 从地图上获取。 这时所进行的工作属于测绘学的范畴。 2 如果所要进行的工作是使用计算机生成并显示虚拟的地形，这 时需要合适的数学方法来生成能体现现实世界中地形特征的d e m 数 据。这是本课题所要研究的内容。 2 1 三维地形造型方法概述 由于地形具有自然界景物的复杂性和随机性的特点，因此，使用传 统的，线性的光滑函数来表示地形表面将很难真实地描述地形的复杂性 和随机特征。 近年来，分形理论1 1 1 3 1 1 4 1 3 3 】的出现和发展，为描述自然界的复杂事 物提供了有效的方法。 分形理论是非线性科学中一个活跃的数学分支，其研究对象是不光 滑的和不可微的几何形体，对应的变量参数是分形维数，分形理论的初 刨形式是分形几何学。分形( f r a c t a l ) 一词是美籍法国科学家 b b m a n d e l b o r t 于1 9 7 5 年提出的一个新名词，用以描述不规则的复杂 图形。由于分形几何概括了人类早已认识到的自然界的固有特征，因此， 分形几何能对客观世界( 包括宏观和微观) 做出比传统几何更为精细的 描绘。 4 硕士论文三维分形地形的研究与实现 目前，分形的明确定义尚未确定，可以被普遍接受的看法是：分形 是指具有以下性质的集合f t 3 】【4 】： ( 1 ) f 具有精细的结构，即任意小的尺度下，f 总有复杂的细节； ( 2 ) f 是不规整的，其整体与局部都不能用传统的几何语言来描述； ( 3 ) f 通常具有自相似性，这种自相似性可以是近似的或是统计意义 下的： ( 4 ) 通常，某种定义f 的分形维数大于它的拓扑维数； ( 5 ) 多数情况下，f 可以以简单方法确定，并由迭代过程产生。 分形理论的数学理论基础十分复杂属于理论科学的研究范畴，目 前分形理论的最成功应用在于计算机图形学领域，即利用分形来模拟生 成使用传统数学难以精确描述的自然界景物物体的表面( 例如：山，树 木等) 。 分形几何关注物体的随机性、奇异性和复杂性，试图透过混乱现象 和不规则构型揭示隐藏在背后的局部与整体的本质联系和运动规律，具 有细节无限以及统计自相似性等典型特征，使用递归算法用简单的规则 来生成复杂景物，在现代计算机图形学中，分形几何在对自然现象的真 实绘制和建模方面有着重要作用。 从分形的性质可以看出，自然界中的地形明显具有分形的特征，因 此基于分形的方法是实现对地形造型的有效方法f 3 j f 4 j f 7 j 【sj f l0 j f 3 3 j f 3 。 2 。2 分形地形建模方法分类 分形布朗运动f 2 】【3 l 【4 l 【9 】1 3 7 儿3 8 】( f b m ，f r a c t a lb r o w n i a nm o t i o n ) 是现 代非线性时序分析中的重要随机过程，它能有效地表达自然界中许多非 线性现象，是用以描述地形表面特征最有效的数学模型之一。 分形地形建模大致可归纳为泊松阶跃法( p o i s s o nf a u l t i n g ) 、傅立叶 滤波法( f o u r i e rf i l t e r i n g ) 、中点位移法( m i d p o i n td i s p l a c e m e n t ) 、逐次随 机增加法( s u c c e s s i v er a n d o ma d d i t i o n s ) 和带限噪声累积法( s u m m i n g b a n dl i m i t e dn o i s e s ) ，小波变换等几类。 泊松阶跃法【6 】【7 1 是最早由m a n d e l b r o t 研究的地形生成算法，它是将 泊松分布用于f b m 的产物。它在服从泊松分布的闻隔上，将高斯随机位 移( 或称步长函数) a n 到一个平面或球面上，其结果具有f b m 特征。这种 方法很适合于用球面生成类似星球的物体，它的主要缺点是算法的时间 复杂度达到了o ( n ) 。 硕士论文三维分形地形的研究与实现 傅立叶滤波法 6 1 17 】是将一个二维的高斯白噪声进行傅立叶变换，在 频域将变换结果同一适当的滤波器相乘，然后再将所乘结果进行傅立叶 反变换，其结果就是i b m ，从而形成类似自然地景的形态。这种方法的 优点是不仅可以精确地控制所有的频率分量，还可以产生不同的纹理图 像效果。傅立叶滤波法的缺点是最终形成的地表结果具有周期性，且算 法的时间复杂度是o ( n l o g n ) ，此外，还存在缺少细节的局部控制以及难 以改变采样的精细程度等缺点。 中点位移法1 6 儿7 l 是标准的分形几何法，可用作快速的地景生成。这 种方法是在细分的过程中，在两个点或多个点之间进行插值的方法来进 行地形建模，因此中点位移法产生了真正的分形地表。因为这种方法具 有高速度以及具有为已有形状增加细节的能力，所以中点位移法成为了 一个有用的面向应用的分形算法，是地形建模中最常用的分形方法。本 课题选用此方法进行三维地形的建模。 逐次随机增加法t 6 1 1 7j 是一个灵活的细分方案，如果需要利用上一级 细分过程确定的点( 不是所有的点都必须用) ，则这些点需要首先增加一 个服从某种分布的随机变量。一般新的点可通过在上一级细分水平基础 上进行线性或非线性插值得到。这个算法的时间复杂度依赖于最终的分 辨率和地表的起伏程度。 带限噪声累积法1 6 儿7 1 是将频率范围受到严格限制的信号反复叠加， 其中每一个信号的幅度是随机变化的，即噪声，因此这种方法也称噪声 合成法。这是一种基于函数的建模方法，每个点的确定独立于它的所有 邻接点，这是此法区别于一般的随机分形算法的独特之处。 小波变换法1 6 1 7 1 是近来又出现的基于小波变换的多分辩率分析方 法，采用迭代小波变换的算法，能有效的生成更精确的i b m 图象。但算 法较中点位移法复杂。 2 3 基于中点位移法的地形建模方法 地形建模的主要任务是生成地形的数字高程模型( d e m ) ，即应用中 点位移法的原理生成二维平面上各个点的高度数据。中点位移法是指在 生成的过程中在多个点间进行插值，从而实现d e m 的细分。具体的细 分方式有三角形细分，正方形细分等。 6 硕士论文三维分形地形的研究与实现 2 3 1 三角形细分法 三角形细分法【6 】【7 7 】是将随机中点位移程序用于三角形地平面而 生成地面特征。此方法的原理如图2 3 1 1 所示。 该细分方法就是对由已知高度值的三个点所构成的三角形各边进 行等分，同时标注各边的中点并按照计算平均数的方法得出各个中点的 高度值，再将各中点连接起来，这样一个三角形就变成了四个小三角形， 然后在各中点原有高度值的基础上增加一个随机变量构成新的高度值。 c b f c 图2 3 1 1 三角形细分 例如：假设点a 、b 、c 的高度分别为h 、h b 、h c ，则点d 、e 、f 的高度分别为： h d = ( h + h b 2 + g d h e = ( h a + h c ) ，2 + g e h f = ( h b + h c ) 2 + g e 上式中的g d ，g f 、g ，是三个不同的随机值。 这种方法的优点是较为灵活，不需要采样点组成矩形或正方形，由 随机点组成的多面体可划分为许多三角形，然后再按此方法进行细分。 这种方法的缺点是细分过程中各中点的坐标值不容易确定，细分的过程 也不容易控制。 2 3 2 正方形细分法 这种算法又称为d i a m o n d s q u a r e 法【6 】【7 】【8 】【1 1 】【16 儿1 ，是将随机中点 位移方法用于正方形地平面而生成地面特征。此方法的原理如图2 3 2 1 所示： 取四个点a 、b 、c 、d 构成正方形，并首先生成这四个点的高度 值。然后分别计算正方形中点o 和各边中点e 、f 、g 、h 的高度值。具 体计算方法如下： 硕士论文 三维分形地形的研究与实现 图2 3 2 1 正方形细分法 中点。的高度值为： h o = ( h a + h s + c + h oj 4+ g o 各边中点e 、f 、g 、h 的高度值为： h z = ( h a + h s + 而d j 3 + g e h f = ( h a + h c + h o j 3 + g f h a = ( h b + h o + h o ) 3 + g o h h = ( h c _ h a 七h o ) 3 + g n 上式中的g d 、g 、g f 、g g 、g 片是不同的随机值。 这样，原来的个正方形就被分成了四个正方形。以上的细分过程 每次都对新形成的正方形重复进行，直到新形成的正方形的边长小于指 定的值为止。如果以上重复的次数足够多，将可以得到相当精细的数字 高程模型。 d i a m o n ds q u a r e 是一种常用的中点髓机位移算法。这种算法是从 由原始点组成的正方形开始，通过采用若干次随机中点位移方法，不断 细分，最后获得相当精细的数字高程模型。此方法的具体举例描述如下： 假设所要求的d e m 由2 5 个点组成( 见图2 3 2 2 ) 。 首先，图2 3 2 2 ( a ) 的四个角已经有了初始高度值，表示为点。 在此基础上，细分的过程由d i a m o n d 步和s q u a r e 步两个步骤构成。 d i a m o n d 步：计算正方形中点的高度值( 中点为两对角线交点) ，中 点的高度值是四个顶点的平均值再加上一个随机量计算得到的。在图 2 3 2 2 ( b ) 中，新值显示成点，已经存在的点显示为点。这样，就已 经得到了五个点。 s q u a r e 步：计算各边中点的高度值。其计算方法是此中点所在边 的两个顶点及正方形中点，共三个点高度的平均值再加上一个与 d i a m o n d 步相似的随机量( 图2 3 2 2 ( c ) ) 。经过这一步后，共得到了九个 点的高度值。这样原来的一个正方形被细分成了多个新的正方形，新的 正方形的个数是2 ”，其中i 是迭代的次数，由于目前是第一次迭代，所 以正方形的个数是2 2 = 4 个。 8 硕士论文三维分形地形的研究与实现 bc 图2 3 2 2 两次d i a m o n d _ s e q u a c e 选代示意图 图2 3 2 2 ( d ) 和图2 3 2 2 ( e ) 分别为第二次执行此算法的d i a m o n d 步和s q h a r e 步的示意图，由于此时迭代次数是2 ，所以可得到2 4 = 1 6 个 正方形，共可得到2 5 个点的高度值。d i a m o n ds q u a r e 可以用迭代或递 归的方法来实现。 可见d i a m o n ds q u a r e 算法用来形成浮点数构成的网格2 6 1 2 7 j f 2 引， 来填充二维分形高度值。这样，实现了地形的建模。这种插值方法构成 了一个双二次曲面的效果，此算法的一个重要优点是地形表面的法线是 连续的，用这个算法生成的的地景轮廓比较柔和。d i a m o n d s q u a r e 算法 的效率较高，所得到的数字高程模型适合使用( n + 1 ) ( n + 1 ) 的二维 数组h ( n ，n ) 来表示。当数字高程模型足够精细时，( n + 1 ) ( n + 1 ) 的 二维数组中的每一个数值可以与显示平面中每个像素点所代表的高度 值相对应。如果把这个二维数组中某个元素h ( i ，j ) 的下标i ，j 分别看 成是空间坐标系中某点a 的x 坐标和y 坐标，这时i ，j 的范围都是( 0 n ) ： 同时。把元素h ( i ，j ) 的值看成是点a 在空间坐标系中的z 坐标，这样， 这个元素h ( i ，j ) 就唯一地确定了空间坐标系中的一个点a ，其坐标为( i ， j ，h ( i ，i ) ) 。整个数组所确定的这一系列的空间坐标系中的点也就构成 了三维地形的数据模型。即达到了生成数字高程模型( d e m ) 的目的。 例如：如果显示平面中有2 5 6 2 5 6 个像素点，每个像素点与数字 高程模型中的一个点对应。这时。可以使用一个2 5 6 2 5 6 的二维数组 来存放这个数字高程模型。同时，也就确定了空间坐标系中的2 5 6 2 5 6 9 硕士论文三维分形地形的研究与实现 共6 5 5 3 6 个点。本课题在具体实现分形地形的建模时，就是选用 d i a m o n d s q u a r e 算法。 2 3 3 中点位移量的确定 在上述两种算法中，随机量g 的选取是地形建模的一个重要问题 f 7 儿1 1 l 。在构建分形地形的数据模型时需要用到随机数发生器，以生成随 机变量样本。在大多数开发系统( 如v i s u a lc + + ，v i s u a lb a s i c 等) 中 都具有实现伪随机数发生器的函数( 如v i s u a lb a s i c 中的r n d ( ) ) ，这类 函数返回在特定区间( 0 ，a ) 上均匀分布的伪随机数。以这个伪随机数 发生器为基础。可以实现具有不同概率特征的随机数序列，并以此随机 数序列作为每次计算高度值时的随机数g 。常用的随机数序列的概率特 征有以下几种： - 均匀分布【5 1 即所产生的随机数在特定范围内出现的概率相等。由于伪随机数发 生器r n d 0 返回在区间( 0 ，a ) 上均匀分布的随机数所以限定( 0 ，a ) 的范围后，直接使用伪随机数发生器r n d 0 就可以产生服从均匀分布的 随机数序列。 正态分布1 5 】 又称高斯分布，是一种自然界中广泛存在的概率分布形式。中心 极跟定理表明，如果跏是任意r 1 个符合相同分布的随机变量的标准化 总和，则砌的概率分布随着n 一。而趋于正态分布，实现过程如下： 对于：z = r n d o 则： e ( x ) = a 2d ( x ) = 小1 1 2 对x 进行标准化有： y = f j e ( x ) ) 4 瓦x 3 对于r 1 个l ，的和： y 。= 匹x i e 晓x | 弱 d 眨x | ) = ( 置一e ( 置) ) d ( 置) = ( 置- ( a 形2 ) ) 山2x n 1 2 通常情况下，当n = 3 或n = 4 时就已经符合需要7 】【1 1 1 。 指数分布1 5 1 以随机数发生器r n d 0 为基础，可以构造服从指数分布的随机数序 列。常用的基本形式为1 7 1 1 1 1j ： 1 0 硕士论文维分形地形的研究与实现 g = 一l n ( r n d o e x + 1 0 1 + a d d 上式中的e x ，a d d 为修正参数。这样，所得到的g 值将服从指数分 布。 以上所给出的随机数序列产生方式都是通用的生成方式，在具体的 三维分形地形建模过程中，根据不同的要求，实现随机数序列的方法会 在原有基础上进行适当的调整。 硕士论文兰维分形地形的研究与实现 3 地形显示的基本技术 本章的内容是在地形建模成功后，如何使用计算机图形学的相关 技术，来实现三维地形的显示。 3 1 三维地形显示的基本过程 三维地形显示的基本步骤如下【3 】： ( 1 ) 数字高程模型生成和细分； ( 2 ) 确定光照角度，观察角度、色彩构成等辅助数据； ( 3 ) 投影变换，将要显示的内容投影到观察面上： ( 4 ) 选择消隐算法，消去三维地形中的不可视部分： ( 5 ) 选择光照模型，实现光照处理，使显示的三维地形具有明暗 效果； ( 6 ) 确定绘图颜色，进行图形的绘制。 本论文中的第二章就是解决以上的步骤( 1 ) 的问题。其它各个步 骤的实现，都需要使用到计算机图形学的相关知识。以下各节分别介绍 解决这些问题的方法。 3 2 地形显示的辅助数据 本课题中实现地形显示的辅助数据主要有角度类数据和颜色构成 数据两类。 3 2 1 角度数据 在进行三维地形显示时，需要用到的角度数据包括以下四种： ( 1 ) 视旋转角度，代表观察者在观察三维地形时，处于以三维地 形为中心所构成的平面直角坐标系中，观察视线与x 轴正方向的夹角， 其范围是0 度到3 5 9 度。如图3 2 1 1 ( a ) 所示。 ( 2 ) 视倾斜角度，代表观察者在观察三维地形时，观察视线与地 平面之间的夹角，其范围是0 度到9 0 度。如图3 2 1 1 ( b ) 所示。 图3 2 1 中的角a 就是视旋转角，角口是视倾斜角。使用这两个角 度可以得出在空间坐标系中的视向量v 。视向量v 的三个分量分别为： 2 硕士论文三维分形地形的研究与实现 t c o s 届c o sa 、c o s 母s i n 口、s i n8 ) 视向量在处理光照信息时有重要应用。 y 轴 厂 、视线 为j 轴 图3 2 1 1 视旋转和视倾斜角度 ( 3 ) 光旋转角度，代表在以三维地形为中心所构成的平面直角坐 标系中，光线与x 轴正方向的夹角，其范围是0 到3 5 9 度。如图3 2 1 2 ( a ) 所示。 ( 4 ) 光倾斜角度，代表光线与地平面之间的夹角，其范围是0 度 到9 0 度。如图3 2 1 2 ( b ) 所示。 y 轴 厂 、光线 八 刁- x 轴 图3 2 1 2 光旋转和光倾斜角度 图3 2 1 2 中的角y 就是光旋转角，角口是光倾斜角。使用这两个 角度可以得出在空间坐标系中的光向量三。光向量三的三个分量分别为： ( c o s 目c o sr 、c o s0s i ny 、s i n 口) 光向量在处理光照信息时有重要应用。 3 2 2 颜色数据 在三维地形显示的时候，如果依照地图学中的习惯，不同的高度要 硕士论文三维分形地形的研究与实现 用不同的颜色显示。因此，应该提供相应的颜色数据，使地形显示符合 地图学的习惯。另外，合适地设定颜色构成数据也可以使显示出的三维 地形更加具有真实感和针对性，例如：以绿色为主的颜色数据可以用来 绘制植被丰富的地形，以褐色为主的颜色数据可以用来绘制缺乏植被的 地形，以白色为主的颜色数据可以用来绘制雪山、雪原等等。 通常情况下，三维地形不是以单一的颜色来绘制，而是使用渐变的 颜色序歹0 来绘制，颜色数据应该能够体现出这一渐变的颜色序列。因此 颜色数据适合以数组的形式提供。例如：假设有数组a t n 用来提供颜色 数据，此数组中的数据a o 】、a i 】、a n - l 】、a n 】分别代表三维 地形中高度值为0 、l 、n 1 、n 的位置的颜色。这样，合理地设定 此数组中的数据n o 】、a 【1 、a n l 】、a n 的值，就可以较好地 实现三维地形的多颜色显示。 3 3投影交换技术 三维的地形图像在使用计算机进行显示时。必须显示在二维的显示 平面上，这时，必须进行投影变换处理。 由第二章的内容可知，使用中点位移法生成的数字高程模型用n 行 n 列的二维数组来存放。这个二维数组可以确定n 1 3 个空间坐标系中的 点。本课题所处理的投影变换就是基于这种地形模型进行的。在处理投 影变换的时候，可以根据视旋转角度的不同进行区别对待。 3 3 1 视线与坐标轴垂直 当视旋转角度为0 、9 0 、l8 0 、2 7 0 度的时候，视线与坐标系的x 轴 或y 轴垂直，此时的情况如图3 3 1 1 所示。 在这种情况下，投影处理时可以按行 或按列进行。下面，以视旋转角度为2 7 0 度为例，讲述本论文进行投影处理的方法。 如图3 3 1 2 所示，假设视倾斜角度为 。以a 、b 、c 三个点为例，这三个点的 x 坐标相同，它们的y 坐标的关系为 y 0 y 1 y 2 ，a 点的z 坐标为0 ( 即高度为 0 ) ，b 点、c 点的z 坐标相等，均为z 。 y j 9 c度 1 8 0 度 。度 l2 7 0 度x 捌 图3 3 1 1 视线与坐标轴垂直的情况 1 4 硕士论文三维分形地形韵研究与实现 图3 3 1 2 投影处理方法 投影面与视线相垂直，a 、b 、c 三个点的投影点分别为a 、b 、c ， 三个点。从图中可以看出：原始点进行投影后，在投影面上，其x 坐标 不变，而其y 坐标的计算方法为： y 1 = y x s i n0 + z x c o s 所以点a 、b 、c 的y 坐标分别为： a j ： y a l = y o x s i n8 + 0 x c o s5 = y ox s i np b ： y b = y l x s i n1 3 + z z o o s8 c 1 ： y c = y 2 x s i n 爵+ z x c o s8 依照同样的方法，就可以算出数字高程模型中所有点在投影面上的 投影点。从而实现投影变换。 3 3 2 视线与坐标轴不垂直 当视旋转角度不为0 、9 0 、1 8 0 、2 7 0 度的时候，视线将不与坐标系的坐标轴垂 直，此时的情况如图3 3 2 1 所示。 这种情况下，进行投影变换时，要先 对原有的数字高程模型所确定的点进行坐 标变换，使视线与坐标轴垂直，然后再按 照图3 3 2 2 进行变换。下面，以视旋转角 度为3 0 0 度的情况为例，讲述进行几何 变换的步骤。 ：式 - 一 擞 视八确 图3 3 2 1 视线与坐标轴不垂直的情 ( 1 ) 进行几何变换前的情况如图3 3 2 2 ( a ) 所示，此时，数字高 程模型( d e m ) 所代表地形的x 、y 坐标所确定的一个正方形( 其边长 为l ) 在坐标系的第一相限； 硕士论文三维分形地形的研究与卖现 y 轴 一 、x 自 视线 ( _ ) 几何变换前 了。 x 、视线 ( b ) 确定新的坐标系 图3 3 2 2 几何交换过程 ( 2 ) 坐标原点不变，以视线的方向作为新坐标系的y 轴正方向糕 构成新的坐标系，如图3 3 2 2 ( b ) 所示： y 轴 、一 函 q 一 y 轴 一 x 南 ( n ) 新的坐标系下的原d e m ( b ) 对d e m 进行平移 圈3 3 2 3 几何变换过程 ( 3 ) 在新的坐标系中，原d e m 所确定的正方形的位置如图3 3 2 3 ( a ) 所示，此时的情况相当于将原d e m 正方形中各点的坐标逆时针旋 转3 0 度( 2 7 0 一口= - 3 0 ) ，这时，需要用到坐标的旋转变换来确定新坐标， 变换形式为【2 】： i x j 2 x x c o s8 。y x s n8 ly = x x s i n 口+ j ，x c o s0 其中( x ，y ) 为变换前的坐标，( x ，y ) 为变换后的坐标。如果用矩阵表 示，其形式为： 这里的转角0 即为2 7 0 口= 3 0 。 小巴。孙 硕士论文兰维分形地形的研究与实现 ( 4 ) 将旋转后的正方形沿y 周正方向平移，使这个正方形位于新 坐标系的第一相限。如图3 3 2 3 ( b ) 所示。从图中可知：d e m 中每一 个点的平移的距离为l s i n 口。其中工为正方形的边长，角口= 2 7 0 a = 3 0 。因此，平移的坐标变换形式为【2 】： l x1 2 x lj ，叫l x s i n 口 即新的x 坐标不变，新的y 坐标为原坐标加上平移距离。如果用 矩阵表示，其坐标变换形式为： | ： = | + i l x s i n0i l x 。2 x x c o s6 y x s t n8 ： = 孙 + e s i n0 其中的角疗为2 7 0 口= 3 0 。 需要注意的是，上面在介绍投影处理的时候是分别以视旋转角度为 2 7 0 度和视旋转角度为3 0 0 度的两种情况为例进行的，当视旋转角度为 其它值的时候，具体的处理方法将有所变化，但进行投影处理的基本思 想与上面的两个例子是一致的。 3 4 消隐处理 在生成三维地形时，如何判断从某一特定观察位置所能看到的场景 中的内容是一个很重要的问题，这就是消隐处理问题。目前，已有多种 硕士论文三雏分形地形的研究与实现 解决这一问题的算法，不同的解决技术有不同的特点。 3 4 1 消隐处理算法的分类 常用的和具有代表性的消隐处理算法有以下几类【2 1 3 】： - 画家算法 画家算法的基本思想是：先把屏幕制成背景色，再把物体的各个面 按照距离视点的远近进行排序，离视点远的在前，离视需跹的在后，构 成深度优先级表。然后，从表头至表尾逐个取出要显示的物体，投影到 屏幕上，这样，后显示的物体将覆盖先显示的物体，由远透近地绘制各 个物体，实现了消隐处理。这个过程与绘画的过程类似，西此称为厕家 算法。 深度缓冲器算法 深度缓冲器算法( d e p t h b u f f e rm e t h o d ) 是一个比较常用的判定物 体表面可见性的算法。其基本思想是将投影平面上的每个像素所对应的 深度进行比较，然后，取最近的像素的属性值作为投影面上该像素的属 性值。由于通常沿着观察系统的z 轴来计算各像素点距观察平面的深 度，因此，这个算法也称为z 缓冲算法( z b u f f e r ) 。z b u f f e r 算法在具 体实现时将显示平面上每一个像素所对应的地面深度信息记录到z 缓 冲器中，在绘制某一像素点时，先检测z 缓冲器的值，若该像素的深度 值小于z 缓冲器中的相应值，表明该像素点距离观察点较近，应该显示， 并以当前的深度值取代z 缓冲器中的原值。否则，将不显示。这样就达 到了消隐的目的。这种算法的思路比较简单，较容易实现，是一种较常 用的消隐算法。本课题选用此方法实现消隐处理。这种算法的缺点是需 要大容量的缓冲器存储空间。 光线跟踪法【4 副 光线跟踪法是一种可实现高度真实感的图形绘制新技术。其基本原 理是从观察点出发，通过屏幕像素向要显示的三维场景投影一条光线， 找出光线与场景的第一个交点即为可见点，并设置相应像素的光亮度作 为交点处的光亮度，从而绘制出一幅完整的三维图形。这种算法的原理 简单，可自动实现消隐，并能模拟出光照效果，从而使显示的三维图形 具有很好的真实感。其主要缺点是求交的计算量很大，需占用较多的时