8. 曲線と曲面

車のボディ、船の船体、此のページの「S」の文字、ゲームのムービーでカメラが飛ぶ経路。
どれも、少なくともデザイナーが保存したファイルの中では、直線や平らな三角形で出来てはいません。
其れらは自由曲線・自由曲面で、少数の点と、其の間を全て埋める式によって表されています。
此の章では其の式を1つずつ組み立てていきます。エルミート曲線、ベジェ曲線、Bスプライン、NURBS、全ての点を通る補間スプライン、そして其れらから作る曲面です。

何故此れが大事なのでしょうか？
CADシステム、フォント形式、ベクタ描画ソフト、アニメーションカーブ、映画用のモデリングツールは全て、正に此の数種類の曲線の上に作られています。
仕組みが分かれば、ペンツールに何故「ハンドル」があるのか、CADファイルの円に何故重みが必要なのか、或るソフトでは1点を動かすと曲線全体が変わるのに別のソフトでは一部しか変わらないのは何故か、が分かる様になります。
検定対策としては、此の章は分野3「モデリング」のシラバス項目曲線・曲面を扱います。
第7章はソリッド全体の表現方法の話でしたが、CADモデルの其のソリッドの面は、殆どの場合此の章の曲面そのものです。
ポリゴンメッシュと細分割曲面は第9章で扱います。

前提として、ベクトルと線型結合（線型代数シリーズ第2章）、外積（第5章）、行列・ベクトル積（第6章）、同次座標（第9章）、そして此のシリーズの第4章のアフィン変換・射影変換と第5章の透視除算を使います。
微分も少し出てきますが、使うのは多項式の微分 $\frac{d}{dt}t^n = n\,t^{n-1}$ だけです。
接線には其れで十分です。

8.1 曲線の3つの表し方

平面上の曲線を書き表す方法は3つあります：

同じ様な形を陽関数 y = f x、陰関数 f x, y = 0、パラメトリックな c t と其の接線ベクトルで表した図

陽関数表現： $y = f(x)$ 。全ての $x$ に対して $y$ が丁度1つ決まります。例： $y = 1.2 - 0.8x^2$ 。
陰関数表現： $f(x, y) = 0$ 。関数が0になる点の集まりが曲線です。例：単位円 $x^2 + y^2 - 1 = 0$ 。 $f$ の符号で何方側に居るかが分かります。 $f < 0$ なら内側、 $f > 0$ なら外側です。
パラメトリック表現（媒介変数表現とも言います）： $\mathbf{c}(t) = (x(t), y(t))$ 。パラメータ $t$ が或る区間を動き、其の各値が1つの点を与えます。例：此れも単位円で、 $0 \le t < 2\pi$ に対して $\mathbf{c}(t) = (\cos t, \sin t)$ 。

其れぞれに得意な事があります：

表現	得意	苦手
陽関数 $y = f(x)$	値の計算、グラフの描画	垂直な接線、閉じた曲線、1つの $x$ に複数の $y$ （円には関数が2つ必要）
陰関数 $f(x, y) = 0$	内外判定、閉じた形	曲線に沿った点の生成（方程式を解く必要がある）
パラメトリック $\mathbf{c}(t)$	順番通りの点の生成、2Dでも3Dでも任意の形、自己交差	内外判定

図の右の曲線は $\mathbf{c}(t) = (t^2 - 1, \; t^3 - t)$ です。
原点で自分自身と交差している（ $t = -1$ と $t = 1$ ）ので、陽関数 $y = f(x)$ では表せませんが、パラメトリック表現なら何の問題もありません。
CGでは、モデリング用の曲線・曲面の殆ど全てにパラメトリック表現を使います。理由は3つあります。
1つ目は描くのが簡単な事です。 $t$ を始めから終わりまで少しずつ進めて、点を繋げば良いだけです。
2つ目は3Dでも全く同じに使える事です。 $z(t)$ を足すだけです。
3つ目は、後で見る様に此の章の曲線は点で制御され、制御点を変換すれば曲線全体が変換される事です。
陰関数曲面にも独自の用途（メタボール、符号付き距離場）があり、第9章で扱います。

接線ベクトル

パラメトリック曲線の各座標を微分すると接線ベクトル $\mathbf{c}'(t) = (x'(t), y'(t))$ が得られます。
其の向きは点が動いている方向で、長さは $t$ が増える時に点が動く速さです。
自己交差する曲線では $\mathbf{c}'(t) = (2t, \; 3t^2 - 1)$ なので、 $t = 1.25$ では：

\mathbf{c}'(1.25) = (2 \cdot 1.25, \; 3 \cdot 1.5625 - 1) = (2.5, \; 3.6875)

此れが図のピンクの矢印です（収まる様に短くして描いています）。
円 $\mathbf{c}(t) = (\cos t, \sin t)$ では $\mathbf{c}'(t) = (-\sin t, \cos t)$ で、長さは常に1、向きは常に半径に垂直です。円の接線は正に其うあるべきです。

向きと速さの違いを覚えておいて下さい。曲線の形は接線の向きだけで決まり、長さはパラメータの進み方で決まります。
同じ円を $(\cos 2t, \sin 2t)$ で描くと、接線の長さは2倍になります。
此の違いが次の節の話の全てです。

何故多項式で、何故3次なのか

此の章の曲線は、各座標に $t$ の多項式を使います。多項式は計算が安く、微分が簡単で、性質を考え易いからです。
但し、次数の高い多項式1本は制御し難いので、長い曲線は短い部分を幾つも繋いで作ります。此れが区分的多項式の曲線で、スプラインと言う言葉の意味です。
（名前の由来は、造船技師や製図者が固定した点に通して滑らかな船体の線を描いた、薄くてしなやかな木の定規です。）

殆どの部分は3次の多項式です：

\mathbf{c}(t) = \mathbf{a}_3 t^3 + \mathbf{a}_2 t^2 + \mathbf{a}_1 t + \mathbf{a}_0, \qquad 0 \le t \le 1

係数ベクトル $\mathbf{a}_k$ が4つあります。
3次は必要な事が全部出来る一番低い次数です。平面内で変曲点（S字）を持てて、3Dでは平面から捩れて出られて（2次曲線は必ず1つの平面上にあります）、4つの係数で丁度両端の点と両端の接線を決められるので、隣の部分と滑らかに繋げられます。
此の章の残りは殆ど、デザイナーが動かせる点から此の4つのベクトルをどう決めるかの話です。

8.2 連続性

2つの部分が出会う所は、どれ位滑らかなのでしょうか？
最初の部分 $\mathbf{a}(t)$ の終わりで次の部分 $\mathbf{b}(t)$ が始まるとします。どちらも $0 \le t \le 1$ です。
滑らかさの測り方は2通りあります。

パラメトリック連続性は、微分をベクトルとして比べます：

$C^0$ （C0連続）：部分同士が繋がっている、 $\mathbf{a}(1) = \mathbf{b}(0)$ 。角があっても構いません。
$C^1$ （C1連続）：更に $\mathbf{a}'(1) = \mathbf{b}'(0)$ 。接線ベクトルが向きも長さも同じ。
$C^2$ （C2連続）：更に $\mathbf{a}''(1) = \mathbf{b}''(0)$ 。2階微分も同じ。

幾何学的連続性は形だけを問います：

$G^0$ ： $C^0$ と同じで、繋がっている事。
$G^1$ ：接線の向きが一致する、つまり或る $k > 0$ で $\mathbf{b}'(0) = k\,\mathbf{a}'(1)$ 。長さは違っても構いません。見た目の角が無くなります。
$G^2$ ：更に曲率が一致し、繋ぎ目の両側で曲線が同じ鋭さで曲がります。

左は2つの曲線が角で出会う様子、右は繋ぎ目での接線ベクトルの向きが同じで長さが違う様子

例題：G1だがC1ではない

$\mathbf{a}(t) = (2t, \; t^2)$ と $\mathbf{b}(t) = (2 + t, \; 1 + t - t^2)$ を考えます。

繋がっているか？ $\mathbf{a}(1) = (2, 1)$ 、 $\mathbf{b}(0) = (2, 1)$ 。繋がっているので $C^0$ かつ $G^0$ です。
接線。 $\mathbf{a}'(t) = (2, \; 2t)$ なので $\mathbf{a}'(1) = (2, 2)$ 。 $\mathbf{b}'(t) = (1, \; 1 - 2t)$ なので $\mathbf{b}'(0) = (1, 1)$ 。
比べる。 $(1, 1) = \tfrac{1}{2}(2, 2)$ で、 $k = \tfrac{1}{2} > 0$ の同じ向きなので、繋ぎ目は $G^1$ です。でも $(1, 1) \ne (2, 2)$ なので $C^1$ ではありません。

画面上では完全に滑らかな繋ぎ目に見えます（図の右半分）。
しかし $t$ を一定の歩幅で進めて曲線上を動く点は、 $(2, 1)$ で突然半分の速さに落ちます。2つ目の部分は $t$ の1単位当たりに進む距離が短いからです。
此の曲線がカメラの経路だったら、其の揺れを感じるでしょう。
そして、形を全く変えずに此れを直せる事に注目して下さい。 $\mathbf{b}$ を2倍の速さで走らせる、つまり $0 \le t \le \tfrac{1}{2}$ で $\tilde{\mathbf{b}}(t) = \mathbf{b}(2t)$ とすれば $\tilde{\mathbf{b}}'(0) = 2\,\mathbf{b}'(0) = (2, 2)$ となり、繋ぎ目は $C^1$ になります。
一言で言えば、G連続性は形の話、C連続性は形とパラメータの付け方の話です。

図の左半分は $C^0$ だけの繋ぎ目です。2つ目の部分は $(1.2, -1.2)$ の向きに出ていき、此れは $(2, 2)$ の正の倍数ではないので角が出来ます。

どの連続性を何に使うか

$G^1$ があれば、シルエットとしては滑らかに見えます。
$G^2$ は光沢のある面で効いてきます。 $G^1$ の繋ぎ目では、映り込みやハイライトの線の曲がり方に目に見える折れが出来ます。車のデザイナーは、見える外板に $G^2$ （以上）を求めます。
$C^1$ と $C^2$ はパラメータが時間の時に効きます。 $C^1$ の経路は速度が、 $C^2$ の経路は加速度まで連続で、カメラワークやアニメーションカーブ（第13章）では其れが欲しくなります。

検定対策として押さえておきたい落とし穴： $C^1$ は普通 $G^1$ を含みますが、必ずではありません。
繋ぎ目で両方の接線ベクトルが零なら、両者は等しい（つまり $C^1$ ）のに向きが無く、其処で曲線が鋭い角を持つ事があります。

8.3 エルミート曲線

3次の部分を一番直接的に決める方法は、何処から始まって何処で終わるか、そしてどの向きに出ていき、どの向きから入ってくるかを指定する事です。
エルミート曲線とは、

\mathbf{c}(0) = \mathbf{p}_0, \qquad \mathbf{c}(1) = \mathbf{p}_1, \qquad \mathbf{c}'(0) = \mathbf{v}_0, \qquad \mathbf{c}'(1) = \mathbf{v}_1

を満たす3次曲線、つまり2つの端点と2つの接線ベクトルで決まる曲線です。

係数を求める

$\mathbf{c}(t) = \mathbf{a}_3 t^3 + \mathbf{a}_2 t^2 + \mathbf{a}_1 t + \mathbf{a}_0$ と $\mathbf{c}'(t) = 3\mathbf{a}_3 t^2 + 2\mathbf{a}_2 t + \mathbf{a}_1$ を4つの条件に代入します：

\begin{aligned} \mathbf{c}(0) &= \mathbf{a}_0 = \mathbf{p}_0 \\ \mathbf{c}'(0) &= \mathbf{a}_1 = \mathbf{v}_0 \\ \mathbf{c}(1) &= \mathbf{a}_3 + \mathbf{a}_2 + \mathbf{a}_1 + \mathbf{a}_0 = \mathbf{p}_1 \\ \mathbf{c}'(1) &= 3\mathbf{a}_3 + 2\mathbf{a}_2 + \mathbf{a}_1 = \mathbf{v}_1 \end{aligned}

最初の2つから $\mathbf{a}_0$ と $\mathbf{a}_1$ が直ぐに決まります。
残りの2つは $\mathbf{a}_2$ と $\mathbf{a}_3$ の連立方程式で、解くと次の様になります：

