What is the range of 2D Perlin Noise? To be explicitly clear, I am asking about only one layer of 'gradient noise'. Gradient noise is an interpolation of gradients, which is what Perlin Noise actually is. I am *not* asking about 'value noise' which is an interpolation of values. More specifically, I am asking directly about Ken Perlin's actual 1985 implementation of Perlin Noise: http://mrl.nyu.edu/~perlin/doc/oscar.html#noise (Sorry for all that, but there is much confusion out there about what Perlin Noise actually is.) My (on paper) calculated range is -sqrt(0.5)..sqrt(0.5), not -1..1 as everyone assumes. sqrt(0.5) = 0.707106781... Upon testing, my implementation's range is also -sqrt(0.5)..sqrt(0.5). The actual range determined by polling the entire (0.0..256.0,0.0..256.0) x,y range at 0.01 intervals was: min..max=-0.694254..0.695643 (very close to -0.707..0.707) LilBudyWizer also came up with the same range in this thread: (If you choose to read the thread, please note that most responses in this thread completely misunderstood where LilBudyWizer was coming from and what he was asking.) http://www.gamedev.net/community/forums/topic.asp?topic_id=255173 ... If we are correct, to make Perlin Noise output a range of exactly -1..1, the result must be scaled by sqrt(2). Can you please test your own Perlin Noise implementations and see if you have the same results? Thanks. [Edited by - Doucette on November 29, 2004 2:28:09 PM]

Sampling at regular intervals is NOT a good way to test the full range of a perlin noise (trust me, I've tried this). You have to take a large number of random samples. Also, note that the distribution of perlin noise is gaussian, so you're not very likely to get the extreme values (which is why the large smaple count is needed - although a smaller count may still give you a good estimate of the range).

You might find this thread useful, although it deals mostly with the improved noise implementation.

EDIT: that thread deals with 3D noise, but it the range doesn't depend on the dimentionality.

technobot,

Sampling at regular intervals *IS* a good way to test the full range of a Perlin Noise if the intervals are small enough. Likewise, random sampling only works if you sample enough random points. My 0.01 interval is plenty small enough.

To reiterate, I sampled it at every 0.01 interval across 0.0..256.0 in 2D. That totals to 655,360,000 evenly spaced sample points. However, the total is irrelevant. What matters is the resolution upon each "cel". For each noise "cel" it is 10,000 sample points, or 100 across x and 100 across y. So, when you picture the worse case scenario of a noise "cel", you can see that it *plenty* of resolution.

But, I did as you said anyway, just to satisfy all types of testing. I performed the same large number of random samples, 655,360,000, on the exact same noise (composed of the exact same gradient array):

min..max = -0.69424..0.695468

Random sampling came up with slightly smaller MINs and slightly larger MAXs, so technobot's method worked better, although either method was sufficient. (It is important to note that you are less likely to make mistakes with random sampling.)

Next, I sampled TEN TIMES that amount: 6,553,600,000 random samples:

min..max = -0.69424..0.695648

This still shows that the range is -sqrt(0.5)..sqrt(0.5), not -1..1 as lots of people think.

...

Concerning 3D Perlin Noise:

Also, assuming that I am correct in my first post (which is what I am here to find out), 3D Noise range *is* different than 2D. And then it is different *again* if you use Ken Perlin's 2002 "Improving Noise" suggestions as he un-randomizes and un-normalizes the gradients which affect the output range. My 3D Perlin Noise, based on Ken Perlin's "Improving Noise" has this range: -1.0332..1.03458. (Based on 6 billion random samples. It took over 62 million samples JUST to break the -1..1 barrier, and over 235 million samples to break both ends of the -1..1 barrier.) I'm not sure if my code is buggy yet, so I do not wish to get into it too much until my 2D range problem is solved.

I would post this in your thread, but it is closed. I *despise* that. Threads that have not solved the issue should not be closed. We might as well continue the 3D discussion here, as I will be getting into that afterwards. But, for now, let's try to avoid getting into 3D and all its extra complications until after we determine whether the 2D range is -sqrt(0.5)..sqrt(0.5). I think 3D discussion will make more sense afterwards.

[Edited by - Doucette on November 29, 2004 3:20:32 PM]

I am not concerned with distribution.
I am only concerned with absolute range.

I.e. What is the minimum and maximum value possible from 2D Perlin Noise?

I believe it is *NOT* the assumed, popular -1..1.

Quote:Original post by Doucette
Sampling at regular intervals *IS* a good way to test the full range of a Perlin Noise if the intervals are small enough.

Actually, come to think of it, you're right - if the intervals are small enough, and if the domain is large enough. Both of these conditions seem to be satisfied in your test though.

Quote:
[...] Next, I sampled TEN TIMES that amount: 6,553,600,000 random samples [...] This still shows that the range is -sqrt(0.5)..sqrt(0.5), not -1..1 as lots of people think.

As I said, "a smaller count may still give you a good estimate of the range" (because the sample distribution is the same - you just need to have enough samples to get a statistical meaning), so this was expected.

Quote:
Concerning 3D Perlin Noise:

Also, assuming that I am correct in my first post (which is what I am here to find out), 3D Noise range *is* different than 2D. And then it is different *again* if you use Ken Perlin's 2002 "Improving Noise" suggestions as he un-randomizes and un-normalizes the gradients which affect the output range. My 3D Perlin Noise, based on Ken Perlin's "Improving Noise" has this range: -1.0332..1.03458. (Based on 6 billion random samples.) I'm not sure if my code is buggy yet, so I do not wish to get into it too much until my 2D range problem is solved.

I would post this in your thread, but it is closed. I *despise* that. Threads that have not solved the issue should not be closed. We might as well continue the 3D discussion here, as I will be getting into that afterwards. But, for now, let's try to avoid getting into 3D and all its extra complications until after we determine whether the 2D range is -sqrt(0.5)..sqrt(0.5). I think 3D discussion will make more sense afterwards.

Ok. Let's see.. assumming the implementation you linked to in the first post, the algorithm is as follows (for all dimentionallities):

1. Find the unit segment/square/cube (or other nD cube) that contains the sample point.
2. For each corner of that find: a) the vector from the corner to the sample point - let's call it the "delta vector"; b) the gradient vector associated with that corner (using the permutation table).
3. Still for each corner, calculate the dot product of the delta vector and the gradient vector for that corner.
4. Interpolate the results, first along the x axis, then the results of that along the y axis, and so on.


