algorithm - Help understanding Simplex Noise

Introduction

This is less of a "how to" on using 2D simplex noise and more of a quest to understand what is happening both in the math and visually. I would rather not copy and paste the code I've found. I really would like to understand it.

I have done my homework on the subject and have read through Stefan Gustavson's paper and other sources many times. I feel like I understand about 70% of what my sources are saying, but when I try to manually follow my code loop through to check my understanding I either get hung up on what the variables represent or the math just doesn't add up.

I have begun to rename the variables in the code I've found in order to better understand what's going on. If someone with some knowledge of what is actually happening can cross reference the original code (basically Gustavson's code) with my code that would be most excellent. I'm not actually done with renaming the variables though, partly because I'm stuck.

My Understanding

Let's say I pass pixel (2, 3) into my noise function. At this point I'm working with a normal grid and my goal is to translate this normal grid into a simplex. This simplex is in the form of many triangles since we're working in 2D and supposedly this is better for various reasons.

To translate this point from the normal grid to the simplex grid, I must scale the point along the main diagonal line. After doing that, I apparently don't care about the decimals because I then Floor the results putting it back near the closest previous grid point.

Now I'm going to align the simplex cell to the normal grid by unskewing the simplex cell. Why I do all this work to get to the simplex cell, then undo it I'm pretty hazy on. Seriously, I think the best way for me to understand this is if someone could whiteboard out in steps what the heck is going on here. Super lost.

I didn't walk away empty handed though. I now have what I believe to be the distance between the original grid point I passed in and the simplex point I translated from that original grid point. Woo.

I think I'll stop here for now, just because I don't want this to turn into a huge wall of text. I'm pretty sure the rest of this will click once I understand the the beginning part.

Weird Math

Using the (2, 3) point from earlier, this is what I get by stepping through my own code on paper:

x = 2
y = 3

skewfactor = 1.830
unskewFactor = 1.479
unskewed_x = 1.520
unskewed_y = 2.520
simplexCell_i = 3
simplexCell_j = 4

x_distance0 = -1.520
y_distance0 = -1.520
i1 = 0
j1 = 1
x1 = -1.309
y1 = -2.309
x2 = -2.5207
y2 = -2.5207
ii = no idea why this isn't i2 or something like that. No idea what this is.
jj = same

Not sure if plotting on a graph would work, but I tried and it looks so bad. I used the original parameters (2, 3), simplexCell_i & j, i1, j1, x1, y1, x2, and y2. Doesn't make any sense visually.

Not just visually, but mathematically as well. What's with (2, 3) returning negative numbers that go off the chart? What am I doing wrong here?

Answer

I think it helps to compare it side-by-side with regular Perlin noise. As explained in the Gustavson paper, Perlin noise works by assigning pseudo-random values (gradient vectors) to each corner of a square grid and then doing some interpolation for points in the interior of a grid cell. So the first step in evaluating Perlin noise is to figure out which grid cell you're in. That's what the floor function is doing: all the values between 0 and 1 are in grid cell 0, between 1 and 2 are in grid cell 1, etc. along each axis. So in classic Perlin noise you'll see some code like

int i = int(floor(x));
int j = int(floor(y));

Once you know which grid cell you're in, the rest of the algorithm can proceed.

With simplex noise, as before, the first thing you've got to do is figure out which grid cell you're in. But it's a simplex grid now, which isn't related to the input x and y in such a simple way as the square grid. However, as Perlin noted, and as Gustavson shows in the picture on page 6, if you scale a square grid along its diagonal by just the right factor, the squashed grid cells now have a shape that can be made up of several simplices. (In 2D, for instance, the squashed square is a rhombus that can be made of 2 equilateral triangles. In higher dimensions you'd have more than 2 simplices in each grid cell, but it's the same idea.)

So this provides a way to bridge the gap between the Cartesian coordinate system and the simplex grid. First you figure out which grid cell you're in with respect to the squashed square grid; then you figure out which simplex you're in within that squashed square grid cell.

To figure out which cell of the squashed square grid you're in, you first execute a linear transformation to a coordinate system whose axes line up with the squashed grid. Perlin writes it something like:

float F2 = 0.5*(sqrt(3.0)-1.0);
float s = (xin+yin)*F2;
float xSquashed = x + s;
float ySquashed = y + s;

Here xSquashed, ySquashed are coordinates in the local space of the squashed grid. If you stare at this for a minute, you'll see it's equivalent to the matrix transformation:

[ xSquashed, ySquashed ] = [ xIn, yIn ] * [ 1+F2 F2   ]
                                          [ F2   1+F2 ]

So it's just a linear change of coordinates, although the matrix multiplication is written out in a way that makes that non-obvious.

Then calculating which grid cell you're in is, just like before, simply a floor call on those local coordinates. That gives you the grid cell index for one corner of the simplex. Some more fiddling with the coordinates determines which simplex you're in within the squashed grid cell, and from there you can figure out the grid cell indices for the other corners of the simplex.

Finally, why do you transform back to the regular, non-squashed coordinate system? It's because in the final stage of the algorithm, when you add together the contributions of all the corners, you want to be working with ordinary distance, not the pseudo-distance in the squashed space. That's so the noise interpolates cleanly and doesn't come out with a squashed appearance. Note that what you're transforming back to regular coordinates isn't the original input point, but the first corner of the simplex. Once you've got that, you can find the locations of the other corners and proceed with the rest of the algorithm.

As before, this transformation is written in an odd-looking form but it's equivalent to the matrix transformation:

float G2 = (3.0 - sqrt(3.0))/6.0;
[ X0, Y0 ] = [ i, j ] * [ 1-G2 -G2   ]
                        [ -G2   1-G2 ]

If you calculate it out, you'll see that this matrix and the one mentioned above are inverses of each other.