[알고리즘] Perlin Noise

들어가기

펄린 노이즈는 Ken Perlin에 의해 1983년에 개발되었다. 이로인해 아카데미에서 Techinical Archivement Award 부분에서 상을 받았다.
일반적인 노이즈는 단순 랜덤에 의해 불규칙적인 값을 생성한다고 보면, 펄린 노이즈는 랜덤한 값이지만 서로 유기적인 값을 생성한다고 보면 된다. 이를 통해 컴퓨터 그래픽 분야에서 유기물이나 사물 텍스처 그리고 동적 시물레이션에 적용하여 자연스런 결과를 얻을 수 있다.
펄린 노이즈에 대한 자세한 내용을 살펴보자.

작성자: ospace114@empal.com, http://ospace.tistory.com/

3 단계

펄린 노이즈는 크게 3단계 과정으로 구분할 수 있다.

1. 그리드 정의
2. 내적
3. 보간

그리드 정의는 전체 영역을 일정 개수로 구분하여 각 그리드별로 랜덤 그리드 벡터를 정의한다.
내적은 각 그리드 영역에서 점들에 대한 오프셋 벡터와 랜덤 그리드 벡터와의 내적을 통해서 영향력을 계산한다.
보간에서 계산된 영항력을 x, y축에 대해 보간하여 부드러운 펄린 노이즈 값을 계산한다.

그리드 정의

전체 영역에 대해 그리드를 n차원으로 일정 개수를 영역을 구분한다. 그리고 그리드 모서리에서 랜덤한 단위 그라디언트 벡터를 생성한다. 단위벡터를 사용함으로써 랜덤한 방향성만 가지게 된다.

출처: wikipedia의 Perlin_noise[1]

어떠한 입력값이든 n차원 그리드 범위내에서 정의되며 하나의 그리드 영역에 위치하도록 한다.
예를 실수인 경우를 보면 정수부는 그리드 영역 선택, 소수부는 그리드 영역 내에서 점의 위치를 선택할때 사용한다.

각 그리드 모서리에 단위 그라디언트 벡터를 생성해야 한다. 이 벡터는 초기 그리드 영역을 생성할 때에 같이 생성되며 랜덤하게 선택된다.
단위 벡터이므로 2차원 인 경우 x축, y축에 대한 방향성을 가지고 가장 단순하게 4가지 경우의 단위 그라디언트 벡터를 생성할 수 있다.

이제 점이 있는 그리드 영역과 해당 영역의 단위 그라디언트 벡터를 얻을 수 있다. 이를 가지고 내적을 해보자.

내적

내적을 통해서 그리드 영역의 점과 각 모서리에 있는 단위 그라디언트 벡터를 가지고 계산하여 각 모서리에 대한 영향력을 계산할 수 있다.
내적을 하기 전에 점과 각 모서리 간에 오프셋 벡터를 구해야 한다. 오프셋 벡터를 구하는 방법은 간단하다. 각 두개의 점이 있으면, 서로 빼주면 된다.

예) 점 (x, y)와 첫번째 모서리(x0, y0) 인경우 (x,y) - (x0, y0) 이므로 (x-x0, y-y0) 가 된다.

이제 오프셋 벡터와 단위 그라디언트 벡터를 가지고 내적을 구한다. 만약 2차원 인 경우는 총 네개의 내적을 구하게 된다.

예) i0 = g(x0, y0) * (x-x0, y-y0)

내적 연산자는 가운데 점으로 표시하지만 편의상 *으로 표시했다.

이제 그리드 각 모서리의 영향도를 얻을 수 있다. 이를 가지고 보간만 하면 된다.

보간

각 모서리의 영향도를 가지고, 점위치에 노이즈 값을 계산한다. 그리드 경계에서 부드럽게 보간하면 더 자연스러운 노이즈가 생성된다.
먼저 x 축에 대해 보간하고 y축에 대해 보간하면 원하는 노이즈 값을 얻게된다.
예를 들어 먼저 x 축에 대해 첫번째 모서리와 두번째 모서리의 영향도인 i0, i1에 대해서 보간한다고 하면,