This is actually the same as for the "Improved Noise" Implementation. The difference is in what's going on behind the scenes, so let's analyze each step.

Step 1:
Nothing interesting.

Step 2:
The smallest possible delta vector for each corner is of length 0. The largest possible delta vector is when all the components are -/+ 1, giving a vector of length Sqrt(n), with n being the dimentionality of the noise. The gradient vectors are always of length 1, since they are normalized during initialization.

Step 3:
Since A.B = |A|*|B|*cos(A,B), this gives us values in the range -Sqrt(n)..Sqrt(n).

Step 4:
This one is actually trickier than it looks. To simplify the analysis, let's consider the 1D example first:
A---P------B

P is the sample point, A and B are the corners of the containing unit segment, t is the distance from A to P, and s(t) is the interpolation factor. Let's call the dot product results for A and B, a and b, respectively. The value at P is then:
p = b*s + a*(1-s)

This gives us the follwing behavior. What's important to remember is that a and b are also functions of t:

- At t=0.5, p is exactly the average of a and b, which is 0.5 for the 1D case.
- At t=0 and t=1, p is zero, because then you either have "p = b*0 + 0*1" or "p = 0*1 + a*0".
- As we approach from t=0.5 to t=0, a decreases linearly, b increases linearly, but s and 1-s do not change linearly. Depending on how s and s-1 interact with their counterparts, this may result in one of two cases: a) p drops monotonically towards zero; or b) p slightly rises to some maximum, and then drops back to zero monotonically.
- As we approach from t=0.5 to t=1, the same thing occurs as when approaching t=0.

I've entered this into excel, and got this (assuming a and b are such that a maximum value is attained):

As can be seen, p decreases monotonically as we go from t=0.5 to t=0 or t=1 (as I suspected). This means that the maximum values for the x interpolation can only be attained for frac(P.x)=0.5. Similarly, the maximum values for the y, z, and so on interpolations are also obtained at frac(P.coord)=0.5. Hence the maximum overall value is obtained for frac(P)=(0.5,0.5,...).

In that case, all the dot products would be between -0.5*Sqrt(n) and 0.5*Sqrt(n), the x interpolations would return the exact averages of the corresponding dot products, and each successive interpolation would retrun the exact average of the corresponding interpolations along the previous axis. If all the dot products are equal to their maximum value for that case, which is 0.5*Sqrt(n), this would then give us the overall maximum of 0.5*Sqrt(n). So if all of the above is correct, and I didn't miss anything, and there are no bugs in the implementation, then we should get the following ranges:

1D: -0.5*Sqrt(1)..0.5*Sqrt(1) = -0.5..0.5
2D: -0.5*Sqrt(2)..0.5*Sqrt(2) = -0.71..0.71
3D: -0.5*Sqrt(3)..0.5*Sqrt(3) = -0.87..0.87

Although, since at least the 3D case should be -1..1 AFAIK, I won't be surprised if I am indeed missing something (or have mistaken in the analysis).

Quote:Original post by Karg
I just depends on how you produce it.

