Title: Problem with diamond-square algorithm Post by: kronikel 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 - (http://i200.photobucket.com/albums/aa143/kronikel/m1.jpg) And it can be seen very clearly when I set the smoothness up - (http://i200.photobucket.com/albums/aa143/kronikel/m2.jpg) 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 Title: Re: Problem with diamond-square algorithm Post by: David Makin 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). Title: Re: Problem with diamond-square algorithm Post by: kronikel 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() Title: Re: Problem with diamond-square algorithm Post by: David Makin 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 ;) Title: Re: Problem with diamond-square algorithm Post by: kronikel 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. Title: Re: Problem with diamond-square algorithm Post by: David Makin 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 ?
Title: Re: Problem with diamond-square algorithm Post by: fractower 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
Title: Re: Problem with diamond-square algorithm Post by: kronikel 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 -
(http://i200.photobucket.com/albums/aa143/kronikel/map2.jpg) And another example - (http://i200.photobucket.com/albums/aa143/kronikel/map.jpg) 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 - (http://i200.photobucket.com/albums/aa143/kronikel/map3.jpg) @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. Title: Re: Problem with diamond-square algorithm Post by: knighty 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?... Title: Re: Problem with diamond-square algorithm Post by: knighty 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.
Title: Re: Problem with diamond-square algorithm Post by: David Makin 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. Title: Re: Problem with diamond-square algorithm Post by: kronikel 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 (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. Title: Re: Problem with diamond-square algorithm Post by: lycium 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.
Title: Re: Problem with diamond-square algorithm Post by: kronikel 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; Title: Re: Problem with diamond-square algorithm Post by: fractower 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. Title: Re: Problem with diamond-square algorithm Post by: kronikel 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. Title: Re: Problem with diamond-square algorithm Post by: knighty 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 :).@David Makin: Thanks! I don't know how much slower FFT is but you can use arbitrary filters with it (more possibilities/variations). Title: Re: Problem with diamond-square algorithm Post by: DarkBeam on September 28, 2011, 04:18:28 PM Already looked here? http://gameprogrammer.com/fractal.html#diamond
Luca ;D Title: Re: Problem with diamond-square algorithm Post by: kronikel 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. Title: Re: Problem with diamond-square algorithm Post by: David Makin 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 (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. Title: Re: Problem with diamond-square algorithm Post by: David Makin 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). Title: Re: Problem with diamond-square algorithm Post by: lycium on September 28, 2011, 11:15:31 PM (http://dl.dropbox.com/u/3038174/brownian_surfaces.png)
Title: Re: Problem with diamond-square algorithm Post by: lycium on September 28, 2011, 11:16:39 PM rather evaluate it directly in a stateless, functional and parallel way :)
Title: Re: Problem with diamond-square algorithm Post by: kronikel 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. Title: Re: Problem with diamond-square algorithm Post by: cKleinhuis on September 29, 2011, 09:37:01 AM It isnt real because perlin or diamond squares wont peoduce caves or holes. . .
Title: Re: Problem with diamond-square algorithm Post by: David Makin 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) Title: Re: Problem with diamond-square algorithm Post by: kronikel 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. Title: Re: Problem with diamond-square algorithm Post by: knighty on September 30, 2011, 10:21:46 PM It isnt real because perlin or diamond squares wont peoduce caves or holes. . . A 3D version (http://www.diku.dk/hjemmesider/ansatte/torbenm/Planet/PSIslides.pdf) of diamond-square algorithm would generate caves :). 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. You could try using a filter that "detects the spikes". Here is a simple example: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. Code: filter(s){//s is the "strength" of the filter. A good value is around 10 if the heigtmap max height is around 1(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 ( Title: Re: Problem with diamond-square algorithm Post by: kronikel 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. (http://i200.photobucket.com/albums/aa143/kronikel/Untitled-1.gif) Title: Re: Problem with diamond-square algorithm Post by: fractower 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() Title: Re: Problem with diamond-square algorithm Post by: kronikel 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. Title: Re: Problem with diamond-square algorithm Post by: David Makin 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 :) Title: Re: Problem with diamond-square algorithm Post by: kronikel 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 - (http://i200.photobucket.com/albums/aa143/kronikel/ls.jpg) Title: Re: Problem with diamond-square algorithm Post by: knighty 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]) 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. Title: Re: Problem with diamond-square algorithm Post by: fractower 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. Title: Re: Problem with diamond-square algorithm Post by: knighty 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). Title: Re: Problem with diamond-square algorithm Post by: David Makin 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 {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. Title: Re: Problem with diamond-square algorithm Post by: David Makin 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 ;) Title: Re: Problem with diamond-square algorithm Post by: knighty 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); Title: Re: Problem with diamond-square algorithm Post by: knighty 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)) Title: Re: Problem with diamond-square algorithm Post by: kronikel 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? Title: Re: Problem with diamond-square algorithm Post by: knighty 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.
Title: Re: Problem with diamond-square algorithm Post by: kronikel 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 Title: Re: Problem with diamond-square algorithm Post by: David Makin 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 ;) The test render: (http://nocache-nocookies.digitalgott.com/gallery/8/141_13_10_11_3_21_04.jpeg) http://www.fractalforums.com/index.php?action=gallery;sa=view;id=8941 (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). Title: Re: Problem with diamond-square algorithm Post by: kronikel 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. (http://i200.photobucket.com/albums/aa143/kronikel/abc.jpg) 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. Title: Re: Problem with diamond-square algorithm Post by: David Makin on October 20, 2011, 10:23:02 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. 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. Go to the UF formula database: http://formulas.ultrafractal.com/ (http://formulas.ultrafractal.com/) Use the browse option to find Damien Jones' colouring formula, dmj.ucl, and in that take a look at his Fractional Brownian Motion formula (dmj-fBm). Then either in UF or using your own implementation try the following settings for the user parameters: Offset (0,0) Scale 0.6 Rotation 0 Scale step 0.6 Rotation step 43 Octaves 8 Exponent 1.9 And from the basic coordinates as input (e.g. in UF using mt.ufm:pixel as the fractal formula) you should get something like this: (http://nocache-nocookies.digitalgott.com/gallery/9/141_20_10_11_10_22_15.jpeg) http://www.fractalforums.com/index.php?action=gallery;sa=view;id=9026 (http://www.fractalforums.com/index.php?action=gallery;sa=view;id=9026) Title: Re: Problem with diamond-square algorithm Post by: xenodreambuie on October 20, 2011, 11:36:23 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. For the Perlin noise, it looks like you're using the old version with the S-curve 3x2 - 2x3, which is not continuous in the second derivative. That produces the slight creasing at peaks and troughs. Instead, change the blending function to x*x*x*(x*(6*x-15)+10). When adding octaves of Perlin noise, you also want to add some big offsets to the position to avoid correlations near the origin. If you're using the standard hash table method for Perlin noise, it doesn't use many random numbers so the generator isn't important. For a good generator, I used to use Mersenne Twister and had no problems with it, but switched to complementary multiply with carry. Make sure it's a full CMWC, not just MWC. To pass the lottery standard tests, as well as being suitable for high resolution chaos game fractals, it's not enough to have a long period and low correlations. It's also necessary to produce all possible sequences of a given length somewhere in the cycle. George Marsaglia's CMWC generators do this, and are simpler than Mersenne Twister and more flexible for seeding or customizing. Title: Re: Problem with diamond-square algorithm Post by: Syntopia on October 21, 2011, 03:02:40 PM If you want to try with GPU acceleration, you could try McEwan's noise functions: http://www.lighthouse3d.com/2011/03/noise-for-glsl/
I did some tests a few months ago, and was able to do some 4D Perlin-like noise ray marching in real-time: http://vimeo.com/28424494 Notice, that it doesn't look even remotely like a landscape (only two different scales of noise were used). You probably need to combine many scales to get something landscape-like. Title: Re: Problem with diamond-square algorithm Post by: kronikel on October 21, 2011, 08:19:55 PM @ David
Very nice results but I'm not familiar with that type of code and it looks like it might be over my head @ Xeno I believe the hash table method is where you have the array of 0-255 in random order? I'm using a different method which I found here - http://www.gutgames.com/post/Perlin-Noise.aspx I just used common sense / analogy to make it 3D I don't notice anything that looks like "3x2 - 2x3" though Maybe this would be a better approach? http://lotsacode.wordpress.com/2010/02/24/perlin-noise-in-c/ @ Syntopia GPU noise would be ideal for me, but as of now I don't know how to do anything on GPU Title: Re: Problem with diamond-square algorithm Post by: kronikel on October 21, 2011, 09:16:26 PM I implemented the hash table version and I guess that was my only problem.
Very smooth (only 3 octaves) but looks great =) (http://i200.photobucket.com/albums/aa143/kronikel/hm.jpg) Only down side is I'll have to figure out how to add the parameters I had in my first code such as frequency, amplitude, number of octaves, etc. And here it is on my planet - (http://i200.photobucket.com/albums/aa143/kronikel/planet.jpg) 3 fps =/ but at this point I have no optimization at all other than a clunky LOD algorithm I made up in one day. And it's at about 200,000 vertices But it's coming along and I owe some thanks to the people here who have helped me out Title: Re: Problem with diamond-square algorithm Post by: xenodreambuie on October 22, 2011, 12:19:57 AM @ Xeno I believe the hash table method is where you have the array of 0-255 in random order? I'm using a different method which I found here - http://www.gutgames.com/post/Perlin-Noise.aspx I just used common sense / analogy to make it 3D I don't notice anything that looks like "3x2 - 2x3" though Maybe this would be a better approach? http://lotsacode.wordpress.com/2010/02/24/perlin-noise-in-c/ The first link there is not "Perlin" noise. It's a poor interpolation between random values. This type is generally called "value" noise, and even with better interpolation, has visible axis alignment. (I wouldn't recommend his method for cellular noise either - sqrts in a nearest neighbour search!) The second link is the standard (original) Perlin algorithm, with the hashed array. Specifically, it's Perlin gradient noise, because it calculates random gradient values at each lattice point, and the result is less axis aligned than value noise. You can also modify (or add a function) to produce Perlin value noise by just interpolating the values instead of the gradients. The smoothing function at the bottom is as I mentioned, x * x * (3 - 2 * x); this is the part that you can improve with the fifth order polynomial. The difference is more visible in 3d than 2d. Title: Re: Problem with diamond-square algorithm Post by: kronikel on October 22, 2011, 03:38:52 AM Here is a comparison of two different methods
(http://i200.photobucket.com/albums/aa143/kronikel/Untitled-1-1.gif) The one with the blue dot is cosine interpolation and the fifth order polynomial, the other frame is linear interpolation and the regular order polynomial. It seems to give it more distinct features. I haven't seen the effects it has in 3D though. The blue dot frame costs about 5-10% more time. I'll have to see 3D before I can tell if it's worth it. Edit: After messing with it a bit it looks like linear interpolation actually looks better and the fifth order polynomial looks better. Also with 3D noise, if you add the octave you are on to your z coordinate for each octave iteration it looks a bit better and reduces some of the repetition. Title: Re: Problem with diamond-square algorithm Post by: xenodreambuie on October 22, 2011, 06:10:59 AM Here is a comparison of two different methods The one with the blue dot is cosine interpolation and the fifth order polynomial, the other frame is linear interpolation and the regular order polynomial. What you want is linear interpolation and smooth with the fifth degree. This gives the smoothest curve for a single octave. It's noticeable on either a 3d surface or a 1d plot. Title: Re: Problem with diamond-square algorithm Post by: Syntopia on October 27, 2011, 08:55:04 PM A small test with the GPU Ashima-noise functions: Nine different scales of noise added together for a 2D heightmap, and still realtime (GPU raytracing with no polygons).
Two different noise functions are shown. Title: Re: Problem with diamond-square algorithm Post by: David Makin on October 28, 2011, 01:14:29 AM Nice !
Am just trying to find time to do something similar, but also to try an alternative method that I think will be a lot faster (in shader fragments but is a lot slower in UF). Title: Re: Problem with diamond-square algorithm Post by: David Makin on October 30, 2011, 09:13:44 PM Was just trawling my old posts to cross-reference something in the current LRIFS thread and came across this which is (I think) relevant here:
http://www.fractalforums.com/programming/linearising-a-normal-distribution-%28for-the-math-geeks%29/msg13802/#msg13802 (http://www.fractalforums.com/programming/linearising-a-normal-distribution-%28for-the-math-geeks%29/msg13802/#msg13802) Title: Re: Problem with diamond-square algorithm Post by: setec on July 16, 2012, 10:50:15 AM kronikel, solution is to extend terrain with virtual space as show on the attached picture; blue - virtual space (no need to allocate mem for it) red - resulting terrain green - seed poles use for blue height function where result is avg of seed poles + random deviation based on roughness |