Print Page - Making a large fractal terrain using a grid structure.

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? :hmh:

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

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!). :dink:

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 (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 :)

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.

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 !

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.

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 (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!

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.

Quote from: igloomedia on July 25, 2010, 02:00:44 PM

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

Quote from: hobold on July 25, 2010, 06:52:57 PM

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

.

Thanks again everyone! ;D This place is certainly very open/friendly compared to many forums I've experienced. looks like I'll be a stayer. :)

@hobold - You've certainly boiled-down the requirements I'm looking for into the right buzz words. hehe. :) I now know what to call what I'm looking for, which is always handy! I'm now reading through 'Wavelet Noise' by Cook et al. So I'm now getting to see why wavelet noise is superior to Perlin noise. The loss of detail (or aliasing) visible when excluding or including the different bands (due to the bands having weak frequency limits?) leads to quite nasty artifacts and the paper shows that quite well in it's many examples. You're also right that I'm looking for a way of modulating the fractional value to create realistic looking terrains rather than just aluminum moonscapes. :)

Actually - I'm wondering about ways to make this fractal world realistic; although I think it's slightly off-topic, when looking at a real world-map it is obvious that most countries are fairly flat, with only some outcrops of mountains, and although most coast-lines are fairly jagged there are not many tiny islands or rocks surrounding the land (which I see in all my fractal terrains I've created so far). I suppose this is due to erosion from the sea (and the sand deposits), but I suppose it could also be a lower fractal value to approximate this.

@DavidMakin - As far as rendering goes, I'm probably going to go with constructing meshes for the various chunks of my landscape. The reason for this is that I'll be implementing rendering in OpenGl ES 1.0 which does not include a shader language (I'm currently learning ES2.0 - I'm comfortable doing all matrix transforms myself, but I haven't gotten to grips with using the shading language yet); but also I'm going to be having some fun with physics in my landscape - the calculations for this will require triangle-triangle collision detection. Building the meshes will be on the CPU so I can share between renderer and physics engine :)

Once again - thanks for all the advice. Due to all the new information I'm absorbing, I'm shifting over to use wavelets or perlin noise (probably wavelets - if I can get a prototype working soon). Cheers :) :dink:

Just a quick update...my Perlin noise prototype is done: http://igloomedia.co.uk/testPerlin.html (http://igloomedia.co.uk/testPerlin.html) Moving the mouse around will change the offsetX and offsetY. It is visibly deterministic, so it covers 1 of the 4 buzzwords at least ;). The speed isn't too good. I'm creating a 64x64 2d perlin noise bitmap every time the mouse moves. It's coded in flash which is quite slow, but hopefully when it's in C it might be a little faster.

In other news - I've looked and read a bit more about wavelets, and I understand the multiresolution sampling nature of them (the M(x) part of Cook et al - Wavelet Noise). But the part I don't understand is the noise function itself (the N(x) part of Cook et als paper). It's very long-winded.

Knowing that wavelet noise is superior to Perlin noise makes me want to use it. Reading the maths behind it makes me want to chicken-out! :P

Hi Nahee - thanks for the welcome to the forums! :)

After testing and considering quite a few options and reading many papers, I have to agree with hobold on this and I think wavelets are the way to go for generating the nicest (fractal) noise for terrains (they're even faster to compute than regular perlin noise, according to pixar).

The paper which I'm using as my tutorial in creating wavelet noise ("Wavelet Noise" - Cook et al, 2005) is here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.8223&rep=rep1&type=pdf (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.8223&rep=rep1&type=pdf)

The maths is quite heavy - and I'm not very comfortable with mathematical notation in general. I have made some progress though...I've gotten the very first step working (i.e. generating 1d noise with a quadratic b-spline filter). This is step 1, section 3.4 Constructing Noise bands on page 4 of the paper which I'm using. There is a nice diagram of this in fig.4a on the same page :)

Anyway, here is my prototype of step.1:
http://igloomedia.co.uk/BSplineNoise.html (http://igloomedia.co.uk/BSplineNoise.html) - clicking the plus/minus buttons will add or remove random coefficients.

(Side note: Progress is painfully slow with the wavelets..unfortunately, this is because of my maths...It takes me a long time to grasp the concepts hidden behind the shorthand mathematical notation. I decode everything first to my own (long) form which I understand...this is because I never learned mathematical notation in school or University; despite majoring in computer science I'm perhaps not the best advert for the British education system ::).
On the other hand, I've still achieved the first step...I'm trying to push forward. I have a stubborn determination to get this working... :) Posting updates here seems to get me more motivated.)