\mathbf{a}_2 = 3(\mathbf{p}_1 - \mathbf{p}_0) - 2\mathbf{v}_0 - \mathbf{v}_1, \qquad \mathbf{a}_3 = 2(\mathbf{p}_0 - \mathbf{p}_1) + \mathbf{v}_0 + \mathbf{v}_1

基底関数

4つの入力其れぞれに掛かる項を纏めると、曲線は重み付きの和になります：

\mathbf{c}(t) = H_0(t)\,\mathbf{p}_0 + H_1(t)\,\mathbf{p}_1 + H_2(t)\,\mathbf{v}_0 + H_3(t)\,\mathbf{v}_1

H_0 = 2t^3 - 3t^2 + 1, \quad H_1 = -2t^3 + 3t^2, \quad H_2 = t^3 - 2t^2 + t, \quad H_3 = t^3 - t^2

此の4つの多項式がエルミート基底関数です。
此れが此の章の全ての曲線に共通する形です。 $t$ の決まった基底関数に、デザイナーが操作するデータを掛けて足し合わせます。
基底関数が曲線の種類の性格を決め、データが個々の曲線を決めます。

t が0から1までの4つのエルミート基底関数と4つの3次バーンスタイン多項式。t = 0.5 での値に印を付けた図

左の図から仕組みが読み取れます。 $t = 0$ では $H_0$ だけが1なので曲線は $\mathbf{p}_0$ から始まり、 $t = 1$ では $H_1$ だけが1です。 $H_2$ と $H_3$ は両端で0ですが片方の端で傾きが1になっていて、其処から接線が入り込みます。
全ての $t$ で $H_0 + H_1 = 1$ なので、点の部分はきちんとした重み付き平均になっています。

行列表現

同じ物を、 $t$ の冪の行ベクトル、決まった行列、データの列の積として書けます：

\mathbf{c}(t) = \begin{bmatrix} t^3 & t^2 & t & 1 \end{bmatrix} \begin{bmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} \mathbf{p}_0 \\ \mathbf{p}_1 \\ \mathbf{v}_0 \\ \mathbf{v}_1 \end{bmatrix}

読み方：行ベクトルと行列の積が4つの基底関数の値になり（行列の1列目が $H_0$ の係数、という具合です）、其れが4つのデータベクトルに掛かります。
右の列は「点の列」なので、最後の段階はxについて1回、yについて1回（及びz）行います。
全ての3次曲線の種類にこういう基底行列があり、行列を替えると曲線の種類が替わります。

例題

$\mathbf{p}_0 = (0, 0)$ 、 $\mathbf{p}_1 = (8, 0)$ 、 $\mathbf{v}_0 = (6, 12)$ 、 $\mathbf{v}_1 = (0, -12)$ とします。
$t = 0.5$ では $H_0 = 2 \cdot 0.125 - 3 \cdot 0.25 + 1 = 0.5$ 、 $H_1 = 0.5$ 、 $H_2 = 0.125 - 0.5 + 0.5 = 0.125$ 、 $H_3 = 0.125 - 0.25 = -0.125$ です（図の点）。従って

\begin{aligned} \mathbf{c}(0.5) &= 0.5\,(0, 0) + 0.5\,(8, 0) + 0.125\,(6, 12) - 0.125\,(0, -12) \\ &= (4, 0) + (0.75, 1.5) + (0, 1.5) = (4.75, \; 3) \end{aligned}

係数でも確かめられます。 $\mathbf{a}_2 = 3(8, 0) - 2(6, 12) - (0, -12) = (12, -12)$ 、 $\mathbf{a}_3 = 2(-8, 0) + (6, 12) + (0, -12) = (-10, 0)$ なので $\mathbf{c}(t) = (-10t^3 + 12t^2 + 6t, \; -12t^2 + 12t)$ 、 $t = 0.5$ では $(-1.25 + 3 + 3, \; -3 + 6) = (4.75, 3)$ です。
此の点を覚えておいて下さい。次の節では全く別の方向から同じ点に辿り着きます。

エルミート曲線の使い道

接線が分かっている場面では、エルミート形式が自然です。各キーに「イン」と「アウト」の接線があるアニメーションソフトのキーフレームカーブ、モーションパス、そして部分同士の接続です。隣り合う部分が端点と接線ベクトルを共有すれば、繋ぎ目は自動的に $C^1$ になります。
弱点は、接線ベクトルを手で編集するのが扱い難い事で、次の曲線は正に其れを解決します。

8.4 ベジェ曲線

ベジェ曲線は制御点 $\mathbf{p}_0, \dots, \mathbf{p}_n$ の列で制御されます。
曲線は最初の制御点から始まり、最後の制御点で終わり、間の制御点の方へ引き寄せられますが、（普通は）其れらには触れません。
制御点を順に結んだ物が制御多角形で、曲線は其の大まかな形を滑らかにした写しの様に付いていきます。
此の曲線は1960年頃、自動車業界で独立に生まれました。シトロエンのポール・ド・カステリョ（1959年に文書化）と、ルノーのピエール・ベジェです。発表したのがベジェだったので、其の名前が定着しました。
今では全てのベクタ描画ソフト、フォント（TrueTypeのアウトラインは2次ベジェ曲線、PostScriptやCFFのアウトラインは3次ベジェ曲線）、SVGのパス、CSSの cubic-bezier() によるイージングカーブに使われています。

バーンスタイン多項式

$n + 1$ 個の制御点を持つ $n$ 次のベジェ曲線は次の通りです：

\mathbf{c}(t) = \sum_{i=0}^{n} B_{i,n}(t)\,\mathbf{p}_i, \qquad B_{i,n}(t) = \frac{n!}{i!\,(n - i)!}\,t^i (1 - t)^{n - i}, \qquad 0 \le t \le 1

重み $B_{i,n}$ がバーンスタイン多項式（バーンスタイン基底関数）です。
前に付いている分数はパスカルの三角形でお馴染みの二項係数で、 $n = 3$ なら1, 3, 3, 1です。
従って3次ベジェ曲線は

\mathbf{c}(t) = (1 - t)^3\,\mathbf{p}_0 + 3t(1 - t)^2\,\mathbf{p}_1 + 3t^2(1 - t)\,\mathbf{p}_2 + t^3\,\mathbf{p}_3

基底関数の図の右半分を見て下さい。
4つの重みは決して負にならず、常に足すと1になります。其れらは $\left((1 - t) + t\right)^3 = 1^3$ を展開した項だからです。
つまり曲線の全ての点は制御点の重み付き平均で、此の1つの事実から以下の性質の殆どが出てきます。

$t = 0.5$ での重みは $\tfrac{1}{8}, \tfrac{3}{8}, \tfrac{3}{8}, \tfrac{1}{8}$ です。
制御点を $\mathbf{p}_0 = (0, 0)$ 、 $\mathbf{p}_1 = (2, 4)$ 、 $\mathbf{p}_2 = (8, 4)$ 、 $\mathbf{p}_3 = (8, 0)$ とすると：

\mathbf{c}(0.5) = \tfrac{1}{8}(0, 0) + \tfrac{3}{8}(2, 4) + \tfrac{3}{8}(8, 4) + \tfrac{1}{8}(8, 0) = \left(\tfrac{0 + 6 + 24 + 8}{8}, \; \tfrac{0 + 12 + 12 + 0}{8}\right) = (4.75, \; 3)

エルミートの例題と同じ点です。
偶然ではありません。理由は直ぐ後で分かります。

ド・カステリョのアルゴリズム

同じ点を、線型補間 $\operatorname{lerp}(\mathbf{a}, \mathbf{b}, t) = (1 - t)\,\mathbf{a} + t\,\mathbf{b}$ （ $\mathbf{a}$ から $\mathbf{b}$ へ割合 $t$ だけ進んだ点）だけで計算する綺麗な方法があります。
ド・カステリョのアルゴリズム：制御多角形の隣り合う点の組を其れぞれ補間すると、点が1つ減ります。新しい点で此れを繰り返し、1点だけ残ったら其れが $\mathbf{c}(t)$ です。

例の曲線で $t = 0.5$ の場合をやってみましょう。補間は全て中点を取るだけです：

\begin{aligned} \mathbf{p}_{01} &= \tfrac{1}{2}\left((0, 0) + (2, 4)\right) = (1, 2) \\ \mathbf{p}_{12} &= \tfrac{1}{2}\left((2, 4) + (8, 4)\right) = (5, 4) \\ \mathbf{p}_{23} &= \tfrac{1}{2}\left((8, 4) + (8, 0)\right) = (8, 2) \\ \mathbf{p}_{012} &= \tfrac{1}{2}\left((1, 2) + (5, 4)\right) = (3, 3) \\ \mathbf{p}_{123} &= \tfrac{1}{2}\left((5, 4) + (8, 2)\right) = (6.5, 3) \\ \mathbf{p}_{0123} &= \tfrac{1}{2}\left((3, 3) + (6.5, 3)\right) = (4.75, 3) \end{aligned}

制御点 0,0 と 2,4 と 8,4 と 8,0 に対する t = 0.5 でのド・カステリョの作図。途中の点と曲線上の点 4.75, 3

最初の3行が1段目、次の2行が2段目、最後の1行が3段目です。
最後の点 $(4.75, 3)$ は、バーンスタイン多項式による計算と完全に一致します。
0.5以外の $t$ では、「中点を取る」の代わりに「割合 $t$ だけ進む」で同じ事をします（課題1で $t = \tfrac{1}{4}$ をやります）。
何故此れで上手くいくのでしょうか？
各段で $(1 - t)$ か $t$ が掛かり、3段の後には $\mathbf{p}_i$ は $\frac{3!}{i!\,(3 - i)!}$ 通りの経路で、其々 $t^i(1 - t)^{3 - i}$ の重みで届きます。此れが正にバーンスタイン多項式です。
ド・カステリョのアルゴリズムは点の重み付き平均しか取らないので数値的に非常に安定で、其の為ソフトウェアでベジェ曲線を評価する標準的な方法になっています。

此の作図には、おまけが2つ付いてきます：

接線。 最後の線分、 $\mathbf{p}_{012}$ から $\mathbf{p}_{123}$ は $\mathbf{c}(t)$ で曲線に接し、3次では $\mathbf{c}'(t) = 3\,(\mathbf{p}_{123} - \mathbf{p}_{012})$ です。此処では $3\,((6.5, 3) - (3, 3)) = (10.5, 0)$ で、 $t = 0.5$ では曲線は水平に動いていて、一番高い所に居ます。
分割。三角形の左の辺に沿った点 $\mathbf{p}_0, \mathbf{p}_{01}, \mathbf{p}_{012}, \mathbf{p}_{0123}$ = $(0, 0), (1, 2), (3, 3), (4.75, 3)$ は曲線の左半分の制御点で、右の辺 $(4.75, 3), (6.5, 3), (8, 2), (8, 0)$ は右半分の制御点です。どちらの半分も又3次ベジェ曲線で、其の制御多角形は元の物より曲線に密着しています。

レンダラーはベジェ曲線を分割で描きます。各部分の制御多角形が殆ど直線になるまで分割して、其の直線を描くのです。
同じ手は曲線同士の交点を求めるのにも使え（両方を小さくなるまで分割する）、フォントの描画の土台にもなっています。

微分と端点での接線

バーンスタイン形式を微分すると、次数が1つ低いベジェ曲線になり、其の制御点は元の制御点の差です：

\mathbf{c}'(t) = n \sum_{i=0}^{n-1} B_{i,n-1}(t)\,(\mathbf{p}_{i+1} - \mathbf{p}_i)

両端では1つの項だけが残ります：

\mathbf{c}'(0) = n\,(\mathbf{p}_1 - \mathbf{p}_0), \qquad \mathbf{c}'(1) = n\,(\mathbf{p}_n - \mathbf{p}_{n-1})

曲線は制御多角形の最初の辺に沿って $\mathbf{p}_0$ を出発し、最後の辺に沿って $\mathbf{p}_n$ に到着します。
例の3次曲線では $\mathbf{c}'(0) = 3\,((2, 4) - (0, 0)) = (6, 12)$ 、 $\mathbf{c}'(1) = 3\,((8, 0) - (8, 4)) = (0, -12)$ です。
此れは正にエルミートの例題の $\mathbf{v}_0$ と $\mathbf{v}_1$ で、どちらも $(4.75, 3)$ になった理由は、同じ曲線だったからです。

