Catmull-Romスプラインをベジェ曲線に変換して描画する

Posted at 2025-03-09

はじめに

コントロールポイントを通らないB-スプラインに対し、Catmull-Romスプラインは必ず通る利点があります。[1]では前者をapproximation、後者をinterpolationとしています。
一方で、なめらかさが劣る（3次B-スプラインはC2連続、Catmull-RomスプラインはC1連続）とか、コントロールポイントの間隔のばらつきが大きいと予期せぬ自己交差が発生するなどの弱点があり、改良版の「Centripetal Catmull–Romスプライン」が考案されたりしています。

定義

Edwin CatmullとRaphael Rom自身による[1]は複数のinterpolationの比較であり、そのどれがいわゆる「Catmull-Romスプライン」なのか若干不明確ですが、[2]ではこれらの内「INTERVAL WIDTH-4. DIFFERENTIABILITY-1. TYPE B-SPLINE. DEGREE OF POLYNOMIAL FOR CARDINAL FUNCTION IS 1」で例示されているもの、とされています。
その係数行列は以下の通りです。

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

Wikipediaでは「Cubic Hermite spline」の中の「Catmull–Rom spline」です。

導出

Catmull-Romスプラインの定義式は

F(t)=\sum_{j}^{}p_{j}C_{jk}(t)

です。B-スプラインなどと同じ式のように見えますが、Catmull-Romスプラインはinterpolationなので、$p_{j}$はコントロールポイントではなくデファイニングポイント（defining point）です。$C_{jk}(t)$は基底関数ではなくブレンディング関数のシフトです。
Catmull-Romスプラインのブレンディング関数は以下の基数関数（cardinal function）です。

