Marching Cubes

• カテゴリ: Sensing › 3D maps & reconstruction
• タグ: mesh-extraction, 3d-reconstruction, geometry, mapping, isosurface

符号付き距離場のようなスカラー値の 3D 格子から、立方体 1 つずつ処理して表面の三角形メッシュを取り出すアルゴリズム。

定義

マーチングキューブ法（Marching cubes）は、体積的なスカラー場を、その等値集合の 1 つである等値面のポリゴンメッシュに変換する。William Lorensen と Harvey Cline が 1987 年に SIGGRAPH で発表したもので、CT や MRI などの医用スキャンから表面を構築するためのものだった。現在では、打ち切り符号付き距離場（TSDF）の地図、占有格子、ニューラル場からメッシュを取り出す標準的な方法になっている。

このアルゴリズムは、隣接する 8 つの格子サンプルが作る立方体を 1 つずつ訪れる。各頂点は、その値を等値レベル（符号付き距離場では 0）と比較して内側か外側に分類される。2 値の頂点が 8 つあるので 256 通りの構成があり、対称性によって少数の基本ケース（元の論文では 15）にまとめられる。そのうえで参照表が、表面が立方体のどの辺を横切るか、その交点をどう三角形につなぐかを示す。横切られた辺上の各頂点の位置は、2 つの頂点の値の間の線形補間で求めるので、頂点は格子間隔よりも細かく配置される。面の法線は通常、場の勾配から得る。

この手法には既知の制約がある。頂点の構成によっては曖昧になり、元のケース表では隣り合う立方体の間に穴が残ることがある。その後の漸近判定法や Marching Cubes 33 などの変種、あるいは関連するマーチングテトラヘドラ法がこれを解決している。鋭い辺や角は丸められてしまうため、鋭い特徴が重要な場合には、勾配の情報を使うデュアルコンタリング（dual contouring）などの手法が好まれる。メッシュの細かさと大きさは格子の解像度で決まる。ニューラル場の場合は、まずネットワークを密な格子上で評価しなければならず、得られるメッシュはその格子より細かくはならない。

重要な理由

マッピングシステムや学習済みシーンモデルは形状を場として保存するが、可視化ツール、物理エンジン、衝突判定器、CAD ソフトウェアはメッシュを前提としている。マーチングキューブ法はこの両者をつなぐ通常の橋渡しであり、その解像度とアーティファクトが、ロボットが計画やシミュレーションに使うメッシュを直接左右する。

主な用途

• 密な RGB-D マッピングや LiDAR マッピングにおける TSDF 地図からのメッシュ抽出
• ニューラルな符号付き距離場や占有場のメッシュへの変換
• 3D スキャンからのシミュレーション用衝突メッシュの構築
• 正解メッシュに対する再構成品質の評価
• 医療用・産業用の体積スキャンからの表面再構成

実際の使われ方

移動ロボットで密なマッピングを行うチームが、深度カメラのフレームを、ボクセルサイズが数センチの TSDF に統合する。フレームごとに地図全体のメッシュを作り直すのではなく、値が変化したブロックだけにマーチングキューブ法を適用し、得られたメッシュをオペレーター用の可視化ツールにストリーミングする。セッションの終わりには完全なメッシュを取り出し、メッシュ間引き（decimation）で簡略化して、静的な衝突メッシュとしてシミュレーターに読み込む。メッシュの穴は、マーチングキューブ法そのものの欠陥ではなく、たいてい未観測の空間や TSDF の打ち切りを示している。

よくある誤解

• マーチングキューブ法は生の点から直接表面を再構成する — 格子上のスカラー場が必要であり、点はまず TSDF、占有格子、陰関数に統合しておかなければならない
• メッシュはボクセルサイズより正確にはなりえない — 頂点は立方体の辺に沿って補間されるので配置は格子より細かいが、ボクセルより小さい特徴はやはり失われる
• マーチングキューブ法は常に水密なメッシュを生成する — 元のケース表には穴が残りうる曖昧なケースがあり、場が打ち切られた所や観測されていない所では表面は開いている
• 鋭い辺は鋭いまま出てくる — この手法は角を丸める。鋭い特徴が重要な場合は、デュアルコンタリングや関連手法が使われる

知っておくべき人

• 深度センサから密な 3D 地図を作る知覚エンジニア
• スキャンから衝突メッシュを作るシミュレーションエンジニア
• 形状のニューラル暗黙的表現を扱う研究者

関連技術

• 打ち切り符号付き距離場（Truncated Signed Distance Field、TSDF）
• デュアルコンタリング（Dual Contouring）
• マーチングテトラヘドラ法（Marching Tetrahedra）
• KinectFusion
• Open3D
• scikit-image

関連用語

• Signed Distance Field
• Neural Implicit Representation
• Point Cloud
• SLAM
• Octree
• Neural Radiance Field

関連プロジェクト

• LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
• Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
• OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
• RTAB-Map: Versatile graph-based SLAM supporting RGB-D, stereo, and LiDAR with real-time operation
• pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
• LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)

動画

• Coding Adventure: Marching Cubes: Sebastian Lague
• Mesh from Math - The basics of Marching Cubes: Deadlock

ウィキペディア

• マーチングキューブ法