三维随机分形地形生成

原文： http://www.gameprogrammer.com/fractal.html

目 录 说明：本页所有图像均经过优化以减小尺寸，所以与实际图像会有细微差别。

1. 第一部分：生成随机分形地形

1. 介绍

2. 自相似

3. 一维中点变换

4. 高度图

5. Diamond-Square 算法 6. 蓝天白云 7. 其它算法 2. 第二部分 关于例子源码

1. 安装 2. 快速起步 3. 使用程序 4. 代码结构 5. 下载源码[Visual C++工程，使用SGI实现的OpenGL]（单击标题下载） 6. 参考

终于找到这个SGI OpenGl地址了： http://www.vckbase.com/tools/ocx/ocx_image/opengl2.exe 介绍 十年前，我参加 1986 年 SIGGRAPH 活动， Gavin S. P. Miller 那篇题为 Definition and Rendering of Terrain Maps 的论文让我充满敬畏。该文描述了少数生成分形地形的算法，作

者还介绍了一个他们认为更先进的新方法。

开始我被这些算法能够生成难以置信的风景图所震惊！（尽管这些算法被作者认为“漏洞百出”）后来，读过论文，这些算法之简单将我完全打败了。

我从此成为一个分形地形迷。 算法背后的数学可能相当复杂。然而，完全理解这些数学并不是掌握这些算法的必要条件。很好，否则我得在解释算法之前讲解所有的数，也许永远也讲不到算法。此外，关于分形数学的文字材料数以吨计，参见本文本的参考部分会有所帮助。

同样的原因，我不会深入到数学细节，也不包括对分形的广泛总览及它们可被用来做的每样东西。相反，我将描述分形地形生成背后的概念，并集中仔细讲解我个人最喜欢的 ”diamond-square” 算法。我将演示如何使用这个算法静态拼嵌高度数据数组，这些数据可用于几何地形数据、地形纹理数据及云纹理映射。

分形有什么用呢？假定你已经知道，那正是你读本文的原因。随机地形图对飞行模拟或制作背景纹理图（如显示一带远山）十分有用。生成地形的算法也可用于生成部分云天的纹理图。

在继续之前，申明一下：我不是游戏程序员。如果你为找到一个快速绘制地形的算法而读此文，那你来错了地方。我只描述生成地形模型的过程。着色绘制是你自己的事。

自相似 任何分形最关键的概念是自相似。当一个物体的一部分放大后看起来仍与整个物体一样，那这个物体就是自相似。

考虑一下人体的循环系统。这是自然界中自相似的好例子。从最大的动脉和静脉分支直到最小的微血管，整个过程都显现相同的分支模式。如果你不知道正在使用显微镜，将无法分辨微血管和大动脉。

现在再考虑一个简单的球。它是自相似的吗？不！大幅度放大后，它看起来不再象一个球，而象块平板。如果你不相信，看看户外。除非恰好你在太空轨道上看本文，否则将完全没法看出球是个球体。球体不是自相似的。它最用传统的欧几里德几何描述而不是分开。

地形属于自相似范畴。手掌上的碎岩锯齿状边缘与远处地平线边的山脊有相同的不规则形状。这使我们可以用分形来生成地形，不管显示时怎么放大，它看起来仍然象地面。

关自相似请注意：严格意义下，它意味着自分辨 (self-identical) ，即，自身精确的缩略拷贝在逐渐放大缩小时可见。我并不知道自然界存在任何自分辨分形。但 mandelbrot 集是自分辨的。我不会进一步讨论 Mandelbrot 集。到参考里找进一步的信息。

一维中点变换 后边要讲的 diamond-square 算法，在两维上使用一种中点变换算法。为帮助你了解个大概，我们先看一维情况。

当山脉出现在远处地平线处时，一维中点变换是绘制山脊的好算法。看看它是怎么工作的： 以一条水平地平线段开始 重复足够多次{ 对场景中的每条线段做{ 找到线段的中点 在 Y 方向上随机移动中点一段距离 减小随机数取值范围 } } 将随机数值域减速小多泊呢？那取决于你想要分形的陡峭程度。每次循环减少的越多，所得山脊线就越平滑。但如果减得太多，则会有明显的锯齿感。可以粗糙度存在一个常量里。后面会解释如何做。

