삼선형 보간법

[right|섬네일|두 [쌍선형 보간법과 하나의 선형 보간법으로 이루어진 삼선형 보간법.]]

**삼선형 보간법**()은 3차원 정규 격자에서 다변량 보간법의 한 방법이다. 이는 국부 축 방향 직사각형 각기둥 내의 중간 점 (x, y, z)에서의 함수 값을 격자점의 함수 데이터를 사용하여 선형적으로 근사한다. 삼선형 보간법은 수치해석학, 데이터 분석, 컴퓨터 그래픽스에서 자주 사용된다.

## 관련 방법
삼선형 보간법은 차원 D = 1 공간에서 작동하는 선형 보간법과 차원 D = 2에서 작동하는 쌍선형 보간법을 차원 D = 3으로 확장한 것이다. 이 보간 방식들은 모두 1차 다항식을 사용하여 2차 정확도를 제공하며, 보간점 주변에 2^D = 8개의 인접한 미리 정의된 값이 필요하다. 삼선형 보간법은 1차 3차원 텐서 B-스플라인 곡선 보간법과 동등하며, 삼선형 보간 연산자는 3개의 선형 보간 연산자의 텐서 곱이다.

(유한 요소 해석에 사용되는) 임의의 비정형 메쉬의 경우 다른 보간 방법을 사용해야 한다. 만약 모든 메쉬 요소가 사면체 (3D 단체)라면, 바리센트릭 좌표가 간단한 절차를 제공한다.

## 공식
right|섬네일|보간점 C를 둘러싸는 정육면체의 여덟 모서리 점

주기적이고 정육면체 격자에서 x_\text{d}, y_\text{d}, z_\text{d}는
각 x, y, z와 관련된 작은 좌표 사이의 차이, 즉:

:\begin{align}
  x_\text{d} = \frac{x - x_0}{x_1 - x_0} \\
  y_\text{d} = \frac{y - y_0}{y_1 - y_0} \\
  z_\text{d} = \frac{z - z_0}{z_1 - z_0}
\end{align}

여기서  x_0 는  x  아래의 격자점을 나타내고,  x_1 은  x  위의 격자점을 나타내며,
y_0, y_1, z_0 및 z_1에 대해서도 마찬가지이다.

먼저 x를 따라 보간하면(C_{0jk}로 정의된 큐브의 면을 반대편 면인 C_{1jk}로 "밀어내는" 것을 상상해 보라), 다음을 얻는다:
: \begin{align}
  c_{00} &= c_{000} (1 - x_\text{d}) + c_{100} x_\text{d} \\
  c_{01} &= c_{001} (1 - x_\text{d}) + c_{101} x_\text{d} \\
  c_{10} &= c_{010} (1 - x_\text{d}) + c_{110} x_\text{d} \\
  c_{11} &= c_{011} (1 - x_\text{d}) + c_{111} x_\text{d}
\end{align}

여기서 c_{000}은 (x_0, y_0, z_0)의 함수 값을 의미한다. 그런 다음 이 값들을 (y를 따라, C_{i0k}에서 C_{i1k}로 "밀어내는" 방식으로) 보간하면 다음을 얻는다:
: \begin{align}
  c_0 &= c_{00}(1 - y_\text{d}) + c_{10}y_\text{d} \\
  c_1 &= c_{01}(1 - y_\text{d}) + c_{11}y_\text{d}
\end{align}

마지막으로 이 값들을 z를 따라(선을 따라 이동하면서) 보간한다:
:c = c_0(1 - z_\text{d}) + c_1z_\text{d} .
이것은 해당 지점에 대한 예측 값을 제공한다.

삼선형 보간의 결과는 세 축을 따라 보간하는 순서에 독립적이다. 즉, x, 다음 y, 마지막으로 z와 같은 다른 순서로 해도 같은 값이 나온다.

### 알고리즘 시각화
섬네일|삼선형 보간의 기하학적 시각화. 원하는 지점의 값과 전체 부피의 곱은 각 모서리 지점의 값과 모서리 대각선 반대편의 부분 부피의 곱의 합과 같다.

위의 연산은 다음과 같이 시각화할 수 있다. 먼저 관심 지점을 둘러싸는 정육면체의 여덟 모서리를 찾는다. 이 모서리들은 c_{000}, c_{100}, c_{010}, c_{110}, c_{001}, c_{101}, c_{011}, c_{111} 값을 가진다.

다음으로, c_{000}과 c_{100} 사이를 선형 보간하여 c_{00}을 찾고, c_{001}과 c_{101} 사이를 보간하여 c_{01}을 찾고, c_{011}과 c_{111} 사이를 보간하여 c_{11}을 찾고, c_{010}과 c_{110} 사이를 보간하여 c_{10}을 찾는다.

이제 c_{00}과 c_{10} 사이를 보간하여 c_{0}를 찾고, c_{01}과 c_{11} 사이를 보간하여 c_{1}을 찾는다. 마지막으로 c_{0}와 c_{1}의 선형 보간을 통해 c 값을 계산한다.

실제로 삼선형 보간은 두 개의 쌍선형 보간법과 하나의 선형 보간법을 결합한 것과 동일하다:
:c \approx l\left( b(c_{000}, c_{010}, c_{100}, c_{110}),\, b(c_{001}, c_{011}, c_{101}, c_{111})\right)