Thanks again for the replies. I think Hobold is right and the downsampling/upsampling is working ok.

I'm now generating some noise tiles as in the pixar paper. downsampling then upsampling and subtracting from the original gaussian noise. This leaves me with the high frequency noise.
Here is my prototype of this: http://igloomedia.co.uk/wavelets.html (http://igloomedia.co.uk/wavelets.html)

I'm not 100% sure, but it looks like my down/up sampling is going slightly wrong, as the second square seems to be blurred diagonally (rather than uniformally, which I would expect). The down/up sampling didn't have this problem in 1D, but now in 2D it does. I suspect it is an array indexing issue (and my own fault).

OK - so I understand this part of the wavelet theory, however, in order to generate different 'bands' of noise, I suppose I will perform a weighted sum of different frequency noise. So my question is: how would I go about generating different frequencies? is each 'band' twice the resolution of the last 'band'? e.g. my slow rolling hills would be very low resolution noise (upscaled) and my little rocky sticking out parts would be a larger resolution noise image added to the low resolution upscaled image. Correct?

In other words, my bands could have these resolutions: 16, 32, 64, 128, 256....etc.

My updates got a bit slow I'm afraid....I've gotten a new job which is mentally energy draining and I don't have quite so much free time now. :(

Right now - it's time to stop for a rose by the wayside and ask for directions. I apologise in advance for the number of questions I'm asking - I seem to have hit a deadend recently.

I have a few questions left...

1. I'm working off the wavelet noise generator given in the pixar paper. (I tested the theory behind it and built prototypes before I jumped in).
In the noise generator in the paper, the solution supplied generates 3D noise. This is great, but not what I want. I just want 2D noise. I understand the B-spline based upsample and downsample filters in 1D - but I don't understand how I would apply this in 2D. In the Pixar wavelets paper it seems as if they are downsampling row-by-row and then column-by-column, and then the same for upsampling. Is this the correct way to do a 2D B-spline down/up sample?

2. Given that I want a 2D heightmap for my terrain, I assume I will need to combine all the noise-bands into one final height (at any given xy). Imagine I have 2 noise bands, one of resolution 16 and another at 32. In order to do a weighted sum of these I assume I'm going to have to upscale the lower frequency/resolutions until they match the highest frequency/resolution. Won't this get very heavy, very fast? In the pixar paper it claims to be faster than perlin noise, I just don't understand how...

3. I'd like my terrain to be deterministic. If I return to coordinate x,y, the landscape I see should always be exactly the same. Ideally, I'd write a function which given x,y parameters, returns a height value. Since wavelet noise uses upscaling and downscaling, it relies on finite-sized images/arrays of which to up/down sample. So, in order to evaluate an xy point, I'd have to first pre-calculate the heightmap/grid in which that point lies? Will there not be anomalies caused by upsampling/downsampling at grid-borders?

Sorry - I realise this is pretty heavy. My mind is boggled too. :p

Cheers, D :)

Quote from: igloomedia on September 12, 2010, 02:53:25 PM

In the Pixar wavelets paper it seems as if they are downsampling row-by-row and then column-by-column, and then the same for upsampling. Is this the correct way to do a 2D B-spline down/up sample?

This is the correct way of using these so-called "separable" wavelets, or these so-called "tensor" splines. Both buzzwords mean essentially the same thing in different contexts: that you can treat all coordinate axes independently of each other. In other words, a 2D signal is just many 1D signals side by side. And it doesn't matter if you process rows first or columns first. (There may be minor differences due to rounding error, but mathematically all coordinate axes are completely interchangeable.)

Quote

Imagine I have 2 noise bands, one of resolution 16 and another at 32. In order to do a weighted sum of these I assume I'm going to have to upscale the lower frequency/resolutions until they match the highest frequency/resolution. Won't this get very heavy, very fast? In the pixar paper it claims to be faster than perlin noise, I just don't understand how...

Let's look at this backwards for a moment. If you had a signal made of 32 sample points, you could use wavelets do decompose it into 16 low pass (also known as "coarse") and another 16 high pass (also known as "detail") coefficients. So the overall amount of data has not changed, you still have 32 numbers.

