新浪博客

.6 蓝天白云
　　1.7 其它算法

　　原 文：Generating Random Fractal Terrain Part I: Generating Random Fractal Terrain
　　译 者：品雪
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

1.1、介绍
　　十年前，我参加1986年SIGGRAPH会议，Gavin S. P. Miller那篇题为“Definition and Rendering of Terrain Maps”的论文让我充满敬畏。该文描述了少数生成分形地形的算法，作者还介绍了一个他们认为更先进的新方法。开始我被这些算法能够生成难以置信的风景图所震惊。（尽管这些算法被作者认为“漏洞百出”）后来，读过论文，这些算法之简单将我完全打败了。我从此成为一个分形地形迷。
　　算法背后的数学可能相当复杂。然而，完全理解这些数学并不是掌握这些算法的必要条件。很好，否则我得在解释算法之前讲解所有的数，也许永远也讲不到算法。此外，关于分形数学的文字材料数以吨计，参见本文本的参考部分会有所帮助。
　　同样的原因，我不会深入到数学细节，也不包括对分形的广泛总览及它们可被用来做的每样东西。相反，我将描述分形地形生成背后的概念，并集中仔细讲解我个人最喜欢的“diamond-square”算法。我将演示如何使用这个算法静态拼嵌高度数据数组，这些数据可用于几何地形数据、地形纹理数据及云纹理映射。
　　分形有什么用呢？假定你已经知道，那正是你读本文的原因。随机地形图对飞行模拟或制作背景纹理图（如显示一带远山）十分有用。生成地形的算法也可用于生成部分云天的纹理图。
　　在继续之前，申明一下：我不是游戏程序员。如果你为找到一个快速绘制地形的算法而读此文，那你来错了地方。我只描述生成地形模型的过程。着色绘制是你自己的事。
1.2、自相似
　　任何分形最关键的概念是自相似。当一个物体的一部分放大后看起来仍与整个物体一样，那这个物体就是自相似。考虑一下人体的循环系统。这是自然界中自相似的好例子。从最大的动脉和静脉分支直到最小的微血管，整个过程都显现相同的分支模式。如果你不知道正在使用显微镜，将无法分辨微血管和大动脉。现在再考虑一个简单的球。它是自相似的吗？不，大幅度放大后，它看起来不再象一个球，而象块平板。如果你不相信，看看户外。除非恰好你在太空轨道上看本文，否则将完全没法看出球是个球体。球体不是自相似的。它最用传统的欧几里德几何描述而不是分开。
　　地形属于自相似范畴。手掌上的碎岩锯齿状边缘与远处地平线边的山脊有相同的不规则形状。这使我们可以用分形来生成地形，不管显示时怎么放大，它看起来仍然象地面。
　　关自相似请注意：严格意义下，它意味着自分辨（self-identical），即，自身精确的缩略拷贝在逐渐放大缩小时可见。我并不知道自然界存在任何自分辨分形。但mandelbrot集是自分辨的。我不会进一步讨论Mandelbrot集。到参考里找进一步的信息。
1.3、一维中点变换
　　后边要讲的Diamond-Square算法，在两维上使用一种中点变换算法。为帮助你了解个大概，我们先看一维情况。当山脉出现在远处地平线处时，一维中点变换是绘制山脊的好算法。看看它是怎么工作的：
　　以一条水平地平线段开始
　　重复足够多次
　　{
　　　　对场景中的每条线段做
　　　　{
　　　　　　找到线段的中点
　　　　　　在 Y 方向上随机移动中点一段距离
　　　　　　减小随机数取值范围
　　　　}
　　}
　　将随机数值域减速小多泊呢？那取决于你想要分形的陡峭程度。每次循环减少的越多，所得山脊线就越平滑。但如果减得太多，则会有明显的锯齿感。可以粗糙度存在一个常量里。后面会解释如何做。
　　来看个例子。我们以一条x从-1.0到1.0，y均为0的线段开始。开始，我们将随机值范围设为-1.0到1.0（可任意取）。这样我们在此范围里生成一个数字，并将中点移动这么多。这之后，我们就得到了：
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

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

