LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@bashomatsutakeshi(場生松 武志)

B-スプラインをベジェ曲線に変換して描画する（その1 OpenとClosed）

Last updated at Posted at 2025-03-06

はじめに

多くの描画APIでB-スプラインの描画はサポートされていません。B-スプラインのコントロールポイントをベジェ曲線のコントロールポイントに変換してベジェ曲線として描画する方法が以前から知られていましたが、検索しても出所不詳なスライドか読み解くのが難しい一般解しか出てきません。そこで、B-スプラインをベジェ曲線に変換して描画する方法の、導出過程や実装例含めた解説を作成しました。次数は3に限定しました。
B-スプラインは以下の3種類[1]ありますが、今回はOpenとClosedを対象にします。
（※文献によっては2種類とし、以下の"Clamped"を"Open"、"Closed"を"Periodic"と称している場合があります）

Open Clamped Closed
gp0open.png gp0clamped.png gp0closed.png

B-スプラインの定義

基底関数（basis function）を用いるバーンスタイン表現で定義されます。[2]

\boldsymbol{S}(t)=\sum_{i=0}^{m-1}b_{i,n}(t)\boldsymbol{P}_i

$t$はパラメトリック変数、$n$は曲線の次数(degree)、$P_i$はコントロールポイントの座標、$b_{i,n}(t)$は基底関数です。$m$はコントロールポイント数で、$m\geq n+1$です。同じ次数でコントロールポイントを任意に増やすことができます。
$n=3$、$m=4$の場合、$b_{0,3}$を$P_0$に、$b_{1,3}$を$P_1$に、$b_{2,3}$を$P_2$に、$b_{3,3}$を$P_3$にそれぞれ乗じた合計がB-スプラインになります。

B-スプラインの基底関数はde Boor-Coxの漸化式（recursion formula）で定義されます。

\begin{align}
&b_{i,0}(t) = 
\left
\{
\begin{array}{ll}
1 & if \quad t_i \leq t < t_{i+1} \\
0 & otherwise
\end{array}
\right. \\
&b_{i,k}(t) =
\frac{t-t_i}{t_{i+k}-t_i} b_{i,k-1}(t) +
\frac{t_{i+k+1}-t}{t_{i+k+1}-t_{i+1}}  b_{i+1,k-1}(t)
\end{align}

$t_i$はノットベクトル（knot vector）で$m+n+1$個の数値列です。ノットベクトルにより曲線の特性を調節することが出来ます。

基本のB-スプライン

$n=3$、$m=4$の場合、ノットベクトル、基底関数、コントロールポイントの関係は以下の図のようになります。
　g01.png

基底関数は三角形状の配列（triangular array）になります。[3]
$t_3\leq t<t_4$の場合に基底関数の0階の$b_{3,0}$が1になり、1階の$b_{2,1}$～$b_{3,1}$、2階の$b_{1,2}$～$b_{3,2}$、3階の$b_{0,3}$～$b_{3,3}$が順次決定されます。

ノットベクトルは以下のような単調増加（uniformly spaced）の数列が基本です。
　$ \begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \end{bmatrix} $

このノットベクトルの場合、$t$の値域は$3\leq t<4$となり、基底関数とB-スプラインの例は以下の通りになります。曲線の始点と終点はコントロールポイントに重なりません。
　gp3.png gp4.png

tの値域を変更する

漸化式の計算はノット間の差と比なので、ノットベクトル全体に同じ値を加えたり乗じたりすることで$t$の値域を任意に変更することができます。上のノットベクトルについては、全体から3を引けば$t$の値域を$0\leq t<1$に変更できます。
以下両者は同じ曲線になります。

tの値域 ノットベクトル
$3\leq t<4$ $ \begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \end{bmatrix} $
$0\leq t<1$ $ \begin{bmatrix} -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix} $

コントロールポイントを増やす

B-スプラインは次数を変えずにコントロールポイントを任意に増やすことができます。コントロールポイントに応じてノットも増えるので、基底関数の三角形状が左右方向にひろがります。5個（$m=5$）に増やした場合のノットベクトル、基底関数、コントロールポイントの関係は以下の図のようになります。
　g02.png

