Perlin Noise Exposed
Author
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]
Author
Just to make sure - could you guys test what ranges you're typically getting and post here? Also please mention if you're using the improved version or the old one and if there are any modification that you've made.
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
Given that i think that it might be your implementation, can you post the code with comparison against Ken's?
Andy
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]
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]
Author
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; for I := 0 to 255 do begin J := Random(256); Permutation[J+256] := Permutation; Permutation[I+256] := Permutation[J]; Permutation := 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+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 = permutation; }}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.
Author
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...
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...
Quote:Original post by technobotQuote: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
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) :
and test:
i'm bit too buzy to compare. BTW, this is done using perlin noise.
-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+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+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.
Author
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...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement