Value Noise and Procedural Patterns: Part 1, Creating a Simple 2D noise

https://www.scratchapixel.com/lessons/procedural-generation-virtual-worlds/procedural-patterns-noise-part-1/creating-simple-2D-noise

Creating a Simple 2D Noise
우리는 이전 챕터에서 noise를 만드는데 사용되는 대부분의 기법들을 설명했다. 더 높은 차원의 noise를 만드는 것은 이제 좀 더 간단한 일로 부터 시작할 것이다. 왜냐하면 그것들은 모두 같은 개념과 기법들을 기반으로 하기 때문이다. 너가 나아가기전에 이전 챕터에서 우리가 설명했던 것을 마스터하고 진정으로 이해하도록 해라. 만약 아직 꽤 명확하지 않다면, 다시 읽고, 너가 질문이 있다면 우리에게 메일을 주어라.

모든 noise functions이 float를 반환하지만 그것의 입력은 float, 2D point or 3D point가 될 수 있다는 것을 기억해라. noise function에 주어지는 이름은 그것의 입력 값의 차원과 관련된다. 2D noise는 그러므로 2D point를 입력으로 받는 noise function이다. 3D noise는 3D point를 취하고, 우리는 심지어 이 강의의 첫 챕터에서 4D noise를 언급했었다. 거기에서 4차원은 사실 시간에 대해 설명한다 (그것은 3D point를 기반으로 noise pattern을 만들 것이지만, 시간에 따라 animated 되는 패턴이다).

만약 너가 Interpolation 강의를 읽었다면 (우리는 만약 너가 읽지 않았다면 그것을 하라고 제안한다) 너는 이미 2D noise가 어떻게 작동할지에 대한 아이디어를 가질지도 모른다. 2D case에 대해, 우리는 한 regular 2D grids (figure 1)의 vertex position에 random values를 분배할 것이다. noise function의 2D version은 2D point를 입력으로 받을 것이다. 이 점을 P라고 부르자. 1D version과 유사하게, 우리는 grid에서 그 점의 position을 찾을 필요가 있다. 1D case 처럼, 우리의 2D grid는 미리 정의된 resolution을 갖는다 (grid는 square이고, 그래서 그 resolution은 x와 y축을 따라 같다). 이 설명을 위해서 4라고 가정하자 (2의 제곱). 우리는 만약 그 점이 grid boundaries 밖에 있다면 grid에 있는 P의 위치를 remap 하는 같은 modulo tric을 사용할 것이다 (만약 P의 좌표가 0보다 더 작거나 4보다 더 크다면). 우리는 P의 x와 y좌표에 modulo 연산을 수행할 것이다. 그것은 우리에게 grid에서 점에 대한 새로운 좌표를 줄 것이다 (이 새로운 점은 Pnoise라고 부르자).

너가 그림 2와 3에서 볼 수 있듯이, 그 점은 한 cell의 4개의 정점들에 의해 둘러싸여 있다. 우리는 interpolation 강의에서 설명된 같은 기법을 사용해서, 그 점에 대한 값을 찾을 것인데, 그 값을 cell corners로부터 선형 보간하여 한다. 이것을 하기 위해서, 우리는 처음에 tx와 ty를 연산할 것인데, 이것들은 우리의 1D noise와 대응되는 것인데.

우리는 이제 tx를 사용하여 오른쪽에 있는 두 개의 모서리에 있는 값과 왼쪽에 있는 두 개의 목서리의 값을 보간할 수 있다ㅏ. 그것은 우리에게 두 개의 값 nx0과 nx1을 주는데, 이것은 x축을 따라 c00/c10 (nx0) 과 c01/c11 (nx1)의 x축을 따라 선형 보간과 일치한다. 우리는 이제 우리가 차례로 ty를 사용하여 선형 보간할 Pnoise의 x축에 수직으로 정렬된 cell의 위아래 변에 두 개의 보간된 값을 가지고 있다. y축을 따라서 하는 이 보간의 결과는 우리의 최종 값 P가 된다.

여기에 우리의 간단한 2D value noise 코드가 있다. grid의 사이즈는 각 side에서 256이다. 1D noise 처럼, t에 대한 remapping function을 바꾸는 것은 가능하다. 이 버전에서, 우리는 Smoothstep을 선택했지만, 너는 그 함수를 무시하고 실험할 수 있다 (tx와 ty를 직접 사용해서), 그리고 Cosin smooth function 또는 너가 아는 다른 smooth function을 사용하여.

