Catmull-Rom スプライン曲線についてのメモ

たのしい複素積分」や「わくわく解析接続」では、マウス(またはタッチ操作)の入力から曲線を構成する際に Catmull-Rom スプライン曲線を使っている。この Catmull-Rom スプライン曲線についてのメモを書いておく。あくまで備忘録であり、 Catmull-Rom スプラインを知らない人向けの記事ではない。

与えられたデータ

\(P_0,P_1,\ldots,P_N\): 通るべき点の列。
\(t_0<t_1<\cdots<t_N\): 各点に対応する、狭義単調増加な実数の列。

\(t_k\) は、典型的には、均等に取ったり(uniform)、点どうしの距離に比例させたり(chordal)する。

与えられた2点を通る線分

\[S_i(t)=\frac{t_{i+1}-t}{t_{i+1}-t_i}P_i+\frac{t-t_i}{t_{i+1}-t_i}P_{i+1}\quad(t_i\le t\le t_{i+1})\]

性質:
\begin{align*}
S_i(t_i)&=P_i, &
S_i'(t)&=\frac{P_{i+1}-P_i}{t_{i+1}-t_i}, \\
S_i(t_{i+1})&=P_{i+1}.
\end{align*}

与えられた3点を通る2次ベジエ曲線

\[Q_i(t)=\frac{t_{i+1}-t}{t_{i+1}-t_{i-1}}S_{i-1}(t)+\frac{t-t_{i-1}}{t_{i+1}-t_{i-1}}S_i(t)\quad(t_{i-1}\le t\le t_{i+1})\]

性質:
\begin{align*}
Q_i(t_{i-1})&=P_{i-1}, \\
Q_i(t_i)&=P_i, \\
Q_i(t_{i+1})&=P_{i+1}, \\
Q_i'(t_{i-1})
&=\left(\frac{1}{t_i-t_{i-1}}+\frac{1}{t_{i+1}-t_i}\right)P_i
-\left(\frac{1}{t_{i+1}-t_{i-1}}+\frac{1}{t_i-t_{i-1}}\right)P_{i-1}
-\left(\frac{1}{t_{i+1}-t_i}-\frac{1}{t_{i+1}-t_{i-1}}\right)P_{i+1} \\
&=\frac{t_{i+1}-t_{i-1}}{(t_i-t_{i-1})(t_{i+1}-t_i)}P_i
-\frac{t_i+t_{i+1}-2t_{i-1}}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})}P_{i-1}
-\frac{t_i-t_{i-1}}{(t_{i+1}-t_i)(t_{i+1}-t_{i-1})}P_{i+1}, \\
Q_i'(t_i)
&=\left(\frac{1}{t_i-t_{i-1}}-\frac{1}{t_{i+1}-t_i}\right)P_i
-\left(\frac{1}{t_i-t_{i-1}}-\frac{1}{t_{i+1}-t_{i-1}}\right)P_{i-1}
+\left(\frac{1}{t_{i+1}-t_i}-\frac{1}{t_{i+1}-t_{i-1}}\right)P_{i+1} \\
&=\frac{t_{i+1}+t_{i-1}-2t_i}{(t_i-t_{i-1})(t_{i+1}-t_i)}P_i
-\frac{t_{i+1}-t_i}{(t_i-t_{i-1})(t_{i+1}-t_{i-1})}P_{i-1}
+\frac{t_i-t_{i-1}}{(t_{i+1}-t_i)(t_{i+1}-t_{i-1})}P_{i+1}, \\
Q_i'(t_{i+1})
&=\left(\frac{1}{t_{i+1}-t_{i-1}}+\frac{1}{t_{i+1}-t_i}\right)P_{i+1}
-\left(\frac{1}{t_i-t_{i-1}}+\frac{1}{t_{i+1}-t_i}\right)P_i
+\left(\frac{1}{t_i-t_{i-1}}-\frac{1}{t_{i+1}-t_{i-1}}\right)P_{i-1} \\
&=\frac{2t_{i+1}-t_i-t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}P_{i+1}
-\frac{t_{i+1}-t_{i-1}}{(t_i-t_{i-1})(t_{i+1}-t_i)}P_i
+\frac{t_{i+1}-t_i}{(t_i-t_{i-1})(t_{i+1}-t_{i-1})}P_{i-1}.
\end{align*}

