Logo by Fiery - 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: Check out the originating "3d Mandelbulb" thread here
 
*
Welcome, Guest. Please login or register. December 01, 2022, 01:55:00 PM


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 19965 times)
0 Members and 1 Guest are viewing this topic.
kronikel
Navigator
*****
Posts: 79



« Reply #15 on: September 28, 2011, 08:03:32 AM »

I definitely agree it's the first few points that are messing it up.
And when you see a cone in the middle poking up, it's not because that point got set too high, it's because the next four points of the following square step got set too low.
I've considered a lot of ways to fix this, such as using a smoothing algorithm or a spline, or maybe a logarithm approach for how the roughness decays.
But I still can't get past how I see these "flag poles" even without randomness at all.
And what is the difference between my code and other ones?
When I look at other people's algorithms I basically see Height = Average of 4 surrounding points +- random
It feels like I'm missing something fundamental.
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #16 on: September 28, 2011, 02:56:59 PM »

You are right. The spikes don't appear clearly in the 2D pictures but they are obvious in 3D. Mandelbrot's midpoint displacement algorithm doesn't have this issue. This quote from wikipedia suggests that the spikes issue is known:
Quote
The idea was first introduced by Fournier, Fussell and Carpenter at SIGGRAPH 1982. It was later analyzed by Gavin S. P. Miller in SIGGRAPH 1986 who described it as flawed.

Quote
@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.
That shouldn't happen because you are initializing the whole array height to the same value... Weird... Aren't you keeping the -r term when removing randomness? That will give a nice looking fractal surface anyway smiley.

@David Makin: Thanks! I don't know how much slower FFT is but you can use arbitrary filters with it (more possibilities/variations).
Logged
DarkBeam
Global Moderator
Fractal Senior
******
Posts: 2512


Fragments of the fractal -like the tip of it


« Reply #17 on: September 28, 2011, 04:18:28 PM »

Already looked here? http://gameprogrammer.com/fractal.html#diamond

Luca grin
Logged

No sweat, guardian of wisdom!
kronikel
Navigator
*****
Posts: 79



« Reply #18 on: September 28, 2011, 08:13:08 PM »

I think it is considered flawed because the terrain produced isn't exactly 100% what is found in nature. But I've never been sure what he meant by that.

When I remove the randomness I also set the very middle point to be up, otherwise it would just create a completely flat surface.
But the middle point is the only one I touch and I had assumed I would get a smooth transition from the base up to the middle point, but I get some cones going down into the terrain.

@DarkBeam I used that exact method, or so I thought. I can't see what I'm doing different.
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #19 on: September 28, 2011, 10:45:18 PM »

@David Makin: Thanks! I don't know how much slower FFT is but you can use arbitrary filters with it (more possibilities/variations).

Yes, but if you look at the raw, basic Perlin method it allows an infinite number of ways of implementing it as the two components involved can be any type that fits the bill i.e. one noise function and one interpolation algorithm - these can essentially be any that you can conceive assuming they have the required number of dimensions (or can be adapted/expanded to the right number of dimensions).

See:

http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

And remember that *any* "noise" will do and *any* "interpolation" will do, in fact really based on that as a simplified/generalised definition of Perlin Noise then it essentially includes the D-S algorithm.
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #20 on: September 28, 2011, 10:54:39 PM »

I think it is considered flawed because the terrain produced isn't exactly 100% what is found in nature. But I've never been sure what he meant by that.

When I remove the randomness I also set the very middle point to be up, otherwise it would just create a completely flat surface.
But the middle point is the only one I touch and I had assumed I would get a smooth transition from the base up to the middle point, but I get some cones going down into the terrain.

@DarkBeam I used that exact method, or so I thought. I can't see what I'm doing different.

I think I found the issue - here:

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


Size will be a power of two and SideLength a power of two minus 1, so if Size is 1024 then SideLength is 1023.
This will *not* work as SideLength itself *has* to be a power of 2, so you can either do this:

            int
                SideLength = Convert.ToInt32(System.Math.Pow(2, int.Parse(tbDetail.Text)) + 1),
                Size = SideLength + 1,
                d = 1025 / Size,
                HalfSide;
            Heights = new Point3D[Size, Size];

Or this:

            int
                SideLength = Convert.ToInt32(System.Math.Pow(2, int.Parse(tbDetail.Text)) + 1),
                Size = SideLength + 1,
                d = 1025 / Size,
                HalfSide;
            Heights = new Point3D[SideLength, SideLength];

but in this case also bitwise & the array-look-up index values with (SideLength-1).

Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #21 on: September 28, 2011, 11:15:31 PM »