{
savePNGfile 함수를 만들었다. 이러면 내가 원하는 만큼 이미지 파일을 저장한다.
원래는 pixels을 직접 조정하여 PNG file을 만들었었는데, 그렇게 한다면 screen의 left upper corner가 시작점이 되어서, 거꾸로 계산을 해야하니, 불편했다. 그래서 pmm -> png로 바꾸어 좀 더 간편하게 할 수 있을 것 같다.

다음은 전체 소스코드와 만들어낸 이미지 결과물이다.

#include <iostream>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio> 
#include <random> 
#include <functional> 

#include "imageSave.h"

#include "GPED_random.h"
#define CHANNEL_NUM 3


#define PI 3.14159265358979323846264338327950288
inline unsigned min(const unsigned& a, const unsigned& b) { return (a < b ? a : b); }
template <typename T = float>
inline T lerp(const T& lo, const T& hi, const T& t) { return lo * (1 - t) + hi * t; }
inline float cosineSmooth(const float& t) { return (1 - std::cosf(t * PI)) * 0.5f; }
inline float smoothStep(const float& t)
{
 // basic smoothstep
 // return t * t * (3 - 2 * t);

 // Ken Perlin SmoothStep
 float t3 = std::powf(t, 3);
 return 6 * t3 * t * t - 15.f * t3 * t + 10 * t3;
}

class ValueNoise2D
{
public:
 ValueNoise2D(unsigned seed = 2011)
 {
  std::mt19937 gen(seed);
  std::uniform_real_distribution<float> distrFloat;
  auto randFloat = std::bind(distrFloat, gen);

  for (unsigned i = 0; i < kMaxTableSize * kMaxTableSize; ++i)
   r[i] = randFloat();
 }

 // Evaluate the noise function at position x
 float eval(const glm::vec2& p)
 {
  int xi = std::floor(p.x);
  int yi = std::floor(p.y);

  int rx0 = xi & kMaxTableSizeMask;
  int rx1 = (rx0 + 1) & kMaxTableSizeMask;
  int ry0 = yi & kMaxTableSizeMask;
  int ry1 = (ry0 + 1) & kMaxTableSizeMask;

  // random values at the corners of the cell using permutation table
  const float& c00 = r[ry0 * kMaxTableSize + rx0];
  const float& c10 = r[ry0 * kMaxTableSize + rx1];
  const float& c01 = r[ry1 * kMaxTableSize + rx0];
  const float& c11 = r[ry1 * kMaxTableSize + rx1];

  // remapping of tx and ty using Smoothstep function;
  float tx = p.x - xi;
  float ty = p.y - yi;
  float sx = smoothStep(tx);
  float sy = smoothStep(ty);

  // linearly interpolate values along the x axis
  float nx0 = lerp(c00, c10, sx);
  float nx1 = lerp(c01, c11, sx);

  // linearly interpolate the nx0/nx1 along the y axis
  return lerp(nx0, nx1, sy);
 }

 static const unsigned kMaxTableSize = 256;
 static const unsigned kMaxTableSizeMask = kMaxTableSize - 1;
 float r[kMaxTableSize * kMaxTableSize];
};


int main()
{
 const int width = 512;
 const int height = 512;
 float* noiseMap = new float[width * height];

 // generate value noise
 ValueNoise2D myNoise;
 float frequency = 0.05f;
 for (unsigned j = 0; j < height; ++j)
  for (unsigned i = 0; i < width; ++i)
   //generate a float in the range [0:1]
   noiseMap[j * width + i] = myNoise.eval(glm::vec2(i, j) * frequency);

 savePNGfile(noiseMap, width, height, "firstTry.png");

 delete[] noiseMap;
 return 0;
}

float consineRemap(const float& a, const float& b, const float& t)
{
 assert(t >= 0 && t <= 1);
 float tRemapCosine = (1 - std::cosf(t * glm::pi<float>())) * 0.5f;
 return lerp(a, b, tRemapCosine);
}
float smoothstepRemap(const float& a, const float& b, const float& t)
{
 // float tRemapSmoothstep = t * t * (3 - 2 * t);

 // Ken Perlin ver.
 float t3 = std::powf(t, 3);
 float tRemapSmoothstep = 6 * t3 * t * t - 15.f * t3 * t + 10 * t3;
 return lerp(a, b, tRemapSmoothstep);
}

class ValueNoise1D
{
public:
 ValueNoise1D(unsigned seed = 2011)
 {
  GPED::Random rand(seed);

  for (unsigned i = 0; i < kMaxVertices; ++i)
   r[i] = rand.randomReal();
 }

 // Evaluate the noise function at position x
 float eval(const float& x)
 {
  // Floor
  int xi = (int)x - (x < 0 && x != (int)x);
  float t = x - xi;

  // Modulo using &
  int xMin = xi & kMaxVerticesMask;
  int xMax = (xMin + 1) & kMaxVerticesMask;

  // return lerp(r[xMin], r[xMax], t);
  // return consineRemap(r[xMin], r[xMax], t);
  return smoothstepRemap(r[xMin], r[xMax], t);
 }

 static const unsigned kMaxVertices = 256;
 static const unsigned kMaxVerticesMask = kMaxVertices - 1;
 float r[kMaxVertices];
};

template<class T>
inline void savePNGfile(T* arr, int width, int height, const std::string& fileName)
{
 // pmm(p6) -> jpg convert
 std::ofstream ofs;
 ofs.open("imageTemp/temp.ppm", std::ios::out | std::ios::binary);
 ofs << "P6\n" << width << ' ' << height << "\n255\n";
 for (unsigned i = 0; i < width * height; ++i)
 {
  unsigned char n = static_cast<unsigned char>(arr[i] * 255);
  ofs << n << n << n;
 }
 ofs.close();
 
 int x, y, n;
 unsigned char* data = stbi_load("imageTemp/temp.ppm", &x, &y, &n, 0);

 std::string destination = "imageResult/" + fileName;
 stbi_write_png(destination.c_str(), x, y, n, data, x * n);
}

}

