24 replies to this topic

[Yourself]

So I've been dabbling with procedural content generation for some years now and especially looking at noise generation.  For those that don't know, noise is a way of generating pseudo-random values over some space in a deterministic way.  That is a noise function assigns one value to each point in space.  If I give it the same coordinates, it will always give the same noise value.  The reason it's pseudo-random is that if you back up and look at it from far away, it looks something like this (in 2D):

http://www.ultimatepronoun.com/images/noise/turbX.png

Now, this isn't just any noise, this is what's called coherent noise (or sometimes gradient noise).  Plain old noise might simply look like static, but coherent noise has a few important properties.  The first property is that it's smooth (or in mathematical terms, it's differentiable).  So if you move a little bit in any direction the noise value will only change by a little bit.  The other property is that it has a constant frequency (so mathematically its Fourier transform peaks at a narrow band).  The frequency is associated with the size of the noise features, so higher frequencies mean smaller features (the noise changes more rapidly but still remains smooth).

So that's what noise is.  What can we do with it?  One obvious application is in generating textures.  Manipulating noise in the right way can allow you to do anything from generating clouds and fire to different kinds of rock or even organic looking textures.  You can even use it to generate animated textures by taking 2D slices of 3D noise.  It can also help in the generation of textures that map onto a sphere without any seams.  Doing this manually can be very difficult, but 3D noise makes it easy.  I'll go into more detail later.

Another of the common applications of noise is to use it to generate height maps and terrain.  By adding together different frequencies of noise scaled by different amounts you can get very convincing terrain.

Another application is in perturbing other functions in space.  This application is called turbulence and involves perturbing the input coordinates to another function by noise.  I.e. before evaluating another function at a given point, p/i], we first compute the value of two different noise functions at p and then add the result onto [i]p and send it to the next function.  First, let's start with two functions that have no turbulence added just to see what they look like normally:

http://www.ultimatepronoun.com/images/noise/mandelbrot.png
http://www.ultimatepronoun.com/images/noise/checkerboard.png

Now, turbulence has two parameters that we can control: frequency and power.  The frequency of the turbulence is just the frequency of the underlying noise functions.  The power is a number that we multiply the noise functions by when we add it to a point.  So no turbulence is just the same as turbulence with 0 power.  So let's add some turbulence with frequency 1 and a low power of 1/16 to our images and see what happens:

http://www.ultimatepronoun.com/images/noise/mandelbrot_p00625_f1.png
http://www.ultimatepronoun.com/images/noise/checkerboard_p00625_f1.png

They get warped and bent a little bit.  The checkerboard now looks a little wavy.  Let's try increasing the frequency to 4.

http://www.ultimatepronoun.com/images/noise/mandelbrot_p00625_f4.png
http://www.ultimatepronoun.com/images/noise/checkerboard_p00625_f4.png

It's almost like looking through a bumpy pane of glass now.  The overall shape is preserved, but the boundaries are warped and twisted.  Let's lower the frequency back to 1 and try increasing the power to 1/4.

http://www.ultimatepronoun.com/images/noise/mandelbrot_p025_f1.png
http://www.ultimatepronoun.com/images/noise/checkerboard_p025_f1.png

So we can get more dramatic changes.  Turbulence can fundamentally change the way functions behave in an interesting way.

So now that we know what noise is and what we can do with it, we've come to the most important part: how do we make noise?  I'll save that for later.

[e_barroga]

I've written perlin noise before. Sounds like the same properties.

[The Scorpion]

I would try the Blur effect.
just draw straigt edged shapes with a blur effect.
It should do the work.

Hope I helped.

[Yourself]

I've written perlin noise before. Sounds like the same properties.

Perlin noise is one implementation of coherent noise and it's one of the ways I'll cover briefly later on. The method I'm going to focus on, however, is simplex noise. The reason for this is that Perlin noise is actually pretty expensive since it has O(2ⁿ) complexity, so each time you go up in dimension by one, its speed decreases by a factor of 2. It simply doesn't scale well. Simplex noise, on the other hand scales with O(n²), so it's much better computationally. The problem is it's difficult to understand mostly because there aren't actually any really good explanations. There is one decent explanation (Simplex Noise Demystified) but it has several magic numbers and constants that are never actually explained and are definitely not empirically determined. I managed to really nail down all the aspects of simplex noise in any number of dimensions, so I'm going to describe that in a later post.

