（机械设计及理论专业论文）基于mpd方法的山脉地形生成研究.pdf

西北j = 业大学硕士学位论文 基于m p d 方法的山脉地形生成研究 摘要 本文以实现分形布朗曲面的随机中点位移法为基础，提出了一种能够生 成具有可控形状山脉地形模型的融合曲面方法，该方法首先生成具有预定形 状的控制源曲面，然后将随机中点位移法融入其中，保证了生成的曲面既具 有预定形状，又有部分分形布朗曲面的特性：本文充分利用二维高斯函数曲 面类似于山包形状且容易控制的特性，提出了一种用于生成控制源曲面的高 斯造型法，使得通过几个直观的参数就可以方便快捷地进行山包源曲面形状 控制：对于一些具有特殊形状的山体，本文采取了对给定的稀疏点进行插值 的方法构造源曲面；最后本文完成了演示程序，通过交互式界面来选择不同 的控制参数和图形生成方法，形成了可控而逼真的山体图形，验证了文中提 出的方法。 关键词： 中点位移法分形布朗运动地形模型插值可视化 摘要 m p d a l g o r i t h m b a s e dm o u n t a i nt e r r a i n g e n e r a t i o n a b s t r a c t i nt h i s p a p e r ，w em a k er e s e a r c ho nm i d - p o i n td i s p l a c e m e n ta l g o r i t h m w h i c hi su s e dt og e n e r a t ef r a c t a lb r o w nm o t i o na n d p r e s e n tas y n t h e t i c a ls u r f a c e g e n e r a t i o na l g o r i t h m w h i c hc a n g e n e r a t e m o u n t a i nt e r r a i nm o d e lo f p r e d e t e r m i n e ds h a p e t h ea l g o r i t h mc o m b i n e sm p da l g o r i t h mw i t hr e s t r a i n i n g s u r f a c et oa s s u r et h ee f f e c to f p a r t sc h a r a c t e ro f f b ms u r f a c ea n d p r e d e t e r m i n e d s h a p e w ea l s op r e s e n tam e t h o dn a m e dg a u s ss c u l p t i n gt og e n e r a t er e s t r a i n i n g s u r f a c eb e c a u s et h ep i c t u r eo f2 dg a u s sf u n c t i o nr e s e m b l e sh i l l i ti sv e r ys i m p l y a n dc o n v e n i e n t l yt ou s et h em e t h o dt oc o n t r o lt h es h a p ea n d p o s i t i o no f t h eh i l l b yi n p u t t i n g s e v e r a li n t u i t i o n i s t i c p a r a m e t e r s a s f o rs o m e s p e c i a ls h a p e d m o u n t a i n ，w ei n t e r p o l a t eo ns o m ee x i s t e ds p a r s ep o i n t st og e n e r a t ei t sr e s t r a i n i n g s u r f a c e s f i n a l l y , w eo f f e rad e m op r o g r a mo f a l lt h em e t h o d s p r e s e n t e d d i a l o g b o x e sa r ed e s i g n e dt oi n p u tp a r a m e t e r sa n do p t i o n s t h ec o n t r o l l a b l ea n dv i v i d p i c t u r e so f v i s u a l i z e dm o d e l s h o wt h ee f f i c i e n c yo f t h e p a p e r k e y w o r d s ： m i d p o i n td i s p l a c e m e n tm e t h o d ，f r a c t a lb r o w nm o t i o n ，t e r r a i nm o d e l ， i n t e r p o l a t i o n ，v i s u a l i z a t i o n i i 西北工业大学硕士学位论文 第一章绪论 1 1 引言 自然对象的根本特征在于其形状的复杂性和不规则性。诸如海岸线、山 脉、云彩这样的形状按传统的欧几里德几何难以描述，但是随着形状大小的 变化，它们常具有一种自相似性，也就是目标的被放大部分与整体相似或相 同的特性。这种统计自相似性就是自然界中分形的基本特性。分形几何【l 】【2 】 这一概念是美国数学家b e n o i tb m a n d e l b r o t 于7 0 年代提出的，它关注物体 的随机性、奇异性、和复杂性，试图透过混乱现象和不规则构型揭示隐藏在 背后的局部和整体的本质联系及运动规律，具有细节无限和统计自相似等典 型特征，用简单规则来生成复杂景物，在现代计算机图形学中，分形几何在 对自然现象的真实描绘和数学建模方面起着有重要作用。 分形几何理论按实现方式的不同分为两大类，确定性分形和随机分形。 随机分形是在描述分形对象的迭代过程中加入随机因素，从而生成具有随机 特性的分形图形的方法。随机分形非常适合于描述海岸线、山脉、云彩这样 具有随机性的自然对象。分形布朗运动( f r a c t a lb r o w n i a nm o t i o n ) 是随机分形 生成法的重要分支，它是通过模拟布朗运动的随机过程来产生一个随机变量， 并把这一变量作为随机因子引入分形体的描述工程中，从而生成分形图形。 在生成地形这一自然对象上，目前常用的方法有两种p 】，分形布朗运动 法和曲面造型方法。分形布朗运动能有效地表达自然界中的许多非线性现象， 也是迄今为止最好地描述真实地形的随机过程【4 1 。r i c h a r dev o s s 在8 0 年代 初就用它绘制出了分形山脉。实现f b m 的算法【5 】有很多种：泊松阶跃法、逆 f o u r i e r 变换法、随机中点位移法【6 】、噪声合成法等。其中随机中点位移法 ( m i d - p o i n td i s p l a c e m e n t ) 其能快速方便的生成图形并具有为已有形状增加 细节的能力而成为一种实用的地形生成算法【”。m p d 方法是利用网格细分过 程中，在两点或多点间进行插值和随机扰动来进行地形生成的。m p d 方法用 于地形模拟存在一个网格细分方式问题，使用较多的网格细分方式有三角形 细分法和菱形方形细分法( d i a m o n d - - s q u a r es u b d i v i s i o n ) 。三角形细分法是将 第一章绪论 三角形各边等分，并连接各边中点，分三角形为四个子三角形，同时对各中 点值加以高斯扰动。用这种方法生成的相邻三角形问无信息传递，导致最终 生成图形存在折痕问题并且不能通过局部平滑去除。菱形方形细分法与此类 似。g a v i nsp m i l l e r 提出了一种改进的中点细分方案【8 1 ，称为方形一方形细 分法( s q u a r e - - s q u a r es u b d i v i s i o n ) 。其内插点的值是上层周围点与它按距离的 加权平均，权值为9 ：3 ：3 ：1 。与此内插点最近的原始点得到最大的权值。这个 方法能达到双二次曲面的效果，生成图形表面的法线是连续的，消除了折痕 现象，但也正因为二次曲面的影响，生成的地形轮廓较柔和。 地形生成的另一种方法是曲面造型方法【9 l 。这种方法是用几何造型方法 生成曲面n ：e r l 地形的大致形状，再对其细节进行扰动修改。这种方法生成地 形很难模拟丰富的地质地形特征，现在也有用纹理合成技术生成地表丰富细 节，然后再将纹理应用于地形模型，并借助于o p e n g l 的渲染技术，一定程 度上弥补了该方法的不足。 地形生成的另一个重要研究方向是生成地形的可控问题。m p d 方法生成 地形快速便捷，但难以预测生成结果的大致形状。目前对于m p d 的生成结 果控制有了一些研究。例如通过给定初始迭代次数和初始迭代数据来控制生 成图形的基本形状和轮廓 i 0 1 ；还有用若干个具有三维高度的控制点组成若干 个三维高度控制面，将此三维高度控制面投影到地平面，用控制高度修正受 其影响的网格点的偏移高度，生成具有高度控制的f b m 模拟地形地貌t n l 。还 有一种地形控制的方法是曲面拟合法f 1 2 叫”，用曲面拟合稀疏分布的高程值 点，再利用分形技术对拟合曲面进行随机扰动，形成符合一定要求的地形表 面。这种方法计算比较复杂，计算量大，实现起来较为不易。近年还出现了 一种直接利用已知地形的统计参数，如平均高程、最大，最小高程、地形标 准差、相关长度等来进行地形再现的方法1 1 5 】。这种方法视地形为一种层次性 的随机统计过程，将分形几何模型与随机点生成技术及实用回归技术相结合， 先利用给定的地形参数，通过模拟符合地形统计特征的随机过程，形成一定 量的用以表征地形骨架的特征点，再进行一定处理，统一为用规则网格分布 形式表示的地形整体骨架，最后利用m p d 方法产生局部细节，完成地形控 制和仿真。 地形生成的最后一步是地形模型的显示，在生成电子游戏使用的地形时 2 曲j e 。i 一业大学坝士学位论文 常使用专用的地形模型软件来制作，较典型的软件是m e t a t o o l s 的b r y c e ，也 有真接使用三维的c a d 软件( 如3 d s m a x ，a u t o c a d 等) 来制作和显示 的。这种方法虽然制作较为方便，但与应用程序结合不紧密。在w i n d o w s 平 台上常用图形开发库o p e n g l 和d i r e c t x 来制作三维图形，该方法使得地形 模型的制作与应用完全包含在应用程序中，因此也要求使用者有一定的三维 图形编程的基础【l “。其中d i r e c t x 虽然提供实时三维图形生成功能，但主要 应用于游戏等低端图形应用程序方面，而o p e n g l 提供了二维和三维的建模、 变幻、光线处理、色彩处理、纹理映射、运动模糊、动画和实时交互等功能， 是绘制真实地形，建立三维交互场景的高性能图形开发工具软件包，与 d i r e c t x 相比，用o p e n g l 来绘制三维地形具有图形质量高、程序可移植性好 等优点【1 7 】。 从以上综述可以看出，地形的真实感和可控性是地形生成研究的两个并 行方向。这两个方向相结合，即生成不仅可视性好，而且能满足一定几何精 度的地形生成方法是地形生成研究的重要发展方向。 1 2 选题意义、研究目的和研究方法 1 2 1 本文的选题意义 计算机图形学的主要研究内容是如何从计算机模型出发，把真实的或想 象的物体画面描述出来。表现具有真实感的图形生成技术一直是这一领域的 重要研究课题。地形生成就是它的个重要研究方向。地形生成技术在自然 景观仿真，地球物理学研究，影视制作及动画游戏等领域中有着广泛的应用。 山脉是一种有代表性的地形现象，是地形生成必不可少的表现对象，因此研 究山脉地形的生成具有重要现实意义。 l 。2 2 本文的研究目的和研究方法 本文的工作就是在上述背景下展开的。本文以分形布朗运动为理论基 础，二维m p d 方法为实现基础，对生成可控山脉地形的方法进行研究，并 将研究方法借助于m a t l a b 和o p e n g l 进行实现，同时又在山脉，云彩的图景 合成方面作了一些研究，实现了山脉和云彩的同窗口显示。 具体实施时，在广泛阅读，分析和理解相关资料与文献，并借鉴已有的 第一章绪论 算法研究成果的基础上，研究解决问题的可行算法。采用理论研究和计算机 仿真相结合的方法进行研究，不断深入细化。在计算机仿真中，充分利用 m a t l a b 编程简洁、调试方便以及具有丰富的图形功能的优点，在原理研究阶 段使用m a t l a b 作为演示验证工具来展示研究结果。在后期，为了进行交互式 操作，即输入参数调控图形的生成效果，必须要为设置的可控参数提供输入 手段，因此又通过v c + + 6 0 制作了对话框。v c + + 支持w i n 3 2 平台应用程序 的开发，具有极为强大的编程功能，另外还可以通过在v c 环境下调用 o p e n g l ，利用o p e n g l 这一图形函数库来实现山脉，云彩的图景合成。 1 3 本文的主要工作及内容安排 1 3 1 本文的主要工作 本文是在大量参考国内外相关文献的基础上，就m p d 方法生成的地形 数据模型不可预知方面进行了一些研究，提出了一种融合曲面的方法来生成 具有预定形状的山脉地形模型。该方法在保持预定形状的同时，其地形表面 也具有m p d 曲面的特征。在融合过程中设置了可调因子，能够针对不同的 目的对生成的地形效果进行调节，如果再结合m p d 方法本身的调控因子， 就能生成更加丰富的地形效果。文中给出了翔实的试验图例对本文方法加以 证明。 为了能够迅速生成融合曲面方法所需的控制源曲面，本文在充分研究正 态分布概率密度函数( 也即高斯函数) 特性的基础上，提出了一种便于使用的 类山包轮廓的地形构建方法。本文称之为高斯造型方法。这种方法以二维高 斯函数的截平面椭圆为控制对象，只需给出椭圆的横纵轴、转角以及中心位 置就可以确定山包的陡峭程度、走势以及位置，再结合高度因子就可以达到 山包的全面控制。这种方法生成图形快速，使用灵活，方便。 高斯造型法对于具有山包特征的山脉地形构建十分有效，但有些山脉不 具有这一特点，例如较平坦的地形或类火山口的地形，用高斯法很难表现， 因此本文还使用了一种插值的方法来构建控制源曲面。这种方法可以生成高 斯造型方法难于表现的曲面，是对高斯造型方法的补充。插值法是通过m a t l a b 的插值函数来实现的。只要构造好初始的低阶数据矩阵，再选择合适的插值 4 西北工业大学硕士学位论文 方式就可以了。 不论是m p d 方法还是融合曲面方法，生成的啦面在局部总会有尖峰， 即使调整控制参数也无法去除，故此本文特别给出了一种具有普遍性的曲面 数据处理方法，局部平滑方法。它不仅可以用来处理m p d 法生成的凸面， 也可以用来处理用融合法生成的曲面，有效的解决了平滑曲面局部尖峰的问 题，使曲面看起来更加真实。 最后，为了使研究方法可视化和可交互操作，本文在v c 6 0 开发环境下， 借助o p e n g l 将数据模型可视化。其间制作了山脉和云彩的纹理贴图，并将 贴图应用在它们的数据模型上，还达到了使二者同屏显示的效果。在本文的 演示程序中给出了线框图( 山脉数据模型) 和全景图( 山脉和云彩的同屏显示) 两种模式，可供查看。在相应的对话框中，还可以输入控制参数，对显示图 形进行调控。为方便查看，又用键盘上的方向键设置了多角度观察的功能。 1 3 2 本文的内容安排 本文共分为五章，前两章是与本文相关的知识背景和基础理论的介绍， 第三、四章是本文生成可控山脉模型方法的实现原理，第五章是数据模型可 视化及图景合成的方法。分别安排如下： 第一章为绪论部分，简要说明本文的选题背景、研究目的、意义、方法 以及内容安排。 第二章概要的介绍分形布朗运动的基本思想和理论知识，实现分形布朗 运动的方法随机中点位移法的原理，这是本文的理论基础。 第三章论述了如何将控制源曲面融入二维m p d 的生成过程以达到生成 既具有m p d 曲面特点又能进行形状控制的目的，同时给出了一种具有普遍 性的曲面数据后处理方法局部平滑法。 第四章针对第三章的要求，论述了控制源曲面的两种生成方法：高斯造 型法和插值函数法，并详细论述了高斯造型法的原理和实现。 第五章首先简要介绍本文程序开发环境，其次论述了山体和云彩的纹理 生成，全景图模型。最后简要介绍了本文的演示程序。 第二章分形布朗运动与随机中点位移法 第二章分形布朗运动与随机中点位移法 2 1 分形布朗运动 2 1 1 分形布朗运动的由来 布朗运动是1 8 2 7 年植物学家r o b e r tb r o w n 发现的。他注意到浮在液面 上的花粉微粒以极不规则的路径运动，其运动轨迹是一条不规则的折线。后 来这被解释为许多微粒通过不断地、连续地碰撞临近的微粒而产生的无规则 的不稳定的随机运动现象。爱因斯坦等科学家对布朗运动进行了数学研究， 最终引出了著名的测定a v o g a d r o 常数的p e r r i n 算法。现在，布朗运动在数 学、物理学、生物学等领域都得到广泛的应用。 描述在自然界中存在的随机分形( 如海岸线、山脉、云彩等) 的最好的数 学模型是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 m o t i o n ) ，它是对布朗运动的推广。在计算机图形学中几乎所有对自然界的 分形模型都是基于i b m 的高维拓展。i b m 已经成为随机分形的理论基础。 2 1 2 分形布朗运动的数学定义 f b m 的数学定义是在w i e n e r 的布朗运动数学定义的基础上给出的，表 述如下： i b m 是定义在某概率空间的一个随机过程x ： 0 r a o ) _ r ，且满足如下 条件： ( a ) 以概率1 ，s ( 0 ) = 0 ，即过程自原点开始。且x ( t ) 是t 的连续函数。 ( b ) 对任何f 0 ，h 0 ，x ( t + h ) - x ( r ) 服从如下分布n ( o ，h 2 “) 眦( f + 旷即) x ) = 击j ：e x p ( 嘉) d u ( 。 h 1 ) ( 2 1 ) 而i b m 曲面的数学定义是上述一维定义的拓展。如果用坐标变量( x ，y ) 代替上述时间变量r ，那么随机变量x ( x ，y ) 可被认为是曲面在点( x ，y ) 的高。 则f b m 曲面定义为在某概率空间上，指数为h ( o h 1 ) 的一个随机过程： 6 西北工业大学硕士学位论文 x ：r _ r 2 满足： ( a ) 以概率l 成立x ( o ，o ) = o ，且x ( x ，y ) 为( x ，y ) 的连续函数。 ( b ) 对任意变量( x ，y ) ，( h ，k ) r 2 ，其二维增量x ( x + ，y + k ) - x ( x ，y ) 服从 期望为0 ，方差为( h 2 + t 2 ) ”的正态分布，其概率满足 p ( z ( x + h , y + k ) 一z ，y ) 力= 1 f 1 i = 亏亍l e x p ( 4 2 厅( h ki 衙西 ( 2 _ 2 2 + 2 、“士。 z l 九+ 七j 一 2 1 3 分形布朗运动的性质 由f b m 的数学定义，可以得到它的若干性质： ( a ) x ( t ) n ( o ，r 2 ”) 只需对式( 2 1 ) 取t = 0 ，再以h 置换r 即可。 ( b ) 式( 2 1 ) 表明x ( t + h ) 一x ( t ) 的分布与t 无关，放f b m 具有增量平稳的特性。 ( c ) 统计自相似性由式( 2 一1 ) 可以推证出p ( x ( t ) x ) = p ( x ( r t ) r h x ) 。 ( d 1f b m 曲面的h a u s d o r f f 维数和盒维数为：d = 3 h 。 f b m 还有其它的数学性质，这里不再赘述。以上的几条性质( 详细证明 见参考文献1 ) 分别与真实地形的数学特征相符，因此公认的结论是f b m 是 摇述真实地形的最好的随机过程。 对于一个分形布朗运动，x ( ，) 是时间变量t 的单值函数，其增量 x ( t 2 ) - x ( t , ) 具有高斯分布，其方差 v a r ( ( x ( t 2 ) 一x “) ) ( t 2 - t t ) ” ( 2 - 3 ) 其中分形参数的范围为：0 h 1 。 当h = l 2 时，由x ( ，) 产生的曲线就是常规的布朗运动。而当日由0 至 l 逐渐变化时，所产生的曲线就表现出由粗糙到光滑的特性，二维分形布朗 曲面也有随变化，其表面粗糙程度发生变化的现象。这一特性和分维数 d 随h 增大而减小有关。 图2 - 1 ( a ) 显示了一维f b m 曲线随h 变化而呈现出不同的形状，最上方 的虚线曲线是h = 0 2 ，中间的曲线是h = 0 5 ，也就是所谓的布朗曲线，最下 方的曲线是h = 0 8 ，此时的曲线较适合作山脉的平面轮廓线。 第二章分形布朗运动与随机中点位移法 o f 育 ( b ) h - - 0 2 4 0 6 08 01 0 01 2 01 4 0 ( 丑) ( c ) h - - 0 8 图2 - 1h 不同取值对i b m 曲线、曲面的影响 上图( a ) 中三条曲线是在同一种子值下得出，( b ) 与( c ) 也有相同的种子值， 因此具有可比性。 2 1 4f b m 的实现方法 严格地合成满足f b m 特性的方法目前已经有很多种，如切变位移法、 分形高斯噪声法、w c i e r s t r a s s - - m a n d e l b r o t 随机函数法等。它们都可以合成 严密精确f b m 函数。然而这些方法并非都可直接应用于计算机地形模型。 在计算机图形学中，一个好的地形模型必须具有高效的时间和空间效率，同 时模型结果还需具备好的视觉效果。甚至为了算法的简洁性和适应性，牺牲 部分f b m 的部分数学特性也是可行的。因此图形学中在上述合成技术上又 8 4 3 2 1 西北工业大学硕士学位论文 发展起来一些分形模拟方法，如泊松阶跃法( p o s s i o nf a u l t i n g ) 、逆傅立叶变 换法( i n v e r s ef o u r i e rt r a n s f o r m a t i o n ) 、逐次随机增加法( s u c c e s s i v e r a n d o m a d d i t i o n ) 、多重线性细分法( m u l t i l i n e a rs u b d i v i s i o n ) 、m p d 法等。p s 法和i f t 法由于计算代价太大已经较少应用，应用较多的是m p d 、s r a 和m s 法等， 其中m p d 法由于计算量小且实现容易而成为地形模拟中非常实用的方法。 下一节将对m p d 法作详细介绍。 2 2 随机中点位移法 2 2 1 随机中点位移法蟓理 随机中点位移法是一种直接模拟i b m 的方法。此方法是对线段中点处 高度进行位移，将位移的高度值作为该中点值，然后将分割的线段再细分出 中点，并加以中点偏移，如此反复，直到达到预定的迭代层数。 m p d 的中点位移量可由式( 2 3 ) 和m p d 的定义导出。已知x ( o ) ：0 ， x o ) 是均值为0 ，方差为盯2 的随机样本，设 x ( 圭) = 圭( z ( 1 ) + ( o ) ) + d 1 ( 2 - 4 ) d 1 是均值为0 ，方差为2 的随机变量。依式( 2 - 3 ) 有： v a r ( x ( t d x ( t i ) ) = ( f 2 - q ) 2 ”盯2( 2 - 5 ) 由式( 2 5 ) 可得 v a t ( x ( 1 ) - x ( o ) ) = 盯2( 2 - 6 ) 州z ( 圭) 一硎) ) = ( 护d 2 ( 2 - 7 ) 综合式( 2 - 4 ) 、( 2 - 5 ) 、( 2 - 7 ) 可得 j = 4 ) 2 ”( 1 2 ( 2 _ l 】r 一2 ) 仃2 ( 2 8 ) 由式( 2 4 ) 可计算x ( 圭) ，同理，以z ( 圭) 为新的起点计算x ( 丢) ，依次类 9 第二章分形布朗运动与随机中点位移法 推，最后可得到当f = ( 圭) “时 = ( 去) 2 ”( 1 2c 2 ) 仃2 这样在确定了叠后，就可以用m p d 算法来产生i b m 曲线了。 2 2 2 二维随机中点位移法的构网形式 ( 2 - 9 ) 用上述的m p d 算法生成的一维i b m 曲线，可用于模拟地形断面，而 将其扩展n - 维，就可以用来处理规则网格的地形数据，产生任意分辨率的 地形模型。用m p d 进行地形模拟时存在一个构网方式( 也即细分方式) 问题。 常用的构网方式有：三角形网、参数方块网和菱形一方形网( d i a m o n d s q u a r e ) ，以及多重线性细分法。 2 2 2 1 三角形网和参数方块网 三角形网是对三角形各边进行等分，再将各中点连接起来，这样就由 一个三角形变成四个三角形，然后再在新产生的中点，也就是原三角形各边 中点上增加一个高斯随机变量。 ， 上 么。斗 圈2 - 2 三角形嗣和参数方块霸的掏罔方式 图中。为1 3 次迭代点，为n + 1 次新产生的点。 参数方块网与三角形网构网方法相似，三角形网是在边线上不断取中 点，并总是用相邻两点来计算中点，只与两点有关，而参数方块网是先由方 块的四个顶点计算中心点，再由边线上的相邻两点计算中心点，是四点和两 点交替进行的。参数方块网是上下相关的，而三角形网是上下无关的，参数 方块网比三角形网更接近m m 曲面。图( 2 2 ) 中示意了这两种网格的构网方 1 0 荫北工业大学硕士学位论文 式。 参数方块网与三角形网这两种构网方式都可以用递归的方式来实现， 但由于相邻两个三角形或方块都是独立进行处理，没有参考相邻的网格，因 此中点在高程上的位移量不同，会出现不匹配的边界，产生裂缝。可从图2 3 ( a ) 中看到这一现象。使用时可以用处理产生随机数的种子值解决【1 9 l f 2 ，使得 公共边中点位移量具有相问的高程值，从而保持协调。 ( _ ) 参数方块网递归法生成的山脉( b ) 菱形一方形网生成的山脉 2 2 2 2 菱形一方形网 图2 - 3 各种构网方式效果图 菱形一方形网的构网方式比参数方块网又进了一步。只有边线上的新 产生的点与3 个点相关，内部点都与周围4 点相关。 j ，b t二j ， 忒j ，t 图2 - 4 菱形一方形构网方式 首先给定初始网四角点的值，以。示出，表示已有值。再由四角点均 值加上偏移量计算出中心点值，以示出，表示新生值。然后由中心点和两 角点，即用已有值的三个近邻点计算出边线中点值，以口示出。完成第一步 第二章分形布朗运动与随机中点位移法 迭代，网格由l 1 变为2 2 。 在第二次迭代中，重复上面的步骤得到四个点( 由其紧邻四个o 点得 到) ，以及由紧邻三点计算出的外围边线上的八个口点。最后对内部四个网 格交叉点，按照菱形取点( 图2 - 4 ( 2 ) q b 用双点划线示出) ，用已有值的四个 紧邻点( 两个。点和两个点) 取均值再加上偏移量计算得出，这时2 2 网 格变为4 4 网格，完成第二步迭代。随后按照上面的方形一菱形步骤不断 迭代，直到达到需要的迭代深度( 分辨率) 。 上面每步所加的偏移量是一个具有高斯分布的随机变量，其方差为 1 = ( 去) “盯2( 2 - l o ) z 每一步的计算可用下式概括： 以( 王y ) = ( 五y ) + g a u s s o ( 2 - 1 1 ) 其中五仁，圳表示当前点向，纠值。z 向，表示取均值步，视点似所在位 置，可能为三点均值，也可能为四点均值。g a u s s ( ) 表示高斯随机数。 图2 - 4 示意了菱形一方形的构网方式。图2 - 3 ( b ) 给出了用菱形方形法生 成的山脉效果图。 2 2 2 3 多重线性细分 多重线性细分严格来说以不是中点位移法，但是它的思想和中点细分 类似，所以也有把它归入中点位移法的。这种方法的实质是内插点的值是周 围点按距离的加权平均。 ，一 9 、 3- 一。 一一一 ， 、 | 3 | 1 ( a ) 4 2 图2 - 5 多重线性细分 图2 - 5 ( a ) 中示意了m i l l e r 的块一块细分，内插点值是周围四角点的值按 1 2 西北工业大学硕士学位论文 权9 ：3 ：3 ：1 来计算的。距离近的点获得较大的权值。以图中示意点为例： x = 竺x 3 + 三x4 + 三x2 + x k(2-12161 61 61 6 、j l 这种方法能产生双二次曲面的效果，也正因如此，曲面的轮廓较柔和。事实 上，这种方法可以推广到更为一般的多重线性细分情形。如图2 - 5 ( b ) 中所示。 x = ( 1 一d x ) o a y ) 爿0 0 + ( 1 一a y ) d r x 0 1 + ( 1 一a x ) a y x l o + d x d y x l l ( 2 - 1 3 ) 式中0 出，a y l 。当然计算出的点值还要加以偏移量。 图2 - 6 多重线性细分法推广 在实际应用中具体使用那种细分方式视具体需要而定，如三角形细分， 以其诱人的速度和为现有形状增加细节的能力，而成为一个面向某些应用的 很有用的分形算法【1 9 i 。其他细分方式也各有其适用的场合。 第三章预定形状的山脉地形生成方法 第三章预定形状的山脉地形生成方法 3 1m p d 方法与曲面造型方法对山脉地形的控制 3 1 1 m p d 方法对山脉数据模型的控制 在现有的多种分形布朗运动的实现方法中，m p d 方法因为算法简单， 易于实现且执行速度快而得到广泛应用。但使用这种方法生成数据模型的过 程是依照网格细化规则自动执行的，在给定分形参数h 和初始方差仃2 的情 况下，山脉数据模型随着随机数发生器种子值的变化而变化，每一次都呈现 出不同的形状，这是由于不同的种子值对应着不同的随机数序列。如果给定 随机数发生器的种子值，那么山脉形状将会固定下来，但对于一个给定的种 子值将生成一个什么样的山脉形状仍然是无法预知的。只有通过大量的试验 才能找出一些基本形状和轮廓符合要求的分形图形，有时甚至找不到这样的 图形。这就给它在某些要求限制地形大致形状的场合中的应用带来限制。 调整分形参数h ，可以调整山脉的地表粗糙或平滑的程度。当h 在区 间( o ，1 ) 上递增取值时，相应的山脉数据模型的形状将会由“粗糙”逐渐变得 平滑。这是由于h 与分维数d 的关系而致。 1 、n h 砖= i 去| 盯2 ( 3 1 ) 由式( 3 - 1 ) 可知，在每步迭代中，中点的随机偏移量的方差叠与初始方 差盯2 成线性关系，且盯2 在整个迭代过程保持恒定，它对数据模型的影响与 h 值改变所导致的丰富变化相比有限的。 3 1 2 曲面造型方法对山脉数据模型的控制 最简单的山脉数据模型是由一些稀疏分布点的高程值构成若干简单的 三角形平面，形成地形框架再依三角形贴以山脉纹理图。这种方法可以通 过对稀疏点的位置和高程设置达到控制的目的，但由于所形成的框架过于简 略而使得最终图形的卡通效果十分明显，地形的真实感受到影响。也有人使 用一些样条函数插值和曲面拟合的方法对数据点进行拟合，形成光滑的连 1 4 西北工业大学硕士学位论文 接，改善了卡通效果，但这种方法对地形细节的不规则性方面就无能为力了- ， 而这正是真实地形的特点所在。为了增加逼真的效果，人们在拟合出的曲面 上施以扰动修改，形成了真实感较强的地形表面。所采用的扰动方法有分形 插值法和多分辨率随机松弛法( m u l t i r e s o l u t i o ns t o c h a s t i cr e l a x a t i o n ) 等。其 中分形插值法是利用i f s ( i t e r a t i o nf u n c t i o ns y s t e m ) 方法构造的分形插值函 数。多分辨率随机松弛法直接结合样条曲面的构造，要求用能量优化方法构 造样条曲面，实现起来计算量大，较为复杂。 3 2m p d 方法与曲面造型方法结合融合曲面法 3 2 1m p d 方法与曲面造型方法的结合 m p d 方法能够随着迭代层数的加大不断地快速生成地形细节，曲面造 型方法可以通过对曲面的设置达到控制的目的。因此考虑如何能够把两种方 法的优点结合起来，达到生成的数据模型既可控制又有地形细节的目的。本 文就是基于这种思想提出了一种综合的方法，既有可控性又不失随机性，是 一种介于完全可控生成和随机生成之间的方法。过程如下： 图3 - 1 数据模型的可控生成方案 本文方法首先是建立一个控制源曲面，在这个曲面上完成对山脉数据 模型的控制要求。对于如何建立控制源曲面的方法，将在下一章中叙述，本 章主要叙述m p d 方法是如何融入数据模型的。 3 2 2 融合曲面的基本原理 在已经具有大致地形形状的曲面上，如何将m p d 方法融入其中呢? 在 通常的二维m p d 方法中，如果我们设数据网格中的某点( 置y ) 的高程值为 z ( x , y 1 则 z ( 蕾y ) = ，( 五y ) + d ( 五y )( 3 - 2 ) 其中d ( x , y ) 是点( 墨y ) 处的随机偏移量，它是个均值为0 ，方差为盯2 的 第三章预定形状的山脉地形生成方法 高斯随机变量。而f ( x ，y ) 是点( 五y ) 周围四邻点的均值， f ( x , y ) = 堑业型堑业业导塑型丝幽( 3 - 3 ) 我们将具有大致地形形状的曲面作为控制源曲面，并令它和最终的要 生成的数据模型矩阵具有相同的行列数。在二维m p d 方法中，设生成的矩 阵为n 聆矩阵，( h 为行列数) ，那么疗与总迭代层数m a x l e v e l 的关系是 r l = 2 “+ l 。这样控制源曲面的数据点与二维m p d 的数据点是一对应 的。 设控制源曲面的数据矩阵为y ，其上某点y ( x ，y ) ，则r ( x ，y ) 与用二维 m p d 方法生成的对应数据点存在一个差值，设这个插值为o f f s e t ，即 o f f s e t = y ( x ，y ) 一z ( x ，y )( 3 - 4 ) 我们就利用这个插值来融合控制曲面与二维m p d 曲面。具体公式为 x ( 置) ，) = z ( y ) + w o f f s e t( 3 - 5 ) x ( x ，j ，) 是最终点的高程值，w 是权因子。显然，当w = 0 时， x ( x , y ) = z ( 础) ，当w = l 时，x ( 础) = y ( x , y ) ，而当w 在0 和1 之间变化时， 如果w 一0 ，则x ( x ，y ) 会更接近于z ( x ，y ) ，也就是说最终得到的曲面会更 接近于二维m p d 曲面。如果w 斗1 ，则x ( x ，y ) 会更接近于y ( x ，y ) ，也就是 说曲面会更接近于控制曲面。当w 在1 2 附近时，曲面为控制曲面与二维m p d 曲面的均值。 砸棚= 塑学( 3 - 6 ) 在生成曲面的过程中，如果w 取固定值，最后得到的曲面数据就是两个 曲面数据的加权平均。这样，生成的曲面尽管具有了和控制曲面类似的形状， 但是表面十分粗糙。尖峰和凹陷随处可见，类似于噪声曲面。 1 6 西北工业大学硕士学位论文 ( a ) 控制源曲面 ( c ) w = 0 8 图3 2w 不同取值的效果 ( b ) w = 0 2 ( d ) w - - 0 5 3 2 3 初始迭代数据的影响 如果使w 随迭代层数变化会有怎样的结果呢? 我们知道在二维m p d 算 法中参加初始迭代的数据值是非常重要的。它对最终山脉数据模型起了决定 基本形状的作用。这是因为m p d 方法每次迭代的结果图形是由上一次迭代 的结果图形和随机位移量共同决定的，这样我们可以通过给出初始迭代数据 矩阵来控制生成图形的基本形状和轮廓。由于会随着迭代层数的增加而 减小这一事实，初始迭代数据将会对生成的结果图形产生较大影响。 以迭代层数m a x l e v e l = 6 为例，开始给定4 个网络角点的值，第一次迭 代生成了3 3 的数据矩阵。第二次迭代生成了5 x 5 的数据矩阵。如果给定 5 5 的初始迭代矩阵，在这个基础上继续使用二维m p d 方法的话，那么最 终的结果曲面将是具有初始5 5 迭代矩阵勾勒出的曲面外形特点。如图3 - 2 1 7 第三章预定形状的山脉地形生成方法 所示，其分形参数h - - - - - 0 8 ，盯2 = 1 ，给定的初始迭代矩阵五取值如下 x o = 0 0 1o 5o 6 5 0 522 o 6 521 0 522 o 0 1 o 5 0 6 5 0 5o o l 2o 5 2o 6 5 2o 5 0 5 0 o l 凰的数据反映出这是个中心低周围高的类似火山口的图形，从图3 - 3 ( a ) 可以看出这个特点。迭代完毕后的6 5 6 5 数据矩阵图形保留了这一特点。 因此这种给定初始迭代矩阵的方法能够达到控制的目的。但是它供操作的余 地不大。在给定5 5 矩阵时，有2 5 个数据可以用做控制设计。但就设计某 一形状而言，它显得粗糙稀疏。倘若再给更多的控制数据，如9 9 矩阵， 又会使得输入数据太多而使用不便。 ( _ ) 初始数据圈( b ) 迭代结果圈 图3 - 3给定初始迭代矩阵的生成效果 3 2 4 融合曲面的效果调节 从上面的讨论可以看出，初始数据对二维m p d 方法生成曲面的影响很 大。考虑将这一结论应用于式( 3 5 ) ，那么这个公式还可以变形为： x ( x ，y ) = f ( x ，y ) + o f f s e t w + ( 1 一w ) d ( x ，y )( 3 7 ) f ( x ，y ) 定义见式( 3 3 ) ，而o f f s e t 定义如下： o f f s e t = y ( x ，y ) 一f ( x ，y )( 3 8 ) 这样就使得d ( x ，y ) 由z ( x ，y ) 中分离出来，便于在编程中实现。 我们知道在控制源曲面r ( x ，y ) 和= 维m p d 曲面z ( x ，y ) 的融合中，如 西北工业大学硕士学位论文 果保持一个固定的权因子，得到的曲面效果粗糙。同时参与二维m p d 方法 的初始迭代数据很重要。如果使w 随迭代的进行，也就是迭代层数的深入而 变化，当开始迭代时w 取的较大，会使曲面接近控制源曲面y ( x ，y ) 。随着 迭代层数的加大，令w 逐渐变小，又使得二维m p d 的曲面效果能够凸现。 这样就使控制源曲面能够融入二维m p d 的曲面生成过程中，而非简单叠 加。实践证明这样的效果要好得多。 图3 _ 4融合曲面 对于w 的取值，可以使用如下公式， w = ( 型m a 娑x l e r e l 署厂 ( 3 - ，)w 2 i 一l l j yj 一i ， 式中s t a g e 为当前迭代层数，r a t e 为扰动因子，m a x l e v e l 为总迭代层数。 若不考虑扰动因子r a t e ，即令r a t e = 1 ，以迭代总层数m a x l e v e l = 6 为例：当 s t a g e 由l 增加到6 ，得到序列为( 1 o 80 60 4 0 2o ) 。可以看出，w 取值达到了在开始迭代时取最大值l ，以体现控制性，而随着迭代层数 s t a g e 的增加，w 也随之减小，直到o ，使随机性的体现逐渐加强。 由于控制源曲面各有不同，为了能够对融合效果进行调整，加入了扰 动因子r a t e ，调整r a t e 大小可以使w 的变化加速或减缓。例如r a t e = 2 时， w 序列为( 1 o 6 40 3 6o 1 6o 0 4 o ) 。与r a t e = 1 时的w 序列相比，明 显要减小得更快一些，最后融合曲面体现的随机性就更强一些。这样，调整 r a t e 便可对融合效果进行调整，如果再配合分形参数h 因子的调整就可以 1 9 第三章预定形状的山脉地形生成方法 使总体效果更加理想。 3 3 局部平滑处理 3 3 1 局部平滑处理方法 不论二维m p d 方法还是融合曲面控制方法，生成的曲面在某些地方会 有一些小尖峰，虽然不影响总体效果但是给人的感觉还是不够自然。显得租 粝。图3 - 3 ( b ) 以及图3 - 4 都反应了这一特点。虽然调整分形参数h 能够减轻 这一现象，但有些时候，即使调整h 也难以将尖峰去除，因此考虑了一种 能够将这些尖峰去除而又不使算法复杂的方法局部平滑处理。其实质是 采用有条件判断的局部平均。 对于迭代网格中某点o ( x ，y ) ，它周围有8 个点，设与它处在同一网格 线上的四个点a 、b 、c 、d 与0 点的差值和为s u m o f f 。 s u m o f f = i ( z 。一z o ) + ( 乙一z 0 ) + ( z c z d ) + ( z d z 0 )