만약 너가 코드를 작동시킨다면, 그거은 다음의 이미지를 만들어낼 것이다 (왼쪽):

그 결과가 아마도 우리가 희맹했던 것 만큼 좋지않다는 것에 주목해라. 그 최종 noise는 꽤 blocky하다. 전문 프로그램에서 나온 Noise는 좀 더 부드러운 결과를 만들어 낸다. 이 수업의 목적은 너에게 noise function이 만들어지는 기본 개념을 가르치는 것이라는 것을 기억해라. 그 결과를 향상시키기 위해, 우리는 좀 더 정교한 기법들을 사용할 필요가 있지만, 만약 너가 간단한 함수를 처음으로 구성할 수 없다면 그것들을 공부하기에 어려울 것이다. 지금은 noise function의 결과에 너무 걱정히자 말아라. 그리고 그것이 어떻게 작동하는지 이해하려 해라. 그리고 그것의 특성들을 배우고 이해해라. 너는 여전히 이 코드를 가지고 놀 수 있고, 우리가 다음 챕터에서 보게 되듯이 몇 가지 흥미로운 효과와 이미지를 만들 수 있다. 너는 다음 less에서 (part 2) 더 좋게 보이는 noise를 만드는 것에 대해 배울 것이다.

3D Noise and Beyond
이 강의에서, 우리는 1D and 2D noise의 예시를 줄 것이다. 우리는 다음 강의에서 noise에서 3D와 4D noise에 대한 코드를 제공할 것이다. 그러나, 만약 너가 interpolation 강의를 읽었고, 이 챕터에서 설명된 개념을 이해했다면, 너는 쉽게 그 코드를 3D noise를 쓰기 위해 확장할 수 있을 것이다. 너가 할 필요가 있는 모든 것은 x축을 따라 random values를 보간하는 것이다 (4개의 값들을 만들어 낸다), 그리고 y축을 따라 이 interpolation의 결과를 보간한다 (2 values). 너는 두 개의 값을 가지게 될 것인데, 최종 결과를 얻기 위해 3번째 차원 (z axis)를 따라 보간할 필요가 있는 값이다 (noise의 두 번째 lesson에서 3D noise에 대한 예제를 포함한다).

이제 우리의 현재 코드에 문제가 있다. 우리는 첫 번째 챕터에서 noise는 많은 메모리를 사용하지 않는 compact function이라고 언급했었다. 그러나 2D case에서 우리는 이미 random values의 256x256 array를 할당했다. 만약 우리가 3D version에 대해 같은 기법을 사용한다면, 우리는 floats의 256x256x256 배열을 할당할 필요가 있다. 그리고 이것은 메모리의 꽤 큰 chunk 가 될 것이다. 이것은 작게 사용하는 함수에 대해 크다. Ken Perlin은 이 문제를 간단하고 우아한 솔루션을 가지고 해결했는데, 우리가 이제 설명할 permutation table의 형태로 풀었다.

Introducing the Concept of Permutation
우리가 noise function이 메모리 효율적이 되도록 원한다고 가정하면, 우리는 우리 스스로 우리의 noise를 계산하기 위해 256 random values의 한 배열을 사용하도록 제한할 것이다. 우리가 1D, 2D or 3D version of the function을 다루든. 이 제한을 다루기 위해서, 우리가 할 필요가 있는 모든 것은 noise function에 대한 어떤 입력 값이 (float, 2D or 3D point) 하나로 map될 수 있게 하고, 오직 이 random values의 array에 있는 한 값에 되도록 보장하는 것이다. 너가 이미 알 듯이, 우리의 noise function에 대한 각 입력 point coordinates가 어떤 정수로 바뀐다. 이 정수는 random values의 array에 대한 look up하기 위해 사용된다. Ken Perlin은 256개의 정수의 부가적인 배열에서 0 ~ 255 숫자를 저장했고, 이 배열의 entries들을 shuffled (permuted) 했고, 무작위로 그것들 중 하나를 swapping 했다. 사실, Perlin은 이 배열의 크기를 512로 확장했고, 0 ~255 범위의 인덱스들을 256 ~ 511 인덱스로 값을 복사했다. 다시 말해서, 그 배열의 처음 절반을 두 번째 절반으로 복사하는 것이다.