　　再次缩减范围，现在是-0.25到0.25。再以该范围内的数变换四个中点后，我们得到了：
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

有两件事你可能已经注意到了。
　　首先，它是递归的。实际上，它可以用一个迭代过程相当自然的实现。对于这种情况，递归或迭代都成。对于表面生成代码，使用迭代实现比递归会有一些好处。所以为保持一致，线和面相应的代码都使用迭代实现。其次，它是个非常简单的算法，然而你能创建非常复杂的结果。这正是分形算法的美妙之处。一些简单的指令可以建立一个具有丰富细节的图像。
　　再跑一下题：少量简单的指令集能够生成复杂图像的事实已经成为一个新的研究领域称为分形图像压缩。其思想是保存建立图像的递归指令而不是保存图像本身。这对于自然界的分形图像是极有用的，因为指令相对图像占用的空间要少得多。“Chaos and Fractals, New Frontiers of Science3”有一章及一个附录涉及本主题，是一般学习分形的好读物。
　　回到现实。不用太费劲，你可以读取本函数的输出到一个绘制程序而得到类似如下的东西：
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　　这可作为窗口景色使用。相关的好东西是它是约束的，所以你可以保留一个相当的小图像并用它拼出整个场景。如果你不介意在每个方向都看见相同的山，那就这么干。
　　好的，在进入 2D 分形表面之前，你得了解粗糙度常量。这个值决定每次循环随机数值域的减少量，也就是说，决　　定分形结果的粗糙程度。例子代码使用一个0.0到1.0之间的浮点数并称之为H。因此2(-h)是1.0（对于小H）到 0.5（对大H）范围内的数。随机数范围在每次循环时乘上这个值。如果H设为1.0，则随机数范围将每次循环减半，从而得到一个非常平滑的分形。将H设为0.0，则范围根本不减小，结果有明显的锯齿感。
　　下边是三个山脊，每个用不同的H的值绘制：
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

