Marching cubes: a high resolution 3D surface construction algorithm
William E. Lorensen Harvey E. Cline
General Electric Company
医療用の2Dデータから3次元の表面を構築したい。
2^8 = 256通りの立方体と表面の交差の仕方しかないので、これを事前に列挙しておけば良い。
しかし、手作業でやると大変でミスも起こりやすいので、工夫する。 nこの頂点が表面の内側にある時と、8-nこの頂点が表面の内側にあるときは等価。これにより128通りに削減できる。 さらに、回転を考慮することで14通りに削減できる。
頂点のインデックスを定め、順番に並べて8bitのインデックスとして 対応する表面を返す。
- 4つの連続するスライスをメモリに読み込む。
- 真ん中の2つのスライスからキューブを切り出す
- キューブの8つの頂点の密度を表面の値と比較し、インデックスを決定
- 事前に用意したテーブルから、インデックスを用いて生成するエッジのリストを得る。
- 各辺の頂点の密度を使用して、線形補完により面と辺の交点を求める。
- 中心差分法を用いて、キューブの各頂点における単位法線を求める。線形補完して、三角形の各頂点における法線を求める。
他の手法に比べてhigh resolutionな表面を構築できる。 重複した頂点の計算を省略することで、定数倍の高速化が可能。 形状のカットを行えるようにした（医療用）。
LolensenとClineは、従来の医療用の3D表面構築手法の解像度が低く、アーティファクトが生じるという課題を解決するため、3D空間を立方体で切り分け、その頂点における密度情報をもとに表面を構築するMarching cubesアルゴリズムを提案した。CT, MRI, SPECTなどのデータに適用し、高解像度の3D表面を構築することに成功した。
- surface reconstruction
当時(1998)はかなり時間がかかっていた(100s ~ 30min)らしく、対話的な使用は難しかった。
実装しようとしたが断念。 ルックアップテーブルを作るところのアルゴリズムがかなり複雑。面の中に含まれる頂点の数(0~4)で場合わけしようとしたが、3の時の 頂点の位置と、対応するカット面のインデックスの取得の方法がわからずに断念した。
14パターンそれぞれのカット面を決めておいて、入力されたパターンを回転させるなどして、14パターンに対応させていく方針がいいのかもしれない。 その場合、ビット列の回転をどう定義するのかという話になってしまうが...
次にやるときは、ルックアップテーブル自体は他のサイトや文献からコピペして使う方が良さそう。
あるいは、marching tetrahedraのほうは、ルックアップテーブルを作る苦しみはほとんどないので、そっちをやった方が実用的かも。