Making a large fractal terrain using a grid structure.

[igloomedia]

Hi everyone!

This is my first post here, and I'm hoping this is the right area to post, but it seems appropriate.

I want to implement a really large virtual world created by generating fractal landscapes. In order to make it really large, I will need to break it down into many separate fractal terrains, stored in grid-cells (because I'm sure my computer doesn't want to have 1000s of kilometers of terrain in its memory all at once  :).

This is my current idea: I will generate the fractal terrain for each grid-cell by using the diamond-square algorithm . The random number generator will be seeded with the grid-cell ID to make sure each grid-cell always produces the same terrain (I am actually doing this already). But my question is how should I realistically join these terrains together seamlessly? 

I could blur the height-fields together near the edges, but this would create an unnaturally smooth terrain at each grid-line.

Could I just seed the edges of the diamond-square algorithm, using the adjacent terrain grid-cells heightfield values?

Is there perhaps a better algorithm than diamond-square available?

Cheers, David

[cKleinhuis]

i would use a random seed for the whole terrain, and not only for the parts,
with the effect, that the fields plug in easily seamlessly together

[cKleinhuis]

and i think the diamond square is not verz apropriate for generating such large terrains,
in mz eyes the perlin noise funktion would create similar results, but they aremore easily usable:

http://en.wikipedia.org/wiki/Perlin_noise

[igloomedia]

Thanks for the advice and reply Trifox.

I'm not sure about the idea of using 1 random seed for the entire large terrain, as this would mean always having to generate the landscape from the same start gridcell. The problem is when I only want to generate the last gridcells - I would have to generate all previous gridcells first, in order to get the same random results. (Because of the random number generator needing to be called precisely the same number of times to reach the same results). In my large virtual world I might want to start on gridcell number 1000 rather than 0 - I'd ideally like to just load the surrounding gridcells in any order. (I hope this makes sense!). 

The perlin noise function seems like it would be ideal - I'm just wondering if it has any down sides compared to diamond-square? I've already found one limitation of diamond-square which I'm not happy with. If seeded with non-planar values (i.e. height values not lying within the same plane) it really breaks down and starts making extremely unnatural looking peaks and valleys along diagonals.

last night I stumbled across the 'square-square' algorithm suggested by Gavin Miller for terrain generation (“The Definition and Rendering of Terrain Maps” 1986). I've seen some results which look far better than diamond-square and I started implementing it. My implementation isn't working - I can't see what I've done wrong though.

I found the square-square algorithm here (on pages 7-8): http://www.gantless.com/programs/macklem.pdf

Unfortunately I can't get the original Miller paper this is based on, otherwise, I might figure out what I did wrong in my implementation. 

