Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by happyinmotion on Thu Dec 01, 2011 4:16 am

Hi All,

I was keen on some smooth flowing patterns for an LPD8806 & Arduino project that I have underway, hence I though to myself "Perlin noise" is what I'm after. It's a noise function that gives a very natural looking pattern, it's often used for simulating clouds and so on, invented by Ken Perlin.

So, I found an implementation on the Arduino forums from Mike Edwards (http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1191768812) so I tried that. Sadly, it was far too slow. Like 10 ms per LED per colour. I've 96 LEDs on this strip, I'd like to run each one with red, green, and blue, and I want the animation to be smooth, really smooth, so that's a maximum of 50 ms per update. I don't know if this is an efficient implementation of the Perlin noise algorithm or not, but 10 ms per LED isn't going to do the job.

Hence there was some scratching of my head until I came across simplex noise. This was also invented by Ken Perlin. Again, some useful person (Stephen Carmody) had written an implementation (http://stephencarmody.wikispaces.com/Simplex+Noise) in Java, so not much effort to get it up and running on an Arduino. Much faster, under 2 ms per LED per colour. Thus the Arduino can manage ten LEDs and full colour. However, still not good enough if I want to run 96 LEDs.

Further scratching around and I finally twigged to a scheme that might just work - just calculate the simplex noise for a few LEDs and interpolate between them. So, six LEDs controlled by simplex noise, the rest with cubic interpolation to fill in the gaps. The interpolation takes under 0.1 ms per LED so bingo - 96 LEDs with a 50 ms update time.

Here's a video of some test patterns to show the difference in shininess between Perlin, simplex, and simplex with interpolation. I suggest viewing at 720p quality or the video compression induces jumpiness that's not present in reality:
http://youtu.be/vtO0A0CRxo8

Here's the code for the patterns in the video. (I know it's not the most tidy code, sorry.)
Code: Select all
/*
Fast and smooth random colour patterns for a LPD8066 addressable RGB LED strip.
By happyinmotion (jez.weston@yahoo.com)

Simplex noise code taken from Stephen Carmody's Java implementation at:
http://stephencarmody.wikispaces.com/Simplex+Noise

Perlin Noise code copyright 2007 Mike Edwards:
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1191768812

// Timing results on a 96 LED strip controlled by an Arduino Nano v3:
// Perlin noise - 10 ms per LED per colour
// Simplex noise - 1 ms per LED per colour
// Cubic interpolation - 0.02 ms per LED per colour
//
// Smooth motion needs a refresh every 50 ms or so. For a 96 RGB LED strip, I used 6 simplex nodes with interpolation between to get it all smoothly flowing.
*/


// LPD8806-based code from Adafruit for RGB LED Modules in a strip
/*****************************************************************************/
// you can also use hardware SPI, for ultra fast writes by leaving out the
// data and clock pin arguments. This will 'fix' the pins to the following:
// on Arduino 168/328 thats data = 11, and clock = pin 13.
#include "LPD8806.h"
#include "SPI.h"


// Strip variables:
const int LEDs_in_strip = 96;
const int LEDs_for_simplex = 6;
// Extra fake LED at the end, to avoid fencepost problem.
// It is used by simplex node and interpolation code.
float LED_array_red[LEDs_in_strip+1];
float LED_array_green[LEDs_in_strip+1];
float LED_array_blue[LEDs_in_strip+1];
float LED_array_hue[LEDs_in_strip+1];
float LED_array_brightness[LEDs_in_strip+1];

int node_spacing = LEDs_in_strip / LEDs_for_simplex;
LPD8806 strip = LPD8806(LEDs_in_strip);

// Perlin noise global variables:
float x1,y1,x2,y2;
// Set up Perlin globals:
//persistence affects the degree to which the "finer" noise is seen
float persistence = 0.25;
//octaves are the number of "layers" of noise that get computed
int octaves = 3;
// Simplex noise global variables:
int i, j, k, A[] = {0, 0, 0};
float u, v, w, s;
static float onethird = 0.333333333;
static float onesixth = 0.166666667;
int T[] = {0x15, 0x38, 0x32, 0x2c, 0x0d, 0x13, 0x07, 0x2a};

