Logo by mclarekin - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Did you know ? you can use LaTex inside Postings on fractalforums.com!
 
*
Welcome, Guest. Please login or register. December 08, 2022, 03:22:54 AM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1] 2 3 4   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: Problem with diamond-square algorithm  (Read 19983 times)
0 Members and 1 Guest are viewing this topic.
kronikel
Navigator
*****
Posts: 79



« on: September 25, 2011, 08:29:21 PM »

I decided to start working on my terrain generator again, and so here I am back with another problem.
It's easy to see what is going wrong, but I can't figure out how it is doing this.
There will be a point here and there that gets set either way too high or way too low which creates huge cone shapes.
There are always huge cones sticking out of the top -

And it can be seen very clearly when I set the smoothness up -

No matter how smooth it is there are still these cones sticking into and out of the terrain.

Here is how I generate the heights -

Code:
SideLength = (2^x) + 1
while SideLength >= 2
{
    HalfSide = SideLength / 2;

    //diamond step
    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] = (Heights[x, y] + Heights[x + SideLength, y] +
                       Heights[x, y + SideLength] + Heights[x + SideLength, y + SideLength]) / 4 +- Randomness;
              }
        }
   
    //square step
    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] = (Heights[x, y] + Heights[x + SideLength, y] +
                  Heights[x + HalfSide, y + HalfSide] + Heights[x + HalfSide, y - HalfSide]) / 4 +- Randomness;

              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 +- Randomness;
         }
    }
    SideLength = SideLength / 2;
    Randomness = Randomness / Roughness;
    }
}
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #1 on: September 25, 2011, 09:44:29 PM »

Assuming I'm correct that "randomness" there is just a simple variable then it's really a "scale" and you need to change the "+-randomness" in the diamond and square functions to "+randomness*random()" where random() is a random generator returning -1 to +1.
The "correct" value of "roughness" is sqrt(2) if I remember correctly - better implemented as 1/sqrt(2) and using *roughness instead of divide.

Also one trick to adjust the roughness to give a more realistic effect for landscapes is to compute the average base height value first then use an extra multiplier based on this i.e. instead of just adding randomness*random() compute the base height first and then add randomness*random()*(value based on height difference from zero, useful range to return from say 0.5 for height zero to 1.0 for all height differences >a given magnitude).
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
kronikel
Navigator
*****
Posts: 79



« Reply #2 on: September 25, 2011, 10:04:10 PM »

What I posted was just a rough summary of my code, but to generate the random part I use -
Average - r + ((float)(random.NextDouble() * r) * 2)

And if it helps any here is the actual code
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);

            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;
            }
        }
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #3 on: September 26, 2011, 12:20:45 AM »

In that case the code looks correct, so all I can think is that there's something inherently wrong with "random.NextDouble() " either in terms of it not actually returning randoms from zero to one or it having sufficient non-randomness to cause the peaks - e.g. maybe it's returning values from -1 to +1 rather than 0 to 1 ?

On the subject of diamond-square landscapes I'm working on a (shader-friendly) implementation that will allow distance-estimated ray stepping because it can return the height very quickly for any point - I'm still improving it so that it's randomness extends infinitely rather than being restricted to one square, obviously to get the optimum minimum distance estimation is a little tricky especially as I've got to relearn any of the maths I once knew with respect to what's essentially statistics in this case wink
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
kronikel
Navigator
*****
Posts: 79



« Reply #4 on: September 26, 2011, 03:51:57 AM »

That sounds pretty interesting.
But I'm pretty certain that the randomness is working.
I have tried using Random.Next(-r, r)
and also Random.Next() / (Int32.MaxValue - 1)
Which is another way of generating a number from 0 to 1, but all give me identical results.

I have also made a version of this in delphi where I have lots of experience in generating random numbers, yet still I get identical results.

There has to be something wrong with which points I'm using to average or which points I'm setting or something.
One thing to note is that the points that are messing up aren't in random places, they form a grid.

Edit:
This is very interesting...
When I take out the randomness completely, so all it does is take the average of the 4 surrounding points, I still get these strange "dimples" popping up everywhere.
« Last Edit: September 26, 2011, 05:22:36 AM by kronikel » Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #5 on: September 27, 2011, 02:29:56 AM »

Maybe try viewing the heights as colours in a 2D plane just to check that it's not your 3D rendering that's causing the problem ?
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
fractower
Iterator
*
Posts: 173


« Reply #6 on: September 27, 2011, 07:24:40 AM »

The output seems to match what one would expect from the code. It appears to be designed to write to each point only once with an exponentially decaying randomness. The early points are essentially random. When the random factor decays, the algorithm defaults to an approximate solution to a Laplacian \nabla ^2 with a few point sources (early points). This solution produces a 1/r type behavior relative to the point sources which is essentially what you are seeing.
Logged
kronikel
Navigator
*****
Posts: 79



