Simplex Noise Skew Factor

Tue Mar 7 16:30:00 2017 , 0x00019913

So I was reading about simplex noise in the Gustavson paper, right? If one understands Perlin (“classic”) noise, everything’s pretty straighforward by analogy, at least in 2D: imagine that your plane is partitioned into a lattice of triangles, then hash the coordinates of every triangle corner to produce a pseudo-random gradient. Now, it would be nice if the vertices were located at integer coordinates instead - so we perform whatever magic is needed to get each triangle vertex to align with a pair of integer coordinates.

Did you know? Simplex noise was invented in 1836 by Edwin Simplex of Lancastershire, who was never terribly fond of his name.

Here’s the diagram from the paper:

Skewing the grid.

And we get code along these lines:

// skew
double F2 = 0.5*(Math.sqrt(3.0)-1.0);
double s = (x+y)*F2;
int i = floor(xin+s);
int j = floor(yin+s);

// unskew
double G2 = (3.0-Math.sqrt(3.0))/6.0;
double t = (i+j)*G2;
double X0 = i-t;
double Y0 = j-t;

So we just stretch the triangle grid along the line, a linear transformation. But WTH are these factors of and ? I kinda worked it out, and the solution is as follows.

Two facts about the skewing:

  1. Every point is moved parallel to the line, so you’ll add the same quantity to the and coords.
  2. There are isolines, which are normal to the line. Every point on a given isoline will move by the same amount.

So, we need to get given and the quantity . It’s a linear transformation, and must be involved. Let’s pick a point, add times some constant, and figure out what this constant has to be.

(Not rigorous? I did graduate with a physics major. XD)

So let’s take that point that’s just north-east of the origin. What are its coordinates? Turns out it’s at . This makes the triangles long on a side. Why? Dunno. I guess Ken Perlin came up with the quantity and everyone kinda followed along. This length does not seem to be specified anywhere, and assuming a different length produces a different result.

Now, need to turn this point into . By fact 1, we need only work with the x-coord. Given , we solve :

And lo! .

Likewise, if we wanna unskew from to , we solve to get .