Hope I helped.

You did not. It seems like you didn't even bother to actually read the topic. I wasn't asking for help and even if I was, blurring random shapes is too vague of an algorithm description to help. Please read the topic before trying to contribute.

[e_barroga]

Looking forward to the method. Now that I think about it, perlin did seem to have ridiculous complexity level.

[chance]

The first property is that it's smooth (or in mathematical terms, it's differentiable). So if you move a little bit in any direction the noise value will only change by a little bit. The other property is that it has a constant frequency (so mathematically its Fourier transform peaks at a narrow band). The frequency is associated with the size of the noise features, so higher frequencies mean smaller features (the noise changes more rapidly but still remains smooth).

Can you get the same effect by constructing your noise from a Fourier series? And choosing the coefficients to get the desired effect, of course.

I've generated some fairly realistic terrain this way. Not as rigorous as your noise functions, but very fast to calculate. Surprisingly few terms are needed to get realistic effects.

[Yourself]

Can you get the same effect by constructing your noise from a Fourier series? And choosing the coefficients to get the desired effect, of course.

I suppose you could, but it would require you to generate first random noise and then filter out the frequencies you're not interested in. Starting from a Fourier series, however, would require you to work with a completely periodic signal. Provided that the period is large enough compared to the wavelength that usually isn't a problem (often noise ends up being periodic for practical reasons). It requires a lot of human intervention, though.

[chance]

Can you get the same effect by constructing your noise from a Fourier series? And choosing the coefficients to get the desired effect, of course.

I suppose you could, but it would require you to generate first random noise and then filter out the frequencies you're not interested in. Starting from a Fourier series, however, would require you to work with a completely periodic signal. Provided that the period is large enough compared to the wavelength that usually isn't a problem...

I just use 10-20 terms of the series, with coefficients that taper the higher-order terms (like 10/N, where N is nth term). And to avoid the periodic appearance, I just add a phase shift p[N] to the sine term. It just takes an instant to generate a very nice sample. Very fast.

Using a random phase shift between say 0-pi/4, generates some interesting terrain. And you can tailor it however you want. I usually pass it through a filter to keep the edges at zero, like sin(i*pi/2L)

1-D example:
sum over i
sum over N
f[i] += C[N] * (cos(i*N*pi/L) + sin(i*N*pi/L + p[N]));

But I don't want to distract your topic. So maybe I'll post some examples in a different topic at some point.

EDIT: testing code box wrap...

Edited by chance, 15 November 2010 - 05:45 PM.

[xshortguy]

My first question is how can we generate a smooth noise map? My first instinct is:

1. Create a two-dimensional array of numbers, each with a random value assigned from [0, 1].
2. Choose a radius R parameter. Then for each point, find the average value of the entries on the disk of radius R. From here, scale everything into one preset standard deviation of the average.
3. After this is done, renormalize the array so that the smallest element is mapped to 0, the largest element is mapped to 1.
Reiterate several times, choosing a smaller radius for each time.

The problem is that I don't quite understand how this will behave. For large grids, there will certainly be gaussians involved in these values, but I'm not sure how well this smooth the object, and it will be computationally expensive. Enlighten me on any quick way of generating this.

[Yourself]

My first question is how can we generate a smooth noise map?

Gradient noise. Rather than trying to assign a pseudo-random value to a finite set of points, we assign a pseudo-random gradient to a finite set of points and then interpolate between them in some fashion. This is what makes Perlin noise so expensive computationally. Perlin noise works by assigning a pseudo-random gradient to each integer grid point. Then, to evaluate the noise function at a particular point, it determines the 2^N surrounding grid points and interpolates between all of them.

Create a two-dimensional array of numbers, each with a random value assigned from [0, 1].

The problem with every approach that does this is that you have to generate all of the noise that you need right from the beginning. It's very expensive in terms of memory and does not scale well.

[Erik Leppen]

The only way I know of to generate this kind of stuff is to first generate 2 x 2 pixels of random data, and then repeatedly split each pixel into 2 x 2 pixels of random data in the range of the original data.