3次ベジェとエルミートの変換

3次ベジェ曲線とエルミート曲線は、同じ3次曲線の集まりの2通りの書き方です：

\begin{aligned} &\text{ベジェ} \to \text{エルミート：} && \mathbf{v}_0 = 3(\mathbf{p}_1 - \mathbf{p}_0), \quad \mathbf{v}_1 = 3(\mathbf{p}_3 - \mathbf{p}_2) \\ &\text{エルミート} \to \text{ベジェ：} && \mathbf{p}_1 = \mathbf{p}_0 + \tfrac{1}{3}\mathbf{v}_0, \quad \mathbf{p}_2 = \mathbf{p}_3 - \tfrac{1}{3}\mathbf{v}_1 \end{aligned}

（8.3節で $\mathbf{p}_1$ と呼んだエルミートの終点は、此処ではベジェの $\mathbf{p}_3$ です。）
此れがIllustratorやInkscape、どの描画ソフトのペンツールにもある「ハンドル」の正体です。ハンドルは内側の制御点で、其れをドラッグすると、アンカーポイントでの接線が其の長さの3倍で決まります。

3次ベジェにも基底行列があります：

\mathbf{c}(t) = \begin{bmatrix} t^3 & t^2 & t & 1 \end{bmatrix} \begin{bmatrix} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} \mathbf{p}_0 \\ \mathbf{p}_1 \\ \mathbf{p}_2 \\ \mathbf{p}_3 \end{bmatrix}

$t = 0.5$ なら、行ベクトルと此の行列の積は又 $\left(\tfrac{1}{8}, \tfrac{3}{8}, \tfrac{3}{8}, \tfrac{1}{8}\right)$ になります。

性質

次の性質は確実に覚えておきましょう：

端点補間：曲線は $\mathbf{p}_0$ と $\mathbf{p}_n$ を通り、一般には其れ以外の制御点は通りません。
端点での接線：其処で曲線は制御多角形の最初と最後の辺に接します。
凸包性：曲線全体が制御点の凸包、つまり制御点を含む一番小さい凸な領域（点の周りに輪ゴムを掛けた形）の中にあります。重みが負でなく足すと1になる事から出てきます。素早い除外に使われます。2本の曲線の凸包が重ならなければ曲線は交わらず、凸包が丸ごと画面外なら曲線も画面外です。
アフィン不変性：曲線にアフィン変換（第4章）を施したければ、制御点に施して新しい点の曲線を描けば、変換した曲線と完全に一致します。アフィン変換は、重みの和が1の重み付き平均を保つからです。
変動減少性：平面内では、どんな直線も、制御多角形と交わる回数より多く曲線と交わる事はありません。曲線が制御多角形よりうねる事はありません。
大域的制御：全てのバーンスタイン多項式は $0 < t < 1$ で正なので、どれか1つの制御点を動かすと、端点以外の曲線の全ての点が動きます。
次数が点の数で決まる：制御点が $n + 1$ 個なら、次数は必ず $n$ です。

左は制御点の凸包の中にある3次ベジェ曲線、右は p2 を 8,4 から 8,7 に動かすと端点以外の全ての点が動く様子

アフィン不変性を数値で確かめてみましょう。90°回転して $(1, 2)$ だけ平行移動する変換、 $(x, y) \mapsto (-y + 1, \; x + 2)$ を使います。
制御点は $(1, 2), (-3, 4), (-3, 10), (1, 10)$ になり、 $t = 0.5$ のバーンスタインの重みで $\left(\tfrac{1 - 9 - 9 + 1}{8}, \tfrac{2 + 12 + 30 + 10}{8}\right) = (-2, 6.75)$ です。
元の曲線上の点 $(4.75, 3)$ を直接変換すると $(-3 + 1, \; 4.75 + 2) = (-2, 6.75)$ 。
同じ点です。
但し注意して下さい。此れが成り立つのはアフィン変換だけで、制御点を透視投影しても、投影した曲線にはなりません。
此の話はNURBSで又出てきます。

次数上げ

形を変えずに、もっと高い次数の曲線が欲しい事があります。例えば、3次しか扱えないシステムに2次の部分を入れる場合です。
次数上げは、曲線を変えずに $n + 1$ 個の制御点を $n + 2$ 個に変えます：

\mathbf{q}_0 = \mathbf{p}_0, \qquad \mathbf{q}_i = \frac{i}{n + 1}\,\mathbf{p}_{i-1} + \left(1 - \frac{i}{n + 1}\right)\mathbf{p}_i \quad (1 \le i \le n), \qquad \mathbf{q}_{n+1} = \mathbf{p}_n

例： $(0, 0), (3, 6), (6, 0)$ の2次曲線は、 $\mathbf{q}_1 = \tfrac{1}{3}(0, 0) + \tfrac{2}{3}(3, 6) = (2, 4)$ 、 $\mathbf{q}_2 = \tfrac{2}{3}(3, 6) + \tfrac{1}{3}(6, 0) = (4, 4)$ の3次曲線になります。
$t = 0.5$ で確かめると、2次曲線は $\tfrac{1}{4}(0, 0) + \tfrac{1}{2}(3, 6) + \tfrac{1}{4}(6, 0) = (3, 3)$ 、3次曲線は $\tfrac{1}{8}(0, 0) + \tfrac{3}{8}(2, 4) + \tfrac{3}{8}(4, 4) + \tfrac{1}{8}(6, 0) = (3, 3)$ です。
フォント変換ツールがTrueTypeの2次のアウトラインを劣化無しに3次に変換出来るのは此の為です。

ベジェ曲線の接続

長い形は3次の部分の連なりです。
最初の部分の制御点を $\mathbf{p}_0, \dots, \mathbf{p}_3$ 、次の部分を $\mathbf{q}_0, \dots, \mathbf{q}_3$ とします。
端点での接線の式から：

$C^0$ ： $\mathbf{q}_0 = \mathbf{p}_3$ 。
$G^1$ ：更に $\mathbf{p}_2$ 、 $\mathbf{p}_3$ 、 $\mathbf{q}_1$ が1本の直線上にあり、 $\mathbf{p}_3$ が他の2点の間にある。
$C^1$ ：更に辺の長さも等しい、 $\mathbf{q}_1 - \mathbf{q}_0 = \mathbf{p}_3 - \mathbf{p}_2$ 。つまり $\mathbf{q}_1 = 2\mathbf{p}_3 - \mathbf{p}_2$ （ $\mathbf{p}_3$ に関する $\mathbf{p}_2$ の対称点）。

p3 = q0 で繋いだ2つの3次ベジェ曲線。角がある場合、辺が一直線だが長さが違う場合、一直線で長さも等しい場合

図の最初の部分は $(0, 0), (1, 3), (4, 3), (5, 1)$ で、最後の辺は $\mathbf{p}_3 - \mathbf{p}_2 = (1, -2)$ です。
右では $\mathbf{q}_1 = (5, 1) + (1, -2) = (6, -1)$ で $C^1$ になります。
真ん中の $\mathbf{q}_1 = (5, 1) + 0.5\,(1, -2) = (5.5, 0)$ は同じ直線上ですが半分の距離しかなく、8.2節の例と同じく $G^1$ だが $C^1$ ではありません。
左の $\mathbf{q}_1 = (6, 3)$ は直線から外れていて、角が見えます。
此れが描画ソフトの「スムーズ」なアンカーポイント（ハンドルが一直線に固定）と「コーナー」のアンカーポイントの違いで、ハンドルの長さまで揃える「対称」オプションにすると $C^1$ になります。
繋ぎ目で $C^2$ を手で保つのはずっと難しく、其れが次の曲線の種類が生まれた理由の1つです。

8.5 Bスプライン曲線

ベジェ曲線には、長くて複雑な形にとって欠点が2つあります。全ての制御点が曲線全体に影響する事と、制御点を増やすと次数が上がる事です。
両方を避ける普通の方法は3次の部分を繋ぐ事ですが、其れだとデザイナーが全ての繋ぎ目で連続性の条件を守り続けなければなりません。
Bスプライン曲線は此の接続を自動でやってくれます。制御点は幾つでも良く、次数は低いまま固定、局所制御が出来て、3次なら $C^2$ 連続性が最初から組み込まれています。

ノットとノットベクトル

次数 $p$ のBスプラインは、 $p$ 次の区分的多項式です。
階数は $k = p + 1$ で、1つの部分の係数の数です。3次Bスプラインは次数3、階数4です。（注意：Bスプラインを階数で呼ぶ本と次数で呼ぶ本があります。）
部分同士はノットと呼ばれるパラメータ値で出会い、ノットは減少しない列のノットベクトル $(t_0, t_1, \dots, t_m)$ に並べます。
制御点が $n + 1$ 個、次数が $p$ なら、ノットベクトルの要素数は $m + 1 = n + p + 2$ です。

曲線は此れも制御点の重み付き和です：

\mathbf{c}(t) = \sum_{i=0}^{n} N_{i,p}(t)\,\mathbf{p}_i

重み $N_{i,p}(t)$ がBスプライン基底関数で、ノットからコックス・ド・ブーアの漸化式で作ります：

N_{i,0}(t) = \begin{cases} 1 & t_i \le t < t_{i+1} \\ 0 & \text{其れ以外} \end{cases}

N_{i,p}(t) = \frac{t - t_i}{t_{i+p} - t_i}\,N_{i,p-1}(t) + \frac{t_{i+p+1} - t}{t_{i+p+1} - t_{i+1}}\,N_{i+1,p-1}(t)

分母が0の分数は0と見做す、という約束付きです（ノットが重なっている時に起こります）。
0次は、1つのノット区間で1、其れ以外で0の箱です。
1段上がる毎に、1つ下の次数の隣り合う2つの関数を0から1に上がる傾斜で混ぜるので、1次はテント、2次は3区間に跨がる滑らかな山、3次は4区間に跨がる釣鐘になります。

名前を知っておきたいノットベクトルは3種類あります：

一様：等間隔のノット、例えば $(0, 1, 2, 3, \dots)$ 。全ての基底関数が互いにずらした写しです。曲線は一般に制御点で始まったり終わったりしません。
開一様（クランプとも言います）：最初と最後のノットを $p + 1$ 回繰り返し、内側のノットは等間隔、例えば $p = 2$ なら $(0, 0, 0, 1, 2, 2, 2)$ 。此れだと曲線はベジェ曲線と同じく $\mathbf{p}_0$ で始まり $\mathbf{p}_n$ で終わり、最初と最後の辺に接します。
非一様：其れ以外の間隔で、内側のノットの重複も含みます。 $r$ 回重なったノットでは連続性が $C^{p-1}$ から $C^{p-r}$ に下がるので、滑らかな曲線にわざと折り目や角を入れる事が出来ます。

コックス・ド・ブーアの例題

次数 $p = 2$ 、制御点4つ（ $n = 3$ ）なので、ノットは $n + p + 2 = 7$ 個。開一様のベクトル

(t_0, \dots, t_6) = (0, 0, 0, 1, 2, 2, 2)

を使います。
パラメータは0から2まで動き、部分は $[0, 1)$ と $[1, 2]$ の2つです。
区間 $[t_2, t_3) = [0, 1)$ にある $t = 0.5$ で評価してみましょう。

0次。 其の区間の箱だけが1です： $N_{2,0}(0.5) = 1$ 、其れ以外の $N_{i,0}(0.5) = 0$ 。

1次。 $N_{2,0}$ を使う関数だけが0でない可能性があり、其れは $N_{1,1}$ と $N_{2,1}$ です：

\begin{aligned} N_{1,1} &= \frac{0.5 - t_1}{t_2 - t_1}N_{1,0} + \frac{t_3 - 0.5}{t_3 - t_2}N_{2,0} = \frac{0.5 - 0}{0 - 0} \cdot 0 + \frac{1 - 0.5}{1 - 0} \cdot 1 = 0 + 0.5 = 0.5 \\ N_{2,1} &= \frac{0.5 - t_2}{t_3 - t_2}N_{2,0} + \frac{t_4 - 0.5}{t_4 - t_3}N_{3,0} = \frac{0.5 - 0}{1 - 0} \cdot 1 + \frac{2 - 0.5}{2 - 1} \cdot 0 = 0.5 \end{aligned}

