三维随机分形地形生成

1、原文： HYPERLINK /fractal.html目 录说明：本页所有图像均经过优化以减小尺寸，所以与实际图像会有细微差别。1.第一部分：生成随机分形地形1.介绍2.自相似3. 一维中点变换4.高度图5. Diamond-Square 算法6.蓝天白云7.其它算法2.第二部分关于例子源码1.安装快速起步使用程序代码结构下载源码Visual C+工程，使用SGI实现的OpenGL（单击标题下载）参考终于找到这个SGI OpenGl 地址了： HYPERLINK /tools/ocx/ocx_image/opengl2.exe /tools/ocx/ocx_image/opengl2.exe介

2、绍十年前，我参加 1986 年 SIGGRAPH 活动，Gavin S. P. Miller 那篇题为 Definition and Rendering of Terrain Maps的论文让我充满敬畏。该文描述了少数生成分形地形的算法，作 者还介绍了一个他们认为更先进的新方法。开始我被这些算法能够生成难以置信的风景图所震惊！（尽管这些算法被作者认为“漏洞百出”） 后来，读过论文，这些算法之简单将我完全打败了。我从此成为一个分形地形迷。算法背后的数学可能相当复杂。然而，完全理解这些数学并不是掌握这些算法的必要条件。很好， 否则我得在解释算法之前讲解所有的数，也许永远也讲不到算法。此外，关于分形

3、数学的文字材 料数以吨计，参见本文本的参考部分会有所帮助。同样的原因，我不会深入到数学细节，也不包括对分形的广泛总览及它们可被用来做的每样东西。 相反，我将描述分形地形生成背后的概念，并集中仔细讲解我个人最喜欢的diamond-square” 算法。我将演示如何使用这个算法静态拼嵌高度数据数组，这些数据可用于几何地形数据、地形 纹理数据及云纹理映射。分形有什么用呢？假定你已经知道，那正是你读本文的原因。随机地形图对飞行模拟或制作背景 纹理图(如显示一带远山)十分有用。生成地形的算法也可用于生成部分云天的纹理图。在继续之前，申明一下：我不是游戏程序员。如果你为找到一个快速绘制地形的算法而读此文，

4、 那你来错了地方。我只描述生成地形模型的过程。着色绘制是你自己的事。自相似任何分形最关键的概念是自相似。当一个物体的一部分放大后看起来仍与整个物体一样，那这个 物体就是自相似。考虑一下人体的循环系统。这是自然界中自相似的好例子。从最大的动脉和静脉分支直到最小的 微血管，整个过程都显现相同的分支模式。如果你不知道正在使用显微镜，将无法分辨微血管和 大动脉。现在再考虑一个简单的球。它是自相似的吗？不！大幅度放大后，它看起来不再象一个球，而象 块平板。如果你不相信，看看户外。除非恰好你在太空轨道上看本文，否则将完全没法看出球是 个球体。球体不是自相似的。它最用传统的欧几里德几何描述而不是分开。地形属

5、于自相似范畴。手掌上的碎岩锯齿状边缘与远处地平线边的山脊有相同的不规则形状。这 使我们可以用分形来生成地形，不管显示时怎么放大，它看起来仍然象地面。关自相似请注意：严格意义下，它意味着自分辨(self-identical)，即，自身精确的缩略拷贝在 逐渐放大缩小时可见。我并不知道自然界存在任何自分辨分形。但mandelbrot集是自分辨的。 我不会进一步讨论Mandelbrot集。到参考里找进一步的信息。一维中点变换后边要讲的diamond-square算法，在两维上使用一种中点变换算法。为帮助你了解个大概， 我们先看一维情况。当山脉出现在远处地平线处时，一维中点变换是绘制山脊的好算法。看看它

