다양한 보간 방법 알아보기

September 21, 2024 0

이 글은 flat, linear, cubic을 포함한 보간(interpolation) 방법을 예제와 함께 설명한다. 이 보간 방법들은 정점 사이의 값을 계산하는 것을 목표로 하며, 고급 보간 방법은 부드러운 값의 기울기를 만드는 것을 목표로 한다. 특히 노이즈 함수¹를 생성할 때 셀 경계를 부드럽게 만드는 것이 중요하다.

Flat

Flat 보간법은 값들 사이를 채우는 가장 간단한 방법이다. 이 방법에서 두 점 사이의 값은 다음 데이터 점에 도달할 때까지 일정하게 유지된다. 예를 들어 GLSL에서 flat 보간을 사용하는 노이즈 함수는 다음과 같이 작성할 수 있다.

float random (in vec2 x) {
  return fract(sin(dot(x, vec2(12.9898,54.233))) * 43758.5453123);
}

float noiseFlat (in vec2 x) {
  return random(floor(x));
}

void main() {
  vec2 st = v_position * 6.;
  float value = noiseFlat(st);
  gl_FragColor = vec4(vec3(value), 1.);
}

그러나 이 방법은 연속한 점들이 같은 값을 갖지 않는 한 데이터 점에서 불연속한 변화가 발생한다.

Linear

flat 보간과 달리, 선형(linear) 보간은 연속성을 제공한다. 한 점이 주어지면, 그 점으로부터 정점까지의 거리가 그 점에 대한 기여도를 결정한다. 정점까지의 거리가 짧을수록 기여도가 커지며, 정규화된 기여도 t가 보간 값을 계산하는 데 사용된다. t=0일 때 보간 함수는 x를, t=1일 때 y를 출력한다. 이 성질은 모든 보간 방법에서 동일하다. Linear 보간법은 아래와 같이 구현된다.

float interp(float x, float y, float t) {
    return (1.0-t)*x + t*y;
}

GLSL에서 선형 보간을 사용하는 노이즈 함수는 다음과 같이 작성할 수 있다.

float noiseLinear (in vec2 x) {
  vec2 i = floor(x);
  vec2 f = fract(x);

  float tl = random(i); // top-left corner
  float tr = random(i + vec2(1.0, 0.0)); // top-right corner
  float bl = random(i + vec2(0.0, 1.0)); // bottom-left corner
  float br = random(i + vec2(1.0, 1.0)); // bottom-right corner

  return mix(mix(tl, tr, f.x), mix(bl, br, f.x), f.y);
}

아래 그림은 1차원 축에서 주어진 여러 점에 대한 flat, linear, cubic 보간 결과를 보여준다. cubic 보간은 다음 절에서 논의한다.

위 그림에서 보듯이, flat 보간 방법은 데이터 점에서 불연속을 보인다. linear 보간은 연속적인 값을 출력하지만, 데이터 점에서 그 기울기가 불연속이다. 반면 cubic 보간은 함수 자체와 그 도함수 모두 연속적이다. 이와 같이 cubic 보간 방법은 보간 함수를 부드럽게 만드는 것을 목표로 한다.

Cubic

다항식의 차수가 증가하면 곡선의 형태를 유연하게 조정할 수 있다. 위의 선형 보간의 경우, 주어진 두 점에서 두 개의 식을 만족할 수 있다.

\[\begin{align} f(0) = x, \nonumber\\ f(1) = y, \end{align}\]

여기서

\[f(t) = a_1 t + a_0.\]

이다. 선형 방정식의 두 파라미터로는 기울기를 조작하기에 충분하지 않다. 선형 보간과 달리, cubic 보간은 더 많은 조건을 만족할 수 있다. 삼차 방정식은 네 개의 파라미터를 가지므로 양 끝점의 기울기를 조정할 수 있다.

삼차 방정식을 다음과 같이 두자.

\[f(t) = a_3 t^3 + a_2 t^2 + a_1 t + a_0.\]

그러면 두 점에서 삼차 방정식의 값과 그 도함수는 아래와 같다.

\[\begin{align} f(0) &= a_0, \nonumber\\ f(1) &= a_3 + a_2 + a_1 + a_0, \nonumber\\ f'(0) &= a_1, \nonumber\\ f'(1) &= 3 a_3 + 2 a_2 + a_1. \nonumber \end{align}\]

두 점을 지나면서 그 점에서 곡선을 부드럽게 하기 위해 기울기를 0으로 두자. 그러면

\[\begin{align} a_0 &= x, \nonumber \\ a_3 + a_2 + a_1 + a_0 &= y \nonumber \\ a_1 &= 0, \nonumber \\ 3 a_3 + 2 a_2 + a_1 &= 0 \end{align}\]

이 만족된다. 따라서 다음을 얻을 수 있다.