以下はノットベクトルの例です。
　$ \begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \end{bmatrix} $

この場合の基底関数とB-スプラインの例は以下の通りになります。
基底関数は、$m=4$と同じものが2つ並んだ形状になります。

gp5.png gp6.png

$t$の値域は$3\leq t<5$ですが、$b_{3,0}$と$b_{4,0}$は同時に1にならないので$b_{0,3}$～$b_{4,3}$の内、同時に有効な（0ではない）項は4個です。曲線形状の決定に関係するコントロールポイントは、$3\leq t<4$では$P_0$～$P_3$、$4\leq t<5$では$P_1$～$P_4$であり、2つの曲線（カーブセグメント）が連なった複合曲線と捉えることができます。

tの値域
$3\leq t<4$ g03.png
$4\leq t<5$ g04.png

そこで、コントロールポイントを2分割し、2回にわけて曲線を描画することができます。

コントロールポイント tの値域 ノットベクトル
0 $ \begin{bmatrix} \boldsymbol{P}_0 & \boldsymbol{P}_1 & \boldsymbol{P}_2 & \boldsymbol{P}_3 \end{bmatrix} $ $3\leq t<4$ $ \begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \end{bmatrix} $
1 $ \begin{bmatrix} \boldsymbol{P}_1 & \boldsymbol{P}_2 & \boldsymbol{P}_3 & \boldsymbol{P}_4 \end{bmatrix} $ $4\leq t<5$ $ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \end{bmatrix} $

$t$の値域を揃えることで同じノットベクトルを使いまわすことができます。

コントロールポイント tの値域 ノットベクトル
0 $ \begin{bmatrix} \boldsymbol{P}_0 & \boldsymbol{P}_1 & \boldsymbol{P}_2 & \boldsymbol{P}_3 \end{bmatrix} $ $0\leq t<1$ $ \begin{bmatrix} -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix} $
1 $ \begin{bmatrix} \boldsymbol{P}_1 & \boldsymbol{P}_2 & \boldsymbol{P}_3 & \boldsymbol{P}_4 \end{bmatrix} $ $0\leq t<1$ $ \begin{bmatrix} -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix} $

Closed B-スプライン

コントロールポイントを循環して用いると、Closed（閉じた）B-スプラインを描画することができます。

コントロールポイント tの値域 ノットベクトル
0 $ \begin{bmatrix} \boldsymbol{P}_0 & \boldsymbol{P}_1 & \boldsymbol{P}_2 & \boldsymbol{P}_3 \end{bmatrix} $ $0\leq t<1$ $ \begin{bmatrix} -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix} $
1 $ \begin{bmatrix} \boldsymbol{P}_1 & \boldsymbol{P}_2 & \boldsymbol{P}_3 & \boldsymbol{P}_0 \end{bmatrix} $ $0\leq t<1$ $ \begin{bmatrix} -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix} $
2 $ \begin{bmatrix} \boldsymbol{P}_2 & \boldsymbol{P}_3 & \boldsymbol{P}_0 & \boldsymbol{P}_1 \end{bmatrix} $ $0\leq t<1$ $ \begin{bmatrix} -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix} $
3 $ \begin{bmatrix} \boldsymbol{P}_3 & \boldsymbol{P}_0 & \boldsymbol{P}_1 & \boldsymbol{P}_2 \end{bmatrix} $ $0\leq t<1$ $ \begin{bmatrix} -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \end{bmatrix} $

　gp9.png

ベジェ曲線のバーンスタイン表現

ド・カステリョ（de Casteljau）のアルゴリズム[4]が直感的にわかりやすくおなじみですが、Bézier自身の論文（[5]など）にはバーンスタイン表現による定義が記載されています。（表記は[6]に合わせてあります）

\boldsymbol{B}(t)=\sum_{i=0}^{n}b_{i,n}(t)\boldsymbol{P}_i \quad , \qquad 0\leq t<1

ベジェ曲線の基底関数の定義は以下の通りです。（漸化式ではない）

