課題: 点群データからのメッシュ復元

入力点群	復元メッシュ

課題1: 点群データからのメッシュ復元

これまでに解説した内容を元にテンプレート・プログラム(トップページからダウンロードする)の内容を改変して、点群データからメッシュを復元してみよう。

変更するべき内容はいずれもsurface_recon.cppのファイル内にあり、それぞれは以下の通りである。

なお、前回同様、これらの箇所には最初の時点ではNOT_IMPL_ERROR()と書かれており、この状態で実行すると、実装されていない箇所がエラーとともに表示されるようになっている。

入力点群の位置の正規化 + オフセット点の生成

今回用いるcompact supportのRBFでは、実際のサポートの大きさをどの程度にするかによって、復元されるメッシュが大きく変化する。そのため、任意の大きさの入力点群に対して、適切なサポートのサイズを決定する必要がある。

通常は、点群を格納する木構造などを作成して、点と点の間の平均距離の定数倍などをサポート半径に用いるのだが、今回の実装では簡単のために、点群の位置を$[-1, 1]^3$の領域に入るように正規化しておき、そのスケールに対して定数でサポート半径を与える。

点群を含むバウンディング・ボックスの計算については、プログラム中に含んであるので、この情報を元に点群の位置を正規化すること。この位置の正規化は法線方向へ点をオフセットするときにも役に立つ。

位置の正規化が終了したら、実際にオフセット点を生成する。ここでもバウンディング・ボックスの大きさに対して一定の割合でオフセット幅を決定する。ただし、実際のオフセット幅を$l$としたなら、オフセットされた点$\mathbf{x}$と、それに対する最近傍点$\mathbf{c}$ならびにその法線$\mathbf{n}$を用いて、陰関数の参照値を$d_i = \mathbf{n} \cdot (\mathbf{x} - \mathbf{c}) / l$のように計算すること。

k-d木から最近傍点を取ってくる際には、法線の情報が取り出せるように、頂点の位置と入力点群の配列内での番号を持ったPoint型を定義してあるので、適宜、これをプログラムの中で、用いると良い。

なお、テンプレートプログラムの中ではxyzが頂点位置、valsが陰関数の参照値を格納する配列 (std::vector型)としてある。

RBF補間のための線形問題を解く

Wendland関数を用いて、$\phi$の値をオフセット点を含む、頂点の集合に対して評価して、線形問題のための疎行列を作成する。

この際、最も大きなデータでは入力点群の数が50000点程度になるため、全てのペアに対してRBFを評価してしまうと、計算時間が大きくなりすぎてしまう。

実際にはWendland関数はcompact supportなので、ほとんどのペアに対しては0を取るはずである。そこで、k-d木を用いてRBFのサポート半径内に入っている頂点だけを取ってきて、疎行列の要素を計算するようにする。

こうすることで、サポート半径の大きさにはよるものの、大幅に疎行列の構築にかかる計算時間を短縮することができる。

線形問題に対するソルバーとして、テンプレートプログラム内ではBiCGSTAB法を用いている。今回の実装は入力点群が多く、行列も大規模になるため、計算時間を反復回数によってコントロールできるように、反復法を用いている。

とはいうものの、ある程度速い計算機で、RBFのサポート半径を絞ってあれば、LDLT法などの直接法であっても十分に速く動作する。実際に試してみてほしい。

マーチング・キューブ法による曲面の抽出

本来であれば、マーチング・キューブ法を行う各グリッドのコーナー点に対して、適宜、陰関数の値を評価するのが(メモリ消費量の観点から)理想的ではあるが、今回の実装では、前回作成したマーチング・キューブ法のプログラムを使い回すために、一度ボリュームデータに陰関数の値を格納しよう。

各コーナー点における陰関数の値を評価する際、安直にはオフセット点を含む全ての入力点群を中心としたRBFの値を評価する必要がある。

繰り返しになるが、今回はcompact supportのWendland関数をRBFとして用いているので、各コーナー点に対してk-d木を用いてサポート半径内に収まる近傍点を取り出し、その点に対してだけRBFの値を評価すれば良い。

ここまで、k-d木を用いて、近傍点だけに適切に評価を行うよう実装できると、最大の50000点を含むデータ (=オフセット点を入れると150000点になる)に対しても、5分はかからずに曲面を抽出できるだろう。

課題2: RBF関数の変更とその効果について調査

今回の実装ではコンパクトサポートのC1級連続Wendland関数を用いた。これをより高次のWendland関数の他、ガウス関数や薄膜スプライン関数などに変更すると、メッシュの復元結果はどのように変化するかを調べよう。ただし、ガウス関数や薄膜スプライン関数はglobal supportなので、k-d木を用いた実装を変更する必要がある。

また、今回の実装ではRBFに、さらに1次の多項式項をつけて曲面を補間したが、これを2次の多項式へと拡張し、$x^2, y^2, z^2, xy, yz, zx$の項を追加すると、メッシュの復元結果はどう変化するかを調べよう。この際、1次の多項式を用いるものと2次の多項式を用いるものがコマンドライン引数によって切り替えられるようにプログラムを工夫すると良い。