はじめに
「その1」でOpenとClosedのB-スプラインを対象に、ベジェ曲線に変換して描画する方法について導出過程や実装例含め解説しました。今回はClamped B-スプライン（※文献によってはOpen B-スプライン）を対象にします。
次数は3限定です。
| Open | Clamped | Closed |
|---|---|---|
 |
 |
 |
Clamped B-スプライン
ノットベクトルの内、先頭および末尾の$n+1$個（$n$は次数）が同じ値（multiple knots／重ね合わせ）だと、曲線の始点と終点がコントロールポイントに重なります。[1]
以下は$m$（コントロールポイント数）ごとのノットベクトルの例です。（$m \geq 9$は省略）
| $m$ | ノットベクトル |
|---|---|
| 4 | $ \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} $ |
| 5 | $ \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 2 & 2 & 2 & 2 \end{bmatrix} $ |
| 6 | $ \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 2 & 3 & 3 & 3 & 3 \end{bmatrix} $ |
| 7 | $ \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 4 \end{bmatrix} $ |
| 8 | $ \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 2 & 3 & 4 & 5 & 5 & 5 & 5 \end{bmatrix} $ |
あとはOpen B-スプラインと一緒 ... のはずですが、de Boor-Coxの漸化式にあてはめると$\frac{t-t_i}{t_{i+k}-t_i}$や$\frac{t_{i+k+1}-t}{t_{i+k+1}-t_{i+1}}$の計算で分母が0になります。これらの場合は $b_{i,k-1}(t)$ や $b_{i+1,k-1}(t)$ も$0$ なので$\frac{0}{0}$をどう扱うべきか、との問題のようです。
この問題については主要な解説書（[2]など）に記載がなく、de Boor自身による実装例のFortranコード[3]でも考慮されていません。おそらく当時（1960年代後半～70年代前半あたり）のFortran処理系では$\frac{0}{0}$は結果$0$になっていたので、支障とならず問題として認識されていなかったのではないかと推測されます。（ゼロ除算エラーは発生せず[4]、結果NaNにもならない）
この問題についての理論面や対処方法を解説したページが以前はあったのですが、見つかりません。（削除されてしまったかも ...）
行列形式
文献[5]に$m\geq 7$の場合の行列形式があり、ひとまずそれを引用することにします。
（※$m\geq 7$とした理由は「avoid smaller polygon special cases」とのことです）
（表記を「その1」に合わせてあります）
| カーブセグメント | $\boldsymbol{R_{bsp}}$ |
|---|---|
| $0$ |  |
| $1$ |  |
| $2$～$m-6$ | Open B-スプラインと同じ |
| $m-5$ |  |
| $m-4$ |  |
B-スプライン用コントロールポイントをベジェ曲線用コントロールポイントに変換する
Open B-スプラインと同様に、左側から$\boldsymbol{R_{bz}}^{-1}$をかけたものが変換行列です。
| カーブセグメント | $\boldsymbol{R_{bsp}}$ |
|---|---|
| $0$ |  |
| $1$ |  |
| $2$～$m-6$ | Open B-スプラインと同じ |
| $m-5$ |  |
| $m-4$ |  |
B-スプライン描画の実装例（Qtアプリの一部抜粋）
QGraphicsScene scene;
QPainterPath pp;
QList<QPointF> cps; // コントロールポイント
int m; // コントロールポイント数
bool bClosed;
bool bClamped;
void drawBsp();
void drawBspSegment(QPointF p0, QPointF p1, QPointF p2, QPointF p3);
void drawClampedBspSegment(QPointF p0, QPointF p1, QPointF p2, QPointF p3, int type);
// B-スプラインを描画する
void MainWindow::drawBsp()
{
pp.clear();
if(bClamped){
if(m < 7)
return; // 6以下は未対応
drawClampedBspSegment(cps[0], cps[1], cps[2], cps[3], 0);
drawClampedBspSegment(cps[1], cps[2], cps[3], cps[4], 1);
for(int i = 2; i < m - 5; i++)
drawBspSegment(cps[i], cps[i + 1], cps[i + 2], cps[i + 3]);
drawClampedBspSegment(cps[m - 5], cps[m - 4], cps[m - 3], cps[m - 2], 2);
drawClampedBspSegment(cps[m - 4], cps[m - 3], cps[m - 2], cps[m - 1], 3);
}else{
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);
}
// Clamped B-スプラインの1セグメントを描画する
void MainWindow::drawClampedBspSegment(QPointF p0, QPointF p1, QPointF p2, QPointF p3, int type)
{
QPointF bzp1, bzp2, bzp3;
switch(type){
case 0:
pp.moveTo(p0);
bzp1 = p1;
bzp2 = (6 * p1 + 6 * p2) / 12;
bzp3 = (3 * p1 + 7 * p2 + 2 * p3) / 12;
break;
case 1:
bzp1 = (8 * p1 + 4 * p2) / 12;
bzp2 = (4 * p1 + 8 * p2) / 12;
bzp3 = (2 * p1 + 8 * p2 + 2 * p3) / 12;
break;
case 2:
bzp1 = (8 * p1 + 4 * p2) / 12;
bzp2 = (4 * p1 + 8 * p2) / 12;
bzp3 = (2 * p1 + 7 * p2 + 3 * p3) / 12;
break;
case 3:
bzp1 = (6 * p1 + 6 * p2) / 12;
bzp2 = p2;
bzp3 = p3;
break;
}
pp.cubicTo(bzp1, bzp2, bzp3);
}
画面・実行例
参考文献
-
B-spline Curves: Definition
https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-curve.html -
Gerald Farin
Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide
ISBN 0-12-249050-9 -
Carl de Boor
A Practical Guide to Splines, pp.134-135
ISBN 0-387-90356-9 -
Stack Overflow -- FORTRAN 77 Divide By Zero Behavior
https://stackoverflow.com/questions/59124365/fortran-77-divide-by-zero-behavior -
Elaine Cohen, Richard F. Riesenfeld
General Matrix Representations for Bezier and B-spline Curves
Computers in Industry 3 (1982) 9-15
https://www.sciencedirect.com/science/article/abs/pii/0166361582900276
関連記事