C_{0,k}(t)=\sum_{i=0}^{k} w(i+t) \prod_{j=i-k}^{i}
\left\{
\begin{array}{ll}
1 & for \quad j=0 \\
1+\frac{t}{j} & otherwise
\end{array}
\right.

$k$は線形ラグランジュ補間を使用するので$1$です。すると、

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

になります。
$w(t)$は2次B-スプラインの基底関数をブレンディング関数化したものです。$w(t)$は幅が3、中心が$\frac{k}{2}=0.5$との条件があり、すると2次B-スプラインの$t$の値域は$0 \leq t < 1$であれば良いので、ノットベクトルは $ \begin{bmatrix} -2 & -1 & 0 & 1 & 2 & 3 \end{bmatrix} $ です。これをde Boor-Coxの漸化式にあてはめて2次B-スプラインの基底関数を導出します。

\begin{array}{l}
b_{0,2}(t)=\frac{1}{2}t^2-t+\frac{1}{2} \\
b_{1,2}(t)=-t^2+t+\frac{1}{2} \\
b_{2,2}(t)=\frac{1}{2}t^2
\end{array}

$b_{0,2}$の$t$を$+1$、$b_{2,2}$の$t$を$-1$シフトして合成することでブレンディング関数化します。

w(t)=
\left\{
\begin{array}{ll}
\frac{1}{2}t^2+t+\frac{1}{2} & for \quad -1 \leq t < 0 \\
-t^2+t+\frac{1}{2} & for \quad 0 \leq t < 1 \\
\frac{1}{2}t^2-2t+2 & for \quad 1 \leq t < 2
\end{array}
\right.

これら基底関数とブレンディング関数のグラフは以下の通りです。

この$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 < -1 \\
-\frac{3}{2}t^3-\frac{5}{2}t^2+1 & for \quad -1 \leq t < 0 \\
\frac{3}{2}t^3-\frac{5}{2}t^2+1 & for \quad 0 \leq t < 1 \\
-\frac{1}{2}t^3+\frac{5}{2}t^2-4t+2 & for \quad 1 \leq t < 2
\end{array}
\right.

となります。$C_{0,1}(t)$と、各項のグラフは以下の通りです。

次に、$C_{0,1}(t)$の各区間を$t$の値域が$0 \leq t < 1$になるようシフトして基底関数化した$C_{jk}(t)$を求めます。$C_{jk}(t)$のグラフは以下の通りです。

最後に、$C_{jk}(t)$とデファイニングポイント$p_{j}$から、Catmull-Romスプライン$F(t)$を求めます。行列形式にまとめると

\begin{align}
\boldsymbol{F}(t) & =
\boldsymbol{C_{jk}}(t)
\begin{bmatrix}
{\boldsymbol{p}}_0 \\
{\boldsymbol{p}}_1 \\
{\boldsymbol{p}}_2 \\
{\boldsymbol{p}}_3
\end{bmatrix}
\\
& =
\begin{bmatrix}
t^3 & t^2 & t & 1
\end{bmatrix}
\boldsymbol{R_{cr}}
\begin{bmatrix}
{\boldsymbol{p}}_0 \\
{\boldsymbol{p}}_1 \\
{\boldsymbol{p}}_2 \\
{\boldsymbol{p}}_3
\end{bmatrix}
\end{align}

ここで$\boldsymbol{R_{cr}}$は係数行列で

\boldsymbol{R_{cr}}=
\frac{1}{2}
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
2 & -5 & 4 & -1 \\
-1 & 0 & 1 & 0 \\
0 & 2 & 0 & 0
\end{bmatrix}

です。

係数行列の別の求め方

係数行列$\boldsymbol{R_{cr}}$は、[1]に「This can be compared with other methods for generating bicubic patches」とある通り、バイキュービック補間と対応します。
（手近なところで）以下の記事から、画像処理におけるバイキュービック補間の補間関数を引用します。

　$f_0(x)=Ax^3-5Ax^2+8Ax-4A$
　$f_1(x)=(A+2)x^3-(A+3)x^2+1$
　$f_2(x)$は$f_1(x)$の$x$の符号反転
　$f_3(x)$は$f_0(x)$の$x$の符号反転

$f_0(x)$、$f_2(x)$、$f_3(x)$の$x$の値域を$0 \leq x < 1$になるようシフトし、行列形式にまとめると

\begin{bmatrix}
f_0(x) & f_1(x) & f_2(x) & f_3(x)
\end{bmatrix}
=
\begin{bmatrix}
x^3 & x^2 & x & 1
\end{bmatrix}
\begin{bmatrix}
A & A+2 & -A-2 & -A \\
-2A & -A-3 & 2A+3 & A \\
A & 0 & -A & 0 \\
0 & 1 & 0 & 0
\end{bmatrix}

$A=-0.5$の場合、係数部分が$\boldsymbol{R_{cr}}$と等しくなります。

Catmull-Romスプライン用defining pointをベジェ曲線用コントロールポイントに変換する

Open B-スプラインと同様に、左側から$\boldsymbol{R_{bz}}^{-1}$をかけたものが変換行列です。

\boldsymbol{R_{bz}}^{-1}
\boldsymbol{R_{cr}}=
\frac{1}{6}
\begin{bmatrix}
0 & 6 & 0 & 0 \\
-1 & 6 & 1 & 0 \\
0 & 1 & 6 & -1 \\
0 & 0 & 6 & 0
\end{bmatrix}

となります。これが変換行列です。

Catmull-Romスプライン描画の実装例（Qtアプリの一部抜粋）

mainwindow.h

private:
    QGraphicsScene scene;
	QPainterPath pp;
	QList<QPointF> dps;	// defining point
	int m;				// defining point数
	bool bClosed;
	void drawCatmullRom();
	void drawCatmullRomSegment(QPointF p0, QPointF p1, QPointF p2, QPointF p3);

mainwindow.cpp

// Catmull-Romスプラインを描画する
void MainWindow::drawCatmullRom()
{
	pp.clear();
	for(int i = 0; i < m - 3; i++)
		drawCatmullRomSegment(dps[i], dps[i + 1], dps[i + 2], dps[i + 3]);
	if(bClosed){
		drawCatmullRomSegment(dps[m - 3], dps[m - 2], dps[m - 1], dps[0]);
		drawCatmullRomSegment(dps[m - 2], dps[m - 1], dps[0], dps[1]);
		drawCatmullRomSegment(dps[m - 1], dps[0], dps[1], dps[2]);
	}
	scene.addPath(pp);
}

// Catmull-Romスプラインの1セグメントを描画する
void MainWindow::drawCatmullRomSegment(QPointF p0, QPointF p1, QPointF p2, QPointF p3)
{
	if(pp.isEmpty()){
		// 最初のセグメントのみ
		pp.moveTo(p1);
	}else{
		// bzp0は前回のbzp3と一致するので、moveTo不要
	}
	QPointF crp1 = (-p0 + 6 * p1 + p2) / 6;
	QPointF crp2 = (p1 + 6 * p2 - p3) / 6;
	QPointF crp3 = p2;
	pp.cubicTo(crp1, crp2, crp3);
}

画面・実行例

参考文献

Edwin Catmull, Raphael Rom
A class of local interpolating splines
Computer Aided Geometric Design, pp.317-326
ISBN 0-12-079050-5
Read the Docs -- Uniform Catmull–Rom Splines
https://splines.readthedocs.io/en/latest/euclidean/catmull-rom-uniform.html
Wikipedia -- Cubic Hermite spline -- Catmull–Rom spline
https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull%E2%80%93Rom_spline

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up