1.4、高度图
　　上边所说的中点变换算法可以用一个一维数组实现，数组成员是表明线段端点垂直位置的高度值。这数组是就是一个一维高度图。它将索引（x值）映射为高度值（y值）。
　　为模拟随机地形，我们想将该算法推广到3D空间。为做到这一点，我们需要一个两维高度值数组，它将索引（x，z）映射为高度（y）。数组只需保存高度值（y）。水平面值（x和z）可以在分析数组时即时生成。通过对每个高度指定一个颜色，可以将一幅高度图显示为一幅图像。如下，高点为白色，低处为黑色。
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　　绘制高度图的方法对于生成云彩纹理图是很有用的，后边还会讨论。这种表达也可以用于播种一个高度图。现在我要讲讲如何拼嵌我们的二维高度图数组。
1.5、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的数组。（本文后面还要参考这图，别忘记了）。图8中，图a的四个角种上了初始高度值，表示为黑点。
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　　这是递归细分过程的起点，该过程分两步：
diamond步
　　取四个点的正方形，在正方形中点生成一个随机值，中点为两对角线交点。中点值是平均四个角值再加上一个随机量计算得到的。这样就得到了一个棱锥。当网格上分布着多个正方形时有点象钻石。
square步
　　取每个四点形成的棱锥，在棱锥的中心生成一个随机值。平均角值再加上与diamond步相同的随机量，计算出每条边中点值。这又给你一个正方形。
　　这样，如果已经生成了一个种子正方形并经过单独一次细分过程将得到四个方形。第二次经过该过程得到16个方形，第三次得到64个方形。增长得很快。方形数目等于2(I + 2)，其中I为递归经过细分过程的次数。参考前五幅插图，下图示意了使用我们的diamond-square算法两次经过数组时发生的情况。
　　对于第一遍经过diamond步时，我们依据四个角的值在数组中心生成一个值。我们平均四个角的值（如果种子值相等则完全没必要），并加上一个-1.0到1.0之间的随机值。在插图b中，新值显示成黑色，已经存在的点显示为灰色。对于square步，我们在相同的范围内生成随机值。这一步时有四个棱锥；他们在数组中心相交，这样我们计算四个diamond中心。diamonds的角被平均以找出新值的基数。插图C用黑色显示新值，现存值为灰色。
　　以上是第一遍，如果用线将这9个点边起来，就可以得到一个线框的表面，看起来就象：
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　　现在进行第二遍。再次从diamond步开始。第二遍与第一遍有两点不同。首先，我们现在有四人四边形面不是一个，因此我们得计算四个方面的中心。其次，这是关键，生成随机数的范围已经被减小了。因为例子的缘故，让我们认为正在使用一个H=1.0的值。这将把我们的随机数取值范围将从(-1.0,1.0)到(-0.5,0.5)。在插图8的D中，我们这一步计算得到的四个正方形中心值显示为黑色。
　　最后，我们进行第二遍的square步。有12个棱锥中心，我们现在需要计算12个新值，如图8的e中黑色所示。现在数组中全部25个元素都已经生成。我们可以得到如下的线框曲面。
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　　如果分配更大的数组，我们可以进行更多遍，每一遍加入更多细节。例如，5遍之后表面看起来如下所示：
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　　前面提到过，数组维数需要为2的整数次方加1。这是因为2D数组中的浮点数必须等于
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形
。8次迭代将需要一个257X257的浮点数组，对于标准的32位IEEE浮点数来说超过256K内存。
　　好了，它就是这么大。用char取代floats会有所帮助。例子程序使用floats，但你要真的关注内存使用那么使用char。修改例子使用之使用-128到128的范围是很容易的，但别忘了将你生成的值限定在-128到128范围里，子序列通过时会生成该范围以外的值，这会导致溢出。这在使用较小的H时尤其可能。
　　例子程序演示了处理尺寸的另外一种方法。用一个大数组依据diamond-square算法进行定位及拼嵌。然后从平行投影体顶视图进行绘制。这个图像被读回来并用作已经拼嵌成较小范围的第二个数组上的纹理图。然而，例子程序并没有这样做，一但图像从帧缓冲读回，第一个数组就被释放了。这有个纹理图的例子：
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　该图经过人工着色，山峰为白色，山谷为绿色，两者之间为灰色。尽管利用例子程序源码试试自己的配色方案。早先还到过用迭代实现这个例程比递归好。原因是，一个递归实现可能翻采用如下形式：
　　执行diamond步
　　执行square步
　　减小随机数范围
　　调用自己四次
　　这是个很简洁的实现，而且毫无疑问它能工作。但它要求用不充足的数据生成某些点。为什么呢？经过第一遍之后，你将再次调用以执行square步，但这时并没有一个棱锥四个角的全部数据。与之相反，我用个迭代实现，伪码如下：
　　当square边长度大于0时
　　{
　　　　遍历数组，对每个正方形表达执行diamond步
　　　　遍历数组，对每个棱锥表达执行diamond步
　　　　减小随机数范围
　　}
　　这样就消除了递归实现中出现的棱锥角丢失问题。但在生成数组边界的点时还是会碰到这个问题。下图中，数组中构成棱锥角的位置用亮灰色表示。它们应该被平均以找出新的基本值，即图中黑色的点。
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　　注意用黑色标记的两个值。它们实际上是相同的值。每次你在square步计算一个边界上的值时，记得同时把它保存在数组对面边上。这意味着前面插图e中，我们实际上不必计算12个单独的值，因为其中的四个在数组相对的两条边上重复。实际上只有8个值需要计算。感兴趣的读都可以练习一下：取出源代码并使用它在边界的值不重复时也能工作。这对算法正常工作是没有必要的，按我写的方式去做就成。
　　如果你还没运行过例子程序，现在或许是时候打开看看了。它从两次迭代生成的曲面开始。曲面是用线框绘制的，只是简单的将数组中的值用线段边接起来。数组中的值被当作Y值，而X和Z坐标是在数组分析时即时生成的。通过将一个方形分成两个三角形可以轻易的使用三角形绘制出这个曲面。三角形通常都是很好的图元，因为它总是凸性的平面。
　　用“View Opeions”对话框调节RAndom seed值。这会导致生成不同的曲面。调高“iterations”值给曲面增加细节。代码限制这个值到10，这对于我32MB内存的Pentium Pro系统有点多，看起来是黑的（或许五年以后，人们会在新的处理器和更高分辨率的显示器上运行这个程序，会对我为什么将它限制到10十分奇怪的……）。第一个H值控制表面粗糙度，默认值为0.7。试着设得更高或更低看看结果如何。是的这个算法偶尔会产生局部尖刺或皱折。但我偏爱尖或皱折不明显依赖于观察角度或飞过它的速度这种超自然的效果。
1.6、蓝天白云
　　现在我们知道如何生成表面。我们可以生成并着色大量的三角形，也可以生成一个高分辨率的纹理图并将它应用到低分辩率的表面。不管怎样，效果相当好。那么，我们怎么生成头上的天空呢？它比你想象得要简单。
　　diamond-square算法拼嵌完成的数组非常适于表示云天的纹理图。与把数组看作一套高度图上的y值相反，把它看成云的不透明度数据。最小数组值代表最蓝。天空中最晰的部分，最大的值代表最白，天空中云最重的部分。分析数组并生成如下的纹理图是相当琐碎的：
三维随机分形地形生成 <wbr>- <wbr>生成随机分形地形

