Catmull-Romスプライン曲線

Catmull-Romスプライン（テンプレート:Lang-en）は、カーディナルスプラインの特殊な場合のひとつ。「一様な」パラメータ間隔を前提とする。3次エルミートスプラインにおいて、接ベクトルとして $𝒎_{k} = \frac{𝒑_{k + 1} - 𝒑_{k - 1}}{2}$ を選択し、3次エルミートスプラインの定義式 $𝒑 (t) = (2 t^{3} - 3 t^{2} + 1) 𝒑_{k} + (t^{3} - 2 t^{2} + t) 𝒎_{k} + (- 2 t^{3} + 3 t^{2}) 𝒑_{k + 1} + (t^{3} - t^{2}) 𝒎_{k + 1}$ にあてはめることにより、以下のCatmull-Romスプラインの式が得られる。 $𝒑 (t) = \frac{1}{2} [\begin{matrix} t^{3} & t^{2} & t & 1 \end{matrix}] [\begin{matrix} - 1 & 3 & - 3 & 1 \\ 2 & - 5 & 4 & - 1 \\ - 1 & 0 & 1 & 0 \\ 0 & 2 & 0 & 0 \end{matrix}] [\begin{matrix} 𝒑_{k - 1} \\ 𝒑_{k} \\ 𝒑_{k + 1} \\ 𝒑_{k + 2} \end{matrix}]$

この曲線は Edwin Catmull とテンプレート:日本語版にない記事リンクにちなんで名付けられた。この手法の主な利点は、元の点セットに沿った点がスプライン曲線の制御点も構成することである^[1]。

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

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

定義（CatmullとRomによる）

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

	Interval Width	Differentiability	Type	Degree of Polynomial for Cardinal Function
例1	3	1	B-SPLINE
例2	4	2	BEZIER
例3	4	1	B-SPLINE	1
例4	6	2	B-SPLINE	2

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