始点・終点・制御点:

始点:\(P_{i-1}\),
制御点:\(\frac{(t_{i+1}-t_{i-1})^2}{2(t_{i+1}-t_i)(t_i-t_{i-1})}P_i-\frac{t_{i+1}-t_i}{2(t_i-t_{i-1})}P_{i-1}-\frac{t_i-t_{i-1}}{2(t_{i+1}-t_i)}P_{i+1}\),
終点:\(P_{i+1}\).

前半部(\(P_{i-1}\)〜\(P_i\))の始点・終点・制御点

始点:\(P_{i-1}\),
制御点:\(\frac{t_{i+1}-t_{i-1}}{2(t_{i+1}-t_i)}P_i+\frac{t_i-t_{i-1}}{2(t_{i+1}-t_{i-1})}\left(\frac{t_{i+1}-t_i}{t_i-t_{i-1}}P_{i-1}-\frac{t_i-t_{i-1}}{t_{i+1}-t_i}P_{i+1}\right)\),
終点:\(P_i\).

後半部(\(P_i\)〜\(P_{i+1}\))の始点・終点・制御点

始点:\(P_i\),
制御点:\(\frac{t_{i+1}-t_{i-1}}{2(t_i-t_{i-1})}P_i+\frac{t_{i+1}-t_i}{2(t_{i+1}-t_{i-1})}\left(\frac{t_i-t_{i-1}}{t_{i+1}-t_i}P_{i+1}-\frac{t_{i+1}-t_{i}}{t_{i}-t_{i-1}}P_{i-1}\right)\),
終点:\(P_{i+1}\).

Catmull-Rom スプライン曲線

\[C_i(t)=\frac{t_{i+1}-t}{t_{i+1}-t_i}Q_i(t)+\frac{t-t_i}{t_{i+1}-t_i}Q_{i+1}(t)\quad(t_i\le t\le t_{i+1})\]

性質:
\begin{align*}
C_i(t_i)&=P_i, & C_i'(t_i)&=Q_i'(t_i), \\
C_i(t_{i+1})&=P_{i+1}, & C_i'(t_{i+1})&=Q_{i+1}'(t_{i+1}).
\end{align*}

始点・終点・制御点:

始点:\(P_i\),
制御点1:\(\frac{1}{3}\left(1+\frac{t_{i+1}-t_{i-1}}{t_i-t_{i-1}}\right)P_i
+\frac{t_{i+1}-t_i}{3(t_{i+1}-t_{i-1})}\left(\frac{t_{i}-t_{i-1}}{t_{i+1}-t_{i}}P_{i+1}-\frac{t_{i+1}-t_{i}}{t_{i}-t_{i-1}}P_{i-1}\right)\),
制御点2:\(\frac{1}{3}\left(1+\frac{t_{i+2}-t_{i}}{t_{i+2}-t_{i+1}}\right)P_{i+1}
+\frac{t_{i+1}-t_i}{3(t_{i+2}-t_{i})}\left(\frac{t_{i+2}-t_{i+1}}{t_{i+1}-t_{i}}P_{i}-\frac{t_{i+1}-t_{i}}{t_{i+2}-t_{i+1}}P_{i+2}\right)\),
終点:\(P_{i+1}\).

実装してみて

「たのしい複素積分」と「わくわく解析接続」では、当初はパラメーターが均等になる ように取っていた(その方が計算式が簡単になる)。しかし、それだと「閉曲線」モードで始点と終点が離れている際に始点と終点の周辺が不自然になる。そこ で、今回、パラメーターに点どうしの距離を反映させることにした。

やってみて気づいたこととしては、 \(t_{i-1}\) と \(t_i\) が近く(マウス入力での連続する2点)て、 \(t_i\) と \(t_{i+1}\) が離れている(「閉曲線」モードでの終点と始点)状況では、\(P_i\) と \(P_{i+1}\) を結ぶ曲線が \(P_{i-1}\) に大きく依存してしまう。このため、マウスの入力をそのまま使うのではなく、密集した点を適度に間引く処理を追加した。

この記事を書くにあたって、JavaScriptでインタラクティブに遊べるやつを載せれば良いかもしれないと思ったが、そうすると永遠に記事を公開できない恐れがあるので、とりあえず公開してしまうことにした。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です