　这与前面的高度图很象，但我已经限定了高、低值以建立清晰有云的天空。也可以用例子程序生成一幅类似的图像。设置“Select rendering type”下拉菜单为“2D mesh/clouds”。（默认时看起来有像素感，试试把“Cloud iterations”值设为8以上修正之）。试试给这H赋不同的值（就是前面刚说过的“Cloud iterations”值），以取得不同的云的效果。
　　如果回到本文开头，第一幅图结合了许多我在这做的讨论。天空是用一个如上的纹理图作的，沿一个八边金字塔重复排放多次曲面几何体用一个高分辩率纹理图绘制。这个纹理图是通过从一个平行顶视图着色一个高度拼嵌有光照曲面而生成的。然后，这个图被读出用作纹理图。跟随本文的例子程序被用于生成本文中出现的几乎所有图像。
1.7、其它算法
　　可能会想对曲面生成有比样本代码更多的控制。例如，可能想用自己的值给数组的前几遍初始化种子值，这样，山、谷……可以基本位于你设计的位置。然后用diamon-square算法填写其它细节。
　　修改代码，使之在赋值时略过已有值的数组成员是易于完成的。初始化数组为，例如，-10.0，给前几遍指定自己的值作为种子，再增强分形生成代码只给当前值为-10.0的赋值。简几遍将不会生成任何值，因为你的种子值已经在那儿了。后续几遍将在种子值在基础上生成新值。
　　如何取得种子值呢？如果想要的形状遵循某个已知的数学公式，如正弦曲线，就用这个函数生成值。否则，你得找出创造性的方法完成。我见过的一种算法是用灰度值绘制自己的高度图。将灰度映射成高度值并存入数组。再用diamond-square算法增加更多细节。
　　除了diamond-square算法，还有许多拼嵌表面的方法。用连续随机增加，2D数组的一个随机部分增高一个很少的量。反复多次，对所选中的数组区域加上一个很小的随机值。这可以生成相当不错的结果，但不是线性计算的。如果计算时间无所谓，那么建议试试这个算法。一另一个相似的方法，制造一个穿过数组的“折断”，并增加其中的一边，就象地震出现一样。再重复多次。这也不是一个线性算法，要多遍才能取得可以接受的结果。参见参考文献以了解更多其它途径。

我的更多文章

下载客户端阅读体验更佳

APP专享