« Reply #7 on: September 27, 2011, 08:04:49 PM »

That's a good idea David, that's actually how I first wrote the algorithm. So here's what I get -

And another example -


And to further rule out it being the way I render the points I completely made a new method for rendering the points. It is a couple lines long and as basic as it can get. Just drawing wire from point to point -


@fractower - The randomness can't be the issue because when I take out the randomness completely, so it simply sets a height based on the average of the 4 corner heights, I get identical results.
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #8 on: September 27, 2011, 11:34:08 PM »

What value of "roughtness" are you using? Maybe it's too high? I'm getting the same effect as you when using too high values. A value around 2 (better when less than 2) should give good results. When roughtness is bigger than two the spikes begins to appear.

Fractower's explanation is right: The algorithm acts somehow as a (multigrid) solver for laplace equation.

Reminds me another terrain generation algorithm: take wihte noise and filter it (using FFT). How is it called?...
« Last Edit: September 28, 2011, 12:25:05 AM by knighty » Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #9 on: September 28, 2011, 12:23:22 AM »

It also looks like there is something wrong with your random value. Its mean sould be 0. Otherwise the spikes appear.
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #10 on: September 28, 2011, 12:31:15 AM »

Reminds me another terrain generation algorithm: take wihte noise and filter it (using FFT). How is it called?...


FFT ? - Spectral Synthesis ? - too slow even for pre-computation at runtime unless you have fairly small grids i.e. really requires that the resulting heights are permanently stored for use.
Perlin noise is fast enough for runtime pre-computation and provides pretty decent results - in fact for pre-computed grids Perlin noise is considerably better than diamond-square unless you considerably enhance the d-s algorithm but if you need realtime computation of height (y) given a location (x,z) then on either GPU or CPU a good d-s implementation should be considerably faster - even if the d-s is somewhat enhanced though maybe not to the point of being as "good" aesthetically as Perlin noise.
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
kronikel
Navigator
*****
Posts: 79



« Reply #11 on: September 28, 2011, 02:31:00 AM »

I will say it again, the randomness is not the issue at all.
Roughness is not the issue either.
I have used 2 along with many other numbers but no matter how smooth I make the terrain there will still be large dips.

I made a whole completely new algorithm exactly copying this one - http://www.intelegance.net/content/codebase/DiamondSquare.pde
And I still get the dips regardless of roughness/randomness.
I worked out the algorithm by hand and the numbers I got were the same as what the code gives me.
You can easily see by hand how the cones come up, but I can't find a way to keep it from happening.
Logged
lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #12 on: September 28, 2011, 03:33:40 AM »

I think Knighty nailed it: you seem to be adding strictly positive random contributions, instead of having a mean of 0.
Logged

kronikel
Navigator
*****
Posts: 79



« Reply #13 on: September 28, 2011, 04:43:16 AM »

Ok this is getting a little frustrating.
IT HAS NOTHING TO DO WITH RANDOMNESS, and my code returns a number between -r and +r, with a mean of 0.

If you use
Code:
    r = AnyNumberAtAll;
    for (int a = 0; a < 20000; a++)
            {
                f += -r + (float)(random.NextDouble() * (r * 2));
            }
            Write((f / 20000).ToString());
It will average together 20,000 random numbers, and the average comes out to be almost exactly 0 every time, with a max of r and a minimum of -r.
Logged
fractower
Iterator
*
Posts: 173


« Reply #14 on: September 28, 2011, 07:22:56 AM »

I agree that the problem is not the random number generator. The issue is that the first few points calculated dominate the terrain preventing a regression to the mean. They act and look like tent poles. On the positive side it produces interesting terrain, but on the bad side it produces the spike artifacts.

One solution is to go back an recalculate the initial spikes once their influence has been established. For example run the same alogrithm in parallel but delayed a couple of iterations like a madrigal. Each location ends up being touched twice, but I think it will eliminate the tent poles. 
Logged
Pages: [1] 2 3 4   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Diamond Images Showcase (Rate My Fractal) Pauldelbrot 1 868 Last post March 16, 2009, 09:21:44 AM
by Nahee_Enterprises
Hip to Be Square Images Showcase (Rate My Fractal) Fractal Ken 0 783 Last post January 10, 2011, 08:20:13 PM
by Fractal Ken
Diamond-square algorithm help Help & Support kronikel 10 1578 Last post April 12, 2011, 02:11:06 AM
by kronikel
Problem with my Diamond Square algorithm Programming mbob61 5 2979 Last post December 12, 2012, 12:17:35 AM
by David Makin
diamond-square midpoint displacement algorithm Landscape/Terrain Generation claude 0 1759 Last post May 25, 2017, 05:52:50 PM
by claude

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.197 seconds with 24 queries. (Pretty URLs adds 0.015s, 2q)