\[\begin{align} a_0 &= x,\nonumber \\ a_1 &= 0,\nonumber \\ a_2 &= 3 (y - x),\nonumber \\ a_3 &= -2 (y - x), \end{align}\]

그리고

\[\begin{align} z &= -2 \cdot (y-x) \cdot t^3 + 3 \cdot (y-x) \cdot t^2 + x \nonumber \\ &= (-2 t^3 + 3 t^2) \cdot y + (1 - (-2 t^3 + 3 t^2)) \cdot x \nonumber \\ &= g(t) \cdot y + (1 - g(t)) \cdot x, \end{align}\]

여기서

\[g(t) = -2 t^3 + 3 t^2.\]

이다. stepping 함수 \(g(t)\)를 사용하면, 위 보간 방법은 선형 보간의 형태로 표현할 수 있다.

한편, 각 정점의 기울기를 양쪽 두 점 사이의 평균 기울기로 선택하면,

\[\begin{align} f(n) &= a_0 = x_n, \nonumber \\ f(n+1) &= a_3 + a_2 + a_1 + a_0 = x_{n+1} \nonumber \\ f'(n) &= a_1 = 0.5 \cdot (x_{n+1} - x_{n-1}), \nonumber \\ f'(n+1) &= 3 a_3 + 2 a_2 + a_1 = 0.5 \cdot (x_{n+2} - x_{n}). \end{align}\]

이 만족되어야 한다. 그러면 다음을 얻을 수 있다.

\[\begin{align} a_0 &= x_n, \nonumber \\ a_1 &= 0.5 x_{n+1} - 0.5 x_{n-1}, \nonumber \\ a_2 &= -0.5 x_{n+2} + 2 x_{n+1} - 2.5 x_n + x_{n-1}, \nonumber \\ a_3 &= 0.5 x_{n+2} - 1.5 x_{n+1} + 1.5 x_n - 0.5 x_{n-1}. \nonumber \\ \end{align}\]

앞서 기울기가 0인 cubic 보간과 달리, 위 cubic 보간 방정식은 선형 보간 형태로 인수분해할 수 없다는 점에 유의한다. 여러 무작위 점에 대해 위 보간 방법들의 예시를 보이면, 각 보간 방법의 도함수는 다음과 같다.

cubic 보간 방법의 함수가 모든 곳에서 미분 가능하므로, 1차 도함수에서 연속임을 볼 수 있다.

2차원 공간에서 cubic 보간을 구현하려면 Bicubic interpolation 페이지를 참고할 수 있다. 그러나 계산량이 많기 때문에, x축과 y축을 따라 독립적으로 보간 값을 계산하는 근사 방법을 사용했다.

float curve (in float x0, in float x1, in float x2, in float x3, in float t) {
  float a_0 = x1;
  float a_1 = 0.5 * x2 - 0.5 * x0;
  float a_2 = -0.5 * x3 + 2.0 * x2 - 2.5 * x1 + x0;
  float a_3 = 0.5 * x3 - 1.5 * x2 + 1.5 * x1 - 0.5 * x0;
  return a_3 * t * t * t + a_2 * t * t + a_1 * t + a_0;
}

float noiseCurve (in vec2 x) {
  vec2 i = floor(x);
  vec2 f = fract(x);

  // v_00, v_10, v_20, v_30
  // v_01, v_11, v_21, v_31
  // v_02, v_12, v_22, v_32
  // v_03, v_13, v_23, v_33

  float v_00 = random(i + vec2(-1.0, -1.0));
  float v_01 = random(i + vec2(-1.0, 0.0));
  float v_02 = random(i + vec2(-1.0, 1.0));
  float v_03 = random(i + vec2(-1.0, 2.0));

  float v_10 = random(i + vec2(0.0, -1.0));
  float v_11 = random(i + vec2(0.0, 0.0));
  float v_12 = random(i + vec2(0.0, 1.0));
  float v_13 = random(i + vec2(0.0, 2.0));

  float v_20 = random(i + vec2(1.0, -1.0));
  float v_21 = random(i + vec2(1.0, 0.0));
  float v_22 = random(i + vec2(1.0, 1.0));
  float v_23 = random(i + vec2(1.0, 2.0));

  float v_30 = random(i + vec2(2.0, -1.0));
  float v_31 = random(i + vec2(2.0, 0.0));
  float v_32 = random(i + vec2(2.0, 1.0));
  float v_33 = random(i + vec2(2.0, 2.0));

  float v_0x = curve(v_00, v_01, v_02, v_03, f.y);
  float v_1x = curve(v_10, v_11, v_12, v_13, f.y);
  float v_2x = curve(v_20, v_21, v_22, v_23, f.y);
  float v_3x = curve(v_30, v_31, v_32, v_33, f.y);

  return curve(v_0x, v_1x, v_2x, v_3x, f.x);
}