（ $N_{1,1}$ の最初の分数は分母が $0 - 0$ なので0と見做します。）

2次。 今度は $N_{0,2}$ 、 $N_{1,2}$ 、 $N_{2,2}$ が0でない可能性があります：

\begin{aligned} N_{0,2} &= \frac{0.5 - t_0}{t_2 - t_0}N_{0,1} + \frac{t_3 - 0.5}{t_3 - t_1}N_{1,1} = 0 + \frac{1 - 0.5}{1 - 0} \cdot 0.5 = 0.25 \\ N_{1,2} &= \frac{0.5 - t_1}{t_3 - t_1}N_{1,1} + \frac{t_4 - 0.5}{t_4 - t_2}N_{2,1} = \frac{0.5}{1} \cdot 0.5 + \frac{1.5}{2} \cdot 0.5 = 0.25 + 0.375 = 0.625 \\ N_{2,2} &= \frac{0.5 - t_2}{t_4 - t_2}N_{2,1} + \frac{t_5 - 0.5}{t_5 - t_3}N_{3,1} = \frac{0.5}{2} \cdot 0.5 + \frac{1.5}{1} \cdot 0 = 0.125 \end{aligned}

そして $N_{3,2}(0.5) = 0$ です。
確認： $0.25 + 0.625 + 0.125 = 1$ 。
Bスプライン基底関数も、何処でも足すと1になり、決して負になりません。なので此処でも曲線の全ての点は重み付き平均です。
制御点を $\mathbf{p}_0 = (0, 0)$ 、 $\mathbf{p}_1 = (2, 4)$ 、 $\mathbf{p}_2 = (6, 4)$ 、 $\mathbf{p}_3 = (8, 0)$ とすると：

\mathbf{c}(0.5) = 0.25\,(0, 0) + 0.625\,(2, 4) + 0.125\,(6, 4) = (1.25 + 0.75, \; 2.5 + 0.5) = (2, \; 3)

内側のノット $t = 1$ では、同じ漸化式から $N_{1,2}(1) = N_{2,2}(1) = 0.5$ 、他は0となるので、 $\mathbf{c}(1) = \tfrac{1}{2}\left((2, 4) + (6, 4)\right) = (4, 4)$ 、真ん中の辺の中点です。
（重複の無いノットの2次Bスプラインでは一般に、繋ぎ目は制御多角形の辺の中点に来ます。）

左はノットベクトル 0,0,0,1,2,2,2 の4つの2次Bスプライン基底関数と t = 0.5 での値、右は其の曲線で c 0.5 = 2,3 と c 1 = 4,4

ノットベクトルがクランプされているので曲線は $\mathbf{p}_0$ で始まり $\mathbf{p}_3$ で終わりますが、 $\mathbf{p}_1$ と $\mathbf{p}_2$ には触れない事に注目して下さい。
実際の評価にはド・ブーアのアルゴリズムを使います。此れはド・カステリョのアルゴリズムを一般化した物で、ノットから取った比で制御点を補間します。ですが定義はコックス・ド・ブーアの漸化式で、紙の上で練習する価値があるのも此方です。

局所制御

$N_{i,p}$ は $t_i$ から $t_{i+p+1}$ までの $p + 1$ 区間（其の台）の外では0です。
従って制御点 $\mathbf{p}_i$ が影響するのは $t_i \le t < t_{i+p+1}$ の部分だけで、逆に曲線の各部分は $p + 1$ 個（3次なら4個）の制御点だけで決まります。
此れが局所制御で、Bスプラインの一番大きな実用上の利点です。

同じ9つの制御点による8次ベジェ曲線とクランプした3次Bスプライン。p4 を上に動かすとベジェ曲線は全体が変わるが、Bスプラインは真ん中だけが変わる

どちらの曲線も同じ9つの制御点を使っていて、どちらも $\mathbf{p}_4$ を3だけ上に動かしました。
ベジェ曲線（8次）は全体が変わり、其の上制御多角形にかなり緩くしか付いていきません。
3次Bスプラインはクランプしたノットベクトル $(0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 6, 6, 6)$ を使っていて、 $N_{4,3}$ は $[t_4, t_8) = [1, 5)$ にしか無いので、変わったのは2つのオレンジの点の間のオレンジの部分だけです。黄色の両端は元の場所に其の儘あります（破線の古い曲線は其の下に隠れています）。
Bスプラインには更に強い凸包性もあります。各部分は其の部分自身の $p + 1$ 個の制御点の凸包の中にあり、此れは全ての点の凸包よりずっと曲線に密着しています。

一様3次Bスプライン

一様なノットなら、3次の部分は全て同じ式になります。
4つの制御点 $\mathbf{p}_i, \dots, \mathbf{p}_{i+3}$ を使う部分は、局所的なパラメータ $0 \le t \le 1$ で次の通りです：

\mathbf{c}(t) = \frac{1}{6} \begin{bmatrix} t^3 & t^2 & t & 1 \end{bmatrix} \begin{bmatrix} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 0 & 3 & 0 \\ 1 & 4 & 1 & 0 \end{bmatrix} \begin{bmatrix} \mathbf{p}_i \\ \mathbf{p}_{i+1} \\ \mathbf{p}_{i+2} \\ \mathbf{p}_{i+3} \end{bmatrix}

重みは $t = 0$ で $\left(\tfrac{1}{6}, \tfrac{4}{6}, \tfrac{1}{6}, 0\right)$ 、 $t = 0.5$ で $\left(\tfrac{1}{48}, \tfrac{23}{48}, \tfrac{23}{48}, \tfrac{1}{48}\right)$ 、 $t = 1$ で $\left(0, \tfrac{1}{6}, \tfrac{4}{6}, \tfrac{1}{6}\right)$ です。
$(0, 0), (3, 6), (9, 6), (12, 0)$ なら：

\begin{aligned} \mathbf{c}(0) &= \tfrac{1}{6}\left((0, 0) + 4\,(3, 6) + (9, 6)\right) = \tfrac{1}{6}(21, 30) = (3.5, \; 5) \\ \mathbf{c}(0.5) &= \tfrac{1}{48}\left((0, 0) + 23\,(3, 6) + 23\,(9, 6) + (12, 0)\right) = \tfrac{1}{48}(288, 276) = (6, \; 5.75) \\ \mathbf{c}(1) &= \tfrac{1}{6}\left((3, 6) + 4\,(9, 6) + (12, 0)\right) = \tfrac{1}{6}(51, 30) = (8.5, \; 5) \end{aligned}

此の部分はどの制御点も通りません。一様Bスプラインは制御点を近似します。

何故 $C^2$ なのでしょうか？
行列表現を2回微分して、両端で評価します。
$\mathbf{p}_i, \dots, \mathbf{p}_{i+3}$ を使う部分の終わりでは

\mathbf{c}(1) = \tfrac{1}{6}(\mathbf{p}_{i+1} + 4\mathbf{p}_{i+2} + \mathbf{p}_{i+3}), \quad \mathbf{c}'(1) = \tfrac{1}{2}(\mathbf{p}_{i+3} - \mathbf{p}_{i+1}), \quad \mathbf{c}''(1) = \mathbf{p}_{i+1} - 2\mathbf{p}_{i+2} + \mathbf{p}_{i+3}

$\mathbf{p}_{i+1}, \dots, \mathbf{p}_{i+4}$ を使う次の部分の始まりでは

\mathbf{c}(0) = \tfrac{1}{6}(\mathbf{p}_{i+1} + 4\mathbf{p}_{i+2} + \mathbf{p}_{i+3}), \quad \mathbf{c}'(0) = \tfrac{1}{2}(\mathbf{p}_{i+3} - \mathbf{p}_{i+1}), \quad \mathbf{c}''(0) = \mathbf{p}_{i+1} - 2\mathbf{p}_{i+2} + \mathbf{p}_{i+3}

制御点が何であっても、3つとも全く同じです。
つまり連続性は基底関数そのものから来ていて、デザイナーは点を自由に動かしても決して其れを壊しません。
取引は此うです。制御点を通る事を諦める代わりに、自動的な $C^2$ の滑らかさと局所制御が手に入ります。

ベジェ曲線との関係

ベジェ曲線はBスプラインの特別な場合です。
制御点4つ、ノットベクトル $(0, 0, 0, 0, 1, 1, 1, 1)$ の3次Bスプラインの基底関数は丁度バーンスタイン多項式なので、其れは3次ベジェ曲線そのものです。
逆方向には、内側の各ノットが $p$ 回重なるまでノットを挿入すれば（ノット挿入）、どんなBスプラインもベジェの部分に切り分けられます。多くのレンダラーやファイル変換ツールは此の方法で扱っています。

8.6 NURBS

今までのどの曲線にも解けない問題があります。正確な円を描く事です。
多項式の曲線では近似しか出来ません（理由は課題5で考えます）。
此れはCADにとって本物の問題です。ドリルの穴、円柱、フィレットは正確に丸くなければなりません。
答えはNURBS（ナーブス）、非一様有理Bスプライン（non-uniform rational B-spline）です。任意のノット（非一様）を持ち、点を重み付きの和で割る（有理、つまり多項式の比）Bスプラインです。

重みと有理形式

全ての制御点に重み $w_i > 0$ を与えます：

\mathbf{c}(t) = \frac{\sum_{i=0}^{n} N_{i,p}(t)\,w_i\,\mathbf{p}_i}{\sum_{i=0}^{n} N_{i,p}(t)\,w_i}

全ての重みが等しければ約分されて、普通のBスプラインに戻ります。
$w_i$ を大きくすると曲線は $\mathbf{p}_i$ に引き寄せられ、小さくすると遠ざかります。

同じ式は同次座標（線型代数シリーズ第9章）で読むとずっと簡単になります。
各制御点を重み付きの同次座標の点、2Dなら $\mathbf{p}^w_i = (w_i x_i, \; w_i y_i, \; w_i)$ 、3Dなら $(w_i x_i, w_i y_i, w_i z_i, w_i)$ と書きます。
すると：

同次座標の点で、普通の多項式のBスプライン（又はベジェ曲線）を評価する。
最後の座標で割る。

此の2番目の段階は、正に第5章の透視除算です。
つまりNURBS曲線は、1つ高い次元の多項式曲線を、wでの除算で元に投影した物です。

正確な4分の1円

次の制御点を持つ2次ベジェ曲線（ノット $(0, 0, 0, 1, 1, 1)$ のNURBS曲線でもあります）を考えます：

\mathbf{p}_0 = (1, 0), \quad \mathbf{p}_1 = (1, 1), \quad \mathbf{p}_2 = (0, 1), \qquad w_0 = 1, \quad w_1 = \tfrac{\sqrt{2}}{2} \approx 0.7071, \quad w_2 = 1

$t = 0.5$ での2次のバーンスタインの重みは $\left(\tfrac{1}{4}, \tfrac{1}{2}, \tfrac{1}{4}\right)$ です。
同次座標の制御点は $(1, 0, 1)$ 、 $(0.7071, 0.7071, 0.7071)$ 、 $(0, 1, 1)$ 。
段階1、同次座標での多項式曲線：

\begin{aligned} &\tfrac{1}{4}(1, 0, 1) + \tfrac{1}{2}(0.7071, 0.7071, 0.7071) + \tfrac{1}{4}(0, 1, 1) \\ &= (0.25 + 0.35355, \; 0.35355 + 0.25, \; 0.25 + 0.35355 + 0.25) \\ &= (0.60355, \; 0.60355, \; 0.85355) \end{aligned}

段階2、最後の座標で割る：

\mathbf{c}(0.5) = \left(\frac{0.60355}{0.85355}, \; \frac{0.60355}{0.85355}\right) = (0.70711, \; 0.70711)

そして $0.70711^2 + 0.70711^2 = 0.5 + 0.5 = 1$ 。45°の位置で、単位円の上に正確に乗っています。
$t = 0.25$ でも同じ段階で $(0.92979, \; 0.36809)$ が得られ、 $0.92979^2 + 0.36809^2 = 0.86451 + 0.13549 = 1.00000$ です。
実は全ての $t$ で $x(t)^2 + y(t)^2 = 1$ が成り立ちます（課題5）。

