Catmull-Romスプライン曲線

**Catmull-Romスプライン**（）は、カーディナルスプラインの特殊な場合のひとつ。「一様な」パラメータ間隔を前提とする。3次エルミートスプラインにおいて、接ベクトルとして
\boldsymbol{m}_k = \frac{\boldsymbol{p}_{k+1} - \boldsymbol{p}_{k-1}}{2}
を選択し、3次エルミートスプラインの定義式
\boldsymbol{p}(t) = \left(2t^3 - 3t^2 + 1\right) \boldsymbol{p}_k + \left(t^3 - 2t^2 + t\right) \boldsymbol{m}_k + \left(-2t^3 + 3t^2\right) \boldsymbol{p}_{k+1} + \left(t^3 - t^2\right) \boldsymbol{m}_{k+1}
にあてはめることにより、以下のCatmull-Romスプラインの式が得られる。

\boldsymbol{p}(t) =
\frac{1}{2}
\begin{bmatrix}
t^3 & t^2 & t & 1
\end{bmatrix}
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
2 & -5 & 4 & -1 \\
-1 & 0 & 1 & 0 \\
0 & 2 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
{\boldsymbol{p}}_{k-1} \\
{\boldsymbol{p}}_k \\
{\boldsymbol{p}}_{k+1} \\
{\boldsymbol{p}}_{k+2}
\end{bmatrix}


この曲線は  Edwin Catmull と  にちなんで名付けられた。この手法の主な利点は、元の点セットに沿った点がスプライン曲線の制御点も構成することである。

曲線の両端に2つの追加点が必要である。
一様なCatmull-Romスプラインの実装では、ループと自己交差が発生する可能性がある。
chordal および centripetal Catmull-Rom スプライン実装はこの問題を解決するが、計算方法が若干異なる。

コンピューターグラフィックスでは、キーフレーム間の滑らかな補間モーションを取得するために Catmull-Rom スプラインが頻繁に使用される。たとえば、離散キーフレームから生成されるカメラパスアニメーションのほとんどは、Catmull-Romスプラインを使用して処理される。これらは主に、計算が比較的容易であること、各キーフレームの位置が正確にヒットすることを保証すること、生成された曲線の接線が複数のセグメントにわたって連続していることを保証することから人気がある。

## 定義（CatmullとRomによる）
文献は複数の方式の補間曲線の比較である。
以下のブレンディング関数のグラフや実験結果が示されており、この内『例3』がCatmull-Romスプライン曲線である。

定義式は、

\mathbf{F}(t) = \sum_{j}^{}{\mathbf{p}}_{j}C_{jk}(t)

である。
{\mathbf{p}}_{j} は定義点（defining point）、C_{jk}(t) はブレンディング関数 C_{0,k}(t) を 0 \leq t  の区間にシフトしたものである。
以下は左から、ブレンディング関数 C_{0,k}(t) とそのシフト C_{jk}(t)、曲線 \mathbf{F}(t) の例である。



ブレンディング関数は以下の基数関数（cardinal function）である。


C_{0,k}(t)=\sum_{i=0}^{k} 
\left[ \prod_{
\begin{array}{c}
j=i-k\\
j \ne 0
\end{array}
}^{i}
\left( \frac{t}{j}+1 \right) \right]
w(t+i) 


線形ラグランジュ補間を使用するので k=1 であり、

C_{0,1}(t)=(1-t)w(t)+(1+t)w(1+t)

になる。
w(t) は2次一様B-スプラインの基底関数をシフトしてブレンディング関数化したものである。

以下は左から、2次一様B-スプラインのブレンディング関数と、シフト前の基底関数である。



C_{0,1}(t) の各項のグラフは以下の通り。


この w(t) を C_{0,1}(t) にあてはめると