So you have first 2 x 2 pixels of random_range([-1, 1]).
Then each pixel P is split into 2 x 2 pixels of the value value_at_P + random_range([-0.5, 0.5)]
Then you have 4 x 4 pixels.
Then each pixel P is split into 2 x 2 pixels of the value value_at_P + random_range([-0.25, 0.25])
Then you have 8 x 8 pixels.
Then each pixel P is split into 2 x 2 pixels of the value value_at_P + random_range([-0.125, 0.125])
Then you have 16 x 16 pixels.
etc. etc.
As each pixel represents a smaller area each iteration, the maximum deviation from P is also made smaller. Also because 1 + 0.5 + 0.25 + 0.125 + ... is bounded at 2 you know for sure all eventual values lie in the interval [-2, 2].
When you have enough pixels, you need a smoothing function (blur, convolution) to flatten everything. Probably this is the most time-consuming step. In GM I think this can be done by using ds_grid_add_disk. For those interested, I have used this circle blurring method for ByteAlity Tower Defense to find the region with the largest crowd of enemies. Adding circles at the same center with different radii comes down to adding "spheres" to the ds_grid and then finding the maximum of the sum of all spheres gives the crowdedest area.

This is the only method I know for this kind of noise generation and I believe NoLimits uses it for height map generation. Of couse as it is defined pixel-wise you can't speak of continuity, but for most game applications this is probably good enough.
You can probably improve this by adding smoothing steps in between, or alter the value at a new "quarter-pixel" by the surrounding values, rather than just using value_at_P only.

[chance]

My first question is how can we generate a smooth noise map?

Gradient noise. Rather than trying to assign a pseudo-random value to a finite set of points, we assign a pseudo-random gradient to a finite set of points and then interpolate between them in some fashion.

This will generate a smooth noise map, but with what statistics? How do you generate a 2D map with a specific frequency distribution?

Edited by chance, 15 November 2010 - 08:50 PM.

[Yourself]

My first question is how can we generate a smooth noise map?

Gradient noise. Rather than trying to assign a pseudo-random value to a finite set of points, we assign a pseudo-random gradient to a finite set of points and then interpolate between them in some fashion.

This will generate a smooth noise map, but with what statistics? How do you generate a 2D map with a specific frequency distribution?

Since the gradients are associated with integer grid locations (and those grid locations have a noise value of 0) the frequency will be related to the size of the grid. To get different frequencies you need only multiply the input coordinates by a given frequency. If I had more time I'd go into detail, but I'm going to Vancouver for a few days (presenting at a conference). I might have some free time to write the post while there.

[chance]

Since the gradients are associated with integer grid locations (and those grid locations have a noise value of 0) the frequency will be related to the size of the grid. To get different frequencies you need only multiply the input coordinates by a given frequency.

Not sure I follow... unless you mean add another grid with a different spatial resolution (interpolated to a common resolution).

Isn't there some way to do this by using the PDF of the distribution you want your statistics to follow?

P.S. what's your paper about?

[Yourself]

Since the gradients are associated with integer grid locations (and those grid locations have a noise value of 0) the frequency will be related to the size of the grid. To get different frequencies you need only multiply the input coordinates by a given frequency.

Not sure I follow... unless you mean add another grid with a different spatial resolution (interpolated to a common resolution).

Isn't there some way to do this by using the PDF of the distribution you want your statistics to follow?

P.S. what's your paper about?