同じ3点の普通の有理でない2次ベジェ曲線（重みが全て1）と比べてみましょう。 $t = 0.5$ では $\tfrac{1}{4}(1, 0) + \tfrac{1}{2}(1, 1) + \tfrac{1}{4}(0, 1) = (0.75, 0.75)$ で、中心からの距離は $\sqrt{0.75^2 + 0.75^2} \approx 1.0607$ 、6%外に出ています。
此れは円ではなく放物線です。

制御点 1,0 と 1,1 と 0,1 の有理2次ベジェ曲線。真ん中の重みが 2、1、2分の√2、0.5 で、其々双曲線、放物線、円、楕円になる

図は其の仲間全体を示しています。
両端の重みを1に固定すると、有理2次ベジェ曲線の真ん中の重みでどの円錐曲線になるかが決まります。 $w_1 < 1$ なら楕円の弧、 $w_1 = 1$ なら放物線、 $w_1 > 1$ なら双曲線です。
此の直角で2辺の長さが等しい制御三角形の場合、 $w_1 = \tfrac{\sqrt{2}}{2}$ の楕円が円になります。
円全体は其ういう弧4つで出来ます。9つの制御点（正方形の角と辺の中点、最初の点を最後に繰り返す）、重みは $1, \tfrac{\sqrt{2}}{2}, 1, \tfrac{\sqrt{2}}{2}, \dots$ と交互、次数2、ノットベクトル $(0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 4)$ です。

射影不変性

NURBS曲線は同次座標を通して定義されているので、射影不変です。同次座標の制御点に射影変換（透視投影でさえ）を施せば、新しい点の曲線は投影した曲線と完全に一致します。
普通のベジェ曲線やBスプライン曲線はアフィン不変なだけです。制御点を投影すると、実質的な重みが変わってしまうからです。
NURBSなら、円の透視図を9つの点の変換だけで正確に計算出来ます。

CADは何故NURBSを使うのか

全てを1つの形式で：直線、円、楕円、円柱、円錐、球、トーラスを正確に表せ、自由曲面も同じ仕組みで扱えます。CADカーネルに必要な曲線と曲面の種類が其々1つで済みます。
ベジェ曲線と普通のBスプラインは特別な場合（重みが全て等しい）です。
局所制御、（重みが正なら）凸包性、よく分かったアルゴリズム（ノット挿入、次数上げ、ド・ブーアの評価）。
アフィン変換と射影変換に対する不変性。
標準である事：CADの交換形式IGESとSTEPは自由形状をNURBSで保存し、Rhinoの様なモデラーはNURBSを中心に作られています。

代償は、点毎のデータが増える事（重みと、管理すべきノットベクトル）と除算、そしてNURBS曲面はGPUで描く前に三角形にテッセレーションしなければならない事です。

8.7 補間スプライン

補間と近似

ベジェ曲線とBスプラインは制御点を近似します。曲線は制御点の方へ引き寄せられますが、一般には其処を通りません。
目で見ながら形をデザインするには理想的ですが、曲線が必ず通らなければならない点がある事もあります。測定データ、キーフレームの値、カメラ経路の通過点です。
与えられた全ての点を通る曲線は、其れらの点を補間すると言います。

左は6つの点を通るカトマル・ロム・スプラインと自然3次スプライン、右は同じ6点を近似する3次Bスプライン

カトマル・ロム・スプライン

カトマル・ロム・スプライン（エドウィン・カトマルとラファエル・ロムに因む）は、一番簡単な補間スプラインです。
$\mathbf{p}_i$ と $\mathbf{p}_{i+1}$ の間の部分に、隣の点から取った接線を持つエルミート曲線を使います：

\mathbf{v}_i = \frac{\mathbf{p}_{i+1} - \mathbf{p}_{i-1}}{2}

各点での接線は、其の両隣の2点を通る直線に平行です。
隣り合う部分は点と接線ベクトルを共有するので、曲線は何処でも $C^1$ です。
各部分は $\mathbf{p}_{i-1}, \mathbf{p}_i, \mathbf{p}_{i+1}, \mathbf{p}_{i+2}$ の4点だけで決まるので、制御は局所的です。
最初と最後の部分は隣の点が1つ足りません。普通は端点を繰り返すか、隣の点を鏡映して1つ作ります（図では鏡映しています）。

基底行列で書くと：

\mathbf{c}(t) = \frac{1}{2} \begin{bmatrix} t^3 & t^2 & t & 1 \end{bmatrix} \begin{bmatrix} -1 & 3 & -3 & 1 \\ 2 & -5 & 4 & -1 \\ -1 & 0 & 1 & 0 \\ 0 & 2 & 0 & 0 \end{bmatrix} \begin{bmatrix} \mathbf{p}_{i-1} \\ \mathbf{p}_i \\ \mathbf{p}_{i+1} \\ \mathbf{p}_{i+2} \end{bmatrix}

例題。 点 $(0, 0), (2, 4), (6, 4), (8, 0)$ の、 $(2, 4)$ から $(6, 4)$ までの真ん中の部分：

\mathbf{v}_1 = \frac{(6, 4) - (0, 0)}{2} = (3, 2), \qquad \mathbf{v}_2 = \frac{(8, 0) - (2, 4)}{2} = (3, -2)

8.3節の $t = 0.5$ でのエルミートの重みを使うと：

\mathbf{c}(0.5) = 0.5\,(2, 4) + 0.5\,(6, 4) + 0.125\,(3, 2) - 0.125\,(3, -2) = (4, 4) + (0, 0.5) = (4, \; 4.5)

行列でも同じです。 $t = 0.5$ での重みは $\left(-\tfrac{1}{16}, \tfrac{9}{16}, \tfrac{9}{16}, -\tfrac{1}{16}\right)$ で、 $-\tfrac{1}{16}(0, 0) + \tfrac{9}{16}(2, 4) + \tfrac{9}{16}(6, 4) - \tfrac{1}{16}(8, 0) = \left(\tfrac{18 + 54 - 8}{16}, \tfrac{36 + 36}{16}\right) = (4, 4.5)$ です。
負の重みに注目して下さい。カトマル・ロム・スプラインには凸包性が無く、点を行き過ぎる事があります。
同じ部分をベジェの部分（8.4節）として書くと、内側の制御点は $(2, 4) + \tfrac{1}{3}(3, 2) = (3, 4.667)$ と $(6, 4) - \tfrac{1}{3}(3, -2) = (5, 4.667)$ です。

カトマル・ロム・スプラインはゲームやアニメーションの至る所にあります。通過点を通るカメラ経路、キーフレームの既定の「スムーズ」補間（第13章）、動く足場の経路、手描きのストロークの平滑化などです。
パラメータを1つ足した変種（テンションを持つカーディナルスプライン、テンション・連続性・バイアスを持つコチャネック・バーテルズ・スプライン）では、各点の周りで曲線がどれ位きつく曲がるかをアニメーターが細かく調整出来ます。

自然3次スプライン

カトマル・ロム・スプラインは $C^1$ に過ぎません。
全ての点を通る $C^2$ の曲線が欲しければ、古典的な答えがあります。自然3次スプラインです。
点が $n + 1$ 個なら3次の部分が $n$ 個、未知の係数が $4n$ 個あり、条件は次の通りです：

各部分が其の両端の点を通る： $2n$ 個の式。
$n - 1$ 個の内側の点で1階微分と2階微分が一致する： $2(n - 1)$ 個の式。
「自然」な端、つまり最初と最後の点で2階微分が0：2個の式。

合わせて $2n + 2n - 2 + 2 = 4n$ 個の式で、未知数 $4n$ 個に丁度です。
パラメータが等間隔なら、全ては点での2階微分 $M_i$ についての小さな連立方程式1つに纏まります：

M_{i-1} + 4M_i + M_{i+1} = 6\,(y_{i-1} - 2y_i + y_{i+1}), \qquad M_0 = M_n = 0

（1つの座標 $y$ について書きました。xとzでも同じ事をします。）
小さな例： $x = 0, 1, 2$ で値 $y = 0, 1, 0$ 。
未知数は1つだけで、 $0 + 4M_1 + 0 = 6\,(0 - 2 + 0) = -12$ 、従って $M_1 = -3$ です。
最初の部分では $s = x - 0$ として、スプラインは $S(s) = \tfrac{M_0}{6}(1 - s)^3 + \tfrac{M_1}{6}s^3 + \left(y_0 - \tfrac{M_0}{6}\right)(1 - s) + \left(y_1 - \tfrac{M_1}{6}\right)s$ で、 $s = 0.5$ では：

S(0.5) = 0 + \frac{-3}{6} \cdot 0.125 + 0 + \left(1 + \frac{3}{6}\right) \cdot 0.5 = -0.0625 + 0.75 = 0.6875

問題は、此の連立方程式が全ての点を結び付けている事です。1つの点を動かすと全ての $M_i$ が変わり、従って曲線全体が変わります。
自然スプラインの制御は大域的で、其の為対話的なツールはカトマル・ロムやBスプラインを好みます。
名前は8.1節の製図用の木のスプラインに由来します。固定した点に通して曲げた薄い板は、近似的に自然3次スプライン、つまり一番曲げの少ない形になり、端が自由なら端では曲がっていません。

曲線	通る点	制御	連続性	凸包性
エルミート	両端点（与えた接線で）	（1つの部分）	接線を共有すれば繋ぎ目は $C^1$	無し
ベジェ	最初と最後の制御点	大域的	繋ぎ目は工夫が必要	有り
Bスプライン（一様3次）	無し（クランプなら最初と最後）	局所的	$C^2$	有り
NURBS	Bスプラインと同じ	局所的	Bスプラインと同じ	有り（重みが正なら）
カトマル・ロム	全ての点	局所的	$C^1$	無し
自然3次スプライン	全ての点	大域的	$C^2$	無し

8.8 曲面

今までの事は全て、パラメータを1つ増やせば曲面に持ち込めます。
パラメトリック曲面は、パラメータの正方形から空間への写像です：

\mathbf{s}(u, v) = (x(u, v), \; y(u, v), \; z(u, v)), \qquad 0 \le u \le 1, \; 0 \le v \le 1

$v$ を固定して $u$ を動かすと曲面上の曲線が得られ、 $u$ を固定しても同じです。
此れがアイソパラメトリック曲線（等パラメータ曲線）で、以下の図の黄色のワイヤーフレームは正に其れです。
1つのパラメータの正方形の上の曲面の一片をパッチと呼びます。

テンソル積曲面と双3次ベジェ曲面

一番簡単な作り方はテンソル積です。曲線の種類を1つ選び、其の基底関数を両方向に使います。
双3次ベジェ曲面（双3次ベジェパッチ）は $4 \times 4$ の格子状の制御点 $\mathbf{p}_{ij}$ 、つまり制御点網を持ち、全部で16点です：

\mathbf{s}(u, v) = \sum_{i=0}^{3}\sum_{j=0}^{3} B_{i,3}(u)\,B_{j,3}(v)\,\mathbf{p}_{ij}

「曲線の曲線」と読んで下さい。
$v$ を固定すると、先ず網の各行 $j$ を $u$ についてのベジェ曲線として評価します。其れで4つの点が得られ、其れが $v$ についてのベジェ曲線の制御点になります。
4つの角の点は曲面上にあり、境界の4つの行と列は境界のベジェ曲線で、内側の4点は曲面に触れずに引っ張ります。
ベジェ曲線の性質（凸包性、アフィン不変性、ド・カステリョ、分割）は全て其の儘使えます。

例題。 此のシリーズのy上向きの約束を守って、網を地面の $4 \times 4$ の格子の上に置きます。 $\mathbf{p}_{ij} = (i, \; h_{ij}, \; -j)$ で、高さ $h_{ij}$ は次の通りです（行 $j$ は見る人から遠ざかる方向、−z方向に進みます）：

	$i = 1$	$i = 2$
$j = 0$	0	0
$j = 1$	2	2
$j = 2$	4	4
$j = 3$	0	0

$(u, v) = (0.5, 0.5)$ で評価します。バーンスタインの重みは両方向とも $\left(\tfrac{1}{8}, \tfrac{3}{8}, \tfrac{3}{8}, \tfrac{1}{8}\right)$ です。