Logged

lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #22 on: September 28, 2011, 11:16:39 PM »

rather evaluate it directly in a stateless, functional and parallel way smiley
Logged

kronikel
Navigator
*****
Posts: 79



« Reply #23 on: September 29, 2011, 01:55:55 AM »

I'm not sure what you mean.
With the way I have it right now SideLength is a power of 2 and Size is a power of 2 + 1.
So using "10" I have a Size of 1025 and a SideLength of 1024 at the start.
Logged
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #24 on: September 29, 2011, 09:37:01 AM »

It isnt real because perlin or diamond squares wont peoduce caves or holes. . .
Logged

---

divide and conquer - iterate and rule - chaos is No random!
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #25 on: September 29, 2011, 11:05:24 AM »

It isnt real because perlin or diamond squares wont peoduce caves or holes. . .


Correct - but if you know a landscape generation algorithm that can return the height/heights per point in the horizontal plane *at runtime* as fast as using an appropriate version of D-S then please point me at it !!

(note I do mean arbitrary points not just an orderly set)
« Last Edit: September 29, 2011, 11:15:30 AM by David Makin » 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 #26 on: September 29, 2011, 07:41:24 PM »

I could be wrong, but I assumed things like that were due to weathering/ erosion/ etc.
I have seen people take terrain and apply another algorithm on top of it to make these though.

And about my problem, I applied a smoothing algorithm to my terrain, and while it did get rid of the cones, it also destroys the detail in the mountains and made everything look like smooth plastic.
So I changed it to only smooth out points that are higher/lower than the points around it by a certain amount, say 30 pixels.
Better results, but this is still just a patch and not nearly a fix for my problem.
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #27 on: September 30, 2011, 10:21:46 PM »

It isnt real because perlin or diamond squares wont peoduce caves or holes. . .
A 3D version of diamond-square algorithm would generate caves smiley. Though I haven't implemented it, that algorithm would require 3 stages:
-cube center point: average of 8 cube corners + random,
-faces center points: average of 4 corners and 2 adjacent cube centers + random.
-edges center points: average of 2 corners and 4 adjacent faces centers +random.
It could also be generelized to higher dimensions. For N dimension you'll need N stages.

And about my problem, I applied a smoothing algorithm to my terrain, and while it did get rid of the cones, it also destroys the detail in the mountains and made everything look like smooth plastic.
So I changed it to only smooth out points that are higher/lower than the points around it by a certain amount, say 30 pixels.
Better results, but this is still just a patch and not nearly a fix for my problem.
You could try using a filter that "detects the spikes". Here is a simple example:
Code:
filter(s){//s is the "strength" of the filter. A good value is around 10 if the heigtmap max height is around 1
   //edges are not processed here but they need to!
   for(l=1; l<N; l++)
      for(c=1; c<N; c++){
         G=tab[l][c]-tab[l-1][c]; G+=tab[l][c]-tab[l+1][c];
         G+=tab[l][c]-tab[l][c-1]; G+=tab[l][c]-tab[l][c+1];//"gradients" in the 4 directions. abs(G) will be higher on spike and "pits".
         G=exp(-s*abs(G));//in order to have in in the range [-1, 1]
         tab[l][c]=G*tab[l][c]+0.25*(1-G)*(tab[l-1][c]+tab[l+1][c]+tab[l][c-1]+tab[l][c+1]);//simple filter
      }
}
I hope it doesn't smoothen the surface too much.

(In case someone is interested, I've attached some very simple evaldraw scripts about FFT based spectral synthesis noise (finally not that slow tease); perlin noise (quite fast (EDIT: it is comparable to original perlin noise there was a bug with name collision) and GPU friendly (link) because it doesn't use any look up table), diamond-square and square-square algorithms)

* square-diamond&co.zip (4.04 KB - downloaded 147 times.)
« Last Edit: October 03, 2011, 12:34:25 PM by knighty » Logged
kronikel
Navigator
*****
Posts: 79



« Reply #28 on: September 30, 2011, 11:56:35 PM »

I made a little animation of the structure being created with no randomness at all, and the center point set up a little.
Hasn't really inspired a working idea for me yet, but maybe someone else can see what's going on.
Logged
fractower
Iterator
*
Posts: 173


« Reply #29 on: October 01, 2011, 08:34:57 PM »

That is a good animation Kronikel. It shows the wavelet basis functions for the square steps. There is a very similar basis for the diamond steps as well. The final surface is a linear combination of these basis functions. Your animation illustrates how the basis set is flawed. I have tried to address this by modifying the basis functions by performing a multigrid smoothing operation inside the main loop.  This required adding two new parameters. Erosion is a smoothing parameter and Erosion_delay is the number of main loops before smoothing is applied. The basis sets are for (Erosion_delay = 1, Erosion = .85) and (Erosion_delay = 2, Erosion = .55). I have also attached terrains made from the delay 2 basis and the original DS results.