6、是怎么工作的：以一条水平地平线段开始重复足够多次对场景中的每条线段做找到线段的中点在Y方向上随机移动中点一段距离 减小随机数取值范围将随机数值域减速小多泊呢？那取决于你想要分形的陡峭程度。每次循环减少的越多，所得山脊 线就越平滑。但如果减得太多，则会有明显的锯齿感。可以粗糙度存在一个常量里。后面会解释 如何做。来看个例子。我们以一条x从-1.0到1.0，y均为0的线段开始。开始，我们将随机值 范围设为-1.0到1.0 （可任意取）。这样我们在此范围里生成一个数字，并将中点移动这么 多。这之后，我们就得到了：现在第二次经过外圈循环，我们有两段，长度均原来的一半。我们的随机值也减半，即 -0.5到

7、 0.5。我们为两个中点都生成一个这个范围内的随机点，结果为：再次缩减范围，现在是-0.25至IJ 0.25。再以该范围内的数变换四个中点后，我们得到了：有两件事你可能已经注意到了。首先，它是递归的。实际上，它可以用一个迭代过程相当自然的实现。对于这种情况，递归或迭 代都成。对于表面生成代码，使用迭代实现比递归会有一些好处。所以为保持一致，线和面相应 的代码都使用迭代实现。其次，它是个非常简单的算法，然而你能创建非常复杂的结果。这正是分形算法的美妙之处。一 些简单的指令可以建立一个具有丰富细节的图像。再跑一下题：少量简单的指令集能够生成复杂图像的事实已经成为一个新的研究领域称为分形图 像压缩。

8、其思想是保存建立图像的递归指令而不是保存图像本身。这对于自然界的分形图像是极 有用的，因为指令相对图像占用的空间要少得多。Choas （混沌）与Fractals （分形）new Frontiers of Science有一章及一个附录涉及本主题，是一般学习分形的好读物。回到现实。不用太费劲，你可以读取本函数的输出到一个绘制程序而得到类似如下的东西：这可作为窗口景色使用。相关的好东西是它是约束的，所以你可以保留一个相当的小图像并用它 拼出整个场景。如果你不介意在每个方向都看见相同的山，那就这么干。好的，在进入2D分形表面之前，你得了解粗糙度常量。这个值决定每次循环随机数值域的减少 量，也就是说，

9、决定分形结果的粗糙程度。例子代码使用一个0.0到1.0之间的浮点数并称之 为H。因此2（-h）是1.0（对于小H）到0.5 （对大H）范围内的数。随机数范围在每次 循环时乘上这个值。如果H设为1.0，则随机数范围将每次循环减半，从而得到一个非常平滑 的分形。将H设为0.0，则范围根本不减小，结果有明显的锯齿感。下边是三个山脊，每个用不同的H的值绘制：高度图上边所说的中点变换算法可以用一个一维数组实现，数组成员是表明线段端点垂直位置的高度值。 这数组是就是一个一维高度图。它将索引（x值）映射为高度值（y值）。为模拟随机地形，我们想将该算法推广到3D空间。为做到这一点，我们需要一个两维高度值数 组

10、，它将索引（x,z）映射为高度（y）。数组只需保存高度值（y）。水平面值（x和z）可以在 分析数组时即时生成。通过对每个高度指定一个颜色，可以将一幅高度图显示为一幅图像。如下，高点为白色，低处为 黑色。绘制高度图的方法对于生成云彩纹理图是很有用的，后边还会讨论。这种表达也可以用于播种一 个高度图。现在我要讲讲如何拼嵌我们的二维高度图数组。Diamond-Square 算法正如本文开头提到过的，我先介绍Gavin S.P.Miller的论文中随机地形生成的概念。具有讽刺 意义的是，Miller在论文中说diamond-square算法是有缺陷的，然后描述了一种完全不同 的基于重量平均和控制点的算

