# Understanding skew factors in Simplex/Improved Perlin Noise

The Simplex Noise (or Improved Perlin Noise) algorithm uses a somewhat mysterious "skew factor" of $\frac{\sqrt{3}-1}{2}$. I did not find any really satisfactory explanation for this factor in the descriptions of Simplex Noise that I read. But I managed to work it out nevertheless, which I thought was a fun exercise and worth a quick write-up.

Simplex noise is constructed by assigning random values to each point in a simplex grid. The simplex grid is a tiling of the plane using rhombuses, each rhombus consisting of two equilateral triangles. See the figure on the right.

Given a point $\left(x,y\right)$ (expressed in normal rectangular coordinates), we first transform the coordinates into $\left(u,v\right)$ expressed in the simplex grid. Then we take the integer parts of u and v to find the corners of the containing equilateral triangle, and take the random values assigned to these corners. The "noise value" of the original point $\left(x,y\right)$ is then some suitable interpolation of these values with respect to the distance from $\left(x,y\right)$ to each corner.

The implementation of this algorithm is explained in detail in several places. The code to transform into and back out of the simplex grid might look like this:

```final double F2 = 0.5*(Math.sqrt(3.0)-1.0);
double s = (xin+yin)*F2;
int u = fastfloor(xin+s);
int v = fastfloor(yin+s);
final double G2 = -(3.0-Math.sqrt(3.0))/6.0;
double t = (u+v)*G2;
double X0 = u+t;
double Y0 = v+t;
```
So the question is, where do these funny factors F2 and G2 come from?

To understand this, let us first consider the general form of the transformation from simplex coordinates $\left(u,v\right)$ in the grid spanned by $\stackrel{\to }{u}$ and $\stackrel{\to }{v}$ to the rectangular coordinates $\left(x,y\right)$. It is

$x=au+bv$
$y=cu+dv$
where $\stackrel{\to }{u}= \left(a,c\right)$ and $\stackrel{\to }{u}=\left(b,d\right)$. So this requires 4 multiplications in the general case.

However, we can freely choose which simplex grid to use! So we can try to choose one that reduces the computational work needed.

First, we can choose the orientation of the grid so that $\stackrel{\to }{u}$ and $\stackrel{\to }{v}$ are symmetric around the diagonal $x=y$. Then $a=d$ and $b=c$, so we can write the transformation as

$x=\left(a-b\right)u+b\left(u+v\right)$
$y=\left(a-b\right)v+b\left(u+v\right)$
Second, we can choose the scale of the grid so that $\left(a-b\right)=1$, and then we get simply
$x=u+t$
$y=v+t$
where $t=b\left(u+v\right)$. This simpler form requires only a single multiplication.

This is exactly the form we see in the above code snippet, with G2 being the name for the constant $b$. We can work out from this that the vectors that span the grid used by the code are

$\stackrel{\to }{u}= \left(1-\frac{3-\sqrt{3}}{6},-\frac{3-\sqrt{3}}{6}\right)$
$\stackrel{\to }{v}= \left(-\frac{3-\sqrt{3}}{6},1-\frac{3-\sqrt{3}}{6}\right)$
The interested reader is encouraged to check that $\stackrel{\to }{u}$, $\stackrel{\to }{v}$, and $\stackrel{\to }{u}+\stackrel{\to }{v}$ all have the same length, so that the triangles that form the grid indeed end up being equilateral.

Working out the inverse of the transformation (again a good exercise for the interested reader) leads to another transformation of the same simple form, this time with the constant $F2 =\frac{\sqrt{3}-1}{2}$ as seen in the code.

So I believe this is the explanation of the mysterious factors F2 and G2 in the example code found by Google searches on the net. They arise from the choice of the simplex grid to use. This choice is made to make the associated coordinate transformation use only a single multiplication, rather than the four required in the general case. This makes the implementation of the algorithm more efficient. Pretty clever, right?

Tags:
• #### Hacking a box of 240x320 displays with the ESP8266

For the last few days, I have been playing with some small displays we have lying around in Labitat. We have ninety-odd of them from an old…

• #### FVWM and Java application window focus

I found the solution for a problem that has been annoying me for quite some time. I am using FVWM for a window manager. A few programs written in…

• #### Improving replication with multiple storage engines

New MariaDB/MySQL storage engines such as MyRocks and TokuDB have renewed interest in using engines other than InnoDB. This is great, but also…

• Post a new comment

#### Error

default userpic