I'm trying to create a more optimized function of the perlin noise algorithm to use in a light installation.

I would like to know if someone sees more possibilities to improve the speed.

Its now pretty fast already (compared with versions I've tried already) and I'm happy with how it looks (sure the other ones are more sophisticated)

It takes about 7 milliseconds for 20 lights. However its just one octave of noise. Two octaves take already 12 milliseconds.

With other interpolations (not lerp but cosine) calculation time will grow fast.

Just to give you an insight of my progress:

I've tested different implementations of the algorithm already. They all took longer than about 20 milliseconds.

http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1191768812 (Two implementations).

http://happyinmotion.livejournal.com/278357.html (Simplex noise)

And I've read some explanations about the algorithm:

http://freespace.virgin.net/hugo.elias/models/m_perlin.html

http://www.gamedev.net/blog/73/entry-1382657-fast-perlin-noise/

I've finally ended up with the version below mainly based on this source (which is kind of the same as the Mike Edwards implementations from the forum post). For me it was easy to undress this code, because it uses clear functions and naming:

http://code.google.com/p/britable/source/browse/trunk/britable/britable.pde

I partly understand the Maths behind it the algorithm, that makes it difficult to come up with good solutions myself (I tried but failed..).

One improvement I can think of can be the use of a lookup table with random values instead of the randomGenerator used. The lookup table can't be massive either due memory constraints.

But is it worth it and how do I implement it in the functions below?

There are examples that use a lookup table (like the 2nd example in this topic: http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1191768812), but this code is kind of messy (or at least not clear from a programming perspective, I think a mathematician wouldn't have trouble reading this).

Below a script where I measure the timing and that prints out some values to check if it works in the Serial monitor.

I suppose its already useful for people who want to do something with this and some leds, so feel free to use it.

I've added the code in an .ino file as attachment as well.

/* Code based on perlin function in this source

http://code.google.com/p/britable/source/browse/trunk/britable/britable.pde#

http://code.google.com/p/britable/

kasperkamperman.com 16-09-2012

*/

const byte amountOfLights = 20;

byte lightArray[amountOfLights]; // lightArray is in bytes just values in range of 0 - 255

unsigned long currentTime; // for time measuring purposes

unsigned long passedTime; // for time measuring purposes

unsigned long longestTime = 0; // for time measuring purposes

float perlinTimeInc = 0.07;

float perlinXInc = 0.05;

float perlinTimePosition;

void setup()

{ Serial.begin(57600);

}

void loop()

{

currentTime = micros(); // store current time

for(byte i=0;i<amountOfLights;i++)

{

float x = float(i)*perlinXInc; // input for x value in the renderNoise function

byte val = renderNoise(x, perlinTimePosition);

lightArray[i] = val;

}

// go a step further in time (input for y function in perlin noise)

perlinTimePosition = perlinTimePosition + perlinTimeInc;

// calculate the time the whole calculation took

passedTime = micros()-currentTime;

// because times will variate, remember the maximum time it took

if(passedTime>longestTime) longestTime = passedTime;

// print the time it took for the current calculation and the maximum time

Serial.print("time: ");

Serial.print(passedTime);

Serial.print(" max: ");

Serial.println(longestTime);

Serial.print("array: ");

// print the array to see the result

// I calculate back to float just for printing purposes

// I this way so actually see a perlin effect

for(byte i=0;i<amountOfLights;i++)

{ float printFloat = (lightArray[i]/255.0) * 9;

Serial.print(printFloat,0);

Serial.print(", ");

}

Serial.println();

Serial.println();

delay(50);

}

// returns a value between 0 - 255 for lights

byte renderNoise(float x, float y)

{

float noise;

// 2 octaves

//noise = perlin_function(x,y) + perlin_function(x*2,y*2);

noise = perlin_function(x,y); // gives noise in the range of -1 to +1

noise = noise *128+127; // scale to a number between 0 - 255

return (byte) noise;

}

float perlin_function(float x, float y)

{

int fx = floor(x);

int fy = floor(y);

float s,t,u,v;

s=perlin_noise_2d(fx,fy);

t=perlin_noise_2d(fx+1,fy);

u=perlin_noise_2d(fx,fy+1);

v=perlin_noise_2d(fx+1,fy+1);

float inter1 = lerp(s,t,x-fx);

float inter2 = lerp(u,v,x-fx);

return lerp(inter1,inter2,y-fy);

}

float perlin_noise_2d(int x, int y) {

long n=(long)x+(long)y*57;

n = (n<<13)^ n;

return 1.0 - (((n *(n * n * 15731L + 789221L) + 1376312589L) & 0x7fffffff) / 1073741824.0);

}

float lerp(float a, float b, float x)

{ return a + x * (b - a);

}