Diamond-Square算法的平滑问题 [英] Smoothing issue with Diamond-Square algorithm
问题描述
它工作正常，除了我得到这些大的锥形，伸出或进入地形。
问题似乎是，现在每一点都被设置得太高或太低。
这是一个问题的图片< br>
当我设置平滑度真的很高时，可以更好地看出
这里是我的代码 -
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），
粗糙度= float.Parse（RoughnessBox.Text）; （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; （int x = 0; x< Size - 1; x = x + SideLength）
（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）; （int x = 0; x< Size - 1; x = x + SideLength）
{
for（int y = 0; y <尺寸-1; y = y + SideLength）
{
if（y！= 0）
高度[x + HalfSide，y] .y = [x，y] .y + Heights [x + SideLength，y] .y + Heights [x + HalfSide，y + HalfSide] .y + Heights [x + HalfSide，y - HalfSide] .y）/ 4 - （（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 /粗糙度
}
}
Gavin SP米勒给了SIGGRAPH '86谈论Fournier，Fussel&木匠的原始算法有根本的缺陷。所以你所看到的对于钻石方法算法的天真实施是正常的。您将需要单独的平滑方法，无论是在每个钻石方形复合步骤之后，还是作为所有菱形平方迭代（或两者）的后处理。米勒解决了这个问题。权重和方块或高斯滤波是一个选择;将初始数组比仅初始4个点（即，手动复制钻石正方形的前几个步骤的结果集或使用某些内置智能，而不是提供无偏的值）将其初始化的数据种类更大;在使用菱形方块增加细节之前，您给数组的初始信息越多，结果越好。
原因似乎在于Square步骤如何执行。在钻石步骤中，我们将平方的四个角的平均值作为平方的中心。然后，在随后的Square步骤中，我们取四个正交相邻邻居的平均值，其中一个是我们刚刚生成的平方的中心点。你能看到问题吗？这些原始的角高值对随后的钻石平方迭代贡献太大，因为它们通过自己的影响力和他们创建的中点来贡献。这导致尖顶（引诱和侵入性），因为本地派生点往往更倾向于那些早期点，而且（通常为3）其他要点也是如此，这会在这些点上产生循环的影响，因为您重复使用钻石广场更高的深度。所以这些类型的混叠问题只会在阵列的初始状态不明确时出现;事实上，发生的伪像可以被看作仅使用4个点的直接几何结果。
您可以执行以下操作之一：
- 做本地过滤 - 一般都很贵。
- 更彻底的种子初始数组 - 需要一些智能。
- 不要从给定的一组初始点平滑太多的步骤 - 即使您对初始数组进行种子化，这也是适用的，这只是一个相对深度的问题您自己的最大位移参数。
I am using the diamond-square algorithm to generate random terrain. It works fine except I get these large cone shapes either sticking out of or into the terrain. The problem seems to be that every now and then a point gets set either way too high or way too low.
Here is a picture of the problem
And it can be better seen when I set the smoothness really high
And here is my code -
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;
}
}
Gavin S. P. Miller gave a SIGGRAPH '86 talk about how Fournier, Fussel & Carpenter's original algorithm was fundamentally flawed. So what you're seeing is normal for any naive implementation of the Diamond Square algorithm. You will require a separate approach for smoothing, either post each Diamond-Square compound step, or as a post-process to all diamond-square iterations (or both). Miller addressed this. Weighting and box or gaussian filtering are one option; seeding the initial array to a greater degree than just the initial 4 points (i.e., replicating the resultsets of the first few steps of diamond-square either manually or using some built-in intelligence, but instead supplying unbiased values); the more initial information you give the array before increasing the detail using diamond-square, the better your results will be.
The reason appears to be in how the Square step is performed. In the Diamond step, we've taken the average of the four corners of a square to produce that square's centre. Then, in the subsequent Square step, we take the average of four orthogonally-adjacent neighbours, one of which is the square's centre point we just produced. Can you see the problem? Those original corner height values are contributing too much to the subsequent diamond-square iteration, because they are contributing both through their own influence AND through the midpoint that they created. This causes the spires (extrusive and intrusive), because locally-derived points tend more strongly toward those early points... and because (typically 3) other points do as well, this creates "circular" influences around those points, as you iterate to higher depths using Diamond-Square. So these kinds of "aliasing" issues only appear when the initial state of the array is underspecified; in fact, the artifacting that occurs can be seen as a direct geometric consequence of using only 4 points to start with.
You can do one of the following:
- Do local filtering -- generally expensive.
- Pre-seed the initial array more thoroughly -- requires some intelligence.
- Never smooth too many steps down from a given set of initial points -- which applies even if you do seed the initial array, it's all just a matter of relative depths in conjunction with your own maximum displacement parameters.
这篇关于Diamond-Square算法的平滑问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