11、法。Miller对diamond-square算法的抱怨阻止他尝试迫使该算法建立一座山，也就是，带有一个 山峰，人为增加网格中心点的高度。他让数组中所有的点都随机生成。如果 Miller简单的只随 机生成中心点，那么即使是他也会同意该算法是个经典的地形生成器。 Diamond-Square算法 可以通过给数组播种值来用一个山峰推出一坐山。比数组中心点更多的点得先播种以构造可接受 的结果。他也抱怨一些固有皱折问题。但你得自己判断。算法最初是由Fourniew，Fussell和 Carpenter 提出的。思想如下：你从一个很大的空2D数组开始。多大呢？为简化起见，他应该是方的，维数应该是 2的n

12、次方加1 (如33X33,65X65,129X129等)。将四个角设为相同高度。如果你察看 所得到东西，它是一个正方形。取个简单的例子，用一个5X5的数组。(本文后面还要参考这图，别忘记了)。图中，图a的 四个角种上了初始高度值，表示为黑点。这是递归细分过程的起点，该过程分两步：diamond步：取四个点的正方形，在正方形中点生成一个随机值，中点为两对角线交点。中点 值是平均四个角值再加上一个随机量计算得到的。这样就得到了一个棱锥。当网格上分布着多个 正方形时有点象钻石。square步：取每个四点形成的棱锥，在棱锥的中心生成一个随机值。平均角值再加上与 diamond步相同的随机量，计算出每条

13、边中点值。这又给你一个正方形。这样，如果已经生成了一个种子正方形并经过单独一次细分过程将得到四个方形。第二次经过该 过程得到16个方形，第三次得到64个方形。增长得很快。方形数目等于2( 2 + I )，其中I为 递归经过细分过程的次数。参考前五幅插图，下图示意了使用我们的diamond-square算法两次经过数组时发生的情况。对于第一遍经过diamond步时，我们依据四个角的值在数组中心生成一个值。我们平均四个角 的值（如果种子值相等则完全没必要），并加上一个-1.0到1.0之间的随机值。在插图b中， 新值显示成黑色，已经存在的点显示为灰色。对于square步，我们在相同的范围内生成随机值

14、。这一步时有四个棱锥；他们在数组中心相交， 这样我们计算四个diamond中心。diamonds的角被平均以找出新值的基数。插图C用黑 色显示新值，现存值为灰色。以上是第一遍，如果用线将这9个点边起来，就可以得到一个线框的表面，看起来就象:现在进行第二遍。再次从diamond步开始。第二遍与第一遍有两点不同。首先，我们现在有四 人四边形面不是一个，因此我们得计算四个方面的中心。其次，这是关键，生成随机数的范围已 经被减小了。因为例子的缘故，让我们认为正在使用一个H = 1.0的值。这将把我们的随机数取 值范围将从（-1.0,1.0）至U （-0.5,0.5）。在插图D中，我们这一步计算得到的四

15、个正方形中 心值显示为黑色。最后，我们进行第二遍的square步。有12个棱锥中心，我们现在需要计算12个新值，如 图e中黑色所示。现在数组中全部25个元素都已经生成。我们可以得到如下的线框曲面。如果分配更大的数组，我们可以进行更多遍，每一遍加入更多细节。例如，5遍之后表面看起来如下所示：前面提到过，数组维数需要为2的整数次方加1。这是因为2D数组中的浮点数必须等于 (2n+1)2。8次迭代将需要一个257X257的浮点数组，对于标准的32位IEEE浮点数来 说超过256K内存。好了，它就是这么大。用char取代floats会有所帮助。例子程序使用floats，但你要真的 关注内存使用那么使用

16、char。修改例子使用之使用-128到128的范围是很容易的，但别忘 了将你生成的值限定在-128至U 128范围里，子序列通过时会生成该范围以外的值，这会导致 溢出。这在使用较小的H时尤其可能。例子程序演示了处理尺寸的另外一种方法。用一个大数组依据diamond-square算法进行定位 及拼嵌。然后从平行投影体顶视图进行绘制。这个图像被读回来并用作已经拼嵌成较小范围的第 二个数组上的纹理图。然而，例子程序并没有这样做，一但图像从帧缓冲读回，第一个数组就被 释放了。这有个纹理图的例子：该图经过人工着色，山峰为白色，山谷为绿色，两者之间为灰色。尽管利用例子程序源码试试自 己的配色方案。早先还到