b_{i,n}(t)=
\begin{pmatrix}
n \\
i
\end{pmatrix}
t^i(1-t)^{n-i} \quad , \qquad t=0, \cdots ,n

gf3.pngは二項係数です。

$n=3$の基底関数のグラフとベジェ曲線の例は以下の通りです。
　gp1.png gp2.png

$t=0$では$b_{0,3}$が1で他は0、$t=1$では$b_{3,3}$が1で他は0です。このため、ベジェ曲線の始点と終点はコントロールポイントに重なります。

曲線の定義を行列形式に変形する

B-スプライン、ベジェ曲線とも、基底関数の定義式を展開して$t$についての多項式に変形することができます。手作業でもできますが、Sage Mathを使うと素早く正確にできます。
以下は例です。

B-スプライン曲線用
var ('t')
t0=-3
t1=-2
t2=-1
t3=0
t4=1
t5=2
t6=3
t7=4
b20=0
b30=1
b40=0
b11=0
b21=(t-t2)/(t3-t2)*b20+(t4-t)/(t4-t3)*b30
b31=(t-t3)/(t4-t3)*b30+(t5-t)/(t5-t4)*b40
b41=0
b02=0
b12=(t-t1)/(t3-t1)*b11+(t4-t)/(t4-t2)*b21
b22=(t-t2)/(t4-t2)*b21+(t5-t)/(t5-t3)*b31
b32=(t-t3)/(t5-t3)*b31+(t6-t)/(t6-t4)*b41
b42=0
b03=(t-t0)/(t3-t0)*b02+(t4-t)/(t4-t1)*b12
b13=(t-t1)/(t4-t1)*b12+(t5-t)/(t5-t2)*b22
b23=(t-t2)/(t5-t2)*b22+(t6-t)/(t6-t3)*b32
b33=(t-t3)/(t6-t3)*b32+(t7-t)/(t7-t4)*b42
b03.coefficients(t)
b13.coefficients(t)
b23.coefficients(t)
b33.coefficients(t)
実行結果
[[1/6, 0], [-1/2, 1], [1/2, 2], [-1/6, 3]]
[[2/3, 0], [-1, 2], [1/2, 3]]
[[1/6, 0], [1/2, 1], [1/2, 2], [-1/2, 3]]
[[1/6, 3]]
ベジェ曲線用
var ('t')
b03=binomial(3,0)*t^0*(1-t)^(3-0)
b13=binomial(3,1)*t^1*(1-t)^(3-1)
b23=binomial(3,2)*t^2*(1-t)^(3-2)
b33=binomial(3,3)*t^3*(1-t)^(3-3)
b03.coefficients(t)
b13.coefficients(t)
b23.coefficients(t)
b33.coefficients(t)
実行結果
[[1, 0], [-3, 1], [3, 2], [-1, 3]]
[[3, 1], [-6, 2], [3, 3]]
[[3, 2], [-3, 3]]
[[1, 3]]

求めた多項式の係数を用いて行列形式（matrix form）にまとめます。
B-スプラインについては；

\boldsymbol{S}(t)=
\begin{bmatrix}
t^3 & t^2 & t & 1
\end{bmatrix}
\boldsymbol{R_{bsp}}
\begin{bmatrix}
{\boldsymbol{P_{bsp}}}_0 \\
{\boldsymbol{P_{bsp}}}_1 \\
{\boldsymbol{P_{bsp}}}_2 \\
{\boldsymbol{P_{bsp}}}_3
\end{bmatrix}

\boldsymbol{R_{bsp}}=
\frac{1}{6}
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
3 & -6 & 3 & 0 \\
-3 & 0 & 3 & 0 \\
1 & 4 & 1 & 0
\end{bmatrix}

ベジェ曲線については；

\boldsymbol{B}(t)=
\begin{bmatrix}
t^3 & t^2 & t & 1
\end{bmatrix}
\boldsymbol{R_{bz}}
\begin{bmatrix}
{\boldsymbol{P_{bz}}}_0 \\
{\boldsymbol{P_{bz}}}_1 \\
{\boldsymbol{P_{bz}}}_2 \\
{\boldsymbol{P_{bz}}}_3
\end{bmatrix}