来看个例子。我们以一条 x 从 -1.0 到 1.0 ， y 均为 0 的线段开始。开始，我们将随机值范围设为 -1.0 到 1.0 （可任意取）。这样我们在此范围里生成一个数字，并将中点移动这么多。这之后，我们就得到了：

现在第二次经过外圈循环，我们有两段，长度均原来的一半。我们的随机值也减半，即 -0.5 到 0.5 。我们为两个中点都生成一个这个范围内的随机点，结果为：

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

再跑一下题：少量简单的指令集能够生成复杂图像的事实已经成为一个新的研究领域称为分形图像压缩。其思想是保存建立图像的递归指令而不是保存图像本身。这对于自然界的分形图像是极有用的，因为指令相对图像占用的空间要少得多。 Choas （混沌）与 Fractals （分形） new Frontiers of Science 有一章及一个附录涉及本主题，是一般学习分形的好读物。

回到现实。 不用太费劲，你可以读取本函数的输出到一个绘制程序而得到类似如下的东西：

这可作为窗口景色使用。相关的好东西是它是约束的，所以你可以保留一个相当的小图像并用它拼出整个场景。如果你不介意在每个方向都看见相同的山，那就这么干。

好的，在进入 2D 分形表面之前，你得了解粗糙度常量。这个值决定每次循环随机数值域的减少量，也就是说，决定分形结果的粗糙程度。例子代码使用一个 0.0 到 1.0 之间的浮点数并称之为 H 。因此 2(-h) 是 1.0( 对于小 H) 到 0.5 （对大 H ）范围内的数。随机数范围在每次循环时乘上这个值。如果 H 设为 1.0 ，则随机数范围将每次循环减半，从而得到一个非常平滑的分形。将 H 设为 0.0 ，则范围根本不减小，结果有明显的锯齿感。

下边是三个山脊，每个用不同的 H 的值绘制： 高度图 上边所说的中点变换算法可以用一个一维数组实现，数组成员是表明线段端点垂直位置的高度值。这数组是就是一个一维高度图。它将索引（ x 值）映射为高度值（ y 值）。

为模拟随机地形，我们想将该算法推广到 3D 空间。为做到这一点，我们需要一个两维高度值数组，它将索引 (x,z) 映射为高度 (y) 。数组只需保存高度值 (y) 。水平面值 (x 和 z) 可以在分析数组时即时生成。

通过对每个高度指定一个颜色，可以将一幅高度图显示为一幅图像。如下，高点为白色，低处为黑色。

绘制高度图的方法对于生成云彩纹理图是很有用的，后边还会讨论。这种表达也可以用于播种一个高度图。 现在我要讲讲如何拼嵌我们的二维高度图数组。 Diamond-Square 算法 正如本文开头提到过的，我先介绍 Gavin S.P.Miller 的论文中随机地形生成的概念。具有讽刺意义的是， Miller 在论文中说 diamond-square 算法是有缺陷的，然后描述了一种完全不同的基于重量平均和控制点的算法。

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

思想如下：你从一个很大的空 2D 数组开始。多大呢？为简化起见，他应该是方的，维数应该是 2 的 n 次方加 1 （如 33X33,65X65,129X129 等）。将四个角设为相同高度。如果你察看所得到东西，它是一个正方形。

取个简单的例子，用一个 5X5 的数组。（本文后面还要参考这图，别忘记了）。图中，图 a 的四个角种上了初始高度值，表示为黑点。

这是递归细分过程的起点，该过程分两步： diamond 步：取四个点的正方形，在正方形中点生成一个随机值，中点为两对角线交点。中点值是平均四个角值再加上一个随机量计算得到的。这样就得到了一个棱锥。当网格上分布着多个正方形时有点象钻石。

square 步：取每个四点形成的棱锥，在棱锥的中心生成一个随机值。平均角值再加上与 diamond 步相同的随机量，计算出每条边中点值。这又给你一个正方形。

这样，如果已经生成了一个种子正方形并经过单独一次细分过程将得到四个方形。第二次经过该过程得到 16 个方形，第三次得到 64 个方形。增长得很快。方形数目等于 2( 2 + I ) ，其中 I 为递归经过细分过程的次数。