The problem of smoothing by the Diamond-Square algorithm

Question

I use a diamond-square algorithm to generate random terrain. It works great, except that I get these large cone shapes protruding from or into the relief. The problem seems to be that from time to time the point gets too high or too low.

Here is a picture of the problem

And it can be better seen when I set the smoothness to the highest level

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; } } 

Answer 1

Gavin S.P. Miller gave SIGGRAPH '86 a message about how the original Fournier, Füssel and Carpenter algorithm was fundamentally wrong. What you see is normal for any naive implementation of the Diamond Area algorithm. You will need a separate approach for smoothing, either submit each step based on Diamonds-Square, or as a post-process for all iterations with a diamond square (or both). Miller turned to this. One option is weighing and boxing or Gaussian filtering; sowing the initial array to a greater extent than only the initial 4 points (i.e., replicating the result set of the first few steps of the diamond square either manually or using some built-in intelligence, but instead providing unbiased values); the more initial information you give to the array before increasing the detail using the diamond square, the better your results will be.

The reason is how the Square step is performed. At the Diamond step, we took the average of the four corners of the square to create this square center. Then, in the next square step, we take the average of four neighbors with orthogonally neighboring neighbors, one of which is only a square center point. Do you see the problem? These initial values ​​of the height of the angle contribute too much to the subsequent iteration with the diamond square, because they contribute both through their influence and through the middle that they created. This leads to spies (extrusive and intrusive), because locally derived points tend more toward those early points ... and because (usually 3) make other points, this creates “circular” influences around these points as you repeat to higher depths using Diamond-Square. Thus, these types of "aliases" occur only when the initial state of the array is unproven; In fact, what is happening artifacts can be considered as a direct geometric consequence of using only 4 points to start.

You can do one of the following:

• Local filtering is usually expensive.
• Pre-align the original array in more detail - some intelligence is required.
• Never smooth too many steps from a given set of starting points, which applies even if you are sowing an initial array, all this is just a matter of relative depth combined with your maximum offset parameters.

Answer 2

I believe that the size of the offset r at each iteration should be proportional to the size of the current rectangle. The logic of this is that the fractal surface is scale invariant, so the change in height in any rectangle should be proportional to the size of this rectangle.

In your code, the change in height is proportional to r, so you must maintain it proportionally to the size of the current grid size. In other words: multiply r by the roughness before the loop and divide r by 2 at each iteration.

So instead

 r = r / Roughness; 

you should write

 r = r / 2; 

Answer 3

The actual flaw in the above algorithm is a mistake in conceptualization and implementation. The diamond square as an algorithm has some artifacts, but these are range-based artifacts. Thus, the technical max for some pixels is higher than some other pixels. Some pixels directly specify values ​​by randomness, while others acquire their values ​​through diamond and quadratic intermediate interpolation processes.

The error here is that you started from scratch. And re-added the value to the current value. This leads to the fact that the range of squares of the diamond starts from zero and spreads up. It should start from scratch and go up and down, depending on chance. Thus, the upper range does not matter. But, if you do not understand this and naively implement everything as added to the value, and do not start from scratch and hesitate from there, you will find hidden artifacts.

Miller's notes were correct, but the flaw was usually hidden within the noise. This implementation shows these problems. It is not normal. And it can be fixed in several different ways. This was one of the reasons why, after I expanded this algorithm to remove all restrictions and restrictions on the size of the memory and made it infinite and deterministic 1 , I still abandoned the main idea here (problems associated with expanding it to 3d and optimizations for GPUs also played a role.

Answer 4

Instead of just smoothing on average, you can use a 2-D medium filter to infer extremes. It is easy to implement and usually generates the desired effect with a lot of noise.