14 KiB
行列による曲線の分割
曲線分割には、ベジエ曲線の行列表現を利用する方法もあります。行列についての節では、行列の乗算で曲線が表現できることを確認しました。特に2次・3次のベジエ曲線に関しては、それぞれ以下のような形になりました（読みやすさのため、ベジエの係数ベクトルを反転させています）。
[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
ならびに
[ B(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\ -3 & 3 & 0 & 0\ 3 & -6 & 3 & 0\ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix} ]
曲線をある点t = zで分割し、新しく2つの（自明ですが、より短い）ベジエ曲線を作ることを考えましょう。曲線の行列表現と線形代数を利用すると、この2つのベジエ曲線の座標を求めることができます。まず、実際の「曲線上の点」の情報を分解し、新しい行列の積のかたちにします。
[ B(t) = \begin{bmatrix} 1 & (z \cdot t) & (z \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
ならびに
[ B(t) = \begin{bmatrix} 1 & (z \cdot t) & (z \cdot t)^2 & (z \cdot t)^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \ -3 & 3 & 0 & 0 \ 3 & -6 & 3 & 0 \ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}
\begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\ 0 & z & 0 & 0\ 0 & 0 & z^2 & 0\ 0 & 0 & 0 & z^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \ -3 & 3 & 0 & 0 \ 3 & -6 & 3 & 0 \ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix} ]
これらの行列をまとめて、仮に**[tの値たち] · [ベジエ行列] · [列ベクトル]**の形式にできたとしましょう。ただし、先頭2つの行列は変わらずそのままだとします。このとき、右端の列ベクトルは、前半部分すなわちt = 0からt = zを表す、新しいベジエ曲線の座標となります。結論からいうと、線形代数の簡単な規則を使えば、この変形は非常に容易です（そして、導出過程を気にしないのであれば、囲みの末尾まで飛ばして結果に行ってもかまいません！）。
新しい凸包の座標の導出
曲線を分割して2つの部分を得るためには、いくつかの段階を経る必要があります。曲線の次数が高くなるほど手間がかかるようになりますので、まずは2次の曲線で見てみましょう。
[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \underset{これを…}{\underbrace{\kern 2.25em Z \cdot M \kern 2.25em}} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \underset{…こうして…}{\underbrace{ M \cdot M^{-1} \cdot Z \cdot M }} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \underset{…こうじゃ！}{\underbrace{ \kern 1.25em \cdot \kern 1.25em Q \kern 1.25em \cdot \kern 1.25em}} \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[M · M-1]は単位行列なので、このような操作ができるのです（これは微積分でいえば、なにかにx/xを掛けるようなものです。関数自体はなにも変わりませんが、解きやすいかたちに変形したり、別のかたちに分解したりといったことが可能になります）。この行列を掛けると、式全体としてはなにも変わりませんが、[なにか · M]という行列の並びを[M · なにか]という並びに変えることができます。そして、これが大きな違いを生み出します。[M-1 · Z · M]の値が分かれば、それを座標に掛け合わせることによって、2次ベジエ曲線の正しい行列表現（すなわち[T · M · P]）と、t = 0からt = zまでの曲線を表す座標の組とが得られます。では、計算してみましょう。
[ Q = M^{-1} \cdot Z \cdot M = \begin{bmatrix} 1 & 0 & 0 \ 1 & \frac{1}{2} & 0 \ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix}
\begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} ]
いいですね！これで、新しい2次ベジエ曲線が得られます。
[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot \left ( Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \left ( \begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z - 1)^2 \cdot P_1 \end{bmatrix} ]
すばらしい。t = 0からt = zの部分曲線を求める場合、始点の座標はそのままになります（もっともです）。制御点は、元々の制御点と始点を、比率zで混ぜ合わせたものになります。そして不思議なことに、新たな終点は2次のベルンシュタイン多項式に似た混ぜ合わせになります。これらの新しい座標は、とても簡単に直接計算ができるのです！
もちろん、これは2曲線のうちの片方にすぎません。t = zからt = 1の部分を得るためには、同様の計算をする必要があります。まず、今さっき行ったのは、一般の区間[0,z]についての計算でした。これは0があるので簡単な形になっていましたが、実際には、次の式を計算していたということがわかります。
[ B(t) = \begin{bmatrix} 1 & ( 0 + z \cdot t) & ( 0 + z \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
区間[z,1]を求めたい場合は、かわりに次のような計算になります。
[ B(t) = \begin{bmatrix} 1 & ( z + (1-z) \cdot t) & ( z + (1-z) \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & z & z^2 \ 0 & 1-z & 2 \cdot z \cdot (1-z) \ 0 & 0 & (1-z)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
先ほどと同じ手法を使い、[なにか · M]を[M · なにか]に変えます。
[ Q' = M^{-1} \cdot Z' \cdot M = \begin{bmatrix} 1 & 0 & 0 \ 1 & \frac{1}{2} & 0 \ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & z & z^2 \ 0 & 1-z & 2 \cdot z \cdot (1-z) \ 0 & 0 & (1-z)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix}
\begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} ]
よって、後半部分の曲線は結局のところ以下のようになります。
[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot \left ( Q' \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \left ( \begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z \cdot P_3 - (z-1) \cdot P_2 \ P_3 \end{bmatrix} ]
おみごと。先ほどと同じようになっていることがわかります。終点の座標はそのままで（もっともです）、制御点は、元々の制御点と終点を比率zで混ぜ合わせたものになります。そして不思議なことに、新たな始点は2次のベルンシュタイン多項式に似た混ぜ合わせになります。ただし、(1-z)の代わりに(z-1)になっています。これらの新しい座標も、とても簡単に直接計算ができるのです！
というわけで、ド・カステリョのアルゴリズムではなく線形代数の方を使うと、どのような2次ベジエ曲線でもある値t = zで分割すれば2つのベジエ曲線となり、しかもその座標は簡単に求められる、ということがわかりました。
[ \begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z - 1)^2 \cdot P_1 \end{bmatrix} ]
および
[ \begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z \cdot P_3 - (z-1) \cdot P_2 \ P_3 \end{bmatrix} ]
3次の曲線についても同様です。ただし、実際の導出はあなたにとっておきますので（自力で書き下してみてください）、新しい座標の組の結果を示すだけにします。
[ \begin{bmatrix} 1 & 0 & 0 & 0 \ -(z-1) & z & 0 & 0 \ (z-1)^2 & -2 \cdot (z-1) \cdot z & z^2 & 0 \ -(z-1)^3 & 3 \cdot (z-1)^2 \cdot z & -3 \cdot (z-1) \cdot z^2 & z^3 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}
\begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z^3 \cdot P_4 - 3 \cdot z^2 \cdot (z-1) \cdot P_3 + 3 \cdot z \cdot (z-1)^2 \cdot P_2 - (z-1)^3 \cdot P_1 \end{bmatrix} ]
および
[ \begin{bmatrix} -(z-1)^3 & 3 \cdot (z-1)^2 \cdot z & -3 \cdot (z-1) \cdot z^2 & z^3 \ 0 & (z-1)^2 & -2 \cdot (z-1) \cdot z & z^2 \ 0 & 0 & -(z-1) & z \ 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}
\begin{bmatrix} z^3 \cdot P_4 - 3 \cdot z^2 \cdot (z-1) \cdot P_3 + 3 \cdot z \cdot (z-1)^2 \cdot P_2 - (z-1)^3 \cdot P_1 \ z^2 \cdot P_4 - 2 \cdot z \cdot (z-1) \cdot P_3 + (z-1)^2 \cdot P_2 \ z \cdot P_4 - (z-1) \cdot P_3 \ P_4 \end{bmatrix} ]
さて、これらの行列を見るに、後半部分の曲線の行列は本当に計算する必要があったのでしょうか？いえ、ありませんでした。片方の行列が得られれば、実はもう一方の行列も暗に得られたことになります。まず、行列Qの各行の値を右側に寄せ、右側にあった0を左側に押しのけます。次に行列を上下に反転させます。これでたちまち***Q'***が「計算」できるのです。
この方法で曲線の分割を実装すれば、再帰が少なくて済みます。また、数値のキャッシュを利用した単純な演算になるので、再帰の計算コストが大きいシステムにおいては、コストが抑えられるかもしれません。行列の乗算に適したデバイスで計算を行えば、ド・カステリョのアルゴリズムに比べてかなり速くなるでしょう。