sin's blog

SiNoise part 1

The first thing I have decided to do for my TSoC project is to add noise-based volcanoes in the game engine.

I couldn't find any resource of how to do this so I went and thought of my an approach. I could identify these as the main two problems-

  • How do I ensure that my noise function "dies out" i.e. reach the value of zero before hitting the border of the region reserved for the volcano?
  • How do I get a sense of distance from the centre of the region reserved?

To answer both these things I proposed my own noise provider at the Teraology forums and got a positive response, though it was modified when I got to the actual implementation :P. I'll explain in detail the one that has been implemented by me "Radial Noise Region Selection".

To start have a look at this diagram-

Noise diagram

An explaination- Noise() is a 1D tile-able noise function. I modified the famous Simplex and Perlin implementations to make them tileable, but lets have a look at that later. It should be apparent how the noise function should "die out" before hitting the boundaries by choosing an appropriate constant. And for a fixed θ it can be observed that the noise value should be maximum at the centre and 0 at the peripheri, hence it gives a sense of distance as well.

Now lets go the first problem of controlling the base noise generators and making it tileable. I'll recommend the readers to go through this awesome paper explaining the Simplex and Perlin noise generators and provides sample implementations which have been used in the Terasology engine. Though I'll try my best that it is not necessary for the reader to study it in exteme detail and a basic knowledge of Perlin is sufficient. Also I shall provide links to the code in case someone wants to use this directly.

Perlin

In the Perlin implementation an randomized array of numbers from 1-256 is used in assigning the Perlin gradient vectors. And we can see this in the implementation-

// Find unit grid cell containing point
int X = fastfloor(x);
int Y = fastfloor(y);
int Z = fastfloor(z);

// Get relative xyz coordinates of point within that cell
x = x - X;
y = y - Y;
z = z - Z;

// Wrap the integer cells at 255 (smaller integer period can be introduced here)
X = X & 255;
Y = Y & 255;
Z = Z & 255;

The X, Y, Z, x, y, z are used in all the further calculations, hence when these values repeat the noise value would repeat. So, we can control the input to the noise in order to control tiling. For example- for a simple tiled procedural texture we could map the (0,0) uv coords to (0,0,0) or (0,0) and (1,1) could be mapped to (256,256,0) or (256,256), But there is still one issue, this 256x256x256 grid will always contain a "fixed amount of noise" i.e. the number of black/white spots we see in the visualisations of noise would almost remain same and the count will also be quite high. this is undesirable if this is to be used as a block's texture in Terasology, hence we need to change all the hardcoded 255, 256, 512 to some variable value so the "amount of noise" can be controlled.

To get the changes done refer this PR I filed over at Terasology. The code over there should be copypasta-able except there is an additional usage of TeraMath.FastRandom so fetch that from here.

Simplex

After much research I concluded that Simplex cannot be tiled in 2D without artifacts due to the nature of the technique. Perlin divides the entire space into hypercubes(squares for 2D) then adds the contribution of each vertex of the hypercube in which our point lies to get the noise value. 256x256 squares will make a big square which will be good to use but in in simplex the hypercubes are replace by simplexes which in 2D are equilateral triangles and the grid looks like this

Simplex grid

Hence instead of a big square that is tiled in the entire coordinate space, we'll be having rhombuses(hold your horses I'll be explaining why rhombus) that are tiled in the entire region :( However it is still possible to get 1D tiled noise from a 2D simplex. Simplex Rhombus Diagonal

If we go along the shorter diagonal of the rhombus then we'll be finding finding values being repeated after crossing on to the next rhombus. Another thing that'll come in handy is that these coordinates are of the type (x,x).

Going a bit deeper into Simplex, how does it work? So adding the contributions from the three vertices of the triangle should be simple, the issue is finding those three vertices, and they are best summed up by this diagram that I stole from that awesome paper.

Simplex Transform

Once such a transformation is done it is really simple to to determine the square cell a point is in and further which transformed simplex it is in by playing around with integral parts and fractional parts. Then the vertices of the transformed simplex are subjected to the inverse transformation.

The algorithm goes on but this is sufficient for our needs.

// Skew the input space to determine which simplex cell we're in
float s = (xin + yin) * F2; // Hairy factor for 2D
int i = TeraMath.floorToInt(xin + s);
int j = TeraMath.floorToInt(yin + s);
float t = (i + j) * G2;
float xo0 = i - t; // Unskew the cell origin back to (x,y) space
float yo0 = j - t;
float x0 = xin - xo0; // The x,y distances from the cell origin
float y0 = yin - yo0;

In rest of the code i, j, x0, y0 are used(hint: these are the inverse transformed integer and fractional parts). Again a permutation array which has the hardcoded size of 256 is used to shuffle things and this is of our particular interest.

// Work out the hashed gradient indices of the three simplex corners
int ii = i & 255;
int jj = j & 255;

ii, jj are used as indices into that array, so we can now see that the grid in the transformed space is a 256x256 square and hence a rhombus in the untransformed space. Again the issue of the "fixed amount of noise", find here the changes I did to get past that.

Now the goal is clear, we need to find that untransformed coordinate which corresponds to 1,1 in the transformed space and then we can scale it with N to find the extreme point of the diagonal for an NxN grid

private static final float F2 = 0.5f * (float) (Math.sqrt(3.0f) - 1.0f);
private static final float G2 = (3.0f - (float) Math.sqrt(3.0f)) / 6.0f;

So putting i = 1, j = 1 in the unskewing formula we get, 0.5773502691896257

Was pretty fun getting here!

Next post should put these noise functions to use...

Edit: Next post is up!

#procgen #proceduralgeneration #noise #perlin #simplex #volcano

- 2 toasts