### 대체 알고리즘
보간 문제의 해를 작성하는 또 다른 방법은 다음과 같다.
:f(x, y, z) \approx a_0 + a_1 x + a_2 y + a_3 z + a_4 x y + a_5 x z + a_6 y z + a_7 x y z

여기서 계수들은 선형 시스템을 풀어 찾는다.
:\begin{align}
  \begin{bmatrix}
    1 & x_0 & y_0 & z_0 & x_0 y_0 & x_0 z_0 & y_0 z_0 & x_0 y_0 z_0 \\
    1 & x_1 & y_0 & z_0 & x_1 y_0 & x_1 z_0 & y_0 z_0 & x_1 y_0 z_0 \\
    1 & x_0 & y_1 & z_0 & x_0 y_1 & x_0 z_0 & y_1 z_0 & x_0 y_1 z_0 \\
    1 & x_1 & y_1 & z_0 & x_1 y_1 & x_1 z_0 & y_1 z_0 & x_1 y_1 z_0 \\
    1 & x_0 & y_0 & z_1 & x_0 y_0 & x_0 z_1 & y_0 z_1 & x_0 y_0 z_1 \\
    1 & x_1 & y_0 & z_1 & x_1 y_0 & x_1 z_1 & y_0 z_1 & x_1 y_0 z_1 \\
    1 & x_0 & y_1 & z_1 & x_0 y_1 & x_0 z_1 & y_1 z_1 & x_0 y_1 z_1 \\
    1 & x_1 & y_1 & z_1 & x_1 y_1 & x_1 z_1 & y_1 z_1 & x_1 y_1 z_1
  \end{bmatrix}\begin{bmatrix}
    a_0 \\ a_1 \\ a_2 \\ a_3 \\ a_4 \\ a_5 \\ a_6 \\ a_7
  \end{bmatrix} = \begin{bmatrix}
    c_{000} \\ c_{100} \\ c_{010} \\ c_{110} \\ c_{001} \\ c_{101} \\ c_{011} \\ c_{111}
  \end{bmatrix},
\end{align}

결과로 다음이 도출된다.

:\begin{align}
  a_0 ={}
    &\frac{-c_{000} x_1 y_1 z_1 + c_{001} x_1 y_1 z_0 + c_{010} x_1 y_0 z_1 - c_{011} x_1 y_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)} +{} \\
    &\frac{ c_{100} x_0 y_1 z_1 - c_{101} x_0 y_1 z_0 - c_{110} x_0 y_0 z_1 + c_{111} x_0 y_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]
  a_1 ={}
    &\frac{ c_{000} y_1 z_1 - c_{001} y_1 z_0 - c_{010} y_0 z_1 + c_{011} y_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)} +{} \\
    &\frac{-c_{100} y_1 z_1 + c_{101} y_1 z_0 + c_{110} y_0 z_1 - c_{111} y_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]
  a_2 ={}
    &\frac{ c_{000} x_1 z_1 - c_{001} x_1 z_0 - c_{010} x_1 z_1 + c_{011} x_1 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)} +{} \\
    &\frac{-c_{100} x_0 z_1 + c_{101} x_0 z_0 + c_{110} x_0 z_1 - c_{111} x_0 z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]
  a_3 ={}
    &\frac{ c_{000} x_1 y_1 - c_{001} x_1 y_1 - c_{010} x_1 y_0 + c_{011} x_1 y_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)} +{} \\
    &\frac{-c_{100} x_0 y_1 + c_{101} x_0 y_1 + c_{110} x_0 y_0 - c_{111} x_0 y_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]
  a_4 ={}
    &\frac{-c_{000} z_1 + c_{001} z_0 + c_{010} z_1 - c_{011} z_0 + c_{100} z_1 - c_{101} z_0 - c_{110} z_1 + c_{111} z_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]
  a_5 =
    &\frac{-c_{000} y_1 + c_{001} y_1 + c_{010} y_0 - c_{011} y_0 + c_{100} y_1 - c_{101} y_1 - c_{110} y_0 + c_{111} y_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]
  a_6 ={}
    &\frac{-c_{000} x_1 + c_{001} x_1 + c_{010} x_1 - c_{011} x_1 + c_{100} x_0 - c_{101} x_0 - c_{110} x_0 + c_{111} x_0}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}, \\[4pt]
  a_7 ={}
    &\frac{ c_{000} - c_{001} - c_{010} + c_{011} - c_{100} + c_{101} + c_{110} - c_{111}}{(x_0 - x_1) (y_0 - y_1) (z_0 - z_1)}.
\end{align}

## 같이 보기
* 선형 보간법
* 쌍선형 보간법
* 삼차 보간
* 방사 보간
* 사면체 보간
* 구형 선형 보간

## 외부 링크
* NASA의 의사 코드, 반복적인 역 삼선형 보간법(꼭짓점과 C 값을 주어졌을 때 Xd, Yd, Zd를 찾음)을 설명한다.
*폴 버크, 보간 방법, 1999년. 이진 논리에 기반하며 어떤 차원으로도 확장될 수 있는(사선형, 오선형, ...) 매우 영리하고 간단한 삼선형 보간법을 찾는 방법을 포함한다.
*켄라이트, 자유형 사면체 변형. 국제 시각 컴퓨팅 심포지엄. Springer International Publishing, 2015 https://link.springer.com/chapter/10.1007/978-3-319-27863-6_74.

분류:유클리드 공간기하학