課題: マーチング・キューブ法とその拡張

ボリューム断面	復元メッシュ

課題1: マーチング・キューブ法の実装

これまでに解説した内容を元にテンプレートプログラム(トップページからダウンロードする)の内容を改変して、マーチング・キューブ法を実装しよう。変更するべき内容は以下の通り。

• volume.h内にあるボリュームデータを読み取る関数Volume::loadを完成させる。
• mcubes.cpp内にある大津の二値化により等値面を張るための閾値を決定するgetThresholdOtsu関数を完成させる。
• mcubes.cpp内にあるmarchCubes関数にあるfor文の内部に三角形取得するソースコードを追加する。

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

課題2: マーチング・キューブ法の発展を実装

通常のマーチング・キューブ法が完成したら、マーチング・キューブ法にある説明を参考に、Marching TetrahedraならびにDual Contouringの実装に挑戦してみよう。

今回の例のようにボリューム・データが入力となっている場合には、あまりこれらの拡張手法の恩恵は受けられないが、次回以降の点群データからの表面メッシュ復元においては、これらの発展的な手法が力を発揮する。

Marching Tetrahedraの実装方針

Marching Tetrahedraの実装はマーチング・キューブ法のそれと、大きくは変わらない。課題1で用いたマーチング・キューブ法のプログラムを参考に、最も単純には$2^4 = 16$の全てのパターンについて、三角形が生成される場所のリストを作成すれば良い。立方体を6つの四面体(=三角錐)に分割する部分についても、立方体の8つの頂点をどう結ぶと6つの四面体になるのかを表すテーブル(=配列)を用意しておくと楽だろう。

Dual Contouringの実装方針

Dual Contouringを実行するためには、キューブの立方体が持つ12のエッジについて、そのエッジがどの4つのキューブに共有されているのかを知る必要がある。今、陰関数を評価するバウンディング・ボックスの最も外側に位置するエッジ以外のエッジの本数はバウンディング・ボックスをキューブへと分割する分割数を$n$として$3 n (n-2)^2$本ある(各軸と平行なエッジがそれぞれ$n(n-2)^2$本ずつある)が、これらに対して上手く番号を降ることで、番号の計算だけから共有される4つのキューブを割り出すことができる。

例えば、x方向に平行なエッジに edges(0, i, j, k) (0はx軸ということ, i, j, kは各軸方向のインデックス)でアクセスできるように準備したとすると、このエッジを共有している4つのキューブは cubes(i, j, k), cubes(i, j + 1, k), cubes(i, j, k+1), cubes(i, j + 1, k + 1) のように表わすようにデータを持つようにしよう。

その上で、各エッジにはエッジ上で表面メッシュが交わる位置とその位置での法線を記録しておく (ボリュームデータを使う場合には、あまり本質的ではないが線形補間で計算しておく)。この情報を元に各キューブの中に発生させる頂点の位置を計算し、あとはキューブとエッジの隣接関係の情報を元に四角形を発生させる。この際、四角形は三角形2つとして表現するとよいだろう。

元々のマーチング・キューブ法の実装の代わりに、エッジとキューブを管理する必要があり、やや実装は煩雑にはなるものの、上記の方針に従えばむしろMarching Tetrahedraよりも簡単だろう。