ブレンディング関数は以下の基数関数（cardinal function）である。 ^{[注 1]} $C_{0, k} (t) = \sum_{i = 0}^{k} [\prod_{\begin{matrix} j = i - k \\ j \neq 0 \end{matrix}}^{i} (\frac{t}{j} + 1)] 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) = {\begin{matrix} \frac{1}{2} t^{3} + \frac{5}{2} t^{2} + 4 t + 2 & f o r - 2 \leq t < - 1 \\ - \frac{3}{2} t^{3} - \frac{5}{2} t^{2} + 1 & f o r - 1 \leq t < 0 \\ \frac{3}{2} t^{3} - \frac{5}{2} t^{2} + 1 & f o r 0 \leq t < 1 \\ - \frac{1}{2} t^{3} + \frac{5}{2} t^{2} - 4 t + 2 & f o r 1 \leq t < 2 \end{matrix}$ になり、 $0 \leq t < 1$ にシフトして $C_{j 1} (t)$ を求め、行列形式にまとめると、 $𝐅 (t) = \frac{1}{2} [\begin{matrix} t^{3} & t^{2} & t & 1 \end{matrix}] [\begin{matrix} - 1 & 3 & - 3 & 1 \\ 2 & - 5 & 4 & - 1 \\ - 1 & 0 & 1 & 0 \\ 0 & 2 & 0 & 0 \end{matrix}] [\begin{matrix} 𝐩_{j} \\ 𝐩_{j + 1} \\ 𝐩_{j + 2} \\ 𝐩_{j + 3} \end{matrix}]$ となり、3次エルミートスプラインとしての定義式と一致する。

性質

B-スプライン曲線との比較

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

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

連続性

Catmull-Romスプライン曲線は定義および以下によりC1連続であり、C2連続ではない。 ${𝐅^{'}}_{k} (1) = \frac{1}{2} [\begin{matrix} 0 & - 1 & 0 & 1 \end{matrix}] [\begin{matrix} 𝐩_{k - 1} \\ 𝐩_{k} \\ 𝐩_{k + 1} \\ 𝐩_{k + 2} \end{matrix}] = {𝐅^{'}}_{k + 1} (0) = \frac{1}{2} [\begin{matrix} - 1 & 0 & 1 & 0 \end{matrix}] [\begin{matrix} 𝐩_{k} \\ 𝐩_{k + 1} \\ 𝐩_{k + 2} \\ 𝐩_{k + 3} \end{matrix}]$ ${𝐅^{″}}_{k} (1) = [\begin{matrix} - 1 & 4 & - 5 & 2 \end{matrix}] [\begin{matrix} 𝐩_{k - 1} \\ 𝐩_{k} \\ 𝐩_{k + 1} \\ 𝐩_{k + 2} \end{matrix}] \neq {𝐅^{″}}_{k + 1} (0) = [\begin{matrix} 2 & - 5 & 4 & - 1 \end{matrix}] [\begin{matrix} 𝐩_{k} \\ 𝐩_{k + 1} \\ 𝐩_{k + 2} \\ 𝐩_{k + 3} \end{matrix}]$

自己交差の発生

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

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

ベジェ曲線への変換

3次ベジェ曲線の行列形式は $𝐏 (t) = [\begin{matrix} t^{3} & t^{2} & t & 1 \end{matrix}] [\begin{matrix} - 1 & 3 & - 3 & 1 \\ 3 & - 6 & 3 & 0 \\ - 3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}] [\begin{matrix} {𝐩_{𝐛 𝐳}}_{0} \\ {𝐩_{𝐛 𝐳}}_{1} \\ {𝐩_{𝐛 𝐳}}_{2} \\ {𝐩_{𝐛 𝐳}}_{3} \end{matrix}]$ であることから、Catmull-Romスプライン曲線と等しくなる3次ベジェ曲線の制御点は $[\begin{matrix} {𝐩_{𝐛 𝐳}}_{0} \\ {𝐩_{𝐛 𝐳}}_{1} \\ {𝐩_{𝐛 𝐳}}_{2} \\ {𝐩_{𝐛 𝐳}}_{3} \end{matrix}] = {[\begin{matrix} - 1 & 3 & - 3 & 1 \\ 3 & - 6 & 3 & 0 \\ - 3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}]}^{- 1} \frac{1}{2} [\begin{matrix} - 1 & 3 & - 3 & 1 \\ 2 & - 5 & 4 & - 1 \\ - 1 & 0 & 1 & 0 \\ 0 & 2 & 0 & 0 \end{matrix}] [\begin{matrix} 𝐩_{k - 1} \\ 𝐩_{k} \\ 𝐩_{k + 1} \\ 𝐩_{k + 2} \end{matrix}] = \frac{1}{6} [\begin{matrix} 0 & 6 & 0 & 0 \\ - 1 & 6 & 1 & 0 \\ 0 & 1 & 6 & - 1 \\ 0 & 0 & 6 & 0 \end{matrix}] [\begin{matrix} 𝐩_{k - 1} \\ 𝐩_{k} \\ 𝐩_{k + 1} \\ 𝐩_{k + 2} \end{matrix}]$ である。

曲面（バイキュービック補間）への拡張

2つのCatmull-Romスプラインの直交座標積を取ることで、点のグリッドを補間する2変量サーフェスを取得できる^[7]。

以下の式で表されるバイキュービックパッチとなる。 $𝐅 (t, u) = [\begin{matrix} t^{3} & t^{2} & t & 1 \end{matrix}] 𝐌 [\begin{matrix} 𝐩_{11} & 𝐩_{12} & 𝐩_{13} & 𝐩_{14} \\ 𝐩_{21} & 𝐩_{22} & 𝐩_{23} & 𝐩_{24} \\ 𝐩_{31} & 𝐩_{32} & 𝐩_{33} & 𝐩_{34} \\ 𝐩_{41} & 𝐩_{42} & 𝐩_{43} & 𝐩_{44} \end{matrix}] 𝐌^{T} [\begin{matrix} u^{3} \\ u^{2} \\ u \\ 1 \end{matrix}]$ ここで $𝐌 = \frac{1}{2} [\begin{matrix} - 1 & 3 & - 3 & 1 \\ 2 & - 5 & 4 & - 1 \\ - 1 & 0 & 1 & 0 \\ 0 & 2 & 0 & 0 \end{matrix}]$ パッチは中央の4点を補間する。隣接パッチ間は1次導関数連続となる。

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