各行をuで。 どの行もx座標は $\tfrac{1}{8}(0 + 3 \cdot 1 + 3 \cdot 2 + 3) = 1.5$ 。高さは、行0が0、行1が $\tfrac{1}{8}(0 + 3 \cdot 2 + 3 \cdot 2 + 0) = 1.5$ 、行2が $\tfrac{1}{8}(0 + 3 \cdot 4 + 3 \cdot 4 + 0) = 3$ 、行3が0。従って4つの行の点は $(1.5, 0, 0)$ 、 $(1.5, 1.5, -1)$ 、 $(1.5, 3, -2)$ 、 $(1.5, 0, -3)$ です。
列をvで。 $y = \tfrac{1}{8}(0 + 3 \cdot 1.5 + 3 \cdot 3 + 0) = \tfrac{13.5}{8} = 1.6875$ 、 $z = -\tfrac{1}{8}(0 + 3 \cdot 1 + 3 \cdot 2 + 3) = -1.5$ 。

\mathbf{s}(0.5, 0.5) = (1.5, \; 1.6875, \; -1.5)

内側の制御点は高さ2と4にありますが、曲面は真ん中で1.6875にしか届きません。制御点網は、曲面が其の中に留まる「籠」です。

偏微分から法線を求める

シェーディング（第10章）には曲面の法線ベクトルが必要です。
偏微分 $\mathbf{s}_u = \frac{\partial \mathbf{s}}{\partial u}$ と $\mathbf{s}_v = \frac{\partial \mathbf{s}}{\partial v}$ （もう一方を固定して1つのパラメータで微分する事）は、其の点を通る2本のアイソパラメトリック曲線の接線ベクトルです。
どちらも接平面の中にあるので、其の外積（線型代数シリーズ第5章）は曲面に垂直です：

\mathbf{n} = \mathbf{s}_u \times \mathbf{s}_v, \qquad \hat{\mathbf{n}} = \frac{\mathbf{n}}{\lVert \mathbf{n} \rVert}

例のパッチには3次のバーンスタイン多項式の微分 $B'_{i,3}(t) = 3\left(B_{i-1,2}(t) - B_{i,2}(t)\right)$ が必要です（ $B_{-1,2} = B_{3,2} = 0$ とします）。
$t = 0.5$ では $B_{\cdot,2} = \left(\tfrac{1}{4}, \tfrac{1}{2}, \tfrac{1}{4}\right)$ なので、其れは $\left(-\tfrac{3}{4}, -\tfrac{3}{4}, \tfrac{3}{4}, \tfrac{3}{4}\right)$ です。

$\mathbf{s}_u$ ：各行に微分の重みを、列には普通の重みを使います。x： $-\tfrac{3}{4} \cdot 0 - \tfrac{3}{4} \cdot 1 + \tfrac{3}{4} \cdot 2 + \tfrac{3}{4} \cdot 3 = 3$ 。高さ：どの行も左右対称（0, 2, 2, 0と0, 4, 4, 0）なので $-\tfrac{3}{4} \cdot 0 - \tfrac{3}{4} \cdot 2 + \tfrac{3}{4} \cdot 2 + \tfrac{3}{4} \cdot 0 = 0$ 。zは行に沿って変わりません。従って $\mathbf{s}_u = (3, 0, 0)$ 。
$\mathbf{s}_v$ ：段階1の4つの行の点に微分の重みを使います。x：どの行の点も $x = 1.5$ なので0。高さ： $-\tfrac{3}{4} \cdot 0 - \tfrac{3}{4} \cdot 1.5 + \tfrac{3}{4} \cdot 3 + \tfrac{3}{4} \cdot 0 = 1.125$ 。z： $-\left(-\tfrac{3}{4} \cdot 0 - \tfrac{3}{4} \cdot 1 + \tfrac{3}{4} \cdot 2 + \tfrac{3}{4} \cdot 3\right) = -3$ 。従って $\mathbf{s}_v = (0, 1.125, -3)$ 。

\mathbf{n} = \mathbf{s}_u \times \mathbf{s}_v = \begin{bmatrix} 0 \cdot (-3) - 0 \cdot 1.125 \\ 0 \cdot 0 - 3 \cdot (-3) \\ 3 \cdot 1.125 - 0 \cdot 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 9 \\ 3.375 \end{bmatrix}

\lVert \mathbf{n} \rVert = \sqrt{0^2 + 9^2 + 3.375^2} = \sqrt{81 + 11.390625} \approx 9.612, \qquad \hat{\mathbf{n}} = \frac{\mathbf{n}}{\lVert \mathbf{n} \rVert} \approx (0, \; 0.936, \; 0.351)

例題の双3次ベジェ曲面と其の制御点網、点 s 0.5, 0.5、接線ベクトル s u と s v、法線 n

法線は殆ど上を向き、少しだけ+z、つまり見る人の方に傾いています。曲面は見る人から遠ざかる程高くなる（行1と行2の高さが2と4）ので、少し手前側を向いているのは理に適っています。
順序が大事です。 $\mathbf{s}_v \times \mathbf{s}_u$ だと地面の中を向いてしまいます。
どちら側が「外」かは、モデリングツールが一貫して守るべき約束事です。

Bスプライン曲面とNURBS曲面

バーンスタイン多項式をBスプライン基底関数に置き換え、 $u$ と $v$ に其々ノットベクトルを1つずつ使うとBスプライン曲面になり、重みを付けて割ればNURBS曲面になります：

\mathbf{s}(u, v) = \frac{\sum_i \sum_j N_{i,p}(u)\,N_{j,q}(v)\,w_{ij}\,\mathbf{p}_{ij}}{\sum_i \sum_j N_{i,p}(u)\,N_{j,q}(v)\,w_{ij}}

曲線の性質は全て引き継がれます。局所制御、正確な2次曲面（球、円柱、トーラスは、8.6節の円弧から作る正確なNURBS曲面です）、射影不変性。
此れがCADの曲面の種類で、B-repのソリッドモデル（第7章）の面にもなります。

クーンズ曲面

デザイナーがパッチの4本の境界曲線は持っているのに、内側の制御点が無い事もあります。
クーンズ曲面（スティーブン・A・クーンズに因む）は、境界から曲面を埋めます。
境界曲線を $\mathbf{c}_0(u) = \mathbf{s}(u, 0)$ 、 $\mathbf{c}_1(u) = \mathbf{s}(u, 1)$ 、 $\mathbf{d}_0(v) = \mathbf{s}(0, v)$ 、 $\mathbf{d}_1(v) = \mathbf{s}(1, v)$ 、角を $\mathbf{P}_{00}, \mathbf{P}_{10}, \mathbf{P}_{01}, \mathbf{P}_{11}$ とすると、双線型ブレンドのクーンズ曲面は次の通りです：

\begin{aligned} \mathbf{s}(u, v) &= (1 - v)\,\mathbf{c}_0(u) + v\,\mathbf{c}_1(u) \\ &\quad + (1 - u)\,\mathbf{d}_0(v) + u\,\mathbf{d}_1(v) \\ &\quad - \left[(1 - u)(1 - v)\,\mathbf{P}_{00} + u(1 - v)\,\mathbf{P}_{10} + (1 - u)v\,\mathbf{P}_{01} + uv\,\mathbf{P}_{11}\right] \end{aligned}

1行目は $v$ 方向のブレンドで、曲線 $\mathbf{c}_0$ と $\mathbf{c}_1$ の間に直線を張ります。
2行目は $u$ 方向のブレンドで、 $\mathbf{d}_0$ と $\mathbf{d}_1$ の間です。
両方を足すと角を2回数えてしまうので、3行目で4つの角の双線型補間を1回引きます。
結果は4本の境界曲線と完全に一致します。

例題。 地面の上の1辺2の正方形： $\mathbf{c}_0(u) = (2u, 0, 0)$ 、 $\mathbf{c}_1(u) = (2u, 0, -2)$ 、 $\mathbf{d}_0(v) = (0, 0, -2v)$ 、そして1辺だけアーチにした $\mathbf{d}_1(v) = (2, \; 4v(1 - v), \; -2v)$ 。此の辺は真ん中で高さ1まで上がります。
$(0.5, 0.5)$ では、vのブレンドが $\tfrac{1}{2}(1, 0, 0) + \tfrac{1}{2}(1, 0, -2) = (1, 0, -1)$ 、uのブレンドが $\tfrac{1}{2}(0, 0, -1) + \tfrac{1}{2}(2, 1, -1) = (1, 0.5, -1)$ 、角 $(0, 0, 0), (2, 0, 0), (0, 0, -2), (2, 0, -2)$ のブレンドが $(1, 0, -1)$ です。

\mathbf{s}(0.5, 0.5) = (1, 0, -1) + (1, 0.5, -1) - (1, 0, -1) = (1, \; 0.5, \; -1)

平らな辺（高さ0）とアーチの頂上（高さ1）の丁度中間で、予想通りです。
クーンズ曲面はCADで最初期の曲面手法の1つで、同じブレンドの考え方は今でもメッシュの穴埋めや、スケッチした境界曲線からの曲面作成に使われています。

線織面・回転面・スイープ曲面

余りによく使うので、モデリングツールに専用のボタンがある作り方が幾つかあります：

4種類の曲面のワイヤーフレーム。線織面としての双線型曲面、回転面としての花瓶、スイープ曲面としての管、例題のクーンズ曲面

線織面は2本の曲線 $\mathbf{a}(u)$ と $\mathbf{b}(u)$ を直線で結びます： $\mathbf{s}(u, v) = (1 - v)\,\mathbf{a}(u) + v\,\mathbf{b}(u)$ 。 $u$ が一定の線は全て直線です。円柱や円錐は線織面で、四辺形の向かい合う2辺を結ぶ双線型曲面もそうです。角が $(0, 0, 0), (2, 2, 0), (0, 2, -2), (2, 0, -2)$ なら図の鞍形、双曲放物面になり、其の中心は角の平均 $(1, 1, -1)$ です。両方向に線織面で、 $v$ が一定の線も直線です。
回転面は断面の曲線を軸の周りに回す物で、「旋盤（ろくろ）」ツールです。xy平面の断面 $(r(v), \; y(v))$ をy軸の周りに $\theta = 2\pi u$ だけ回すと、第5章の回転行列を使って $\mathbf{s}(u, v) = \mathbf{R}_y(\theta)\,(r(v), y(v), 0) = (r(v)\cos\theta, \; y(v), \; -r(v)\sin\theta)$ です。花瓶、グラス、瓶、車輪、チェスの駒。図のオレンジの曲線が断面です。NURBSの弧で出来た断面と8.6節の正確な円を組み合わせると、正確なNURBS曲面になります。
スイープ曲面は、断面の曲線を経路の曲線に沿って、経路に垂直に保ちながら動かします。回さずに動かせば押し出し、つまり平行移動スイープで、軸の周りに回せば又回転面（回転スイープ）です。此れらは第7章のスイープ表現のソリッドの面です。一般の場合は経路に沿って動く座標系が必要で（例えば図の様に経路の接線から作る）、其の為きつい曲がりでスイープが思わぬ捩れ方をする事があります。パイプ、ケーブル、レール、取っ手、押し出した文字。
上のクーンズ曲面が4つ目の例です。

トリム曲面

NURBSパッチは常に正方形を変形した物です。
実際の部品には穴や丸い切り欠き、他の曲面に沿った縁があります。
トリム曲面はパッチを其の儘使い、 $(u, v)$ パラメータの正方形の中にトリム曲線を描き加えて、正方形のどの部分を残すかを示します。例えば穴を囲む閉曲線です。
残した領域だけが形の一部になります。
CADのソリッドの面の殆どはトリムしたNURBSパッチで、B-repモデル（第7章）の面が任意の輪郭を持てるのは此の為です。
トリムはテッセレーションを難しくし、隣り合う2つのトリム曲面の境界は3Dでは一般に完全には一致しないので、CADデータをメッシュに変換する時に小さな隙間が出来る原因（「ウォータータイト」の問題）になります。

描画の為のテッセレーション

GPUが描くのは三角形で、パッチではありません。
其の為描画の前に曲面をテッセレーションします。パラメータの格子で評価し、隣り合う点を結んで三角形にするのです。

パラメータの正方形を 4×4 の格子の32個の三角形に分け、同じ三角形を双3次ベジェ曲面に写した図