// Simplex noise parameters:
// Useable values for time increment range from 0.005 (barely perceptible) to 0.2 (irritatingly flickery)
// 0.02 seems ideal for relaxed screensaver
float timeinc = 0.02;
// Useable values for space increment range from 0.8 (LEDS doing different things to their neighbours), to 0.02 (roughly one feature present in 15 LEDs).
// 0.05 seems ideal for relaxed screensaver
float spaceinc = 0.1;
// Simplex noise variables:
// So that subsequent calls to SimplexNoisePattern produce similar outputs, this needs to be outside the scope of loop()
float yoffset = 0.0;
float saturation = 1.0;


void setup()
{
  // Start up the LED strip
  strip.begin();

  // Update the strip, to start they are all 'off'
  strip.show();

  Serial.begin(9600);
  Serial.println("Setup done ");
}


void loop() {
  int repeats = 200;

  // Perlin noise for five red LEDs
  timeinc = 0.1;
  for ( int i=0; i<repeats; i++ ) {
    PerlinNoisePattern( 5 );
    yoffset += timeinc;
  }

  AllOff();
  delay(500);

  // Simplex noise for ten full-colour LEDs
  // No interpolation.
  timeinc = 0.02;
  for ( int i=0; i<repeats; i++ ) {
    SimplexNoisePattern( spaceinc, timeinc, yoffset, 10);
    yoffset += timeinc;
  }
  AllOff();
  delay(500);

  // Simplex noise for whole strip of 96 LEDs.
  // (Well, it's simplex noise for 6 LEDs and cubic interpolation between those nodes.)
  for ( int i=0; i<repeats; i++ ) {
    SimplexNoisePatternInterpolated( spaceinc, timeinc, yoffset);
    yoffset += timeinc;
  }
  AllOff();
  delay(500);
}



void PerlinNoisePattern(int numLEDs) {
  float xoffset = 1.0;
  for (int j=0; j < numLEDs; j++) {
    xoffset += spaceinc;
   
    // Caluclate Perlin Noise (range -1 to 1), expand and bias that range:
    // Takes around 10 ms per call, so only doing this for the red LEDs, not full colour
    int r = int(PerlinNoise2(xoffset,yoffset,persistence,octaves)*196+32);       
    // Clip output to the brightness level of 0-127 that the LED strip accepts.
    // Doing this with constrain() is slooow. Doing this explicitly adds no time at all. Conclusion: constrain() sucks.
    if ( r>127 ) { r=127; }
    else if ( r<0 ) { r=0; }

    strip.setPixelColor(j, r, 0, 0);
  }
 
  strip.show();
}



void SimplexNoisePattern( float spaceinc, float timeinc, float yoffset, int numLEDs) {
    // Calculate simplex noise for LEDs that are nodes:
    // Store raw values from simplex function (-0.347 to 0.347)
    float xoffset = 0.0;
    for (int i=0; i<numLEDs; i++) {
      xoffset += spaceinc;
      LED_array_red[i] = SimplexNoise(xoffset,yoffset,0);
      LED_array_green[i] = SimplexNoise(xoffset,yoffset,1);
      LED_array_blue[i] = SimplexNoise(xoffset,yoffset,2);
    }
 
    // Convert values from raw noise to scaled r,g,b and feed to strip.
    // Raw noise is -0.347 to +0.347 or thereabouts.
    for (int i=0; i<numLEDs; i++) {
      int r = int(LED_array_red[i]*403 + 16);
      int g = int(LED_array_green[i]*403 + 16);
      int b = int(LED_array_blue[i]*403 + 16);
     
      if ( r>127 ) { r=127; }
      else if ( r<0 ) { r=0; }  // Adds no time at all. Conclusion: constrain() sucks.
 
      if ( g>127 ) { g=127; }
      else if ( g<0 ) { g=0; }
 
      if ( b>127 ) { b=127; }
      else if ( b<0 ) { b=0; } 
 
      strip.setPixelColor(i, r, g, b);
    }

    // Update strip 
    strip.show();
}