17、过用迭代实现这个例程比递归好。原因是：一个递归实现可能翻采用如下形式:执彳亍diamond步；执行square步；减小随机数范围调用自己四次。这是个很简洁的实现，而且毫无疑问它能工作。但它要求用不充足的数据生成某些点。为什么呢? 经过第一遍之后，你将再次调用以执行square步，但这时并没有一个棱锥四个角的全部数据。与之相反，我用个迭代实现，伪码如下：当square边长度大于0时遍历数组，对每个正方形表达执行diamond步遍历数组，对每个棱锥表达执行diamond步减小随机数范围这样就消除了递归实现中出现的棱锥角丢失问题。但在生成数组边界的点时还是会碰到这个问题。 下图中，数组中构成棱锥角的

18、位置用亮灰色表示。它们应该被平均以找出新的基本值，即图中黑 色的点。注意用黑色标记的两个值。它们实际上是相同的值。每次你在square步计算一个边界上的值时， 记得同时把它保存在数组对面边上。这意味着前面插图e中，我们实际上不必计算12个单独的值，因为其中的四个在数组相对的 两条边上重复。实际上只有8个值需要计算。感兴趣的读都可以练习一下：取出源代码并使用它在边界的值不重复时也能工作。这对算法正常 工作是没有必要的，按我写的方式去做就成。如果你还没运行过例子程序，现在或许是时候打开看看了。它从两次迭代生成的曲面开始。曲面 是用线框绘制的，只是简单的将数组中的值用线段边接起来。数组中的值被当作

19、Y值，而X和 Z坐标是在数组分析时即时生成的。通过将一个方形分成两个三角形可以轻易的使用三角形绘制 出这个曲面。三角形通常都是很好的图元，因为它总是凸性的平面。用View Opeions对话框调节 RAndom seed值。这会导致生成不同的曲面。调高iterations值给曲面增加细节。代码限制这个值到10，这对于我32M内存的 PentiumPro系统有点多，看起来是黑的（或许五年以后，人们会在新的处理器和更高分辨率的 显示器上运行这个程序，会对我为什么将它限制到10十分奇怪的）。第一个H值控制表面粗糙度，默认值为0.7。试着设得更高或更低看看结果如何。是的这个算法偶尔会产生局部尖刺或皱折

20、。但我偏爱尖或皱折不明显依赖于观察角度或飞过它的 速度这种超自然的效果蓝天白云现在我们知道如何生成表面。我们可以生成并着色大量的三角形，也可以生成一个高分辨率的纹 理图并将它应用到低分辩率的表面。不管怎样，效果相当好。那么，我们怎么生成头上的天空呢？ 它比你想象得要简单。diamond-square算法拼嵌完成的数组非常适于表示云天的纹理图。与把数组看作一套高度图上 的y值相反，把它看成云的不透明度数据。最小数组值代表最蓝。天空中最晰的部分，最大的值 代表最白，天空中云最重的部分。分析数组并生成如下的纹理图是相当琐碎的：这与前面的高度图很象，但我已经限定了高、低值以建立清晰有云的天空。也可以用

21、例子程序生成一幅类似的图像。设置 Select rendering type下拉菜单为2D mesh/clouds。（默认时看起来有像素感，试试把Cloud iterations值设为8以上修正之）。 试试给这H赋不同的值（就是前面刚说过的Cloud iterations值），以取得不同的云的效果。如果回到本文开头，第一幅图结合了许多我在这做的讨论。天空是用一个如上的纹理图作的，沿 一个八边金字塔重复排放多次曲面几何体用一个高分辩率纹理图绘制。这个纹理图是通过从一个 平行顶视图着色一个高度拼嵌有光照曲面而生成的。然后，这个图被读出用作纹理图。跟随本文的例子程序被用于生成本文中出现的几乎所有图像

