algorithm - Diamond-Square 算法的平滑问题

Question

我正在使用菱形方 block 算法生成随机地形。它工作正常，除了我得到这些大圆锥形状或者伸出或插入地形。问题似乎是时不时会有一个点设置得太高或太低。

这是问题的图片

当我将平滑度设置得非常高时可以更好地看到它

这是我的代码-

private void CreateHeights()
    {
        if (cbUseLand.Checked == false) 
            return;
        int
            Size = Convert.ToInt32(System.Math.Pow(2, int.Parse(tbDetail.Text)) + 1),
            SideLength = Size - 1,
            d = 1025 / (Size - 1),
            HalfSide;
        Heights = new Point3D[Size, Size];
        float
            r = float.Parse(tbHeight.Text),
            Roughness = float.Parse(RoughnessBox.Text);

        //seeding all the points
        for (int x = 0; x < Size; x++)
            for (int y = 0; y < Size; y++)
                Heights[x, y] = Make3DPoint(x * d, 740, y * d);

        while (SideLength >= 2)
        {
            HalfSide = SideLength / 2;

            for (int x = 0; x < Size - 1; x = x + SideLength)
            {
                for (int y = 0; y < Size - 1; y = y + SideLength)
                {
                    Heights[x + HalfSide, y + HalfSide].y =
                      (Heights[x, y].y +
                      Heights[x + SideLength, y].y +
                      Heights[x, y + SideLength].y +
                      Heights[x + SideLength, y + SideLength].y) / 4 - r + ((float)(random.NextDouble() * r) * 2);
                }
            }

            for (int x = 0; x < Size - 1; x = x + SideLength)
            {
                for (int y = 0; y < Size - 1; y = y + SideLength)
                {
                    if (y != 0)
                        Heights[x + HalfSide, y].y = (Heights[x, y].y + Heights[x + SideLength, y].y + Heights[x + HalfSide, y + HalfSide].y + Heights[x + HalfSide, y - HalfSide].y) / 4 - r + ((float)(random.NextDouble() * r) * 2); 
                    if (x != 0)
                        Heights[x, y + HalfSide].y = (Heights[x, y].y + Heights[x, y + SideLength].y + Heights[x + HalfSide, y + HalfSide].y + Heights[x - HalfSide, y + HalfSide].y) / 4 - r + ((float)(random.NextDouble() * r) * 2);
                }
            }
            SideLength = SideLength / 2;
            r = r / Roughness;
        }
    }

Answer 1

Gavin S. P. Miller 在 SIGGRAPH '86 上发表了演讲，讲述了 Fournier、Fussel 和 Carpenter 的原始算法是如何存在根本性缺陷的。因此，您所看到的对于 Diamond Square 算法的任何简单实现都是正常的。您将需要一种单独的平滑方法，要么发布每个 Diamond-Square 复合步骤，要么作为所有 diamond-square 迭代(或两者)的后处理。米勒解决了这个问题。加权和框或高斯滤波是一种选择；将初始数组播种到比最初的 4 个点更大的程度(即，手动或使用某些内置智能复制 diamond-square 前几步的结果集，但提供无偏值)；在使用 diamond-square 增加细节之前为数组提供的初始信息越多，结果就越好。

原因似乎在于 Square 步骤的执行方式。在菱形步骤中，我们取正方形四个角的平均值来生成该正方形的中心。然后，在随后的 Square 步骤中，我们取四个正交相邻邻居的平均值，其中一个是我们刚刚生成的正方形的中心点。你能看出问题所在吗？那些原始角高度值对随后的菱形正方形迭代贡献太大，因为它们通过它们自己的影响和它们创建的中点做出贡献。这会导致尖顶(突出和侵入)，因为局部派生的点更倾向于那些早期的点......并且因为(通常是 3 个)其他点也这样做，这会在你迭代时围绕这些点产生“循环”影响使用 Diamond-Square 到更高的深度。所以这些“别名”问题只有在数组的初始状态未指定时才会出现；事实上，出现的伪影可以看作是仅使用 4 个点开始的直接几何结果。

您可以执行以下操作之一:

• 进行本地过滤——通常很昂贵。
• 更彻底地预置初始阵列 - 需要一些智能。
• 永远不要从一组给定的初始点开始平滑太多步 - 即使您确实为初始阵列设置种子也是如此，这只是相对深度与您自己的最大位移参数相结合的问题。