Catmull–Rom Spline補間

Catmull–Rom Spline補間は、曲線で補間ができるアルゴリズムで、実装が容易に行える。

条件

補間のためには合計4点が必要となり、内側の2点で補間が行われる。( 0 ≦ t ≦ 1 )
すなわち以下のような状況になる。

ここで用意する4点の座標をtの関数と見て、
f(-1)・f(0)・f(1)・f(2)としている。

まとめると、
入力 : t , 4点の座標
出力 : 補間された座標
となる。

導出

補間のための式を以下の形式で近似して表現したいと考える。

$$f(t) = a_1t^3 + a_2t^2 + a_3t + a_4 ・・・★$$

このa1・a2・a3・a4を求めることができれば、tで補間を行うことができる。
また、f(-1)・f(0)・f(1)・f(2)は入力の座標として既に得られている。

ここでtに0を代入すると

$$f(0) = a_4$$

となり、a4が決定する。
さらに、fをtについて微分してみると

$$f'(t) = 3a_1t^2 + 2a_2t + a_3$$

すると

$$f'(0) = a_3$$

となるが、f'(0)がどのような値かは分からない。
そこで近似して考えてみる。
f'(0)はf(0)付近での接線の傾きであることを考えて近似してみると

$$f'(0) = a_3 ≒ \frac{f(1)-f(-1)}{2}$$

となり、a3が決定する。

ここでf(1)とf'(1)を計算し、それらの連立方程式を解くことを考えてみる(a1,a2のみが未知数)

$$f(1) = a_1 + a_2 + a_3 + a_4 ・・・①\\ f'(1) = 3a_1 + 2a_2 + a_3 ・・・②$$

これは未知数はa2・a3・f'(1)の3つで式が2本なので解くことはできないが、
先程の近似のようにf'(1)も近似してみると、

$$f'(1) ≒ \frac{f(2)-f(0)}{2}$$

となり、未知数2、式2本で解けるようになる。

② - ① × 2より、

$$f'(1) - 2f(1) = a_1 - a_3 - 2a_4 \\ ⇔\\ a_1 = f'(1) - 2f(1) + a_3 + 2a_4 \\ ⇔\\ a_1 = \frac{f(2)-f(0)}{2} - 2f(1) + a_3 + 2a_4$$

となり、a1が決定する。
最後にa2を解いていく。

$$a_2 = f(1) - a_1 - a_3 - a_4 \\ ⇔\\ a_2 = f(1) - f'(1) + 2f(1) - a_3 - 2a_4 - a_3 - a_4\\ ⇔\\ a_2 = 3f(1) - \frac{f(2)-f(0)}{2} - 2a_3 - 3a_4$$

となり、a2が決定する。
こうして、もとの式（★）がt以外全て求まったことになる。

$$f(t) = a_1t^3 + a_2t^2 + a_3t + a_4 ・・・★$$

★にt=0.0-1.0を代入すると補間された座標を得ることができる。

実装

https://github.com/mushe/ProceduralAlgorithms/tree/main
https://github.com/mushe/Catmull-Rom-spline/

参考

1. Doyub Kim, "Fluid Engine Development", A K Peters/CRC Press, 2017

https://www.amazon.co.jp/-/en/Doyub-Kim-ebook/dp/B01MRDA6S8

2. Cubic Hermite spline#Catmull–Rom_spline - Wikipedia

https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull–Rom_spline