std::mt19937 gen(seed);
std::uniform_real_distribution<float> distrFloat;
auto randFloat = std::bind(distrFloat, gen);

// create an array of random values and initialize permutation table
for (unsigned i = 0; i < kMaxTableSize * kMaxTableSize; ++i)
{
 r[i] = randFloat();
 permutationTable[i] = i;
}

// shuffle values of the permutation table
std::uniform_int_distribution<unsigned> distrUInt;
auto randUInt = std::bind(distrUInt, gen);
for (unsigned i = 0; i < kMaxTableSize; ++i)
{
 unsigned k = randUInt() & kMaxTableSizeMask;
 std::swap(permutationTable[i], permutationTable[k]);
 permutationTable[i + kMaxTableSize] = permutationTable[i];
}

random values의 배열을 직접 look up 하는 대신에, 우리는 처음에 우리의 integer position을 사용해서 이 permutation array에 lookup을 할 것이다. 우리가 알듯이, 우리의 입력을 필수적으로 255의 배수이다. 이 숫자가 201이라고 하자. permutation array에서 lookup을 하기 위해 이 값을 사용하는 것은 index position 201에 있는 테이블에 저장된 값을 반환할 것이다. 이 lookup의 결과는 0 ~ 255 사이의 정수이고, 우리는 이제 그것을 random values의 배열에서 인덱스로서 상요할 수 있다.

너는 왜 permutation array가 그 함수 주기의 크기를 두 배 시키는지 궁금해 할지도 모른다 (256 대신에 512 크기). 만약 우리가 2D noise를 다룬다면, 우리는 처음에 우리의 입력 point의 x 좌표에 대해 integer value를 사용하여 permutation table에서 look up을 처음에 할 것이다 (설명된 대로). 이것은 [0:255] 범위의 정수 값을 반환할 것이다. 우리는 input point y coordinate에 대한 정수값에 이 loopup 결과를 더할 것이다. 그리고 이러한 두 수의 합을 permutation table의 인덱스로서 다시 사용할 것이다. 그 첫 번쨰 permutation lookup의 결과는 [0:255]이고, 점 y의 좌표에 대한 정수값 또한 [0:255]이기 때문에, permutation table에 대한 가능한 index value의 범위는 [0:511]이다. 그러므로 permutation array의 사이즈는 512이다. 이 코드가 너에게 상황을 정리하는데 도움이 될 지도 모를 것이다:

int rx0 = xi & kMaxTableSizeMask;
int rx1 = (rx0 + 1) & kMaxTableSizeMask;
int ry0 = yi & kMaxTableSizeMask;
int ry1 = (ry0 + 1) & kMaxTableSizeMask;

// random values at the corners of the cell using permutation table
const float& c00 = r[permutationTable[permutationTable[rx0] + ry0]];
const float& c10 = r[permutationTable[permutationTable[rx1] + ry0]];
const float& c01 = r[permutationTable[permutationTable[rx0] + ry1]];
const float& c11 = r[permutationTable[permutationTable[rx1] + ry1]];

이 기법은 매우 깔끔하다. 왜냐하면 그것은 너가 너의 noise function에 더 많은 차원을 더할 때 계속해서 작동하기 때문이다. 그것은 우리에게 어떤 입력 point를 random value array의 특정 위치로 매핑하는 기법을 제공한다. 우리가 하는 모든 것은 입력 point의 좌표를 permutation table의 인덱스로서 사용하는 것이다. 프로그래밍에서 이 기법을 hash table이라고 부르거나 또는 hash function이라고 부른다. 이러한 기법은 그 당시에 꽤 인기있었다 (끄리고 여전히 그렇지만, 어린 개발자들에게는 잘 알려져 있지 않다). 그것들은 특정한 key를 memory block에 저장된 어떤 데이터로 mapping하는데 유용하고, lookup process를 효율적으로 만든다. (hash functions에 대해 더 배우기 위해서는 programming techniques 레슨을 체크해라).

여기에 마지막으로 permutation table을 사용한 우리의 2D noise function의 최신 메모리 효율 버전이 있다.