Marching Cubes

• 類別: Sensing › 3D maps & reconstruction
• 標籤: mesh-extraction, 3d-reconstruction, geometry, mapping, isosurface

一種演算法，逐一處理由純量值組成的 3D 網格（例如符號距離場）中的每個立方體，從中取出表面的三角網格。

定義

行進立方體演算法（Marching cubes）把體積純量場轉換成其中一個等位集（稱為等值面）的多邊形網格。William Lorensen 與 Harvey Cline 於 1987 年在 SIGGRAPH 發表這個演算法，用來從 CT 與 MRI 等醫學掃描建立表面。如今，它是從截斷符號距離場（TSDF）地圖、佔據網格或神經場取出網格的標準方式。

演算法會逐一走訪由八個相鄰網格取樣點構成的每個立方體。每個角點都會拿它的值與等值水準（對符號距離場而言為零）比較，分類為內部或外部。八個二元角點產生 256 種組態，利用對稱性可化約成一小組基本情況（原始論文中為 15 種）；接著由一張查找表指出表面穿過立方體的哪些邊，以及如何把這些交點連成三角形。每個頂點在被穿過的邊上的位置，是以兩個角點值之間的線性內插求得，因此頂點的位置比網格間距更精細。表面法向量通常取自場的梯度。

這個方法有已知的限制。有些角點組態有歧義，原始的情況表可能在相鄰立方體之間留下破洞；後來的變體，例如漸近判定法與 Marching Cubes 33，或相關的行進四面體演算法，解決了這個問題。銳利的邊與角會被磨圓，這就是在銳利特徵很重要時，會偏好使用對偶輪廓法（dual contouring）及其他類似、運用梯度資訊的方法的原因。網格的細節與大小取決於網格解析度：對神經場而言，必須先在稠密網格上評估網路，而得到的網格不可能比該網格更精細。

為何重要

建圖系統與學習所得的場景模型以場的形式儲存幾何，而視覺化工具、物理引擎、碰撞檢查器與 CAD 軟體需要的是網格。行進立方體演算法是兩者之間常見的橋梁，因此它的解析度與瑕疵，直接決定機器人用來規劃與模擬的網格樣貌。

主要應用

• 在稠密 RGB-D 與光達建圖中，從 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