\boldsymbol{R_{bz}}=
\begin{bmatrix}
-1 & 3 & -3 & 1 \\
3 & -6 & 3 & 0 \\
-3 & 3 & 0 & 0 \\
1 & 0 & 0 & 0
\end{bmatrix}

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

B-スプラインと等しくなるベジェ曲線のコントロールポイントを求めます。

\boldsymbol{B}(t)=
\boldsymbol{S}(t)

なので

\boldsymbol{R_{bz}}
\begin{bmatrix}
{\boldsymbol{P_{bz}}}_0 \\
{\boldsymbol{P_{bz}}}_1 \\
{\boldsymbol{P_{bz}}}_2 \\
{\boldsymbol{P_{bz}}}_3
\end{bmatrix}
=
\boldsymbol{R_{bsp}}
\begin{bmatrix}
{\boldsymbol{P_{bsp}}}_0 \\
{\boldsymbol{P_{bsp}}}_1 \\
{\boldsymbol{P_{bsp}}}_2 \\
{\boldsymbol{P_{bsp}}}_3
\end{bmatrix}

です。
両辺に左側から$\boldsymbol{R_{bz}}^{-1}$をかけると

\begin{bmatrix}
{\boldsymbol{P_{bz}}}_0 \\
{\boldsymbol{P_{bz}}}_1 \\
{\boldsymbol{P_{bz}}}_2 \\
{\boldsymbol{P_{bz}}}_3
\end{bmatrix}
=
\boldsymbol{R_{bz}}^{-1}
\boldsymbol{R_{bsp}}
\begin{bmatrix}
{\boldsymbol{P_{bsp}}}_0 \\
{\boldsymbol{P_{bsp}}}_1 \\
{\boldsymbol{P_{bsp}}}_2 \\
{\boldsymbol{P_{bsp}}}_3
\end{bmatrix}

となり、$\boldsymbol{R_{bz}}$と$\boldsymbol{R_{bsp}}$に値をあてはめて計算すると

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

となります。これが変換行列です。
以下はコントロールポイントを変換した例です。青色がB-スプライン用のコントロールポイント、赤色がそれを変換したベジェ曲線用のコントロールポイントです。
　gp4b.png gp9b.png

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

mainwindow.h
private:
	QGraphicsScene scene;
	QPainterPath pp;
	QList<QPointF> cps;	// コントロールポイント
	int m;				// コントロールポイント数
	bool bClosed;
	void drawBsp();
	void drawBspSegment(QPointF p0, QPointF p1, QPointF p2, QPointF p3);
mainwindow.cpp
// B-スプラインを描画する
void MainWindow::drawBsp()
{
	pp.clear();
	for(int i = 0; i < m - 3; i++)
		drawBspSegment(cps[i], cps[i + 1], cps[i + 2], cps[i + 3]);
	if(bClosed){
		drawBspSegment(cps[m - 3], cps[m - 2], cps[m - 1], cps[0]);
		drawBspSegment(cps[m - 2], cps[m - 1], cps[0], cps[1]);
		drawBspSegment(cps[m - 1], cps[0], cps[1], cps[2]);
	}
	scene.addPath(pp);
}

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

画面・実行例
bsp1.png

参考文献

  1. B-spline Curves: Definition
    https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-curve.html

  2. Wikipedia -- B-スプライン曲線
    https://ja.wikipedia.org/wiki/B-%E3%82%B9%E3%83%97%E3%83%A9%E3%82%A4%E3%83%B3%E6%9B%B2%E7%B7%9A

  3. Carl de Boor
    A Practical Guide to Splines, P.132
    ISBN 0-387-90356-9

  4. ベジェ曲線入門
    https://pomax.github.io/bezierinfo/ja-JP/index.html#decasteljau

  5. P. Bézier
    Mathematical and Practical Possibilities of UNISURF
    Computer Aided Geometric Design, P.139
    ISBN 0-12-079050-5

  6. Wikipedia -- Bézier curve
    https://en.wikipedia.org/wiki/B%C3%A9zier_curve

関連記事

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?