The 16 high pass coefficients tend to look like the result of an edge detection filter; if there was a lot of detail in the original signal (perhaps because it was a fractal), then the high pass results tend to be noisy. The 16 low pass coefficients, in contrast, look like a smoothed and shrunken version of the original signal (missing all the small details). Thus the first level low pass result is amenable to being decomposed again, into eight second level low pass and another eight second level high pass coefficients.

This can be done recursively until we end up with just a single low pass coefficient (which represents the average of the whole original signal), and 31 (16+8+4+2+1) high pass coefficients of various levels. So in this case, the lower the frequency, the fewer coefficients there are.

This is where the speed comes from: you never have to process more numbers than there are pixels. Upsampling and downsampling are distinct steps only in theory; in practice this is just a matter of how you access some numbers in an array. Perhaps this will become clearer if you dig into yet another buzzword: wavelet lifting scheme (lifting is another way to actually compute wavelet transforms; ignore the theory for now, and just focus on the layout of the interleaved low and high pass coefficients).

Quote

So, in order to evaluate an xy point, I'd have to first pre-calculate the heightmap/grid in which that point lies? Will there not be anomalies caused by upsampling/downsampling at grid-borders?

The border does indeed cause a bit of extra trouble. I think the method described in the paper generates a repeating noise pattern, so they have one giant tile that wraps around at its borders. But in practice they can conceal the repetition simply by using only subsets of that giant tile. As they zoom in, they can just keep adding new detail (i.e. more upsampling and more high pass coefficients). Repetition is not as noticeable here, because the details may repeat, but the coarse structure doesn't.

Once again thanks Hobold. Your response has cleared my mind on how to tackle a few of these problems. I've decided to tackle one problem at a time for now, as the big picture is quite dizzying.
Regarding my prototypes created in Flash, my last Flash prototype suffered from odd diagonal blurring which shouldn't have happened. I've now decided to skip the prototyping stage and get straight into coding it in C. I've taken the Pixar source code (literally copied and pasted) and modified it by commenting out a few lines and adjusting others in order to achieve 2D noise tile generation.
However - I see something weird happening. I trace the float values which it creates in the 2D noise array; specifically this line: printf("noise[%i]=%f\n", i, noise);. But some rows are output as simply zeros. I know this cannot be right, because a row of all zeros would mean a very odd looking black horizontal line in the noise tile.
I believe I'm doing everything correctly in order to modify it to output 2D rather than 3D - because this should be just a case of changing the array access to ignore Z outputs. Without further ado, here is the C source I'm currently working on:

Code:

#define ARAD 16
static float *noiseTileData; static int noiseTileSize; 
int Mod(int x, int n) {int m=x%n; return (m<0) ? m+n : m;} 

void Downsample (float *from, float *to, int n, int stride ) {
    float *a, aCoeffs[2*ARAD] = { 
        0.000334,-0.001528, 0.000410, 0.003545,-0.000938,-0.008233, 0.002172, 0.019120,
        -0.005040,-0.044412, 0.011655, 0.103311,-0.025936,-0.243780, 0.033979, 0.655340,
        0.655340, 0.033979,-0.243780,-0.025936, 0.103311, 0.011655,-0.044412,-0.005040,
        0.019120, 0.002172,-0.008233,-0.000938, 0.003546, 0.000410,-0.001528, 0.000334};
    a = &aCoeffs[ARAD];
    for (int i=0; i<n/2; i++){
        to[i*stride] = 0;
        for (int k=2*i-ARAD; k<=2*i+ARAD; k++)
            to[i*stride] += a[k-2*i] * from[Mod(k,n)*stride];
    }
}

void Upsample( float *from, float *to, int n, int stride) {
    float *p, pCoeffs[4] = { 0.25, 0.75, 0.75, 0.25 };
    p = &pCoeffs[2];
    for (int i=0; i<n; i++){
        to[i*stride] = 0;
        for (int k=i/2; k<=i/2+1; k++)
            to[i*stride]+= p[i-2*k] * from[Mod(k,n/2)*stride];
    }
}

float gaussianNoise() {
    float range = 1-(-1);
    float randomNum = -1 + ((float)random()/RAND_MAX)*range;
    //printf("gaussian noise: %f\n", randomNum);
    return randomNum;
}