True. That's why I specifically asked for the range of only one layer of gradient noise based on Ken Perlin's original code (http://mrl.nyu.edu/~perlin/doc/oscar.html#noise).

Quote:Original post by Karg
Just create a point with the maximum values for each octave and combine them to see what you get. Same for the minimums. Then you can scale to whatever values you want.

Perlin Noise is not multiple 'octave' layers. It is just one layer. This is a common misunderstanding as most implementations of Perlin Noise use multiple layers with a lacunarity (gap in frequency) of 2.0 which produces perfect "octave" layers. Perlin Noise, fundamentally, is only one of these layers. It is fine to use multiple layers of Perlin Noise (called spectral synthesis), but defining Perlin Noise as multiple layers is wrong.

The maximum and minimum values of only one Perlin Noise layer is all I want to know. You (Karg) are writing as if the max and min values are already known and as if I am asking for something else. (Please excuse me if I am wrong and misunderstood.) Anyway, figuring out the min/max range is the point of this entire thread.

I hope that explains it well.

...

technobot, your results were *exactly* what I had calculated for the noise ranges of Ken Perlin's original implementation.

Your steps 1..4 look good. Step 4 was hard to follow, but I followed it and it looks good and has the same results that I got.

Quote:Original post by technobot
So if all of the above is correct, and I didn't miss anything, and there are no bugs in the implementation, then we should get the following ranges:

1D: -0.5*Sqrt(1)..0.5*Sqrt(1) = -0.5..0.5
2D: -0.5*Sqrt(2)..0.5*Sqrt(2) = -0.71..0.71
3D: -0.5*Sqrt(3)..0.5*Sqrt(3) = -0.87..0.87

Although, since at least the 3D case should be -1..1 AFAIK, I won't be surprised if I am indeed missing something (or have mistaken in the analysis).

I do not think you are missing anything. I think your calculations are correct. If you would have done 4D Perlin Noise, it would have come to a range of exactly -1..1.

I have not yet coded 3D *original* Perlin Noise. I will code it right now and post the ranges of my results...

Done. I'm calculating my results. So far, the range is:

-0.765153..0.720143 after 2.04 BILLION random samples!

-0.866025..0.866025 is the expected range.

Why isn't it close?

For two reasons. Firstly, 3D noise is calculated from *EIGHT* gradients (whereas 2D noise is calculated from only four gradients) and they both only have 256 pseudo-random gradients to choose from. If you think of it, it is much less likely that eight gradients that either closely maximize or minimize the noise value exist out of the 256. That's 3.125% of all the gradients. Secondly, assuming that those eight gradients do exist out of the list of 256, it is much less likely that those eight are going to all be corners around the same 3D "cel" of noise. Therefore, it is going to take A LOT longer to randomly stumble upon values close to the min and max values, assuming the even exist. There is a good chance that the -0.765153..0.720143 range above is the actual range of my noise (which would change if I randomized the pseudo-random 256 gradients used). This brings me to my next idea for testing:

I may code a 3D Perlin Noise function that keeps randomizing the 8 gradients, so that I will be testing an ever changing 3D Perlin Noise area, not a static area of noise that perhaps has no values close to the extremities of the range.

...

Concerning "Improved Noise" Perlin Noise:

Quote:Original post by technobot
This is actually the same as for the "Improved Noise" Implementation. The difference is in what's going on behind the scenes, so let's analyze each step.

3D Perlin Noise based on Ken Perlin's improved noise from his "Improving Noise" paper is different (and has a different range) from the original implementation. Here is a partial list of "Improving Noise" differences, specifically only the differences that change the range:

"Improving Noise" Perlin Noise:
1) The gradients are *not* normalized, and have a length of sqrt(2).
2) The gradients are *not* random and do *not* point in the direction that maximizes (or minimizes) the noise value.

In fact, here they are:

1,1,0, -1,1,0, 1,-1,0, -1,-1,0,
1,0,1, -1,0,1, 1,0,-1, -1,0,-1,
0,1,1, 0,-1,1, 0,1,-1, 0,-1,-1,
1,1,0, -1,1,0, 0,-1,1, 0,-1,-1

(The last row is the first row repeated, on purpose.)

These gradients create a different range than the original 3D noise, due to the two points above. Now that we have the range of Perlin's original noise calculated, let's work on his Improved Noise range!

Once we do this, I bet it will explain why we *both* got ranges slightly over and under -1..1 for our 'improved' noise. Everyone thinks Perlin Noise is from -1..1, and I believe that is not the case.

(Here is the "Improved Noise" paper to see the full list of differences, which include using a new s-curve: http://mrl.nyu.edu/~perlin/paper445.pdf.)

[Edited by - Doucette on November 30, 2004 9:10:39 PM]

Quote:Original post by gamelife
I guess higher value could be possible - though extremely rare in real cases.

My range (as shown in the third post in this thread) was -1.0332..1.03458 for improved 3D Perlin Noise. Assuming my code is correct, it shows your assumption is right.

Also, thanks for the breakdown which proves it breaks the -1..1 barrier. It's easier to assume someone's code is wrong without a mathematical proof.

I will get to work on a proof of the actual range today.

[Edited by - Doucette on November 30, 2004 9:16:09 AM]