Just in case anyone is interested, here is the code I came up with for a square-square algorithm (I'm prototyping the algorithm in AS3):

 

Code:

function squareSquareStep():void {	
	var newGridRes:int = currentGridRes+1;//current grid res is the number of vertices across and down the square is
	var newHeightValuesArray:Array = new Array(newGridRes*newGridRes);
	var newRowNum:int = 0;
	var oneSixteenth:Number = 1.0/16.0;
	var a,b,c,d:Number;
	var e,f,g,h:Number;	
	for (var sqY:int = 0; sqY<currentGridRes-1; sqY++){//vertical loop 
		for (var sqX:int = 0; sqX<currentGridRes-1; sqX++){//horizontal loop 
			a = getAttribFromArrayAt(sqX,sqY);//get attrib from array at reads a height value from the heightValuesArray
			b = getAttribFromArrayAt(sqX+1, sqY);
			c = getAttribFromArrayAt(sqX,sqY+1);
			d = getAttribFromArrayAt(sqX+1,sqY+1);
			//calc new square			
			e = ((9*a + 3*b + 3*c + 1*d)*oneSixteenth) + randomRange();
			f = ((3*a + 9*b + 1*c + 3*d)*oneSixteenth) + randomRange();
			g = ((3*a + 1*b + 9*c + 3*d)*oneSixteenth) + randomRange();
			h = ((1*a + 3*b + 3*c + 9*d)*oneSixteenth) + randomRange();
			//output top vals
			newHeightValuesArray[(sqX*2)+(newRowNum*newGridRes)]=e;
			newHeightValuesArray[(sqX*2+1)+(newRowNum*newGridRes)]=f;		
			//output bot vals
			newHeightValuesArray[(sqX*2)+((newRowNum+1)*newGridRes)]=g;
			newHeightValuesArray[(sqX*2+1)+((newRowNum+1)*newGridRes)]=h;
		}	
		newRowNum+=2;	
	}
	heightValuesArray = newHeightValuesArray;
	currentGridRes = newGridRes;
}

Anyone know anything of the square-square algorithm or how it compares to the perlin-noise function?

Cheers, David

[hobold]

The diamond square algorithm seems to produce lattice artifacts (at least the example image in the wikipedia article has some).

A method named "successive random additions" (a description is hiding somewhere in http://www.inf.uni-konstanz.de/cgip/bib/files/Saupe88c.pdf ) avoids such artifacts, but is conceptually close to midpoint displacement algorithms.

The continuity of your fractal planet cannot be fixed locally as an afterthought. I think you will have to use an algorithm that is global in principle. But that doesn't mean that you cannot evaluate it locally on demand, for just the parts of the landscape that you need.


I would be tempted to use wavelets, more specifically an octave band decomposition of some separable, symmetrical, biorthogonal filter pair with compact support. These are fairly common in image compression, so you should be able to find good literature about them. The basic idea then is to compute a tile of the landscape as an inverse wavelet transform of some "random" wavelet coefficients (I'll explain where those are coming from in a moment). For any landscape tile, only a limited number of coefficients influences the result (slightly more coefficients are needed than the tile has pixels).

The wavelet coefficients (in the case of an octave band decomposition) organize structures (of your landscape, or, more generally, of "the signal") from coarse to fine, not unlike a Fourier transform. But wavelets (the ones I would use) remain localized in space, too. That means only the coarsest level, consisting of a fairly small number of coefficients (theoretically just a single one), is really global. All other coefficients determine shape locally, and need to be generated only on demand.

The coarsest level is essentially a very low resolution map of the whole fractal planet. You can either specify it yourself, fixing large features such as continents and oceans as you wish, or initialize it randomly.


That leaves the problem of finding random wavelet coefficients locally, but repeatably. I think that can be done recursively. Imagine that each grid cell of the coarsest level stores a fixed random seed. Then you can recursively subdivide that cell in four smaller ones (i.e. a quadtree), and generate four new random seeds for those child cells from the one seed of the parent cell. So as you descend from coarse to fine, you keep re-seeding the random number generator. That way, each grid cell, no matter its depth in the quadtree, has a random, but deterministic, random seed associated to it, which can then be used to repeatably generate wavelet coefficients for that tile of that detail level.

[igloomedia]

Hi Hobold, thanks for your reply. I've heard of wavelets before, but never really investigated them. It seems sort of like a fourier-transform pattern, but the amplitude of the wave builds and decays rather rapidly.  Please correct me if I'm wrong, but after looking at several wavelets it seems that they are all symmetrical - obviously they become more complicated when the coefficients of one wavelet depend on another - but I believe they would still be symmetrical and would repeat themselves eventually. I'm curious just because, I wouldn't want to walk half way around my virtual landscape to find an identical mountain range    Cheers! David

[David Makin]

Which method you use basically boils down to whether you're aiming at what would be called "quality" versus rendering speed.
If after quality then either using perlin noise or wavelets would probably be best but if wanting speed then the best method is the simplest which is square-based midpoint displacement i.e. compute midpoints of sides and new centre point. Obviously this method has really noticeable artifacts but it really cannot be beaten for speed and especially lends itself to quickly computing subsets of the full mesh which is not possible using the diamond-square method.
Of course to avoid that type of artefact one can use the Vista Pro triangular midpoint displacent method but that obviously has other drawbacks.

One quick method I have used regarding seeding is to have a base seed value for the whole and n seed values for each depth (e.g. 4 for each depth of diamond square) in the tree and simply combine the seed for the current position with the seed for the appropriate section of the next (e.g. simply using xor or plain add) - if I remember correctly applying that wasn't as simple as I've put it here but it does work when you get it correct !

[David Makin]

I should add there is an alternative method I've used that's also pretty quick and can be used at different levels of speed vs. quality (I don't mean in the sense of realtime adjustment though).
It's a method I thought of and applied as fBm colourings in MMFrac and later in Ultra Fractal (that's when I realised it's sort of a low-tech version of perlin noise).

Baically create a 1D fBm landscape outline using whatever method you prefer.

Then to create the 2D heights simply sum look-up values from the array using indexes from as many angles of line in the 2D plane as you like - the minimum possible to produce a true 2D landscape being 4 look-ups i.e. for the point (x,y) use indexes in x (0 degrees), y (90 degrees), x+y (45 degrees) and x-y (-45 degrees).

Obviously you could scale the indexes as you wish (giving different wavelengths) or offset the indexes (to change phase) and scale the looked up values separately before summation (changing ampitudes) and of course add more angles e.g. using 8 or 16 look-ups, even doubling up some angles at different wavelengths/phases.

This method with 8 angles of line is probably as fast (on a CPU) as the square midpoint displacement method with about the same amount of artifice, howver programmatically it couldn't be simpler even for a shader - just have your 1D array in a texture.

[David Makin]

In case anyones interested here are some images using the single look-up array method - here using 8 angles with 0,90,+45 and -45 using an amplitude 32* bigger than the angles at 22.5, 67.5, -22.5 and -67.5 - in MMFrac it was possible to fly aound the 3D landscape @640*480 on a 486 PC provided it had an FPU

http://www.fractalforums.com/index.php?action=gallery;su=user;cat=39;u=141

[igloomedia]

Hi again everyone! Thanks for the replies David I checked out the images which look quite cool, but I see lattice artifacts on the image with the many islands? Is this caused by the number of angles used in the algorithm? I'm afraid I haven't had much time recently to investigate the various methods posted here (I've been on a quest to find out how the square-square subdivision works).

I eventually figured out the square square algorithm, thanks to Dr.Gavin Miller (a very cool and humble guy, not to mention the original creator of the algorithm) - he explained how he originally created the algorithm based on subdivisions with random offsets - this helped me a lot, and the algorithm just 'clicked' in my mind.

So - here is my AS3 prototype: http://igloomedia.co.uk/square-square.html

It's fractal value is 0.5, and the roughness is quite random. The program loops (you can skip faster by pressing a key). Each step of the subdivision is displayed, so you can see how the algorithm smoothes and modifies itself - which I  think is quite cool to watch.

I will soon investigate the other ideas mentioned here (Dr.Miller himself reccomended perlin noise due to the speed of CPUs/GPUs nowadays)....I'm just wondering with what I have at the moment, if it would be possible to seed adjacent gridcells to seamlessly join together. Perhaps I'm thinking about this in the wrong way. Perhaps I should generate a very large/low-res map of the world and then seed gridcells using the low res map, which then refine it.

To me, producing a landscape seems the easy bit....finding the right scheme to break it down into manageable chunks seems very tricky!

[cKleinhuis]

hey, i do not get what the problem is with the chunks ...

you have a 2dimensional function ( e.g. a modified perlin noise ) which produces endless results in every direction, so, you initialize it with a seed ( for more octaves you can use more than one seed ) , and then you have the function for your  terrain, e.g. you have squares of 100x100 values, then to render the 100st-x and 100st-y tile you would call the function with

myperlin( 100*100+offsetx,100*100+offsety )

where offset is a number between 0 (inclusive) and 100 ( exclusive )

the 0,0 tile would then be:
 
myperlin(offsetx,offsety)

and everything fits perfectly together, so, it is just a question on how to design your 2d function, but the standard perlin noise is a good starting point for such a functionn....

[igloomedia]

Hi again Trifox - I haven't had much time to investigate other methods of terrain generation suggested in this post yet. But you're right. I'm looking into Perlin noise right now and it seems exactly what's needed in terms of managing the 'chunks'. Seeding once and then just being able to get heights as an x/y function seems great and exactly what I need....I'll study this more, cook up another prototype and post the results here once ready Thanks for pointing out the ease of use to me - I hadn't realised exactly how the Perlin function worked before. I'm quite new in general to fractals and terrain generation - I'm doing this as a hobby after becoming interested just a week or two ago. I'm learning though and the suggestions are definitely helping - cheers! 

[hobold]

Not all kinds of wavelet filters are symmetrical. The orthogonal wavelets, for example, are not (as opposed to the biorthogonal family, which is preferred in image compression exactly because of its symmetry). You can think of the filters as basis functions, just like spline basis functions. That does not mean that the shapes built from that basis all must be symmetrical.

My explanation probably was a bit too much information cramped into too little space ... I'll try to give at least a few more buzzwords to untangle the various concepts that together can make up a fractal landscape.

1. procedurally generated, deterministic
You don't want to store a planet-sized map, so you want to compute just the currently visible parts on demand. That computation has to yield consistent results every time you revisit that part of the landscape, thus the procedure used has to control randomness in a way that makes it perfectly repeatable.

2. localized
You want to compute small parts of the whole thing, without the need to compute much of the invisible surroundings.

3. efficiency
The process must be reasonably quick, so that you can indeed compute individual tiles of the map without a noticeable pause.

4. some control about the type of fractal
You'll probably want to control some parameters like, are these rolling hills or steep peaks and cliffs. Randomness shouldn't be so wild as to create 20 mile high mountains that would appear rather unrealistic to a human observer. (Okay, maybe your planet is made of aluminum and has no gravity. )


The wavelets I suggested "automatically" fulfill a few of these criteria. They give you some amount of control, because you can freely adjust the amplitude of the various frequency bands (corresponding to structure size at various detail levels). That allows one to constrict the overall hight of the mountains, but still get a pretty rough skyline (or vice versa, if you wish). Wavelets are localized, too, at least if you chose one of the many filter types that have compact support.

Wavelets can be quite efficient. Google for "Lifting Scheme", and chose a suitable wavelet (say, the Daubechies (2,2)-wavelet, also known as the 5/3 filter pair, or occasionally as the first order spline wavelet). This one can be computed purely in integer arithmetic, with just a dozen or so additions/shifts per pixel, and the computation can be nicely parallelized for SIMD.


The quadtree I suggested because its recursive nature causes it to be localized. As you descend from the root of the tree to a particular leaf, you are following one specific, unique path associated with that one leaf. If information from that path is used as random seed, you have determinism. Quadtrees tend to be efficient, because their depth grows only as the logarithm of the number of leaves (this is true of most any tree data structure).


Regardless of the specific method, wavelets or no wavelets, the four buzzwords are probably qualities that you need to look four in the candidates.

[David Makin]

Hi again everyone! Thanks for the replies David I checked out the images which look quite cool, but I see lattice artifacts on the image with the many islands?

Yes Increasing the number of angle look-ups essentially compensates for the artifice, but of course the next sensible step up from 8 angles is 16 and then the algorithm starts getting less optimum speedwise - though I think still considerably faster than perlin noise or wavelets - depending on the hardware speed of look-up versus the functions/algorithms required for perlin or wavelets.

Incidentally if you use a separate looped 1D array for each angle you could have a wrap-around landscape that could have design control with say 32 arrays/look-ups - here one could raise/lower areas and divide the adjustment between the 32 (or more) arrays such that effects of the change at other locations is minimised - I may have a go at that in UF at some point (using UF's switch control for user landscape design)

[David Makin]

1. procedurally generated, deterministic
You don't want to store a planet-sized map, so you want to compute just the currently visible parts on demand. That computation has to yield consistent results every time you revisit that part of the landscape, thus the procedure used has to control randomness in a way that makes it perfectly repeatable.

2. localized
You want to compute small parts of the whole thing, without the need to compute much of the invisible surroundings.

3. efficiency
The process must be reasonably quick, so that you can indeed compute individual tiles of the map without a noticeable pause.

4. some control about the type of fractal
You'll probably want to control some parameters like, are these rolling hills or steep peaks and cliffs. Randomness shouldn't be so wild as to create 20 mile high mountains that would appear rather unrealistic to a human observer. (Okay, maybe your planet is made of aluminum and has no gravity. )

I agree with these - though I will add that one of course should consider exactly how you are going to render it - nowadays you basically have a choice of using voxels or converting to a mesh or using a distance estimation method (if your heights algorithm is suitable for doing so) - I suspect the distance estimation method will become increasingly favourite the way hardware seems to be heading

.