C_{0,1}(t)=
\left\{
\begin{array}{ll}
\frac{1}{2}t^3+\frac{5}{2}t^2+4t+2 & for \quad -2 \leq t 
になり、0 \leq t  にシフトして C_{j1}(t) を求め、行列形式にまとめると、

\mathbf{F}(t) =
\frac{1}{2}
\begin{bmatrix}
t^3 & t^2 & t & 1
\end{bmatrix}
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
2 & -5 & 4 & -1 \\
-1 & 0 & 1 & 0 \\
0 & 2 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
{\mathbf{p}}_j \\
{\mathbf{p}}_{j+1} \\
{\mathbf{p}}_{j+2} \\
{\mathbf{p}}_{j+3}
\end{bmatrix}

となり、3次エルミートスプラインとしての定義式と一致する。

## 性質

### B-スプライン曲線との比較
Catmull-Romスプライン曲線は定義点を通るinterpolationであるのに対し、B-スプライン曲線は制御点を通らないapproximationである。

以下左から、3次一様B-スプラインのブレンディング関数とシフト前の基底関数、曲線の例である。



### 連続性
Catmull-Romスプライン曲線は定義および以下によりC1連続であり、C2連続ではない。

{\mathbf{F}}_k'(1) =
\frac{1}{2}
\begin{bmatrix}
0 & -1 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
{\mathbf{p}}_{k-1} \\
{\mathbf{p}}_k \\
{\mathbf{p}}_{k+1} \\
{\mathbf{p}}_{k+2}
\end{bmatrix}
=
{\mathbf{F}}_{k+1}'(0) =
\frac{1}{2}
\begin{bmatrix}
-1 & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
{\mathbf{p}}_k \\
{\mathbf{p}}_{k+1} \\
{\mathbf{p}}_{k+2} \\
{\mathbf{p}}_{k+3}
\end{bmatrix}


{\mathbf{F}}_k*(1) =
\begin{bmatrix}
-1 & 4 & -5 & 2
\end{bmatrix}
\begin{bmatrix}
{\mathbf{p}}_{k-1} \\
{\mathbf{p}}_k \\
{\mathbf{p}}_{k+1} \\
{\mathbf{p}}_{k+2}
\end{bmatrix}
\neq
{\mathbf{F}}_{k+1}*(0) =
\begin{bmatrix}
2 & -5 & 4 & -1
\end{bmatrix}
\begin{bmatrix}
{\mathbf{p}}_k \\
{\mathbf{p}}_{k+1} \\
{\mathbf{p}}_{k+2} \\
{\mathbf{p}}_{k+3}
\end{bmatrix}


### 自己交差の発生
曲線の途中で、定義点の間隔の差が大きいと尖った形状（カスプ）や自己交差が発生する場合がある。

以下は自己交差の例である。



### ベジェ曲線への変換

3次ベジェ曲線の行列形式は

\mathbf{P}(t)=
\begin{bmatrix}
t^3 & t^2 & t & 1
\end{bmatrix}
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
3 & -6 & 3 & 0 \\
-3 & 3 & 0 & 0 \\
1 & 0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
{\mathbf{p_{bz}}}_0 \\
{\mathbf{p_{bz}}}_1 \\
{\mathbf{p_{bz}}}_2 \\
{\mathbf{p_{bz}}}_3
\end{bmatrix}

であることから、Catmull-Romスプライン曲線と等しくなる3次ベジェ曲線の制御点は

\begin{bmatrix}
{\mathbf{p_{bz}}}_0 \\
{\mathbf{p_{bz}}}_1 \\
{\mathbf{p_{bz}}}_2 \\
{\mathbf{p_{bz}}}_3
\end{bmatrix}
=
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
3 & -6 & 3 & 0 \\
-3 & 3 & 0 & 0 \\
1 & 0 & 0 & 0
\end{bmatrix}
^{-1}
\frac{1}{2}
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
2 & -5 & 4 & -1 \\
-1 & 0 & 1 & 0 \\
0 & 2 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
{\mathbf{p}}_{k-1} \\
{\mathbf{p}}_k \\
{\mathbf{p}}_{k+1} \\
{\mathbf{p}}_{k+2}
\end{bmatrix}
=
\frac{1}{6}
\begin{bmatrix}
0 & 6 & 0 & 0 \\
-1 & 6 & 1 & 0 \\
0 & 1 & 6 & -1 \\
0 & 0 & 6 & 0
\end{bmatrix}
\begin{bmatrix}
\mathbf{p}_{k-1} \\
\mathbf{p}_k \\
\mathbf{p}_{k+1} \\
\mathbf{p}_{k+2}
\end{bmatrix}

である。

## 曲面（バイキュービック補間）への拡張
2つのCatmull-Romスプラインの直交座標積を取ることで、点のグリッドを補間する2変量サーフェスを取得できる。

以下の式で表されるバイキュービックパッチとなる。

\mathbf{F}(t,u) =
\begin{bmatrix}
t^3 & t^2 & t & 1
\end{bmatrix}
\mathbf{M}
\begin{bmatrix}
{\mathbf{p}}_{11} & {\mathbf{p}}_{12} & {\mathbf{p}}_{13} & {\mathbf{p}}_{14} \\
{\mathbf{p}}_{21} & {\mathbf{p}}_{22} & {\mathbf{p}}_{23} & {\mathbf{p}}_{24} \\
{\mathbf{p}}_{31} & {\mathbf{p}}_{32} & {\mathbf{p}}_{33} & {\mathbf{p}}_{34} \\
{\mathbf{p}}_{41} & {\mathbf{p}}_{42} & {\mathbf{p}}_{43} & {\mathbf{p}}_{44} 
\end{bmatrix}
\mathbf{M}^T
\begin{bmatrix}
u^3 \\
u^2 \\
u \\
1
\end{bmatrix}

ここで

\mathbf{M}=
\frac{1}{2}
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
2 & -5 & 4 & -1 \\
-1 & 0 & 1 & 0 \\
0 & 2 & 0 & 0
\end{bmatrix}

パッチは中央の4点を補間する。隣接パッチ間は1次導関数連続となる。

## テンションパラメータの拡張

接ベクトルの係数 1/2 をテンションパラメータ \tau に置き換えた
\boldsymbol{m}_k = \tau ( \boldsymbol{p}_{k+1} - \boldsymbol{p}_{k-1} )
をCatmull-Romスプラインとしている場合がある。

この場合の定義式は以下となる。

\boldsymbol{p}(t) =
\begin{bmatrix}
t^3 & t^2 & t & 1
\end{bmatrix}
\begin{bmatrix}
-\tau & 2-\tau & \tau-2 & \tau \\
2\tau & \tau-3 & 3-2\tau & -\tau \\
-\tau & 0 & \tau & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
{\boldsymbol{p}}_{k-1} \\
{\boldsymbol{p}}_k \\
{\boldsymbol{p}}_{k+1} \\
{\boldsymbol{p}}_{k+2}
\end{bmatrix}


なお、\tau とKochanek–Bartelsスプラインのテンションパラメータ（\tau_{KB} とする）の関係は
\tau = \frac{1-\tau_{KB}}{2}
である。

また、等価な3次ベジェ曲線の制御点は

\begin{bmatrix}
{\mathbf{p_{bz}}}_0 \\
{\mathbf{p_{bz}}}_1 \\
{\mathbf{p_{bz}}}_2 \\
{\mathbf{p_{bz}}}_3
\end{bmatrix}
=
\frac{1}{3}
\begin{bmatrix}
0 & 3 & 0 & 0 \\
-\tau & 3 & \tau & 0 \\
0 & \tau & 3 & -\tau \\
0 & 0 & 3 & 0
\end{bmatrix}
\begin{bmatrix}
\mathbf{p}_{k-1} \\
\mathbf{p}_k \\
\mathbf{p}_{k+1} \\
\mathbf{p}_{k+2}
\end{bmatrix}

である。

## 脚注
### 注釈

### 出典

## 参考文献
* 
* 

## 関連項目
* 3次エルミートスプライン
* Centripetal Catmull-Romスプライン
* バイキュービック補間
* ベジェ曲線
* スプライン曲線
* B-スプライン曲線
* Kochanek–Bartelsスプライン曲線

## 外部リンク
* Fussy - 曲線描画