void SimplexNoisePatternInterpolated( float spaceinc, float timeinc, float yoffset) {
    // Calculate simplex noise for LEDs that are nodes:
    // Store raw values from simplex function (-0.347 to 0.347)
    float xoffset = 0.0;
    for (int i=0; i<=LEDs_in_strip; i=i+node_spacing) {
      xoffset += spaceinc;
      LED_array_red[i] = SimplexNoise(xoffset,yoffset,0);
      LED_array_green[i] = SimplexNoise(xoffset,yoffset,1);
      LED_array_blue[i] = SimplexNoise(xoffset,yoffset,2);
    }

    // Interpolate values for LEDs between nodes
    for (int i=0; i<LEDs_in_strip; i++) {
      int position_between_nodes = i % node_spacing;
      int last_node, next_node;

      // If at node, skip
      if ( position_between_nodes == 0 ) {
        // At node for simplex noise, do nothing but update which nodes we are between
        last_node = i;
        next_node = last_node + node_spacing;
      }
      // Else between two nodes, so identify those nodes
      else {
        // And interpolate between the values at those nodes for red, green, and blue
        float t = float(position_between_nodes) / float(node_spacing);
        float t_squaredx3 = 3*t*t;
        float t_cubedx2 = 2*t*t*t;
        LED_array_red[i] = LED_array_red[last_node] * ( t_cubedx2 - t_squaredx3 + 1.0 ) + LED_array_red[next_node] * ( -t_cubedx2 + t_squaredx3 );
        LED_array_green[i] = LED_array_green[last_node] * ( t_cubedx2 - t_squaredx3 + 1.0 ) + LED_array_green[next_node] * ( -t_cubedx2 + t_squaredx3 );
        LED_array_blue[i] = LED_array_blue[last_node] * ( t_cubedx2 - t_squaredx3 + 1.0 ) + LED_array_blue[next_node] * ( -t_cubedx2 + t_squaredx3 );
      }
    }
 
    // Convert values from raw noise to scaled r,g,b and feed to strip
    for (int i=0; i<LEDs_in_strip; i++) {
      int r = int(LED_array_red[i]*403 + 16);
      int g = int(LED_array_green[i]*403 + 16);
      int b = int(LED_array_blue[i]*403 + 16);
     
      if ( r>127 ) { r=127; }
      else if ( r<0 ) { r=0; }  // Adds no time at all. Conclusion: constrain() sucks.
 
      if ( g>127 ) { g=127; }
      else if ( g<0 ) { g=0; }
 
      if ( b>127 ) { b=127; }
      else if ( b<0 ) { b=0; } 
 
      strip.setPixelColor(i, r, g, b);
    }

    // Update strip 
    strip.show();
}



/*****************************************************************************/
// Simplex noise code:
// From an original algorythm by Ken Perlin.
// Returns a value in the range of about [-0.347 .. 0.347]
float SimplexNoise(float x, float y, float z) {
  // Skew input space to relative coordinate in simplex cell
  s = (x + y + z) * onethird;
  i = fastfloor(x+s);
  j = fastfloor(y+s);
  k = fastfloor(z+s);
   
  // Unskew cell origin back to (x, y , z) space
  s = (i + j + k) * onesixth;
  u = x - i + s;
  v = y - j + s;
  w = z - k + s;;
   
  A[0] = A[1] = A[2] = 0;
   
  // For 3D case, the simplex shape is a slightly irregular tetrahedron.
  // Determine which simplex we're in
  int hi = u >= w ? u >= v ? 0 : 1 : v >= w ? 1 : 2;
  int lo = u < w ? u < v ? 0 : 1 : v < w ? 1 : 2;
   
  return k_fn(hi) + k_fn(3 - hi - lo) + k_fn(lo) + k_fn(0);
}


int fastfloor(float n) {
  return n > 0 ? (int) n : (int) n - 1;
}


float k_fn(int a) {
  s = (A[0] + A[1] + A[2]) * onesixth;
  float x = u - A[0] + s;
  float y = v - A[1] + s;
  float z = w - A[2] + s;
  float t = 0.6f - x * x - y * y - z * z;
  int h = shuffle(i + A[0], j + A[1], k + A[2]);
  A[a]++;
  if (t < 0) return 0;
  int b5 = h >> 5 & 1;
  int b4 = h >> 4 & 1;
  int b3 = h >> 3 & 1;
  int b2 = h >> 2 & 1;
  int b = h & 3;
  float p = b == 1 ? x : b == 2 ? y : z;
  float q = b == 1 ? y : b == 2 ? z : x;
  float r = b == 1 ? z : b == 2 ? x : y;
  p = b5 == b3 ? -p : p;
  q = b5 == b4 ? -q: q;
  r = b5 != (b4^b3) ? -r : r;
  t *= t;
  return 8 * t * t * (p + (b == 0 ? q + r : b2 == 0 ? q : r));
}