$N \times N$ の格子には頂点が $(N + 1)^2$ 個、三角形が $2N^2$ 個あります。 $N = 4$ なら頂点25個と三角形32個（図）、 $N = 16$ なら頂点289個と三角形512個です。
各頂点では上の外積で法線も評価するので、形は平らな三角形で出来ていても陰影は滑らかになります。
適応的テッセレーションは、曲面が強く曲がっている所や画面上で大きい所に三角形を多く、其れ以外に少なく使います。
すると分割の細かさが違う隣のパッチ同士が共有する辺で一致しなければならず、さもないと其の間にひび割れ（クラック）が出来ます。普通は、辺の両側で同じ分割数を使う事にします。

最近のGPUは此れを自分で出来ます。
OpenGLとVulkanでは、テッセレーション制御シェーダーがどれ位細かく分割するかを決め、固定機能のテッセレータが $(u, v)$ の点と三角形を生成し、テッセレーション評価シェーダーが其々について $\mathbf{s}(u, v)$ を、例えば此の章のバーンスタインの式で計算します（Direct3Dでは2つのプログラム可能な段階をハルシェーダーとドメインシェーダーと呼びます）。
此れらの段階はGLSLシリーズの第15章で出てきます。
映画やアニメーションのツールでは、任意のメッシュの繋がり方を扱える細分割曲面をパッチの代わりに使う事がよくあります。第9章で説明します。

8.9 実際には：コードと検定のポイント

C++：ド・カステリョとコックス・ド・ブーア

どちらのアルゴリズムも数行で書けます。
此のプログラムは線型代数シリーズの linalg.hh の Vec2 と其の演算子を使い、8.4節と8.5節の例題を繰り返します：

#include "linalg.hh"
#include <cstdio>
#include <vector>

// Linear interpolation between two points: (1 - t) a + t b.
Vec2 lerp(Vec2 a, Vec2 b, float t) { return (1.0f - t) * a + t * b; }

// de Casteljau's algorithm: interpolate neighbors until one point is left.
Vec2 deCasteljau(std::vector<Vec2> p, float t) {
  for (size_t n = p.size() - 1; n > 0; n--) {
    for (size_t i = 0; i < n; i++) {
      p[i] = lerp(p[i], p[i + 1], t);
    }
  }
  return p[0];
}

// Cox-de Boor recursion: B-spline basis function N_{i,p}(t), with 0/0 = 0.
float basisN(int i, int p, float t, const std::vector<float> &knots) {
  if (p == 0) {
    return (knots[i] <= t && t < knots[i + 1]) ? 1.0f : 0.0f;
  }
  float a = 0.0f, b = 0.0f;
  float da = knots[i + p] - knots[i];
  float db = knots[i + p + 1] - knots[i + 1];
  if (da != 0.0f) a = (t - knots[i]) / da * basisN(i, p - 1, t, knots);
  if (db != 0.0f) b = (knots[i + p + 1] - t) / db * basisN(i + 1, p - 1, t, knots);
  return a + b;
}

int main() {
  std::vector<Vec2> bezier = {{0, 0}, {2, 4}, {8, 4}, {8, 0}};
  for (float t : {0.0f, 0.25f, 0.5f, 1.0f}) {
    Vec2 c = deCasteljau(bezier, t);
    printf("Bezier   c(%.2f) = (%g, %g)\n", t, c.x, c.y);
  }

  std::vector<float> knots = {0, 0, 0, 1, 2, 2, 2};
  std::vector<Vec2> ctrl = {{0, 0}, {2, 4}, {6, 4}, {8, 0}};
  float t = 0.5f;
  Vec2 c{};
  printf("N(0.5)  =");
  for (int i = 0; i < 4; i++) {
    float n = basisN(i, 2, t, knots);
    printf(" %g", n);
    c = c + n * ctrl[i];
  }
  printf("\nB-spline c(0.5) = (%g, %g)\n", c.x, c.y);
  return 0;
}

期待される出力：

Bezier   c(0.00) = (0, 0)
Bezier   c(0.25) = (2.09375, 2.25)
Bezier   c(0.50) = (4.75, 3)
Bezier   c(1.00) = (8, 0)
N(0.5)  = 0.25 0.625 0.125 0
B-spline c(0.5) = (2, 3)

deCasteljau がベクトルを値渡しで受け取るのはわざとで、自分のコピーを段毎に上書き出来る様にしています。
basisN は8.5節の漸化式を其の儘書いた物です。学習には十分ですが、同じ低い次数の関数を何度も計算し直すので、実際のライブラリは1つの区間の0でない関数を全部纏めて1つの三角形のループで評価します（又はド・ブーアのアルゴリズムを使います）。
もう1つ細かい点：半開区間 $t_i \le t < t_{i+1}$ だと、一番最後のパラメータ値（此処では $t = 2$ ）がどの区間にも入らないので、ライブラリは範囲の終わりを特別扱いします。

シェーダー関数：3次ベジェ曲線上の点

GPUではバーンスタイン形式が便利です。ループが無く、掛け算の数も決まっています。
此の関数は3次ベジェ曲線の位置と接線を返します。頂点の帯を経路に沿って曲げる（髪の毛、ロープ、軌跡、曲がった道路）時や、テッセレーション評価シェーダーの中で生成された頂点を置く時に必要になる物です。

Slang GLSL HLSL

// Point on a cubic Bezier curve: Bernstein weights (1-t)^3, 3t(1-t)^2, 3t^2(1-t), t^3.
float3 bezierPoint(float3 p0, float3 p1, float3 p2, float3 p3, float t) {
  float s = 1.0 - t;
  return s * s * s * p0 + 3.0 * s * s * t * p1 + 3.0 * s * t * t * p2 + t * t * t * p3;
}

// Tangent c'(t) = 3 [ (1-t)^2 (p1-p0) + 2t(1-t) (p2-p1) + t^2 (p3-p2) ].
float3 bezierTangent(float3 p0, float3 p1, float3 p2, float3 p3, float t) {
  float s = 1.0 - t;
  return 3.0 * (s * s * (p1 - p0) + 2.0 * s * t * (p2 - p1) + t * t * (p3 - p2));
}

// Point on a cubic Bezier curve: Bernstein weights (1-t)^3, 3t(1-t)^2, 3t^2(1-t), t^3.
vec3 bezierPoint(vec3 p0, vec3 p1, vec3 p2, vec3 p3, float t) {
  float s = 1.0 - t;
  return s * s * s * p0 + 3.0 * s * s * t * p1 + 3.0 * s * t * t * p2 + t * t * t * p3;
}

// Tangent c'(t) = 3 [ (1-t)^2 (p1-p0) + 2t(1-t) (p2-p1) + t^2 (p3-p2) ].
vec3 bezierTangent(vec3 p0, vec3 p1, vec3 p2, vec3 p3, float t) {
  float s = 1.0 - t;
  return 3.0 * (s * s * (p1 - p0) + 2.0 * s * t * (p2 - p1) + t * t * (p3 - p2));
}

// Point on a cubic Bezier curve: Bernstein weights (1-t)^3, 3t(1-t)^2, 3t^2(1-t), t^3.
float3 bezierPoint(float3 p0, float3 p1, float3 p2, float3 p3, float t) {
  float s = 1.0 - t;
  return s * s * s * p0 + 3.0 * s * s * t * p1 + 3.0 * s * t * t * p2 + t * t * t * p3;
}

// Tangent c'(t) = 3 [ (1-t)^2 (p1-p0) + 2t(1-t) (p2-p1) + t^2 (p3-p2) ].
float3 bezierTangent(float3 p0, float3 p1, float3 p2, float3 p3, float t) {
  float s = 1.0 - t;
  return 3.0 * (s * s * (p1 - p0) + 2.0 * s * t * (p2 - p1) + t * t * (p3 - p2));
}

8.4節の制御点（z = 0）と t = 0.5 なら、bezierPoint は (4.75, 3, 0) を、bezierTangent は (10.5, 0, 0) を返します。
此処の積は全てスカラーとベクトルの積なので、どの言語でも * で正しいです。SlangとHLSLで mul が必要なのは、行列が関わる積だけです。

検定のポイント

曲線はどの点を通るか？ ベジェ：最初と最後の制御点だけ。一様Bスプライン：どれも通らない。クランプ（開一様）Bスプライン：最初と最後。エルミート：両端点（其処で与えた接線を取る）。カトマル・ロムと自然スプライン：全ての点。双3次ベジェ曲面：4つの角だけ。
ベジェ曲線の端点での接線は制御多角形の最初と最後の辺に沿う： $\mathbf{c}'(0) = n(\mathbf{p}_1 - \mathbf{p}_0)$ 、 $\mathbf{c}'(1) = n(\mathbf{p}_n - \mathbf{p}_{n-1})$ 。ベジェ ↔ エルミート： $\mathbf{v}_0 = 3(\mathbf{p}_1 - \mathbf{p}_0)$ 、 $\mathbf{v}_1 = 3(\mathbf{p}_3 - \mathbf{p}_2)$ 。
凸包性：ベジェ、Bスプライン、（重みが正の）NURBS曲線は制御点の凸包の中にある。重みが負でなく、足すと1になるから。カトマル・ロムとエルミートには無い。
局所制御と大域的制御：ベジェ曲線と自然スプラインは大域的、Bスプライン、NURBS、カトマル・ロムは局所的。3次Bスプラインの1つの部分は4つの制御点で決まる。
次数：制御点が $n + 1$ 個のベジェ曲線は $n$ 次。Bスプラインの次数は独立に選べ、ノット数 $=$ 制御点数 $+$ 次数 $+ 1$ 。階数 $=$ 次数 $+ 1$ 。
C連続とG連続： $C^1$ は接線ベクトルが等しい事、 $G^1$ は向きが等しい事だけ。3次ベジェの接続： $\mathbf{p}_2, \mathbf{p}_3 = \mathbf{q}_0, \mathbf{q}_1$ が一直線なら $G^1$ 、更に辺の長さも等しければ $C^1$ 。一様3次Bスプラインは $C^2$ 、カトマル・ロムは $C^1$ 。ノットの重複は連続性を下げる。
NURBSが加える物：重みと有理形式。同次座標とwでの除算で計算する。正確な円錐曲線（重み $1, \tfrac{\sqrt{2}}{2}, 1$ の4分の1円）と射影不変性。ベジェ曲線とBスプライン曲線は特別な場合。有理でない曲線はアフィン不変なだけ。
アフィン不変性：曲線の全ての点ではなく、制御点を変換する。
曲面：テンソル積パッチ（双3次ベジェは制御点16個）、法線 $= \mathbf{s}_u \times \mathbf{s}_v$ 、4本の境界曲線からのクーンズ曲面、2本の曲線の間の直線による線織面、回転面とスイープ、 $(u, v)$ 領域のトリム曲線、描画前の三角形へのテッセレーション。

8.10 まとめ

パラメトリック曲線 $\mathbf{c}(t)$ がCGの標準。順番に点を生成し易く、2Dでも3Dでも任意の形を表せる。陽関数は閉じた曲線や垂直な曲線を作れず、陰関数は内外判定に向く。
接線ベクトル $\mathbf{c}'(t)$ は向き（形）と速さ（パラメータの付け方）を表す。 $C^n$ 連続性は微分のベクトルを、 $G^n$ は形だけを比べる。 $G^1$ は接線の向きが同じ、 $G^2$ は曲率が同じ。
3次の部分が標準。変曲点、3Dでの捩れ、滑らかな接続が出来る一番低い次数。全ての曲線の種類は「基底関数×データ」、つまり $t$ の冪の行とデータの列の間に基底行列を挟んだ形。
エルミート曲線は端点と接線を使う。ベジェ曲線はバーンスタインの重みで制御点を使い、ド・カステリョのアルゴリズムは線型補間の繰り返しで其れを評価・分割する。端点を補間し、端の辺に接し、凸包の中に留まり、アフィン不変で変動減少性を持ち、制御は大域的。
Bスプラインはノットベクトル上の区分的多項式で、コックス・ド・ブーアの漸化式で定義される。局所制御が出来、次数は点の数と無関係で、一様3次Bスプラインは $C^2$ 。ベジェ曲線は、クランプしたノットで内側のノットが無い特別な場合。
NURBSは同次座標を通して重みを加える。正確な円や其の他の円錐曲線、射影不変性、全てのCAD形状を1つの表現で。
補間スプラインは点を通る。カトマル・ロム（ $C^1$ 、局所的、接線は隣の点から）と自然3次スプライン（ $C^2$ 、大域的）。
曲面：テンソル積のベジェ・Bスプライン・NURBSパッチ。 $\mathbf{s}_u \times \mathbf{s}_v$ から法線。境界からのクーンズ曲面。線織面、回転面、スイープ曲面。穴の為のトリム曲面。描画の為の三角形へのテッセレーション（GPUではテッセレーションの段階）。