void GenerateNoiseTile(int n) {
    if (n%2) n++;//tile size must be even
    //int ix, iy, iz, i, sz=n*n*n*sizeof(float); float *temp1=(float *)malloc(sz),*temp2=(float *)malloc(sz),*noise=(float *)malloc(sz);
    int ix, iy, iz, i, sz=n*n*sizeof(float); float *temp1=(float *)malloc(sz),*temp2=(float *)malloc(sz),*noise=(float *)malloc(sz);
    /* Step 1. Fill the tile with random numbers in the range -1 to 1. */ 
    //for (i=0; i<n*n*n; i++) noise[i] = gaussianNoise();
    for (i=0; i<n*n; i++) noise[i] = gaussianNoise();
    /* Steps 2 and 3. Downsample and upsample the tile */
    for (iy=0; iy<n; iy++) for (iz=0; iz<n; iz++) {//each x row
        i = iy*n + iz*n*n;
        Downsample(&noise[i], &temp1[i], n, 1);
        Upsample(&temp1[i], &temp2[i], n, 1);
    }
    for (ix=0; ix<n; ix++) for (iz=0; iz<n; iz++) {//each y row
        i = ix + iz*n*n;
        Downsample(&temp2[i], &temp1[i], n, n);
        Upsample(&temp1[i], &temp2[i], n, n);
    }/*
    for (ix=0; ix<n; ix++) for (iy=0; iy<n; iy++) {//each z row
        i = ix + iy*n;
        Downsample(&temp2[i], &temp1[i], n, n*n);
        Upsample(&temp1[i], &temp2[i], n, n*n);
    }*/
    /* Step 4. Subtract out the coarse-scale contribution */
    //for (i=0; i<n*n*n; i++) {noise[i]-=temp2[i];}
    for (i=0; i<n*n; i++) {noise[i]-=temp2[i];}
    /* Avoid even/odd variance difference by adding odd-offset version of noise to itself */
    int offset=n/2; if (offset%2==0) offset++;
    for (i=0,ix=0; ix<n; ix++) for (iy=0; iy<n; iy++) //for (iz=0; iz<n; iz++)
        //temp1[i++] = noise[ Mod(ix+offset,n) + Mod(iy+offset,n)*n + Mod(iz+offset,n)*n*n ];
        temp1[i++] = noise[Mod(ix+offset,n) + Mod(iy+offset,n)*n];
    //for (i=0; i<n*n*n; i++) {noise[i]+=temp1[i];}
    for (i=0; i<n*n; i++) {noise[i]+=temp1[i];}
    noiseTileData=noise; noiseTileSize=n; free(temp1); free(temp2);
    printf("Generated noise tile of size %i\n",n);
    for (i=0; i<n*n; i++) {
        printf("noise[%i]=%f\n", i, noise[i]);
    }
}

I'm sure I must have slipped up. I don't want to believe pixar messed up in one of their papers ;)

Hi everyone,

I was very stuck with the wavelet noise generation, so rather than dwelling on it, for now I've been continuing and I've done the texture/colour generation part of the program. I'm hoping that some visible results will give me some motivation to finish this project, and also create some more interest here on the forum.

Currently it is using these factors for each 'terrain type': altitude, slope, temperature, humidity. And it's using these terrain types: 'rock', 'soil', 'vegetation', 'precipitation' (snow).

Here are a few screenshots:
(http://igloomedia.co.uk/screenshots/sc1.png)
(http://igloomedia.co.uk/screenshots/sc2.png)
(http://igloomedia.co.uk/screenshots/sc2.png)
(http://igloomedia.co.uk/screenshots/sc3.png)
(http://igloomedia.co.uk/screenshots/sc4.png)
(http://igloomedia.co.uk/screenshots/sc5.png)
(http://igloomedia.co.uk/screenshots/sc6.png)
(http://igloomedia.co.uk/screenshots/sc7.png)

These are using quite a low resolution mesh, so I think the results are not too bad.
The mesh is generated using the square-square method (I discussed this previously)...ideally, I'd be using wavelets for more control of shape and the possibility of stretching on (seamlessly) to infinity.

So, that's the only progress for now. RIP Mandelbrot, thanks for the insights.

Cheers. David :)

Welcome to Fractal Forums

Fractal Software => Help & Support => Topic started by: igloomedia on July 22, 2010, 04:15:50 PM