int shuffle(int i, int j, int k) {
  return b(i, j, k, 0) + b(j, k, i, 1) + b(k, i, j, 2) + b(i, j, k, 3) + b(j, k, i, 4) + b(k, i, j, 5) + b(i, j, k, 6) + b(j, k, i, 7);
}


int b(int i, int j, int k, int B) {
  return T[b(i, B) << 2 | b(j, B) << 1 | b(k, B)];
}


int b(int N, int B) {
  return N >> B & 1;
}


/*****************************************************************************/
// Perlin noise code:
// using the algorithm from http://freespace.banned.net/hugo.elias/models/m_perlin.html
// thanks to hugo elias
float Noise2(float x, float y)
{
  long noise;
  noise = x + y * 57;
  noise = (noise << 13) ^ noise;
  return ( 1.0 - ( long(noise * (noise * noise * 15731L + 789221L) + 1376312589L) & 0x7fffffff) / 1073741824.0);
}

float SmoothNoise2(float x, float y)
{
  float corners, sides, center;
  corners = ( Noise2(x-1, y-1)+Noise2(x+1, y-1)+Noise2(x-1, y+1)+Noise2(x+1, y+1) ) / 16;
  sides   = ( Noise2(x-1, y)  +Noise2(x+1, y)  +Noise2(x, y-1)  +Noise2(x, y+1) ) /  8;
  center  =  Noise2(x, y) / 4;
  return (corners + sides + center);
}

float InterpolatedNoise2(float x, float y)
{
  float v1,v2,v3,v4,i1,i2,fractionX,fractionY;
  long longX,longY;

  longX = long(x);
  fractionX = x - longX;

  longY = long(y);
  fractionY = y - longY;

  v1 = SmoothNoise2(longX, longY);
  v2 = SmoothNoise2(longX + 1, longY);
  v3 = SmoothNoise2(longX, longY + 1);
  v4 = SmoothNoise2(longX + 1, longY + 1);

  i1 = Interpolate(v1 , v2 , fractionX);
  i2 = Interpolate(v3 , v4 , fractionX);

  return(Interpolate(i1 , i2 , fractionY));
}

float Interpolate(float a, float b, float x)
{
  //cosine interpolations
  return(CosineInterpolate(a, b, x));
}

float LinearInterpolate(float a, float b, float x)
{
  return(a*(1-x) + b*x);
}

float CosineInterpolate(float a, float b, float x)
{
  float ft = x * 3.1415927;
  float f = (1 - cos(ft)) * .5;

  return(a*(1-f) + b*f);
}

float PerlinNoise2(float x, float y, float persistance, int octaves)
{
  float frequency, amplitude;
  float total = 0.0;

  for (int i = 0; i <= octaves - 1; i++)
  {
    frequency = pow(2,i);
    amplitude = pow(persistence,i);

    total = total + InterpolatedNoise2(x * frequency, y * frequency) * amplitude;
  }
  return(total);
}



void AllOff() {
  // Reset LED strip
  strip.begin();
  strip.show();
}


I'd love to see a library for the LPD8806 & Arduino combination that includes as many shiny algorithms as possible. Here's simplex, but I'd also love to see some reaction-diffusion patterns and whatever else people can think of. I'm slowly working away at some more ideas (as well as working on the hardware for this project) and I'm happy to share the implementations, but there seems to be enough people using the LPD8806 & Arduino combination that a library could help all of us.
happyinmotion
 
Posts: 29
Joined: Tue Nov 01, 2011 5:15 pm

Re: Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by Cranium on Thu Dec 01, 2011 9:48 am

I'd love to see more done with this as well. I don't know how good it will look on a single LED strip but I'm also working on designing a matrix of LEDs using 5050 RGB leds and LPD8806's made up of 10cm x 10cm PCBs that can connect together to make larger panels. These types of algorithms would be ideal to use with this.

