Perlin Noise – Fractal (Iterative)
So I took the next step in my Perlin Noise odyssey, and applied the noise function iteratively. Each iteration is called an octave, and the amplitude of each function is determined by a property usually called ‘persistence’ but which I call decay, as I think this is more descriptive of what it does – it reduces the amplitude in each iteration. The conventional formual for ‘fractal’ perlin noise doubles the frequency and halves the amplitude with each iteration (octave) so this is what I have done. This isn’t the only algorithm, but it seems the most common one, so I’ve done that first. Next I will explore some alternative algorithms, and see what effects they produce.I am noticing some sluggishness, so I should do some optimization too. I didn’t give the ui code as it’s very similar to the previous one, except I used a button to trigger redrawing, for performance reasons.’
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
public class PerlinNoise {
//initialize random seed
public var seed:uint = prng(Math.random()*0x7fffffff);
public function PerlinNoise() {
}
public function getFractalNoise(size:int,octaves:int,decay:Number):Array {
var field:Array;
var totalAmplitude:Number = 1;
var totalField:Array = getPerlinNoise_2D(size, 1, 1);
var freq:int;
var amp:Number;
for(var o:int = 1; o <= octaves; o++){
freq = Math.pow(2,o);
amp = Math.pow(decay,o);
if(freq < size) {//cannot have frequency > len .. no sub-pixel rendering
field = getPerlinNoise_2D(size, amp, freq);
totalAmplitude+=amp;
for(var g:int = 0; g < size; g++){
for(var h:int = 0; h < size; h++){
totalField[g][h] += field[g][h];
}
}
}
}
//normalize values to between -1 * 1
for(var i:int = 0; i < size; i++){
for(var j:int = 0; j < size; j++){
totalField[i][j] = totalField[i][j]/totalAmplitude;
}
}
return totalField;
}
public function getPerlinNoise_1D(len:int=200, octaves:int=8, decay:Number=1):Array {
var graph:Array;
//totalGraph holds accumulated values
var totalGraph:Array = getNoiseFunctionResults(len, 1, 1);
var totalAmplitude:Number= 1;//used to normalize amplitude
for(var o:int = 1; o <= octaves; o++){
if(Math.pow(2,o) < len) {//cannot have frequency > len
graph = getNoiseFunctionResults(len, Math.pow(decay,o)/*amplitude*/, Math.pow(2,o)/*frequency*/);
totalAmplitude+=Math.pow(decay,o);
for(var g:int = 0; g < graph.length; g++){
//add the graphs together by shifting them so they are centred on y=0 (subtract their amplitude/2)
totalGraph[g] += graph[g];
}
}
}
//normalize values in totalGraph to be between -0.5 & 0.5 by dividing by accumulated amplitude
for(var i:int = 0; i < totalGraph.length; i++){
totalGraph[i] = totalGraph[i]/totalAmplitude;
}
return totalGraph;
}
public function getPerlinNoise_2D(size:int=200, amplitude:Number=1, frequency:int=5):Array {
var spacing:Number = size/frequency;
var gradient:Array = [];
var gp:Vector.<Number>;//grid point
var seed:uint;
var nextseed:uint = prng(Math.random()*0x7fffffff);
for(var g:int = 0; g <= frequency; g++){
gradient[g] = [];
for(var h:int = 0; h <= frequency; h++){
seed = prng(nextseed); //using 'old' nextseed ;-)
nextseed = prng(seed);
//each point in the gradient is a 2-point vector
gp = gradient[g][h] = new Vector.<Number>(2,true);//fixed length vector - maybe help memory use?
gp[0] = (seed/0x7fffffff)*2 - 1;
gp[1] = (nextseed/0x7fffffff)*2 - 1;
}
}
//calculate the resulting value for each x,y
var results:Array = []
var gx0:int;
var gx1:int;
var gy0:int;
var gy1:int;
var s:Number;
var t:Number;
var u:Number;
var v:Number;
for(var x:int= 0; x < size; x++){
results[x] = [];
for(var y:int = 0; y < size; y++){
//determine the surrounding gridpoints as multiples of spacing
gx0 = Math.floor(x/spacing);
gx1 = gx0+1;
gy0 = Math.floor(y/spacing);
gy1 = gy0 +1;
var xf:Number = (x - gx0)/spacing;//x as a fractional value of spacing
var yf:Number = (y - gy0)/spacing;//y as a fractional value of spacing
//calculate the dot-products of the 2 vectors
/*s = g(x0, y0) · ((x, y) - (x0, y0)) ,
t = g(x1, y0) · ((x, y) - (x1, y0)) ,
u = g(x0, y1) · ((x, y) - (x0, y1)) ,
v = g(x1, y1) · ((x, y) - (x1, y1)) . */
/*s = gradient[x0][y0] · [xf - gx0, yf - gy0];
t = gradient[x1][y0] · [xf - gx1, yf = gy0];
u = gradient[x0][y1] · [xf - gx0, yf - gy1];
v = gradient[x1][y1] · [xf - gx1, yf - gy1];*/
s = gradient[gx0][gy0][0]*(x/spacing - gx0)+ gradient[gx0][gy0][1]*(y/spacing - gy0);
t = gradient[gx1][gy0][0]*(x/spacing - gx1) + gradient[gx1][gy0][1]*(y/spacing - gy0);
u = gradient[gx0][gy1][0]*(x/spacing - gx0) + gradient[gx0][gy1][1]*(y/spacing - gy1);
v = gradient[gx1][gy1][0]*(x/spacing - gx1) + gradient[gx1][gy1][1]*(y/spacing -gy1);
//calcuate the weighted averages
var Sx:Number = S_curve(x/spacing-gx0);
var a:Number = s + Sx*(t - s);
var b:Number = u + Sx*(v - u);
var Sy:Number = S_curve(y/spacing - gy0);
var z:Number = a + Sy*(b - a);
results[x][y] = z;
}
}
return results;
}
// S-curve takes number between 0 & 1 and shifts its closer to 0 or 1
private function S_curve(p:Number):Number {
return 3*p*p - 2*p*p*p;
}
private function getNoiseFunctionResults(len:int=200, amplitude:Number=1, freq:int=1):Array {
//trace("getNoise(amplitude="+amp+",frequency"+freq+")");
var result:Number = 0;//between -0.5 & 0.5
var wavelength:Number= len/freq;//divide imgWidth by frequency to get wavelength
var results:Array = [];
//start with random seed
var seed:uint = Math.round(Math.random()*0x7FFFFFFF); //seed for prng... can be any uint (except 0)
//get next seed - used for interpolation
var nextseed:uint = prng(seed);
//for each x value
for(var x:int = 0; x < len; x++){
//if we are on a factor of wavelength ... get psuedorandom y value
if(x % wavelength == 0){
//store nextseed as seed
seed = nextseed;
//get next nextseed
nextseed = prng(seed);
//get y value from pseudorandom number
result = (seed/0x7FFFFFFF)*amplitude - amplitude/2;
} else {
//interpolate value between seed & nextseed
result = (interpolate(seed, nextseed, (x % wavelength)/wavelength)/0x7FFFFFFF)*amplitude - amplitude/2;
}
results.push(result);
}
return results;
}
private function prng(seed:uint):uint {
//to get a full period sequence you should feed back the seed
return seed * 16807 % 0x7FFFFFFF;
//return 0xCCCCCCCC;
//to get a value between 0 & 1, divide result / 0x7FFFFFFF
}
private function interpolate(a:int,b:int,i:Number):Number {
//cosine interpolation
var ft:Number = i*Math.PI;
var f:Number = (1 - Math.cos(ft)) * .5;
return a*(1-f) + b*f;
}
}
}
// Copyright (c) 2008 David Wilhelm
// MIT license: http://www.opensource.org/licenses/mit-license.php