f(x) = i0 + smoothstep(x) * (i1 - i0) for 0 <= x <= 1 [1]

x 값은 입력 x좌표에서 소수부에 해당한다고 보면된다. 물론 값 매핑에 의해서 계산된 값을 사용할 수도 있다. smoothstep()은 부드러운 보간에 사용되는 함수이다.[3]
smoothstep()에 나온 결과로 i0와 i1 사이에 선형 보간을 한다.
2차원 인 경우는 상단과 하단의 x 축에 대한 보간을 하고, 보간된 상단, 하단 값으로 y 축에 대한 보간을 진행한 결과가 노이즈 값이 된다.

구현

2차원에 대한 펄린 노이즈 계산을 자바스크립트로 간단하게 구현해보았다. 개인적으로 구현한 부분이라 틀린 부분도 있을 수 있으니 참고만 하시기 바랍니다.

const GRID_SIZE = 256;
const sampleGridients = [[1,0],[0,1],[-1,0],[0,-1]];
const grid = new Array(GRID_SIZE * GRID_SIZE);

for(let i=0; i < grid.length; ++i) {
    grid[i] = sampleGridients[random(sampleGridients.length)];
}

function noise(x, y) {
    let ix = Math.floor(x);
    let fx = x - ix;
    ix %= GRID_SIZE;
    let iy = Math.floor(y);
    let fy = y - iy;
    iy %= GRID_SIZE;

    const gridents = [grid[ix+iy*GRID_SIZE], grid[ix+1+iy*GRID_SIZE],
        grid[ix+(iy+1)*GRID_SIZE], grid[ix+1+(iy+1)*GRID_SIZE]];
    const offsets = [[fx, fy], [fx-1, fy], [fx, fy-1], [fx-1, fy-1]];
    const influences = gridents.map((it,idx)=>dot(it, offsets[idx]));

    fx = smoothstep(fx);
    const x0 = lerp(influences[0], influences[1], fx);
    const x1 = lerp(influences[2], influences[3], fx);
    fy = smoothstep(fy);
    return lerp(x0, x1, fy);
}

function dot(l, r) {
    return l[0] * r[0] + l[1] * r[1];
}

function lerp(l, r, f) {
    return l + f * (r - l);
}

function smoothstep(t) {
    return t * t * t * (t * (t * 6 - 15) + 10);
}

function random(max) {
    return Math.floor(Math.random() * max);
}

참고

[1] Perlin noise, https://en.wikipedia.org/wiki/Perlin_noise, 2022/01/24
[2] HHot, Perlin Noise, https://m.blog.naver.com/dj3630/221512874599, 2022/01/24
[3] Smoothstep, https://en.wikipedia.org/wiki/Smoothstep, 2022/01/24
[4] Fataho, Perlin Noise Explained Tutorial 2, https://www.youtube.com/watch?v=MJ3bvCkHJtE

관련자료

• https://www.arendpeter.com/Perlin_Noise.html
• https://www.youtube.com/watch?v=WLFOgCV4vHc
• https://www.youtube.com/watch?v=wbpMiKiSKm8

결론

간단하게 펄린 노이즈를 살펴보았다. 이외에도 다양한 노이즈 함수가 존재한다.

출처: https://docs.aws.amazon.com/ko_kr/lumberyard/latest/userguide/component-gradients-fastnoise.html

그리고, 연산 방식을 조금씩 변경하여 다른 형태의 노이즈도 생성가능하다. 위의 구현은 2차원이지만 3차원, 4차원으로 확장가능하다. 저도 이제야 시작하는 단계라서 얼마나 활용가능한지는 모르겠지만, 재미있는 건 확실하다.ospace.