The arduino would certainly have issues computing these algorithms but one thing I've considered that I haven't seen much is using multiple arduinos working together and communicating over a serial bus to distribute load for more complex animations.

I'll be watching for updates on your progress with this. :)
Cranium
 
Posts: 20
Joined: Tue Oct 25, 2011 7:08 am

Re: Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by happyinmotion on Thu Dec 01, 2011 1:02 pm

I've been testing out algorithms in Processing and I've realised that basically, I'm just missing toxiclibs. Sadly, I don't have the time or programming skill to port it.

My project is entirely one-dimensional so I've not thought about how this could work across a matrix. Certainly with more LEDs the computational load starts to get more than one Arduino will cope with (well, until a 32-bit version comes out). Still, you can interpolate in two dimensions, so I wonder how your matrix might look with simplex nodes at the corners (and maybe one in the center) and interpolation across the rest? And what size matrix are you after? I've got this working on nearly a hundred LEDs, so a 10x10 LED matrix should be feasible.
happyinmotion
 
Posts: 29
Joined: Tue Nov 01, 2011 5:15 pm

Re: Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by Cranium on Thu Dec 01, 2011 1:27 pm

With what I would like to do, it would require a much larger size. Each 10cm x 10cm PCB will have at least 36 LEDs on it and more if I can fit it. I haven't really started working on the design yet so don't know the numbers for sure. But I would like it to support as many of these PCB's connected together as possible. Perhaps an arduino on each would make it scalable.
Cranium
 
Posts: 20
Joined: Tue Oct 25, 2011 7:08 am

Re: Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by happyinmotion on Thu Dec 01, 2011 2:14 pm

Ooo, that's going to be lots of LEDs. I don't know how you'd go about doing that, but I might have some algorithms for you (eventually).
happyinmotion
 
Posts: 29
Joined: Tue Nov 01, 2011 5:15 pm

Re: Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by pounce on Thu Dec 01, 2011 4:42 pm

From an end result perspective how about a low tech and low geek factor approach and simply pre-generate the 288byte writes and read them from a card?
pounce
 
Posts: 82
Joined: Wed Nov 23, 2011 5:36 pm

Re: Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by Cranium on Thu Dec 01, 2011 4:53 pm

That would work for a repeating sequence that is pre-generated and indeed, may be the only option available for scaling with the Arduino.

However, having random patterns generated on the fly would create the most diverse and intriguing patterns over a long period of time. One could argue that the patterns will be the same from the time of booting up; however, a clock could be easily added to essentially get a random seed each time it has to be restarted. :)
Cranium
 
Posts: 20
Joined: Tue Oct 25, 2011 7:08 am

Re: Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by happyinmotion on Thu Dec 01, 2011 6:26 pm

Yup, one suggestion that I've received from several places is to use a lookup table to replace the simplex noise function.

An Arduino Nano has 2 kB of SRAM just sitting there doing not much. You could replace the millisecond simplex noise function with a microsecond lookup. Given that the end result is going to be scaled into a 0-127 brightness range, then the lookup table wouldn't need to be too big, a byte per value should do it. A thousand bytes of smooth randomness should be enough to avoid anyone noticing the repeating nature of the pattern. If it is, then there's little tricks to be tried to make it look more random. One I like is to start by reading the R brightness value from a given position, let's call it x. Read the G from x+offset, and B from x+offset+offset. Then change that offset and you'll get a different pattern from the same lookup table. Other tricks are to start from a random position, read the table backwards, etc.
happyinmotion
 
Posts: 29
Joined: Tue Nov 01, 2011 5:15 pm

Re: Smooth flowing random patterns on an LPD8806 strip - Perlin & simplex noise

by wetterberg on Fri Dec 02, 2011 11:31 am

Very nice indeed - I'll be trying out your code next week :)

The lookup idea is a good one, though - one trick to try is to read from the lookup at (some prime number)*(some speed) - if you do intervals like 3ms, 7ms and 5ms you'll get a 35ms cycle out of it, while keeping the temporal res higher. Read the table like a parallelogram and you've increased the perceived res even further.

I'll be staring intently at this thread, since I have a 7+7 meter double helix to run...!
wetterberg
 
Posts: 10
Joined: Fri Nov 25, 2011 11:21 am