Logo by bib - 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. October 03, 2022, 07:37:50 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 19774 times)
0 Members and 1 Guest are viewing this topic.
kronikel
Navigator
*****
Posts: 79



« Reply #30 on: October 01, 2011, 09:47:58 PM »

I'll have to give this a try as soon as I get the time.
I'm still in search of a simple "height = average of 4 corners +- randomness" method, but this looks great for now.
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #31 on: October 02, 2011, 07:12:26 PM »

I'll have to give this a try as soon as I get the time.
I'm still in search of a simple "height = average of 4 corners +- randomness" method, but this looks great for now.

The fastest way to do that is the most obvious - do it in a single step i.e. mid-point=average of 4 corners+/-random and midpoint of each "side"=average of 2 end-points+/-random - this is considerably faster than diamond-square and very simple to implement in terms of returning the height for any given single location - the problem is that the artifice produced is also very obvious smiley
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 #32 on: October 03, 2011, 01:49:51 AM »

That is how I originally had mine set up. It took the average of the two endpoints and there were no cone shapes at all.
But as I made my lighting algorithm more realistic the nasty lines became more and more apparent.

Here's a pic using fractower's version -
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #33 on: October 03, 2011, 12:28:46 PM »

Nice landscape. Unfortunately there are still some spikes there.
The simplest "height = average of 4 corners +- randomness" method (that don't have artifacts) I could think of is to solve Poisson's equation:
laplacian(F(x,y))=g(x,y)
Where g(x,y) gives a random value at each (x,y). It could be solved using Gauss-Seidel method:
Code:
F[x][y] <- 1/4*(F[x+1][y]+F[x-1][y]+F[x][y+1]+F[x][y-1]+g[x][y])
(g{x}{y} is initialized with small (actually depending on the desired max height) zero mean random values)
It have very slow convergence rate but it is fun to see how the terrain grows smiley. I don't know how to introduce roughness factor though. Any ideas?
For faster convergence, multigrid algorithm is perfect.
« Last Edit: October 03, 2011, 12:39:42 PM by knighty » Logged
fractower
Iterator
*
Posts: 173


« Reply #34 on: October 04, 2011, 04:00:44 AM »

I think the method that Knighty suggests will have the same problem as the DS algorithm because the basis functions are almost the same. The solution to Poisson's equation for point sources is a 1/r tent. A better basis would be Gaussian functions. Unfortunately I am not sure how to do this efficiently.

I suspect the spikes are coming from multiple secondary spikes on the basis functions lining up. I found that the spikes can be somewhat reduced by creating a separate erosion parameter for the diamond and square steps, but this is just a patch. At this point I think the best solution is to climb the mountains of the world and make pointy cairns, so over time the undesirable artifacts seem more natural.
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #35 on: October 04, 2011, 05:11:16 PM »

I think the method that Knighty suggests will have the same problem as the DS algorithm because the basis functions are almost the same. The solution to Poisson's equation for point sources is a 1/r tent. A better basis would be Gaussian functions. Unfortunately I am not sure how to do this efficiently.
It depends on the distribution law of g(x,y). For a gaussian and uniform distributions, i don't get the spikes as in DS algorithm. With a distrution that gives few points with high value i get the spikes but they are of different nature. The difference with DS is that the gradient of the obtained heightfield is limited to a value around max(g(x,y)). With DS the gradient tend to infinity at the spikes (cusp singularities). This is because the heights calculated at a given level are frozen at the next levels thus acting like boundary values. Note that the 1/r tent will happen if g(x,y) is a Dirac's delta distribution.

I agree that the spikes are due to the the basis function which is related to the laplacian. I wouldn't go for a gaussian but a (cubic) spline may give nice results at the expense of more points to interpolate (16 instead of 4). I presume that as the laplacian is related to bilinear interpolation there is a partial differential equation related to higher order splines.

Another approache is to use weighted interpolation: The weights are function of the level at which the interpolated points were calculated. I got good results with weight=2^(parameter*level) where parameter is in the interval [0,1]. if parameter==0, we have an unweighted interpolation. Values between 0 and 1 soften the spikes. It is possible to use values higher than 1 but then there are other artifacts that appear (and a nice fractal pattern, pictures later).
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #36 on: October 05, 2011, 05:48:32 AM »

Here's my latest in-progress Diamond-Square formula for Ultra Fractal, not released to the formula database yet.
It's written so you have rapid return of height values given a location even on a random access basis i.e. ideal for shaders etc.
In fact in UF it's only around 50% slower to render the default than it is to render the default Mandelbrot.
At the moment the only extension beyond the repeating square is by splitting the square into smaller fully random squares, this is really all that's necessary in UF as of course formulas like this are primarily used in UF simply to create texturing rather than for creating landscapes but of course splitting the area could be done either from known data or using more sophisticated generation for realistic landscapes.
This version does not vary the roughness factor based on current height or location but I intend to extend it to do so.

Use Standard:Basic:Real as the outside colouring.

Code:
testSquare {
; 0                   1                   2                   3
; b       *1          b        *1         b        *1         b
;
;
;          0          1         2         3         4
;*2       *3         *2        *3        *2        *3        *2
;
; 4                   5                   6                   7
;          5          6         7         8         9
; b       *1          b        *1         b        *1         b
;
;
;         10         11        12        13        14
;*2       *3         *2        *3        *2        *3        *2
;
; 8                   9                  10                  11
;         15         16        17        18        19
; b       *1          b        *1         b        *1         b
;
;
;         20         21        22        23        24
;*2       *3         *2        *3        *2        *3        *2
;
;12                  13                  14                  15
;
; b        *1         b        *1         b        *1         b
global:
  int r[3*62]
  int i = 0
  int seed = @seed
  repeat
    r[i] = seed = random(seed)
  until (i=i+1)>=3*(@depth+@rand)
init:
  float h[16]
  float nh[25]
  float x = (0.25*real(#pixel))%1.0
  float y = (0.25*imag(#pixel))%1.0
  float f = 1.0/#randomrange
  float q = 2.0^(@depth+@rand-1)
  int v[16]
  int nv[25]
  int d = 0
  int j = 0
  int k = 0
  int m = 0
  if x<0.0
    x = x + 1.0
  endif
  if y<0.0
    y = y + 1.0
  endif
  x = x*2.0^(@depth+@rand)
  y = y*2.0^(@depth+@rand)
  repeat
    h[d] = 0.0
    v[d] = 0
  until (d=d+1)>=16
  d = 0
loop:
  repeat
    m = 0
    if y>=q
      y = y - q
      m = m + 5
    endif
    if x>=q
      x = x - q
      m = m + 1
    endif
    if d<@rand*3
      j = 0
      k = 0
      repeat
        nh[k] = f*(nv[k]=v[j]+r[d+2])
        nh[k+2] = f*(nv[k+2]=v[j+1]+r[d+2])
        nh[k+4] = f*(nv[k+4]=v[j+2]+r[d+2])
        j = j + 4
      until (k=k+10)>=25
      j = 0
      k = 0
      repeat
        nh[k+1] = f*(nv[k+1]=v[j+1]+r[d+1])
        nh[k+3] = f*(nv[k+3]=v[j+2]+r[d+1])
        nh[k+5] = f*(nv[k+5]=v[j+4]+r[d])
        nh[k+6] = h[j+5]
        nv[k+6] = v[j+5]
        nh[k+7] = f*(nv[k+7]=v[j+5]+r[d])
        nh[k+8] = h[j+6]
        nv[k+8] = v[j+6]
        nh[k+9] = f*(nv[k+9]=v[j+6]+r[d])
        j = j + 4
      until (k=k+10)>=20
      nh[k+1] = f*(nv[k+1]=v[j+1]+r[d+1])
      nh[k+3] = f*(nv[k+3]=v[j+2]+r[d+1])
    else
      j = 0
      k = 0
      repeat
        nh[k] = 0.25*(h[j]+h[j+1]+h[j+4]+h[j+5]) + f*(nv[k]=v[j]+r[d+2])
        nh[k+2] = 0.25*(h[j+1]+h[j+2]+h[j+5]+h[j+6]) + f*(nv[k+2]=v[j+1]+r[d+2])
        nh[k+4] = 0.25*(h[j+2]+h[j+3]+h[j+6]+h[j+7]) + f*(nv[k+4]=v[j+2]+r[d+2])
        j = j + 4
      until (k=k+10)>=25
      j = 0
      k = 0
      repeat
        nh[k+1] = 0.25*(h[j+1]+nh[k]+nh[k+2]+h[j+5]) + f*(nv[k+1]=v[j+1]+r[d+1])
        nh[k+3] = 0.25*(h[j+2]+nh[k+2]+nh[k+4]+h[j+6]) + f*(nv[k+3]=v[j+2]+r[d+1])
        nh[k+5] = 0.25*(nh[k]+h[j+4]+h[j+5]+nh[k+10]) + f*(nv[k+5]=v[j+4]+r[d])
        nh[k+6] = h[j+5]
        nv[k+6] = v[j+5]
        nh[k+7] = 0.25*(nh[k+2]+h[j+5]+h[j+6]+nh[k+12]) + f*(nv[k+7]=v[j+5]+r[d])
        nh[k+8] = h[j+6]
        nv[k+8] = v[j+6]
        nh[k+9] = 0.25*(nh[k+4]+h[j+6]+h[j+7]+nh[k+14]) + f*(nv[k+9]=v[j+6]+r[d])
        j = j + 4
      until (k=k+10)>=20
      nh[k+1] = 0.25*(h[j+1]+nh[k]+nh[k+2]+h[j+5]) + f*(nv[k+1]=v[j+1]+r[d+1])
      nh[k+3] = 0.25*(h[j+2]+nh[k+2]+nh[k+4]+h[j+6]) + f*(nv[k+3]=v[j+2]+r[d+1])
      f = @sharp*f
    endif
    j = 0
    repeat
      k = 0
      repeat
        h[j] = nh[m]
        v[j] = nv[m]
        j = j + 1
        m = m + 1
      until (k=k+1)>=4
      m = m + 1
    until j>=16
    q = 0.5*q
  until (!@fast && q<1) || (@fast && x==0.0 && y==0.0) \
        || (d=d+3)>=3*(@depth+@rand)
  if @fast
    z = ((0.5/@scale)+h[5])*@scale
  else
    z = ((0.5/@scale)+0.25*(h[5]+h[6]+h[9]+h[10]))*@scale
  endif
bailout:
 false
default:
  title = "Diamond Square wrapped"
  magn = 0.75
  int param depth
    caption = "fBm Depth"
    default = 10
    min = 2
    max = 31
    hint = "Defines rhe detail level i.e. the resolution of the fBm. \
            A value of 2 gives fBm 4*4 detail, a value of \
            3 gives fBm with 8*8 detail and so on. So the default \
            of 9 gives fBm with 512*512 detail and a value of \
            31 gives you fBm with detail 2147483648*2147483648. \
            The overall detail of the random patterns is also controlled \
            by the Random Depth value and that adds or removes detail in \
            powers of 2 in a similar manner. For instance the defaults of 9 \
            for the fBm Depth and 1 for the Random Depth combine to give an \
            overall detail level of 1024*1024 for the complete wrapped \
            pattern. Essentially this means at UF Magnification 1 for a layer \
            then a combined value of 14 is enough even for print size renders \
            at say 8000*8000 pixels and if you are at higher magnification \
            you simply add one to the combined depth per doubling of thr UF \
            magnification or per doubling of the render resolution and you \
            can similarly reduce the value by one for each halving of the \
            magnification or render resolution. So in fact for a normal work \
            render in a 640*480 window with UF magnificastion 1 then a \
            combined Depth of 10 (==1024*1024) is good enough for accurate \
            representation of results when the value is increased to account \
            for higher render resolution/increased magnificatiion. Of course \
            the lower the Depth, the faster the render. Changing the Bit \
            Depth only alters the resolution of the pattern, not the shape, \
            so if wanting exactly similar results at different detail levels \
            then changing the fBm Depth is better than chnging the Random \
            Depth though that couuld also be done when there's no choice \
            left i.e. for reducing detail when fBm Depth is 2 or increasing \
            detail when fBm Depth is 31."
  endparam
  int param rand
    caption = "Random Depth"
    default = 0
    min = 0
    max = 31
    hint = "Specifying values >0 causes the random algorithm to add the \
            specified number of bit-depths prior to the diamond-square method \
            as being raw randoms. This can be used to add more variation to \
            the wrapped fBm squares, the more random depths specified then \
            the more variety you get. Of course when using values >0 then \
            the overall detail level of the wrapped squares is increased and \
            for optimum rendering you need to consider the sum of Bit Depth \
            and Random Depth with respect to magnification and pixel \
            resolution changes. Each Random Depth has less overhead \
            than each Bit Depth in terms of render time. Note that although \
            changing the Bit Depth alone does not really change the patterns \
            (other than their resolution) changing the Random Depth will \
            result in noticeable changes to the pattern by increasing the \
            variation as the Random Depth is increased and vice-versa."
  endparam
  float param sharp
    caption = "Sharpness"
    default = 0.707106781186548
    min = 0
    hint = "The larger the value then the 'sharper' the fBm, in general \
            values from 0.4 to 0.8 work best."
  endparam
  int param seed
    caption = "Random Seed"
    default = 12
    hint = "Use any value you like, each will produce a different pattern. \
            Because of the nature of the UF random generator some values \
            will produce patterns with obvious non-random patterns in them. \
            Just try values until you find one that's of a style you require \
            i.e. one that's more like pure fBm or one that has some \
            non-randomness in it."
  endparam
  float param scale
    caption = "Scale"
    default = 4.0
    hint = "Can be used to adjust the gradient indexes so they are restricted \
            to the range 0 to 1 i.e. so they don't wrap round the gradient. \
            Decrease the value if unwanted gradient wrapping is occurring. \
            The higher you set the 'Sharpness' then the more likely gradient \
            wrapping is to occur."
  endparam
  bool param fast
    caption = "Fast with artifice"
    default = true
    hint = "When enabled the renders will be marginally faster and there will \
            be slightly more noticeable artifice in the patterns at the \
            lowest detail level of the selected overall depth."
  endparam
}

The above would be better written in C/C++/Objective C or assembler - for instance the combining of the randoms at each depth should really be a pure xor but I couldn't do that in UF.
Also the statistical randomness of the (delphi?) random used in UF is appalling.

« Last Edit: October 05, 2011, 06:14:15 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
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #37 on: October 07, 2011, 10:46:39 PM »

Note that I'm pretty sure that the routine in my previous post can be optimised by combining some or all of the loops per pixel.

As it stands it renders at 4096*4096 within Ultra Fractal at around 190 kiloheights/second *using a single thread* on my 2.66GHz Westmeres (or at around 1.6 megaheights/second using up to 24 threads) which means that a suitably modified version on GPU will be quite fast - easily fast enough to use for a realtime multi-resolution mesh rendered landscape and maybe (hopefully) fast enough for realtime in a DE based ray-marching renderer wink
« Last Edit: October 13, 2011, 03:15:26 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
knighty
Fractal Iambus
***
Posts: 819


« Reply #38 on: October 12, 2011, 12:32:12 PM »

the two pictures below show Poisson's equation terrains. The first is done with a Gauss distribution law. The second with a a distribution generated this way:
Code:
return 2*(rnd<0.1 ? 0.9 :-0.1);
One important thing when using this method with repeating boundarys (which I used): Be sure that the sum of all the random values is exactly 0. Otherwise it will not converge.


* ter-poisson-solve-gauss-distrib.JPG (43 KB, 720x413 - viewed 805 times.)

* ter-poisson-solve-0.9--0.1-distrib.JPG (35.17 KB, 720x413 - viewed 1174 times.)
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #39 on: October 12, 2011, 12:44:57 PM »

Now some pictures with the (modified) weighted interpolation suggested in my previous post. Unfortunately it didn't work as expected: it emphasises diagonal and axis directions too much. In order to reduce these artifacts I've added some randomness:
Code:
weight=linearInterpolation(1,rnd,intrpolparam0)*2^(strengthParam*levelOfCurrentPoint*linearInterpolation(1,rnd,intrpolparam1))
It gives some interresting landscapes even if there are still some artifacts So it may need some postprocessing. In the pictures below, only "strengthParam" is varied from 0 to 2.


* ter-roug0.45-smth0.0-rnd.JPG (39.66 KB, 720x413 - viewed 578 times.)

* ter-roug0.45-smth0.5-rnd.JPG (42.12 KB, 720x413 - viewed 545 times.)

* ter-roug0.45-smth1.0-rnd.JPG (45.7 KB, 720x413 - viewed 892 times.)

* ter-roug0.45-smth2.0-rnd.JPG (52.04 KB, 720x413 - viewed 848 times.)
Logged
kronikel
Navigator
*****
Posts: 79



« Reply #40 on: October 12, 2011, 07:33:55 PM »

Those are some interesting results.

I'm still so confused as to how I can copy other people's source code and still end up with the same artifacts.
A google search for "diamond square algorithm source" gives a few examples, and I'd say I've tried about all of them -.-
This one http://www.intelegance.net/code/diamondsquare.shtml shows results which don't appear to have any artifacts.
I can't get it to work but does anyone care to explain?
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #41 on: October 12, 2011, 08:24:17 PM »

I'm not sure I understand correctly. Everybody is getting artifacts with DS. I just notice that the number and "intensity" of the spikes change depending on the seed value of the random numbers generator. This is not surprising because the probability to get extreme values at the begining (say: random<0.1 or >0.9) is not negligible.
Logged
kronikel
Navigator
*****
Posts: 79



« Reply #42 on: October 13, 2011, 02:04:31 AM »

I suppose they all have artifacts in one way or another, but with my way I end up with VERY distinguished cones just about everywhere regardless of anything.
I don't see this happening in other people's
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #43 on: October 13, 2011, 03:23:21 AM »

Note that I'm pretty sure that the routine in my previous post can be optimised by combining some or all of the loops per pixel.

As it stands it renders at 4096*4096 within Ultra Fractal at around 190 kiloheights/second *using a single thread* on my 2.66GHz Westmeres (or at around 1.6 megaheights/second using up to 24 threads) which means that a suitably modified version on GPU will be quite fast - easily fast enough to use for a realtime multi-resolution mesh rendered landscape and maybe (hopefully) fast enough for realtime in a DE based ray-marching renderer wink

The test render:


http://www.fractalforums.com/index.php?action=gallery;sa=view;id=8941

Note that for better quality, at least to avoid the artifice relating to the non-random randoms, the Mersenne twister would be optimum but almost any decent random generator would be better than the built in defaults (that goes for any OS/language and also applies to randoms for optimum rendering of chaos-game fractals).
« Last Edit: October 13, 2011, 03:33:40 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 #44 on: October 20, 2011, 08:52:47 PM »

I took a little time to learn perlin noise, but I'm a little disappointed.
Hopefully I'm doing something wrong, but perlin looks much worse than d-s.

This is a 2d slice of 3d noise.
The artifacts are pretty clear with most settings I put it on.

Any tips? Maybe try a random generator that isn't the default one?
If so, what might be a good one to use with real-time in mind?
Edit: Just tried the "multiply with carry" method and didn't see a difference so I don't think randomness is creating artifacts.
« Last Edit: October 20, 2011, 09:47:37 PM by kronikel » 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 850 Last post March 16, 2009, 09:21:44 AM
by Nahee_Enterprises
Hip to Be Square Images Showcase (Rate My Fractal) Fractal Ken 0 763 Last post January 10, 2011, 08:20:13 PM
by Fractal Ken
Diamond-square algorithm help Help & Support kronikel 10 1561 Last post April 12, 2011, 02:11:06 AM
by kronikel
Problem with my Diamond Square algorithm Programming mbob61 5 2954 Last post December 12, 2012, 12:17:35 AM
by David Makin
diamond-square midpoint displacement algorithm Landscape/Terrain Generation claude 0 1706 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.19 seconds with 24 queries. (Pretty URLs adds 0.011s, 2q)