Making a large fractal terrain using a grid structure.

[igloomedia]

Thanks again everyone!  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      

[igloomedia]

Just a quick update...my Perlin noise prototype is done: 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!

[hobold]

The "Wavelet Noise" paper is very thorough, phew. Don't let that scare you. As far as I can decode it, the method there is for a different use case, but everything you can learn from it will be useful for your terrain generator. I suspect that the described method is higher quality noise then you really need, and more general. A specialized terrain generator could probably be tuned for more speed relatively easily.

[Nahee_Enterprises]

    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.

Greetings, and Welcome to this particular Forum !!!   

Good luck with your "world" terrain.

[igloomedia]

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

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

[cKleinhuis]

thank you for pointing the paper, in fact i am old fashioned and didnt knew the wavelet method for noise functions
i often heard about wavelets at university, but more for using compact data storage for realtime graphics application
thx again, i will read it also

[igloomedia]

Here's another quick update... I've been working on step.2 (downsampling) and step.3 (upsampling) of the algorithm....however, I think I'm doing something wrong as you can see - the downsampled and upsampled splines don't really match ('D' is downsample and 'U' is upsample). http://igloomedia.co.uk/BSplineNoise.html  

Note: downsampling only works when N (the number of coefficients) is even. 2,4,6,8...etc.

[hobold]

The downsampling followed by upsampling is supposed to be a loss of information. The idea is to discard all the high frequency detail that would cause aliasing later on.

I think you are doing the right thing. Try upsampling twice. From then on, the down-up combination is stable and does not lose any more information.

[igloomedia]

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

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.

[hobold]

Take your time. This is not a race, it is an exploration. It is okay to stop for a rose by the wayside, or to ask for directions.

You are right about the power of two sequence. A finer level of detail (of wavelet noise) always has exactly double the frequency (i.e. double resolution along each axis). That's where the name "octave band decomposition" comes from.

I agree that diagonal blur is probably a bug. The wavelet filters that are used in the paper should have very little directional bias.

[igloomedia]

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

[hobold]

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

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

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.

[igloomedia]

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

[igloomedia]

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:









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 

[igloomedia]

Just to say I've corrected my previous error in the prototype wavelet noise.
There was a directional bias to the downsample/upsample previously (because I wasn't correctly accessing the arrays), this has now been removed and is now working.

So here is the working wavelet noise:
http://igloomedia.co.uk/wavelets.html

I could at this stage generate noise in different octave bands and then sum them into some fractal noise - but for now I'm going to focus on making this into a deterministic function of the form waveletNoise(x,y):z