接ベクトルの係数 $1 / 2$ をテンションパラメータ $τ$ に置き換えた $𝒎_{k} = τ (𝒑_{k + 1} - 𝒑_{k - 1})$ をCatmull-Romスプラインとしている場合がある^[8]。

この場合の定義式は以下となる。 $𝒑 (t) = [\begin{matrix} t^{3} & t^{2} & t & 1 \end{matrix}] [\begin{matrix} - τ & 2 - τ & τ - 2 & τ \\ 2 τ & τ - 3 & 3 - 2 τ & - τ \\ - τ & 0 & τ & 0 \\ 0 & 1 & 0 & 0 \end{matrix}] [\begin{matrix} 𝒑_{k - 1} \\ 𝒑_{k} \\ 𝒑_{k + 1} \\ 𝒑_{k + 2} \end{matrix}]$

なお、 $τ$ とKochanek–Bartelsスプラインのテンションパラメータ（ $τ_{K B}$ とする）の関係は $τ = \frac{1 - τ_{K B}}{2}$ である^[9]。

また、等価な3次ベジェ曲線の制御点は $[\begin{matrix} {𝐩_{𝐛 𝐳}}_{0} \\ {𝐩_{𝐛 𝐳}}_{1} \\ {𝐩_{𝐛 𝐳}}_{2} \\ {𝐩_{𝐛 𝐳}}_{3} \end{matrix}] = \frac{1}{3} [\begin{matrix} 0 & 3 & 0 & 0 \\ - τ & 3 & τ & 0 \\ 0 & τ & 3 & - τ \\ 0 & 0 & 3 & 0 \end{matrix}] [\begin{matrix} 𝐩_{k - 1} \\ 𝐩_{k} \\ 𝐩_{k + 1} \\ 𝐩_{k + 2} \end{matrix}]$ である。

脚注

注釈

テンプレート:Reflist

出典

テンプレート:Reflist

参考文献

外部リンク

Fussy - 曲線描画

↑ ^1.0 ^1.1 テンプレート:Citation
↑ Catmull, Rom (1974), p.325 Figure 5に基づき作成
↑ N. Dyn, M. S. Floater, and K. Hormann. Four-point curve subdivision based on iterated chordal and centripetal parameterizations. Computer Aided Geometric Design, 26(3):279–286, 2009.
↑ P. J. Barry and R. N. Goldman. A recursive evaluation algorithm for a class of Catmull-Rom splines. SIGGRAPH Computer Graphics, 22(4):199–204, 1988.
↑ Read the Docs - Uniform Catmull–Rom Splines
↑ Catmull, Rom (1974), p.319
↑ Catmull, Rom (1974), pp.322-323
↑ テンプレート:Cite web
↑ テンプレート:Cite journal

引用エラー: 「注」という名前のグループの <ref> タグがありますが、対応する <references group="注"/> タグが見つかりません

[CR-1] 1.0 ^1.1 テンプレート:Citation

[2] Catmull, Rom (1974), p.325 Figure 5に基づき作成

[3] N. Dyn, M. S. Floater, and K. Hormann. Four-point curve subdivision based on iterated chordal and centripetal parameterizations. Computer Aided Geometric Design, 26(3):279–286, 2009.

[4] P. J. Barry and R. N. Goldman. A recursive evaluation algorithm for a class of Catmull-Rom splines. SIGGRAPH Computer Graphics, 22(4):199–204, 1988.

[5] Read the Docs - Uniform Catmull–Rom Splines

[7] Catmull, Rom (1974), p.319

[9] Catmull, Rom (1974), pp.322-323

[10] テンプレート:Cite web

[11] テンプレート:Cite journal

[1]

[2]

[3]

[4]

[5]

[注 1]

[6]

[注 2]

[7]

[8]

[9]

Catmull-Romスプライン曲線

目次

定義（CatmullとRomによる）