간단한 3차 보간법

Abstract

입력된 4개의 정점을 지나는 3차곡선을 계산하는 방법이다.

Input

4개의 정점 (x1, y1), (x2, y2), (x3, y3), (x4, y4)

Output

3차 곡선을 f(x) = ax^3 + bx^2 + cx + d 라고 할 때 입력으로부터 a, b, c, d의 계수를 계산한다.

Calculation

f(x)의 방정식이 ax^3 + bx^2 + cx + d이므로 4개의 입력을 각각 공식에 대입한다.

y1 = a*(x1)^3 + b*(x1)^2 + c*(x1) + d 

y2 = a*(x2)^3 + b*(x2)^2 + c*(x2) + d 

y3 = a*(x3)^3 + b*(x3)^2 + c*(x3) + d 

y4 = a*(x4)^3 + b*(x4)^2 + c*(x4) + d 

이를 4차원 벡터와 행렬로 표현하면 

Y = C * M

- Y = (y1, y2, y3, y4) as Vector

- C = (a, b, c, d) as Vector

- M의 1행 (x1^3, x1^2, x1, 1) as 4x4 Matrix

- M의 2행 (x2^3, x2^2, x2, 1)

- M의 3행 (x3^3, x3^2, x3, 1)

- M의 4행 (x4^3, x4^2, x4, 1)

구하고자 하는 것은 Coefficient인 C이므로 양변에 M의 역행렬 InvM을 곱한다.

Y = C * M

Y * InvM = C * (M * InvM) = C * Identity = C

단 이 때 곡선이 연속적이지 않거나 행렬 M의 determinant값이 0이면 InvM을 구할 수 없으므로 해는 존재하지 않는다. 

이 밖에도 Cubic Spline이나 Bezier Curve 등을 이용하여 곡선을 얻어낼 수 있지만 Cubic Spline의 경우 구간에 따른 공식이 다르거나 복잡하며, Bezier Curve는 일반적으로 x와 y에 대한 식이 아닌 t에 관한 식으로 공식이 정리된다. 또 Bezier Curve의 경우 원하는 정점을 지나게 하기 어려운 단점이 있다. 

현재 기술한 방식은 지나는 정점을 많게 하여 곡률을 여러번 변경시키면 계산량이 많아진다는 단점이 있지만, 3차원 곡선을 보간할 경우 일반적으로 Graphics에서 사용하는 4x4 행렬과 4차원 벡터를 사용하여 손쉽게 계산이 가능하고 4개의 정점을 모두 지나는 곡선이 생성된다.