8.11 用語

English	日本語	備考
free-form curve / surface	自由曲線／自由曲面	単純な式ではなく制御データで決まる形
explicit / implicit / parametric representation	陽関数表現／陰関数表現／パラメトリック表現	$y = f(x)$ 、 $f(x, y) = 0$ 、 $\mathbf{c}(t)$
tangent vector	接線ベクトル	$\mathbf{c}'(t)$ ：向きと速さ
spline	スプライン	区分的多項式の曲線
parametric continuity (C0, C1, C2)	パラメトリック連続性（C0・C1・C2連続）	微分のベクトルが等しい
geometric continuity (G1, G2)	幾何学的連続性（G1・G2連続）	接線の向きが等しい、曲率が等しい
curvature	曲率	曲線がどれ位鋭く曲がるか
Hermite curve	エルミート曲線	端点と端点での接線
basis function / basis matrix	基底関数／基底行列	曲線の種類毎に決まった重み
Bézier curve	ベジェ曲線	バーンスタインの重みを付けた制御点
Bernstein polynomial	バーンスタイン多項式	二項係数 × $t^i(1 - t)^{n-i}$
control point / control polygon	制御点／制御多角形	デザイナーが動かすデータ
de Casteljau's algorithm	ド・カステリョのアルゴリズム	線型補間の繰り返し
subdivision	分割	曲線を同じ種類の2本に分ける
convex hull property	凸包性	曲線は制御点の凸包の中に留まる
affine invariance	アフィン不変性	曲線の代わりに制御点を変換する
variation diminishing property	変動減少性	制御多角形よりうねらない
global / local control	大域的制御／局所制御	動かした点の影響が何処まで及ぶか
degree elevation	次数上げ	同じ曲線で制御点を1つ増やす
B-spline curve	Bスプライン曲線	連続性が自動で保たれる区分的多項式
knot / knot vector	ノット／ノットベクトル	部分同士の繋ぎ目
uniform / open uniform / non-uniform	一様／開一様／非一様	ノットの間隔
degree / order	次数／階数	階数 = 次数 + 1
Cox–de Boor recursion	コックス・ド・ブーアの漸化式	Bスプライン基底関数を定義する
NURBS	NURBS（非一様有理Bスプライン）	重みと除算：正確な円錐曲線
weight	重み	曲線を其の制御点に引き寄せる
conic section	円錐曲線	円、楕円、放物線、双曲線
projective invariance	射影不変性	制御点を投影すれば曲線が投影される
interpolation / approximation	補間／近似	点を通るか、近くを通るだけか
Catmull–Rom spline	カトマル・ロム・スプライン	補間、C1、局所的
natural cubic spline	自然3次スプライン	補間、C2、大域的
parametric surface / patch	パラメトリック曲面／パッチ	パラメータの正方形の上の $\mathbf{s}(u, v)$
isoparametric curve	アイソパラメトリック曲線（等パラメータ曲線）	u又はvを一定にした曲線
tensor-product surface	テンソル積曲面	両方向に同じ基底
bicubic Bézier patch	双3次ベジェ曲面	制御点16個
control net	制御点網	パッチの制御点の格子
partial derivative / normal vector	偏微分／法線ベクトル	$\mathbf{n} = \mathbf{s}_u \times \mathbf{s}_v$
Coons patch	クーンズ曲面	4本の境界曲線から埋める
ruled surface	線織面	2本の曲線の間の直線
bilinear patch	双線型曲面	両方向に線織面
surface of revolution	回転面	断面を軸の周りに回す
sweep surface / extrusion	スイープ曲面／押し出し	断面を経路に沿って動かす
trimmed surface / trimming curve	トリム曲面／トリム曲線	(u, v) 領域で残す部分を示す
tessellation	テッセレーション	曲面を三角形に変える

8.12 課題

★ 制御点 $(0, 0), (2, 4), (8, 4), (8, 0)$ の3次ベジェ曲線を、 $t = \tfrac{1}{4}$ でド・カステリョのアルゴリズムで評価し、途中の6つの点を全て書き出して下さい。其の後、バーンスタインの重み $\tfrac{27}{64}, \tfrac{27}{64}, \tfrac{9}{64}, \tfrac{1}{64}$ で結果を確かめて下さい。
★★ 2次Bスプラインのノットベクトルが $(0, 0, 0, 1, 2, 3, 3, 3)$ です。制御点は幾つで、多項式の部分は幾つありますか？コックス・ド・ブーアの漸化式で全ての $N_{i,2}(1.5)$ を計算し、足すと1になる事を確かめ、 $t = 1.5$ で曲線に影響する制御点はどれかを答えて下さい。
★★ 点 $(0, 0), (2, 2), (4, 2), (6, 0)$ について、 $(2, 2)$ と $(4, 2)$ でのカトマル・ロムの接線、真ん中の部分のベジェの制御点4つ、そして其の部分の $t = 0.5$ での点を（エルミートの重みとバーンスタインの重みの両方で）求めて下さい。
★★ 8.6節の4分の1円のNURBSを $t = \tfrac{1}{4}$ と $t = \tfrac{3}{4}$ で同次座標の制御点を使って評価し、どちらの点も原点から距離1にある事を確かめ、同じパラメータで有理でない曲線（重みが全て1）が円からどれだけ離れているかを計算して下さい。
★★★ 4分の1円のNURBSで、全ての $t$ について $x(t)^2 + y(t)^2 = 1$ となる事を示して下さい（ヒント： $s = 1 - t$ と置き、分子を分母の2乗と比べる）。其の上で、多項式の曲線 $(x(t), y(t))$ では何故円弧を正確に描けないのか、そしてwでの除算が何を変えるのかを説明して下さい。

選択問題

問1 ★ 制御点 $\mathbf{p}_0, \mathbf{p}_1, \mathbf{p}_2, \mathbf{p}_3$ を持つ3次ベジェ曲線について、正しい物はどれか。


あ	曲線は4つの制御点全てを通る。
い	次数は制御点の数と同じ4である。
う	$\mathbf{p}_1$ を動かすと、曲線の最初の3分の1だけが変わる。
え	始点で、曲線は $\mathbf{p}_0$ から $\mathbf{p}_3$ への直線に接する。
お	曲線全体が4つの制御点の凸包の中にある。

問2 ★★ 次の曲線のうち、与えられた全ての点を通り、且つ局所制御が出来る（1点を動かしても曲線の限られた部分しか変わらない）物はどれか。


あ	カトマル・ロム・スプライン
い	ベジェ曲線
う	一様3次Bスプライン曲線
え	自然3次スプライン
お	有理2次ベジェ曲線（NURBS）

問3 ★★ 2つの3次ベジェ曲線を繋ぐ。1つ目の制御点は $(0, 0), (1, 2), (3, 2), (4, 0)$ 、2つ目は $(4, 0), (6, -4), (7, -2), (8, 0)$ で、どちらも $0 \le t \le 1$ である。繋ぎ目の連続性はどれか。


あ	$C^0$ だが $G^1$ ではない
い	$G^1$ だが $C^1$ ではない
う	$C^1$ だが $C^2$ ではない
え	$C^2$
お	$C^0$ ですらない（2つの部分が繋がっていない）

8.13 実践課題

ド・カステリョで紙の上に曲線をデザインし、4通りの方法で確かめ、正確な円を描く。
方眼紙（少なくとも25 × 17マス、xは0から24、yは−4から12、1マス = 1単位）、定規、鉛筆、色ペン2本、コンパス、電卓を用意して下さい。
主役の曲線の制御点は $\mathbf{p}_0 = (0, 0)$ 、 $\mathbf{p}_1 = (0, 8)$ 、 $\mathbf{p}_2 = (12, 12)$ 、 $\mathbf{p}_3 = (16, 4)$ です。

制御多角形。 4つの制御点と破線の制御多角形を描いて下さい。凸包を色鉛筆で薄く塗って下さい。
t = 1/2 でのド・カステリョ。 定規を使って3本の辺の中点、次に新しい2本の線分の中点、最後の中点を作図し、6つの座標を全て書き留めて下さい。最後は $\mathbf{c}(0.5) = (6.5, 8)$ になる筈です。最後の線分を描いて下さい。其れが其処での接線です。
更に点を。 バーンスタインの重み（ $\tfrac{27}{64}, \tfrac{27}{64}, \tfrac{9}{64}, \tfrac{1}{64}$ と其の逆順）で $\mathbf{c}(\tfrac{1}{4})$ と $\mathbf{c}(\tfrac{3}{4})$ を計算して下さい。 $t = 0, \tfrac{1}{4}, \tfrac{1}{2}, \tfrac{3}{4}, 1$ の5点を打ち、 $\mathbf{p}_0$ を最初の辺に沿って出発し、最後の辺に沿って $\mathbf{p}_3$ に到着する様に、其れらを通る曲線を描いて下さい。
分割による確認。 手順2の作図から、曲線の左半分の制御点（ド・カステリョの三角形の左の辺）を書き出して下さい。其の半分を、其れ自身の $t = \tfrac{1}{2}$ で中点を使って評価して下さい。手順3の $\mathbf{c}(\tfrac{1}{4})$ と完全に一致しなければいけません。
エルミートによる確認。 曲線のエルミートのデータ $\mathbf{v}_0 = 3(\mathbf{p}_1 - \mathbf{p}_0)$ と $\mathbf{v}_1 = 3(\mathbf{p}_3 - \mathbf{p}_2)$ を計算し、重み $\tfrac{1}{2}, \tfrac{1}{2}, \tfrac{1}{8}, -\tfrac{1}{8}$ で $t = \tfrac{1}{2}$ でのエルミート形式を評価して下さい。再び $(6.5, 8)$ にならなければいけません。
滑らかな続き。 $\mathbf{q}_0 = \mathbf{p}_3$ から始まる2つ目の3次の部分を加えます。繋ぎ目が $C^1$ になる様に $\mathbf{q}_1$ を選び、 $\mathbf{q}_2$ 、 $\mathbf{q}_3$ は自由に選んで下さい（例えば $(22, -2)$ と $(24, 4)$ 。必要なら紙を継ぎ足して下さい）。其の制御多角形を描き、もう1本のペンで曲線を描いて下さい。其の後、繋ぎ目が $G^1$ にしかならない $\mathbf{q}_1$ の別の選び方に印を付けて下さい。
正確な円。 2枚目の紙に、コンパスで原点を中心とする半径4の円を描いて下さい。制御点 $(4, 0), (4, 4), (0, 4)$ に重み $1, \tfrac{\sqrt{2}}{2}, 1$ を付け、有理曲線を $t = \tfrac{1}{4}, \tfrac{1}{2}, \tfrac{3}{4}$ で計算して下さい（同次座標の点、其れから除算）。其れらを1色で打って下さい。次に重みを全て1にして同じ3つのパラメータで計算し、もう1色で打って下さい。

自分で確かめる方法：手順3では、曲線の全ての点が塗った凸包の中にあります。手順4は手順3を、手順5は手順2を完全に再現します。手順6では、 $\mathbf{p}_2$ 、 $\mathbf{p}_3$ と選んだ $\mathbf{q}_1$ が1本の直線上にあり、 $\mathbf{p}_3$ が丁度真ん中にあり（ $C^1$ の場合）、 $G^1$ の別案は同じ直線上ですが距離が違います。手順7では、重みを付けた3点は全て原点から距離4でコンパスの円の上にあり（真ん中の点は約 $(2.828, 2.828)$ ）、重みの無い点は円の外、約4.14、4.24、4.14の距離にあります。
最後に、4つの確認の其々について、此の章のどの性質を示しているかを1文ずつ書いて下さい。

コメント（0）

まだコメントはありません。