Sorry, thought I'd get a chance to reply while waiting for my plane in LAX, but they don't have free wi-fi (and it's also a terrible airport). I'm waiting for my flight out of YVR right now which *does* have free wi-fi (and is a nice airport), but I don't have much time. The way the gradient noise works is by assigning a gradient to each integer grid point. It also constrains the value of the noise to be 0 at those grid points. So basically the frequency is fixed to the size of the grid. If another frequency is desired, you can just use a change of coordinates to get the desired frequency content.

I'll explain this more (with an actual implementation in pseudo-code) when I get back tonight or tomorrow.

[chance]

The way the gradient noise works is by assigning a gradient to each integer grid point. It also constrains the value of the noise to be 0 at those grid points. So basically the frequency is fixed to the size of the grid. If another frequency is desired, you can just use a change of coordinates to get the desired frequency content.

But won't that approach limit your grid to one particular frequency? What if you want a particular frequency distribution, with a particular PSD? Like turbulence for example. A wide range of frequencies are present - each with its own relative magnitude compared to other frequencies.

With your method, to achieve that distribution in a single realization, you'd need to add an infinite number of frequencies, each with its own weighting. That doesn't sound practical.

There must be a method that uses a frequency distribution, or PSD function, to generate the desired statistics in one step.

Edited by chance, 18 November 2010 - 09:44 PM.

[Gamer3D]

But won't that approach limit your grid to one particular frequency? What if you want a particular frequency distribution, with a particular PSD? Like turbulence for example. A wide range of frequencies are present - each with its own relative magnitude compared to other frequencies.

With your method, to achieve that distribution in a single realization, you'd need to add an infinite number of frequencies, each with its own weighting. That doesn't sound practical.

There must be a method that uses a frequency distribution, or PSD function, to generate the desired statistics in one step.

A small sample of frequencies should produce convincing turbulence. If that's not good enough for you, then using a different noise function is in your interests.

EDIT: Before yourself posts the implementation, here is a fun little thing about simplex noise:

For n dimensional simplexes, we can scale up along the (1, 1, 1, ..., 1) axis to reach a hypercube. The equation to solve to find the scale factor is

2 = (1 + x) ^ 2 + (n-1)x^2

The solution to this is

x = (sqrt(1 + n) - 1) / n

For simplicity, this finds the difference between the scale factor and 1. The scale factor is 1 + x.

Edited by Gamer3D, 19 November 2010 - 04:10 AM.

[Yourself]

But won't that approach limit your grid to one particular frequency?

Yes, that's the point.

There must be a method that uses a frequency distribution, or PSD function, to generate the desired statistics in one step.

Not one that's cheap.

The equation to solve to find the scale factor is

Okay, where does that equation come from? I've never seen an equation actually given anywhere and my approach to this problem was different. One problem I often ran in to is that a simplex tiling in dimensions greater than 2 isn't regular, so the simplex edges end up having different lengths, so the choise of this scaling factor is somewhat arbitrary (but the one you give is the one that's used and has some important qualities).

[chance]

A small sample of frequencies should produce convincing turbulence.

It does. I described my method in post #8 above. It works great.

I'm just trying to understand how one produces a random realization with the spatial statistics from a particular PSD. I've seen presentations about numerical simulations of imaging through turbulence. Atmospheric effects are simulated using a series of closely space "screens". I just never thought about how the screens are calculated.

I found a paper by a guy at the Keck Observatory here where he describes two methods. The first one looks like a convolution in Fourier space, then a transform back to regular space. The other method looks similar to the Fourier series method, but with other polynomials.

Unfortunately I don't have access to an FFT algorithm so I can't test the first one.

[Gamer3D]

Okay, where does that equation come from? I've never seen an equation actually given anywhere and my approach to this problem was different. One problem I often ran in to is that a simplex tiling in dimensions greater than 2 isn't regular, so the simplex edges end up having different lengths, so the choise of this scaling factor is somewhat arbitrary (but the one you give is the one that's used and has some important qualities).

Here is my reasoning:

• To form a single simplex with equal sides, we start with a shape formed by the origin and points at positive 1 on every the axis.
• The distance between any two points that are not the origin is sqrt(1). (0^2 + 0^2 + ... + 0^2 + 1^2 + 0^2 + ... + 0^2 + 1^2 + 0^2 + ... = 2, by extension of the pythagorean theorem)
• If we scale this shape along the axis (1, 1, 1, 1, ..., 1), that distance will remain unchanged. This means that we only need to make that distance equal to the distance from a point to the origin.
• So we get this: 2 = (1 + x)^2 + x^2 + x^2 + ... + x^2 (this will scale (1, 0, 0, ... 0) by 1 + x along our (1, 1, 1, ..., 1) axis)
• So now we have the scale factor to get from axis-aligned unit vectors to an equilateral polyhedron with n + 1 vertices.
• The problem is that it is not the polyhedron we want. However, some thought will show that a regular hypercube, scaled by 1 / (x + 1) along the (1, 1, 1, ..., 1) axis, gives our desired stretched hypercube divided into equilateral polyhedra, and scaling by (x + 1) transforms it back.
• And there we have it.

EDIT: As a note, this will give a simplex with all edges equal. Also had to make a correction.

EDIT #2: I just realized I threw around a lot of terms incorrectly. Should be fixed now.

Edited by Gamer3D, 19 November 2010 - 08:42 AM.