kronikel


« 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


« 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. midpoint=average of 4 corners+/random and midpoint of each "side"=average of 2 endpoints+/random  this is considerably faster than diamondsquare 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



Logged




kronikel


« 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 GaussSeidel method: F[x][y] < 1/4*(F[x+1][y]+F[x1][y]+F[x][y+1]+F[x][y1]+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 . 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


« Reply #36 on: October 05, 2011, 05:48:32 AM » 

Here's my latest inprogress DiamondSquare 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. 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+@rand1) 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 bitdepths prior to the diamondsquare 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 viceversa." 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 nonrandom 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 \ nonrandomness 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




David Makin


« 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 multiresolution mesh rendered landscape and maybe (hopefully) fast enough for realtime in a DE based raymarching renderer


« Last Edit: October 13, 2011, 03:15:26 AM by David Makin »

Logged




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: 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.



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: 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.



Logged




kronikel


« 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


« 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


« 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 multiresolution mesh rendered landscape and maybe (hopefully) fast enough for realtime in a DE based raymarching renderer The test render: http://www.fractalforums.com/index.php?action=gallery;sa=view;id=8941Note that for better quality, at least to avoid the artifice relating to the nonrandom 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 chaosgame fractals).


« Last Edit: October 13, 2011, 03:33:40 AM by David Makin »

Logged




kronikel


« 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 ds. 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 realtime 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




