I’ve been using Perlin noise a lot in the last month for both teaching and research. It’s the kind of thing that I like, incorporating algorithms, math, and intuition to make a tool that’s practical and useful. Perlin noise is based on the pseudorandom number generator rand(), which is notoriously nonrandom. If you make a million or so calls to rand() and use the least-significant byte of each number as a grayscale value for a single pixel in a 1024×1024 grid, you get something like this.
See the vertical lines? They are not supposed to be there. What you’re supposed to see is something more like this, which was generated with the Mersenne Twister.
Of course, the Mersenne Twister hadn’t been invented yet back in 1982 when Ken Perlin was working on his noise function, and if it had been it probably would have been too slow. One nice thing about rand() is that it is fast. Ken solved this by using rand() to generate a bunch of random values, then permuting them using a random permutation which is also created using rand(). The results look pretty good.
He used the following method for generating a random permutation.
/// Randomly permute array p of size n
void permute(int* p, int n){
for(int i=n-1; i>0; i--){ //for each index
int j = rand()%n; //random index
//swap p[i] with p[j]
int k = p[i];
p[i] = p[j];
p[j] = k;
} //for
} //permute
The fourth line of code is technically incorrect. You see, ideally you should generate a random permutation in which each permutation is equally likely. To get that, you’d have to change the fourth line to:
int j = rand()%(i+1); //random smaller index
It’s not hard to see why this works. One can prove it correct by induction on n. (See Lecture Notes on Algorithms if you are unfamiliar with correctness proofs or mathematical induction.) The key step is this. The probability of p[n-1]being any particular value i is 1/n, because we swap in any one of the values i with equal probability. Therefore it is equally probable that we get a permutation ending in any particular value i.
Even if you’re not theoretically inclined, you can verify this experimentally for permutations of size n by performing t trials using rand() and plotting the number of times each permutation is chosen. In the following graphs t=100,000,000, the red line shows the number of times each permutation is chosen by the incorrect algorithm, and the green line shows the number of times each permutation is chosen by the correct algorithm. First of all for n=4.
Now for n=5.
Of course, this makes no practical difference at all to Perlin Noise. Most implementations use a fixed permutation anyway, but one chosen at “random” and hard-coded into the algorithm. For example:
const int p[256] = {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
}; //const int p
But it’s an interesting piece of trivia, at least to me.
Outside the Box 