[알고리즘] 보간 (interpolation)

선형 보간 ( Linear Interpolation ) ( Lerp )

선형 보간은 1차원 직선상에서 두개의 위치의 값이 주어졌을때 그사이에 있는 값을 찾기 위한 비례식 입니다.

위의 예시를 참고로 합니다.

a(2,1), b(7,4) 두개의 위치를 알고있을때 c의 위치를 구하기위해서는 선형 보간법을 사용할 수 있습니다.

이때 c의 정확한 위치를 알수는 없으나 좌표상에서 어느정도의 비율에 위치하였는지는 유추가 가능합니다.

위의 공식은 C++ 내부의 구현해둔 함수로 사용이 가능합니다.

Util.h 에 있는 Lerp 템플릿 함수

위의 사진의 원본출처에서 좀더 상세한 구현도 볼 수 있습니다.

[Algorithm] 선형 보간법 (Linear interpolation)

---

---

쌍선형 보간 ( Bilinear Interpolation ) 

쌍선형 보간법은 1차원 선상의 선형 보간법을 기본으로 합니다.

점 A, B, C, D 사이의 쌍선형 보간 B를 구하는 과정은 다음과 같습니다.

점 A 와 B 사이의 선형보간인 m 을 구합니다.

다음으로 점 D 와 C 사이의 선형보간인 n 을 구합니다.

마지막으로 보간 m 과 n 사이의 선형보간 R을 구합니다. 

 

보간의 위치를 바꾸어

점 A 와 D 사이의 보간 p를 구하고

점 B 와 C 사이의 보간 q를 구하고

마지막으로 보간 p 와 q 사이의 선형보간 R을 구할 수 있습니다.

---

---

삼차 보간 ( Cubic Interpolation )

삼차 보간법은 3차 함수를 활용 합니다.

두점 a, b가 삼차함수 그래프 위에 있다고 가정하며 계산 합니다.

위의 예시처럼 되었을때

3차함수인 f(x) = mx3 + nx2 + jx + k 를 사용해야하는데 이때 m, n, j, k 를 찾아내야 합니다.

따라서 조금더 쉽게 계산하기 위해서 아래처럼 가정하여 계산 합니다.

자세한 계산방법은 이미지의 출처인 원본 블로그를참고하도록 합니다.

선형보간법(linear interpolation)과 삼차보간법(cubic interpolation), 제대로 이해하자

---

---

구면 선형 보간 ( Spherically Interpolation / Slerp)

구면 선형 보간은 선형 보간처럼 두 지점 사이의 위치를 파악하는 것입니다.

다만 이름에서 유추 할 수 있듯이 구면인 곡선으로 파악하기위한 보간법 입니다.

시작지점 a, 도착지점 b 가 주어졌을때 직선이아닌 하나의 구체평면 위에 위치한 것으로 가정하여 호의 거리를 선형적으로 보간해서 위치를 얻어 내는 것 입니다.

 

위에서 보듯이 직선거리를 3등분하였을때 시작지점에서 각지적을 직선으로 연결하였을경우 호(원의길이)가 서로 다른 것을 볼 수 있습니다. 이때 두점사이의 각을 일정하게 보간하기위해서 구면 선형 보간을 사용 합니다.

 

0 <= t <= 1 인 단위원(반지름 1)에서 두 점 사이 보간 결과를 r 이라고 하면

입니다. 이때 n을 먼저 구하면

 

이 되며 반지름이 1이기 때문에

 이므로

이고 m도 같은 방식으로 구하면 (m에서 벡터P1에 수선을 내려 똑같이 하면됩니다.)

 

이고 대입하면

의 결과를 얻을 수 있습니다.

---

 

---

베지어 곡선 ( Bezier Curve )

베지어 곡선은 매개곡선(parametric curve)입니다.

베지어곡선은 1차, 2차, 3차, 4차로 나뉘어 집니다.

1차 베지어 곡선 ( Linear )

B(t) = (1−t)P0+tP1,     t∈[0,1]

점 P0과 P1이 주어졌을 때, 단지 두 점 사이의 직선일 뿐이다. [출처] 베지어 곡선 (Bezier Curve)|작성자 네네

2차 베지어 곡선 ( Quadratic )

 

B(t) = (1 − t)2P0 + 2t(1 - t)P1 + t2P2,    t∈[0,1]

함수 B(t)와 점 P0, P1, P2를 이용하는 경로(path). 중간점 Q0은 P0에서 P1까지, Q1은 P1에서 P2까지 변하면서 1차 베지어 곡선을, 점 B(t)는 Q0에서 Q1까지 변하면서 2차 베지어 곡선을 그린다. 트루타입 글꼴은 2차 베지어 곡선으로 이루어진 베지어 스플라인을 사용한다. [출처] 베지어 곡선 (Bezier Curve)|작성자 네네

3차 베지어 곡선 ( Cubic )

 

B(t) = P0(1 − t)3 + 3P1t(1 - t)2 + 3P2t2(1 - t) + P3t3,    t∈[0,1]

평면 또는 3차원 공간에서 4개의 점 P0, P1, P2, P3으로 정의되며, 방향은 P0 -> P1 -> P2 -> P3이다. 보통 P1이나 P2는 방향 정보만을 위해 존재한다. P0과 P1 사이의 거리는 P3으로 돌아서기 전, P2와 곡선 간의 거리를 결정한다. 3차 베지어 곡선은 1차 베지어 곡선을 그리는 중간점 Q0, Q1, Q2 및 2차 베지어 곡선을 그리는 점 R0, R1로 이루어진다. PostScript, Asymptote, Metafont, GIMP (GNU Image Manipulation Program) 같은 이미징 시스템은 구부러진 모양을 그릴 때 3차 베지어 곡선으로 이루어진 베지어 스플라인을 사용한다. [출처] 베지어 곡선 (Bezier Curve)|작성자 네네

4차 베지어 곡선

4차 베지어 곡선은 1차 베지어 곡선을 그리는 중간점 Q0, Q1, Q2, Q3 및 2차 베지어 곡선을 그리는 R0, R1, R2, 그리고 3차 베지어 곡선을 그리는 S0, S1로 이루어진다.

[출처] 베지어 곡선 (Bezier Curve)|작성자 네네

---

---

현재 C++, DX를 공부하면서 Util에 보간 함수 3가지가 있습니다.

1. Lerp
2. Quadratic 
3. Cubic

우선은 단순하게 점갯수에따라 보간에 사용하는 함수가 다르다고 파악하고있으나

차차 점도 공부해야 할 듯 합니다.