The computation cost is ~1.5 times the original DS algorithm.

Code:
void model()  
{
  
  
  
  int
    Size = GRID,
    SideLength = Size - 1,
    SideLength2 = Size - 1,
    d = 1025 / (Size - 1),
    HalfSide,
    HalfSide2,
    QSide2;
  //Heights = new Point3D[Size, Size];
  //float
  float r = r_init;
  float e = Erosion;
  //Roughness = float.Parse(RoughnessBox.Text);
  float hit;
  int grid_cnt = 0;

  srand(rand_init);

  for (int x = 0; x < Size; x++)
    for (int y = 0; y < Size; y++)
      Heights[x][y] = 0;

  
  while (SideLength2 >= 4)
    {
      HalfSide = SideLength / 2;
      HalfSide2 = SideLength2 / 2;
      QSide2 = HalfSide2 / 2;
      if(SideLength >=2){
if(SideLength == 2) r = r / Roughness;
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 + r - 2*r*(rand()/(1.0*RAND_MAX));
     }
 }

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 + r - 2*r*(rand()/(1.0*RAND_MAX));
if (x != 0)
 Heights[x][ y + HalfSide] =
   (Heights[x][ y] + Heights[x][ y + SideLength] + Heights[x + HalfSide][ y + HalfSide] + Heights[x - HalfSide][ y + HalfSide]) / 4 + r - 2*r*(rand()/(1.0*RAND_MAX));
     }
 }
      }
      
      if(grid_cnt >= Erosion_delay){
for (int x = 0; x < Size - 1; x = x + SideLength2)
 {
   for (int y = 0; y < Size - 1; y = y + SideLength2)
     {

Heights[x + HalfSide2][ y + HalfSide2] = Heights[x + HalfSide2][ y + HalfSide2]*(1-e)+
 (Heights[x + QSide2][ y + QSide2] +
  Heights[x + SideLength2 - QSide2][ y + QSide2] +
  Heights[x + QSide2][ y + SideLength2 - QSide2] +
  Heights[x + SideLength2 - QSide2][ y + SideLength2 - QSide2]) * e / 4;

     }
 }

for (int x = 0; x < Size - 1; x = x + SideLength2)
 {
   for (int y = 0; y < Size - 1; y = y + SideLength2)
     {
if (y != 0)
 Heights[x + HalfSide2][ y] = Heights[x + HalfSide2][ y]*(1-e)+
   (Heights[x + QSide2][ y] + Heights[x + SideLength2 - QSide2][ y] +
    Heights[x + HalfSide2][ y  + QSide2] + Heights[x + HalfSide2][ y - QSide2]) * e / 4;
if (x != 0)
Heights[x][ y + HalfSide2] = Heights[x][ y + HalfSide2]*(1-e)+
 (Heights[x][ y + QSide2] + Heights[x][ y + SideLength2 - QSide2] +
  Heights[x + QSide2][ y + HalfSide2] + Heights[x - QSide2][ y + HalfSide2]) * e / 4 ;
     }
 }
SideLength2 = SideLength2 / 2;
      }
      
      grid_cnt++;
      SideLength = SideLength / 2;
      r = r / Roughness;
    }
}



* basis_1.jpg (32.52 KB, 500x500 - viewed 1827 times.)

* basis_2.jpg (32.31 KB, 500x500 - viewed 1936 times.)

* Ed2_E.0.jpg (42.9 KB, 500x500 - viewed 1850 times.)

* Ed2_E.55.jpg (37.76 KB, 500x500 - viewed 1869 times.)
« Last Edit: October 01, 2011, 08:37:23 PM by fractower » 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 867 Last post March 16, 2009, 09:21:44 AM
by Nahee_Enterprises
Hip to Be Square Images Showcase (Rate My Fractal) Fractal Ken 0 778 Last post January 10, 2011, 08:20:13 PM
by Fractal Ken
Diamond-square algorithm help Help & Support kronikel 10 1576 Last post April 12, 2011, 02:11:06 AM
by kronikel
Problem with my Diamond Square algorithm Programming mbob61 5 2975 Last post December 12, 2012, 12:17:35 AM
by David Makin
diamond-square midpoint displacement algorithm Landscape/Terrain Generation claude 0 1747 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.212 seconds with 27 queries. (Pretty URLs adds 0.01s, 2q)