Da Fish in Sea

So I’ve been struggling with making 2D Perlin Noise for about a week. Most of the stuff on the web seems to assume you have a degree in mathematics… kinda daunting. Ken Perlin’s source code is heavily optimized to the point of obfuscation so it wasn’t much help either. However I did find the following resources helpful:

Ken Perlin’s slideshow about Perlin Noise
— This gave me a high level view of what PN is and the images certainly inspired me to pursue it a little further.

Hugo Elias’s page
– This gives a good visual understanding of the concept behind Perlin Noise, and helped me implement the 1D version. However the 2D algorithm doesn’t seem to corespond to Perlin’s implementation ( I could be wrong).

Matt Zucker’s page
– a pretty thorough and clear explanation of Perlin’s implementation (as far as I can tell.) My implementation is directly following this explanation.

I also did some research into Psuedo Random number generators… ultimately found the Park Miller Carta generator to be the one of choice. It boils down to a single line of code:

1
 seed = seed * 16807 % 0x7FFFFFFF;

Which, when executed recursively, produces a sequence of numbers of sufficient randomness between 0 & 0×7FFFFFFF. I also found an AS3 PRNG implementation which is nicely done. However since it can be done in one line I decided to just do that. You do need to start it off with a random seed, so for that I just used plain old Math.random(). In fact I could probably have just used Math.random() for everything since it’s probably just a PRNG under the hood anyways…. whatever.

So here’s a demo of my implementation, with sliders for amplitude and frequency. Note that it is only one ‘layer’ of noise here : the next step is to add many layers together as I did in the 1D example previously.

You’ll need Flash Player 10 as I used the new Vector type. See previous posts for where to get it.

Here’s the code, first the demo itself:

1
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
package  {

    import flash.display.Sprite;

    import flash.display.Bitmap;

    import flash.display.StageScaleMode;

    import flash.display.StageAlign;

    import flash.display.BitmapData;

    import flash.text.TextField;

    import flash.events.Event;

    import com.bit101.components.*;

    import flash.geom.Rectangle;



    [SWF(backgroundColor="0xFFFFFF", width="600", height="400", frameRate="30")]    

    public class PerlinNoise2D extends Sprite {



        private const imgWidth:Number = 300;    

        private const imgHeight:Number = 300;

        private var octaves:int = 8;

        private var decay:Number= 1;

        private var amplitude:Number=1;

        private var frequency:Number=3;

        private var bm:Bitmap;

        private var bmd:BitmapData;



        public function PerlinNoise2D() {

            stage.scaleMode = StageScaleMode.NO_SCALE;

            stage.align = StageAlign.TOP_LEFT;



            //create a bitmap data 

            bmd = new BitmapData(imgWidth, imgHeight, false, 0x000000);

            //create a bitmao using the data object

            bm = new Bitmap(bmd);

            addChild(bm);

            drawGradient(amplitude,frequency);

            drawUI();

        }

        private function drawUI():void {

            var ui:Sprite = new Sprite();

            //amplitude

            var amplitude_sldr:HSlider = new HSlider(ui, 50, 20, function(e:Event):void {

                    amplitude = e.target.value;

                    amplitude_val.text = ""+amplitude;

                    drawGradient(amplitude,frequency);

                });

            amplitude_sldr.setSliderParams(0,1,1);

            var amplitude_lbl:Label = new Label(ui, 0, 15, "amplitude");

            var amplitude_val:Label = new Label(ui, 150, 15, "1");



            //frequency - between 0 & 1

            var frequency_sldr:HSlider = new HSlider(ui, 50, 40, function(e:Event):void {

                    frequency = Math.round(e.target.value);

                    frequency_val.text = ""+frequency;

                    drawGradient(amplitude,frequency);

                });

            frequency_sldr.setSliderParams(1,10,3);

            var frequency_lbl:Label = new Label(ui, 0, 35, "frequency");

            var frequency_val:Label = new Label(ui, 150, 35, "3");

            ui.x = 300;

            ui.y = 5;

            ui.alpha= 0.8;

            addChild(ui);

        }



        private function drawGradient(a:Number, f:Number):void {

            var c:uint;



            var perlin:PerlinNoise = new PerlinNoise();

            bmd.fillRect(new Rectangle(0, 0, imgWidth, imgHeight), 0x000000);           



            //get 2D Perlin noise

            var pNoise:Array = perlin.getPerlinNoise_2D(imgWidth,a/*amplitude*/,f/*frequency*/);

            //loop through each point and draw

                for(var x:int = 0; x < imgWidth; x++){

                    for(var y:int = 0; y < imgHeight; y++){

                        //normalize pNoise from -1 - 1 to 0-1 range (x255 for color)

                        var r:int = Math.floor((pNoise[x][y]/2 + 0.5)*256);

                        c =  r << 16 | r << 8 | r;

                        bmd.setPixel(x,y,c);

                    }

                }

        }



    }

}

// Copyright (c) 2008 David Wilhelm

// MIT license: http://www.opensource.org/licenses/mit-license.php

And now the PerlinNoise class that does all the hard work

1
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
package  {



    public class PerlinNoise {



        //initialize random seed

        public var seed:uint = prng(Math.random()*0x7fffffff);



        public function PerlinNoise() {

            /*call getPerlinNoise_1D*/

        }



        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

There’s probably room for optimization, but I want to keep it fairly readable, and comprehensible.. at least for myself.

This entry was posted on Friday, September 12th, 2008 at 6:59 pm and is filed under 3d, flash. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.