22、。其它算法可能会想对曲面生成有比样本代码更多的控制。例如，可能想用自己的值给数组的前几遍初始化 种子值，这样，山、谷可以基本位于你设计的位置。然后用diamon-square算法填写其它 细节。修改代码，使之在赋值时略过已有值的数组成员是易于完成的。初始化数组为，例如，-10.0， 给前几遍指定自己的值作为种子，再增强分形生成代码只给当前值为-10.0的赋值。简几遍将 不会生成任何值，因为你的种子值已经在那儿了。后续几遍将在种子值在基础上生成新值。如何取得种子值呢？如果想要的形状遵循某个已知的数学公式，如正弦曲线，就用这个函数生成 值。否则，你得找出创造性的方法完成。我见过的一种算法是用灰度值

23、绘制自己的高度图。将灰 度映射成高度值并存入数组。再用diamond-square算法增加更多细节。除了 diamond-square算法，还有许多拼嵌表面的方法。用连续随机增加，2D数组的一个随机部分增高一个很少的量。反复多次，对所选中的数组区域 加上一个很小的随机值。这可以生成相当不错的结果，但不是线性计算的。如果计算时间无所谓， 那么建议试试这个算法。一另一个相似的方法，制造一个穿过数组的 折断”，并增加其中的一边，就象地震出现一样。再 重复多次。这也不是一个线性算法，要多遍才能取得可以接受的结果。参考参考文献以了解更多其它途径。第二部分关于例子源码安装这个例子源码放在一个zip文件中，

24、用你惯用的解压缩软件打开。如果你没有zip工具，试试 HYPERLINK 源码使用OpenGL API绘制。如果你的机器上没有则请下载一个。注意 本程序认SGI实现的OpenGL，注意文件名。快速起步启动Fractal例子程序打开View Options对话框从 Select render type 下拉菜单选 2D mesh/renderd将Interations值改为4将Tile值改为3。使用程序自己试试就知道了。代码结构fractmod.c和fractmod.h是本例子程序的核心C代码。它构成分形生成模块。CFractalExampleView 类是从 1996.12 期M$ Journ

25、al: HYPERLINK /msj /msj 发现的 COpenGLView 类衍生的。COpenGLView 类由 Ron Fosner 写成，他说这是他 fully-blown COpenGLView 类的精简 版。要真正看懂，去买他那本由 Addison-Welsley出版书：OpenGL prgramming for windows95 and windows nt 。COpenGLView 有一个 RenderScene 虚成员，我们在 CFractalExampleView 里重载之。这里将完成主要的绘制工作。函数先检查Rendering type的设定。当设为2D mesh/l

26、ines or 1D midpoint displacem ent时，工作由RenderScene完成。否则，别的函数被调用。CFractalExampleViewe:OnViewDialog 生成 View Options 对话框，并处理设置及在 CFractalExampleView与对话框类间提取数据。CFractalExampleView:OnInitialUpdate 管理设置所有 CFractalExamleView 成员变量 为其默认值（含对话框值）。实际上关于代码是如何工作的并没有太多可解释的地方。我假定你是一个能干的程序员，且我已 经尽力给代码加上详细的注释。如果你不熟悉 OpenGL，注意gl开头的函数都是OpenGL API调用，详见VC+的帮助文档或Blue Book。有一个特性是刚开始加进代码中的。在FractalExampleView.cpp文件中，有一个名为 DEF_HIGHT_VALUE的预处理常量。它传给fractmod.c文件中的分形生成函数，用来缩放 高度值。其实它应该是由View Options对话框控制的变量。尽管加上这个特性好了。关键代码：1、Square步的端点值平均算法(fractmod.