茂加部珈琲店

主にtech関連のメモ置き場です

有理Bスプライン曲線の非有理化

今回はNURBS曲線の小ネタです
非有理化と言っていますが、正しくは計算過程で一時的に次元を上げることができるよ、という話です
これを利用すれば、有理化を考慮していないアルゴリズム(Bスプライン用の計算など)に、NURBSを適用することができます

有理化されたn次Bスプライン曲線を、非有理(すべての重さが1)のn+1次Bスプライン曲線に変換する

n次の有理Bスプライン曲線は、簡単にn+1次の非有理曲線に変換することができます。　　 NURBS曲線の定義を思い出してみましょう

{ \displaystyle C(u) = \frac{\sum_{i=0}^{k-1} N_{i,n}(u)w_iP_i } {\sum_{i=0}^{k-1} N_{i,n}(u)w_i} }

注目するのは、{ w_iP_i}の部分です。例えば、{P_i}が三次元ベクトル {\begin{pmatrix} x_i \\ y_i \\ z_i \end{pmatrix}} で、ウェイト{w_i}が設定されているとすると、
{w_iP_i=\begin{pmatrix} x_iw_i \\ y_iw_i \\ z_iw_i \end{pmatrix}}となります。
ここで、{P'_i = \begin{pmatrix} x_iw_i \\ y_iw_i \\ z_iw_i \\ w_i \end{pmatrix}, w'_i = 1} とすれば、{w'_iP'_i=\begin{pmatrix} x_iw_i \\ y_iw_i \\ z_iw_i \\ w_i \end{pmatrix}}です。 xyz成分が一致しているので、これでなんとかなりそうです。
問題は、重み{w}が変更されてしまうので、分母が変わってしまうことです。{w'_i}はすべて1ですので、正規化係数の分母は1になり消えます
よって、このときのNURBSは { \displaystyle C(u) = \sum_{i=0}^{k-1} N_{i,n}(u)w'_iP'_i = \begin{pmatrix} \sum_{i=0}^{k-1} N_{i,n}(u)x_iw_i \\ \sum_{i=0}^{k-1} N_{i,n}(u)y_iw_i \\ \sum_{i=0}^{k-1} N_{i,n}(u)z_iw_i \\ \sum_{i=0}^{k-1} N_{i,n}(u)w_i \end{pmatrix} }

あら偶然、結果のw成分に、重みの変更で消えた分母が見えています。これで結果の全体を除算して、xyz成分だけを取り出すと、{\frac{\sum_{i=0}^{k-1} N_{i,n}(u)w_iP_i } {\sum_{i=0}^{k-1} N_{i,n}(u)w_i}}となり、正しい結果を得れることがわかります

まとめ

有理Bスプライン曲線を、Bスプライン曲線用のアルゴリズムに適用するときは、次のような手順で一時的にn+1次のBスプライン曲線に変換する

  • n+1次の新しいベクトルを用意し、先頭n次元にn次ベクトルの制御点座標をコピーする
  • コピーしたベクトルに、重さ{w}を掛ける
  • コピーしたベクトルのn+1次元要素に、重さ{w}をコピーする
  • (アルゴリズムを適用する)
  • 結果全体を、結果のn+1次元要素で割る
  • 結果の先頭n次元を取り出して終わり

多くの場合、重み付きn次元座標はn+1次元ベクトルとして保存されているので、コードにするとかなり単純になります。 ベクトルの計算やコピーは、最適化がきくかどうかなどで変わってくるので、一番早い方法を検証する必要がありそうです