Sign in to follow this  

Perlin Noise Exposed

This topic is 4832 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been playing around with my perlin noise recently, trying to fix the a problem I had since the first time I implemented it - it wasn't giving me the full -1..1 range. I've even rewritten my implementation based on Ken Perlin's imporved noise reference implementation, hoping it would solve the problem. It didn't. I went over it several times, they're algorythmically identical as far as I can tell. After two days of investigation, I beleive I've found the problem: perlin noise has a gaussian-like distribution! Not only that, but it occasionally gives values outside of the -1..1 range. The range breaches could be a small bug in my implementation, but as I said, I checked it several times, it doesn't seem to be the case. Note that this is for a single octave. Combining several octaves to form fBm results in a true gaussian distribution. The range violations are not that much of an issue. They're so rare and small that they can be safely clipped away without any noticeable difference. But the distribution is a problem. In practical terms it means one cannot reliably predict the effective range one would get for any given set of samples. Theoritcally, the range is -1..1; but in practice it usually fluctuates between -0.6..0.6 and -0.7..0.7. It is quite hard to get values outside the latter, and getting values outside of -0.8..0.8 on both sides is nearly impossible (on one side just requires some luck), except for the largest sample sets. But occasionaly such values do creep in, leaving the actual effective range unpredictable. Now this isn't always a problem, but it can be if you rely on the range heavily. Ideally, such problems require a uniform distribution, not a gaussian-like one. There's no easy solution to this. If you don't scale the values, you usually only get part of the range, and can't predict which part. If you do scale them, you get the whole -1..1 range, but you risk getting values outside that range. If you scale and clip, you risk getting visual artifacts. Normalizing all the vectors involved in the dot products completely eliminates the -1..1 range breaches (another evidence it's not a bug) and produces a better distrubution, but still not quite satisfactory. Further, it requires a square-root call for each dot product, which is not desirable. And what's far worse, it makes the dot products strictly direction dependant, resulting in discontinuities around integer postions. Just thought you should know perlin noise has its problems too. If you have any ideas how to make the distribution more uniform, or if you know a different noise function that is reproducible, smooth, reasonably fast, and has a near-uniform distribution (or close to that), please post them. From all of you who's using perlin noise, if you're getting the full -1..1 range of values on a regular basis, please let me know. Thanks. EDIT: fixed image links (hopefully.. if not, they can be found here) [Edited by - technobot on September 17, 2004 8:30:37 AM]

Share this post


Link to post
Share on other sites
Um that's not something i've ever seen before, and i've written several terrain generating engines, and used both Ken's and another implementation (from a Gamasutra article the name of which i'll dig out if you want it).

Given that i think that it might be your implementation, can you post the code with comparison against Ken's?

Andy

Share this post


Link to post
Share on other sites
From the code, I don't see why values other than in the interval [-1,1] should be possible:

Lerp is a convex operation if the u, v and w parameters are inside [0,1]. Convex means that the range of things which come out never exceed the range of things you plug in (i.e. a and b).

Thus, return values outside [-1,1] are only possible if u, v or w are outside [0,1] or the lerp-parameters a and b are outside [-1,1].

Lets check whether u, v and w are inside [0,1]. x, y and z are surely inside [0,1]. The fade function maps [0,1] onto [0,1] (I've plotted it to check that), so also u, v and w are inside [0,1].

The (a,b) parameters of the lerp function are given by the grad function. Possible return values of the grad function are x,-x,y,-y,z,-z. However, x,y,z are always inside [0,1] (resp. x-1,y-1,z-1 are inside [-1,0]), so the return of the grad function is also in between -1 and 1.

Thus, the return of the noise function should be in [-1,1].
So your implementation must be buggy.
You could check the following things:

* x,y,z inside [0,1]
* u,v,w inside [0,1]
* The returns of the grad function should be inside [-1,1]

Share this post


Link to post
Share on other sites
Quote:
Original post by NineYearCycle
Um that's not something i've ever seen before, and i've written several terrain generating engines, and used both Ken's and another implementation (from a Gamasutra article the name of which i'll dig out if you want it).

Given that i think that it might be your implementation, can you post the code with comparison against Ken's?

Andy


If you can dig out the name of that article (for reference sake), that would be really nice. :)

Here are the relevant parts of my code:

var
// Permutation table for perlin noise:
Permutation: array [0..511] of Byte; // Double length to avoid masking


//------------------------------------------------------------------------------
procedure InitPerlinNoise(const Seed: Longint);
var
I, J: Byte;
begin
// Prepare:
RandSeed := Seed;

// Init the permutation table:

for I := 0 to 255 do
Permutation[I] := I;
for I := 0 to 255 do
begin
J := Random(256);
Permutation[J+256] := Permutation[I];
Permutation[I+256] := Permutation[J];
Permutation[I] := Permutation[I+256];
Permutation[J] := Permutation[J+256];
end;
end; { InitPerlinNoise }


//------------------------------------------------------------------------------
// DotGrad - converts the speficied gradient hash to a gradient vector, then
// computes and returns the dot product between that and the specified vector:
function DotGrad(GradHash: Byte; const X, Y, Z: Single): Single;
// The gradient vectors 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)
var
U,V: Single;
begin
// We only need the low 4 bits:
GradHash := GradHash and $F;

// Select one non-zero component from the X or Y set:

if (GradHash < 8) then
U := X
else
U := Y;

// Find the other non-zero component:

if (GradHash < 4) then
V := Y
else if (GradHash and $D = $C) then // 12 or 14
V := X
else
V := Z;

// Adjust the signs and return the result:

if (GradHash and 1 = 1) then
U := -U;
if (GradHash and 2 = 2) then
V := -V;
Result := U + V;
end; { DotGrad }


//------------------------------------------------------------------------------
// Lerp - linearly interpolates the two specified values by the specified factor
// and returns the result:
function Lerp(const Factor, Val1, Val2: Single): Single;
begin
Result := Val1 + Factor * (Val2 - Val1);
end; { Lerp }


//------------------------------------------------------------------------------
// LerpFactor - returns the bi-cubic-like version of the specified Lerp factor:
function LerpFactor(const Factor: Single): Single;
begin
Result := Factor * Factor * Factor * (Factor * (6 * Factor - 15) + 10);
end; { LerpFactor }


//------------------------------------------------------------------------------
// This implementation is based on Ken Perlin's implementation, found at
// http://mrl.nyu.edu/~perlin/noise/
function PerlinNoise(X, Y, Z: Single): Single;
var
IX, IY, IZ: Byte;
G00, G01, G10, G11: Word;
FX, FY, FZ: Single;
begin
// Find container cube:

IX := Floor(X) and $FF;
IY := Floor(Y) and $FF;
IZ := Floor(Z) and $FF;

// Find offset within cube:

X := X - Floor(X);
Y := Y - Floor(Y);
Z := Z - Floor(Z);

// Compute intrpolation factors for X and Y (we'll calculate Z when we need
// it, since we only use it once):

FX := LerpFactor(X);
FY := LerpFactor(Y);
FZ := LerpFactor(Z);

// Find gradient vector index hashes for the cube corners on the XY plane
// (we'll add the Z component later):

G10 := Permutation[IX ] + IY;
G11 := Permutation[IX +1] + IY;

G00 := Permutation[G10 ] + IZ;
G01 := Permutation[G10+1] + IZ;
G10 := Permutation[G11 ] + IZ;
G11 := Permutation[G11+1] + IZ;

// Compute the final noise value:

Result := Lerp(FZ, Lerp(FY, Lerp(FX, DotGrad(Permutation[G00 ], X , Y , Z ),
DotGrad(Permutation[G10 ], X-1, Y , Z )),
Lerp(FX, DotGrad(Permutation[G01 ], X , Y-1, Z ),
DotGrad(Permutation[G11 ], X-1, Y-1, Z ))),
Lerp(FY, Lerp(FX, DotGrad(Permutation[G00+1], X , Y , Z-1),
DotGrad(Permutation[G10+1], X-1, Y , Z-1)),
Lerp(FX, DotGrad(Permutation[G01+1], X , Y-1, Z-1),
DotGrad(Permutation[G11+1], X-1, Y-1, Z-1))));
end; { PerlinNoise }



And here is Ken's version (from the link in my original post):

// JAVA REFERENCE IMPLEMENTATION OF IMPROVED NOISE - COPYRIGHT 2002 KEN PERLIN.

public final class ImprovedNoise {
static public double noise(double x, double y, double z) {
int X = (int)Math.floor(x) & 255, // FIND UNIT CUBE THAT
Y = (int)Math.floor(y) & 255, // CONTAINS POINT.
Z = (int)Math.floor(z) & 255;
x -= Math.floor(x); // FIND RELATIVE X,Y,Z
y -= Math.floor(y); // OF POINT IN CUBE.
z -= Math.floor(z);
double u = fade(x), // COMPUTE FADE CURVES
v = fade(y), // FOR EACH OF X,Y,Z.
w = fade(z);
int A = p[X ]+Y, AA = p[A]+Z, AB = p[A+1]+Z, // HASH COORDINATES OF
B = p[X+1]+Y, BA = p[B]+Z, BB = p[B+1]+Z; // THE 8 CUBE CORNERS,

return lerp(w, lerp(v, lerp(u, grad(p[AA ], x , y , z ), // AND ADD
grad(p[BA ], x-1, y , z )), // BLENDED
lerp(u, grad(p[AB ], x , y-1, z ), // RESULTS
grad(p[BB ], x-1, y-1, z ))),// FROM 8
lerp(v, lerp(u, grad(p[AA+1], x , y , z-1 ), // CORNERS
grad(p[BA+1], x-1, y , z-1 )), // OF CUBE
lerp(u, grad(p[AB+1], x , y-1, z-1 ),
grad(p[BB+1], x-1, y-1, z-1 ))));
}
static double fade(double t) { return t * t * t * (t * (t * 6 - 15) + 10); }
static double lerp(double t, double a, double b) { return a + t * (b - a); }
static double grad(int hash, double x, double y, double z) {
int h = hash & 15; // CONVERT LO 4 BITS OF HASH CODE
double u = h<8 ? x : y, // INTO 12 GRADIENT DIRECTIONS.
v = h<4 ? y : h==12||h==14 ? x : z;
return ((h&1) == 0 ? u : -u) + ((h&2) == 0 ? v : -v);
}
static final int p[] = new int[512], permutation[] = { 151,160,137,91,90,15,
131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
};
static { for (int i=0; i < 256 ; i++) p[256+i] = p[i] = permutation[i]; }
}




Quote:
Original post by Lutz
From the code, I don't see why values other than in the interval [-1,1] should be possible:

[...]

The (a,b) parameters of the lerp function are given by the grad function. Possible return values of the grad function are x,-x,y,-y,z,-z. However, x,y,z are always inside [0,1] (resp. x-1,y-1,z-1 are inside [-1,0]), so the return of the grad function is also in between -1 and 1.


This is where you are wrong. The grad function calculates a dot product of two vectors - the gradient vector and the (x,y,z) vector, which I'll call the delta vector. If the vectors are normalized, then the dot product indeed returns values inside [-1,1]. But if they are not normalized, then the result is multiplied by the lengths of the vectors. The length of the gradient vectors is always Sqrt(2) in this implementation. And since one of gradient vector's coordinates is always 0, the effective length of the delta vector ranges from 0 to Sqrt(2). Hence the dot product, and therefore the result of the grad function, are multiplied by up to a factor of 2. So the return value of grad is inside [-2,2], not [-1,1]. If you look at Ken's code, he does not normalize the vectors - that is the way it should be. In fact, as I wrote earlier, normalizing the vectors results in discontinuities, because then the dot product reduces to a simple cosine, which is direction dependant.

The [-1,1] range of the entire noise function, at least in this implementation, stems from the behavior the interpolation function. It makes it so that the maximum contribution of any corner of a unit cell is exactly in the center of that unit cell. And there, the effective length of the delta vector is 0.5*Sqrt(2), which exactly normalizes the dot product to the desired [-1,1] range.

Share this post


Link to post
Share on other sites
I did a little more research. Here's what I've found:
1. The old version of perlin noise has true gaussian distribution.
2. The difference between the old and new versions' distributions apparently stems from the distribution of the grad function, which is gaussian in the old perlin noise, and can be described by f=1-|x| in the new version.
3. This site confirms my claims, and suggets somewhat of a solution: since values outside [-0.7,0.7] are extremely rare, one can quite safely divide the noise function by 0.7, and clip away any extreme values. It's not as good as a uniform or near-uniform ditribution, but at least it's workable...

Share this post


Link to post
Share on other sites
Quote:
Original post by technobot
Quote:
Original post by NineYearCycle
Um that's not something i've ever seen before, and i've written several terrain generating engines, and used both Ken's and another implementation (from a Gamasutra article the name of which i'll dig out if you want it).

Given that i think that it might be your implementation, can you post the code with comparison against Ken's?

Andy


If you can dig out the name of that article (for reference sake), that would be really nice. :)


this must be the most linked to article ever by the way [smile]

A Real-Time Procedural Universe, Part One: Generating Planetary Bodies in fact i probably deserve rating down just for linking to it again [grin]

Anyway, i used his implementation of the algorithm, not being clever enough to work it out myself(!) so most of what you've posted has gone totally over my head, however using a single octave i've still never seen the odd patterning you showed in your screenshot or the abnormal distribution.

Good luck figuring it out anyway im bookmarking this thread!

Andy

Share this post


Link to post
Share on other sites
Strange. My re-implementation of improved perlin noise gives values in range
-0.97...0.98
after 106 tests.
I guess, something is wrong with your test, or your reimplementation. For instance, you may be checking points with z=0, or something.

My re-implementation (also pascal) :

const perlin_G:array[0..15] of array[0..2] of single=
(
( 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)
);
function perlin1(p:vector3;octave:longint):real;
var xi,yi,zi:longint;f:vector3;
tmp:real;grd:vector3;
function fade(t:real):real;
begin
result:=t * t * t * (t * (t * 6 - 15) + 10);
end;
var u,v,w:real;
function lerp(t,a,b:real):real;
begin
result:=a+t*(b-a);
end;
function grad(h:longint;x,y,z:single):single;
var r,a:single;
type plongint=^longint;
begin
h:=h and 15;
result:=x*perlin_g[h][0]+y*perlin_g[h][1]+z*perlin_g[h][2];
end;
var a,aa,ab,b,ba,bb:longint;
begin
// make values to be nonnegative(because of "floor")
p.x:=p.x+10000;
p.y:=p.y+10000;
p.z:=p.z+10000;
xi:=floor(p.x);
yi:=floor(p.y);
zi:=floor(p.z);
f.x:=p.x-xi;
f.y:=p.y-yi;
f.z:=p.z-zi;
u:=fade(f.x);
v:=fade(f.y);
w:=fade(f.z);
{A = p[X ]+Y, AA = p[A]+Z, AB = p[A+1]+Z}
{B = p[(X+1)]+Y, BA = p[B]+Z, BB = p[(B+1)]+Z;}

a:=hashtable[octave];
b:=a;
a:=(hashtable[(a+xi) and 255]+yi)and 255;aa:=(hashtable[A]+zi)and 255;ab:=(hashtable[(a+1)]+zi)and 255;
b:=(hashtable[(b+xi+1)and 255]+yi)and 255;ba:=(hashtable[b]+zi)and 255;bb:=(hashtable[(b+1)]+zi)and 255;
with f do
result:=lerp(w, lerp(v, lerp(u, grad(hashtable[AA ], x , y , z ), // AND ADD
grad(hashtable[BA ], x-1, y , z )), // BLENDED
lerp(u, grad(hashtable[AB ], x , y-1, z ), // RESULTS
grad(hashtable[BB ], x-1, y-1, z ))),// FROM 8
lerp(v, lerp(u, grad(hashtable[AA+1], x , y , z-1 ), // CORNERS
grad(hashtable[BA+1], x-1, y , z-1 )), // OF CUBE
lerp(u, grad(hashtable[AB+1], x , y-1, z-1 ),
grad(hashtable[BB+1], x-1, y-1, z-1 ))));
end;


and test:

procedure testrange;
var n:longint;min_noise_v,max_noise_v,noise_v:single;testpos:vector3;
const tests=1000000;
begin
min_noise_v:=100;
max_noise_v:=-100;
for n:=0 to tests-1 do begin
testpos.x:=2000*random();
testpos.y:=2000*random();
testpos.z:=2000*random();
noise_v:=perlin1(testpos,random(100));
if noise_v>max_noise_v then max_noise_v:=noise_v else
if noise_v<min_noise_v then min_noise_v:=noise_v;
end;
writeln('min noise value=', min_noise_v, 'max noise value=', max_noise_v);
readln;
end;


i'm bit too buzy to compare. BTW, this is done using perlin noise.

Share this post


Link to post
Share on other sites
Quote:
Original post by Basiror
you could check if values are beyond 0.7 and smooth it with neighbouring values

Assuming I understand you correctly, that will not acheive much, because pelin noise is already smooth anyway.
Quote:
Original post by NineYearCycle
this must be the most linked to article ever by the way [...]

Ah, I know this one. :) Forgot it had a pelin noise implementation attached to it though. Thanks.
Quote:

using a single octave i've still never seen the odd patterning you showed in your screenshot or the abnormal distribution.

I only get that patterning if I normalize all the vectors before computing the dot product. Since that is not usually done, it's not surprising you've never seen it before. As for the distribution, it seems to be an intrinsic property of perlin noise, although perhaps it's not that hard to miss...
Quote:
Original post by Dmytry
Strange. My re-implementation of improved perlin noise gives values in range
-0.97...0.98
after 106 tests.

With 10^6 random samples, I get that range as well. But there are only very few samples near the extremes of that range. I get the reduced ranges when sampling at regular intervals inside some area around the origin, the way it's done when generating terrain. Try counting how many values you get outside of [-0.8, 0.8]. If the distribution is anywhere near uniform, you should get fairly large counts. If the distribution is gaussian, you should only get a very small fraction of the total.


Anyway, it seems I'll just divide by 0.75 and clamp. That seems to work reasonably well...

Share this post


Link to post
Share on other sites
A more accurate solution would be as follows:

Suppose you know the distribution of values output from Perlin noise, say some distribution p(x).

To generate a uniform random value, start by computing your perlin noise function to get a value x. Then compute integral 0..x, p(t)dt. This will give you a value between 0 and 1, uniformly distributed. And since this is a continuous transformation of the output of your Perlin noise function, it will still be nice and smooth like the original.

Also note that you no longer need to use perlin noise, it can also be some kind of fractal noise, etc.

I suppose the only part left would be figuring out the distribution for your noise function, but this should be easy using statistical techniques.

Share this post


Link to post
Share on other sites
Take any four uniformly distributed numbers and average them. You should indeed get a gaussian distribution. This is what you're basically doing with the 4 perlin corner vectors(uniform) and your DotGrad function.

Consider it this way. Generate a random number in the range [0,1]. Say 0.7. You only have a 30.0% chance to land in the range [0.7,1] again. Multiply four 30.0% chances together. You only have a 0.81% chance that you'll land in the upper 30% for all four.

Consider also that most of the time this is the desired result. You only want really really tall mountains or really really low valleys less than 1% of the time. If this is not the case and you want truly uniform values, try using a standard Psuedo-random number generator(PRNG) where you feed two input values and get back a predictable result each time. (I would recommend RANROT)

Share this post


Link to post
Share on other sites
Quote:
Original post by technobot
Quote:
Original post by Dmytry
Strange. My re-implementation of improved perlin noise gives values in range
-0.97...0.98
after 106 tests.

With 10^6 random samples, I get that range as well. But there are only very few samples near the extremes of that range. I get the reduced ranges when sampling at regular intervals inside some area around the origin, the way it's done when generating terrain. Try counting how many values you get outside of [-0.8, 0.8]. If the distribution is anywhere near uniform, you should get fairly large counts. If the distribution is gaussian, you should only get a very small fraction of the total.


Anyway, it seems I'll just divide by 0.75 and clamp. That seems to work reasonably well...

I don't think perlin noise have really gaussian distribution. Yes,it's looks kinda like, but it surely not.
(IIRC if you add up infinitely many uniform distributions you'll get gaussian, if it's not so my text doesn't make much sense and i need to renew my statistics)

I would not clamp. I might multiply, but i think it's not very good to clamp. There's ~106 points on the screen. It will be sometimes visible. Also, you get derivative discontinuity.

You can try to get some function of noise to change distribution.
For instance something like
f(x)=x/sqrt(x2+1)
clamps to range more-or-less gently.
So you can use
noise2=f(noise(...blabla...)*k)/f(k)
(try with different k.)

In fact, by taking carefully choosen function of noise value you can get any distribution you want, if you know distribution of noise. Read some statistics books for more detailed information.

To convert to uniform you need to make function that returns probability that value is less than parameter. (can't remember correct English term). Approximation can be done by sorting many samples., so you get table of that, then least-square-fitting polynomial of high enough degree, so you'll not need big table.

Then, to convert uniform to distribution you want, you need to take function that is inverse function of intergal of distribution_you_want.

edit: OPS, Pragma and Vystrax was first.
Anyway, Perlin isn't really gaussian because there's only 4 random numbers and also because of spline(it changes distribution).

Share this post


Link to post
Share on other sites
Quote:
To convert to uniform you need to make function that returns probability that value is less than parameter. (can't remember correct English term).


It's called a CDF or Cumulative Distribution Function.

Share this post


Link to post
Share on other sites
Quote:
Original post by Pragma
Quote:
To convert to uniform you need to make function that returns probability that value is less than parameter. (can't remember correct English term).


It's called a CDF or Cumulative Distribution Function.

Thanks.

BTW, about my post,
"
You can try to get some function of noise to change distribution.
For instance something like
f(x)=x/sqrt(x2+1)
clamps to range more-or-less gently.
So you can use
noise2=f(noise(...blabla...)*k)/f(k)
(try with different k.)
"
, f(x) _looks_ like CDF of some distribution with peak at 0.

Share this post


Link to post
Share on other sites
Ok, thanks guys. Running the noise function trhough f(x)=(2-|x|)*x gives a near uniform ditribution in the [-0.5,0.5] range, and linear distribution outside that. It's as uniform as I could get it so far without using look-up tables.

Vystrax, that's a good point about the tall moutains etc. It occured to me as well some time ago. Still, the chance for extreme values in the unmodified perlin noise seems a bit too low to me. I'll have to play with it some more to see what looks best.

Share this post


Link to post
Share on other sites

This topic is 4832 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this