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 中。他们不在每一帧之后对整个地图重新生成网格，而只对数值发生变化的块运行移动立方体算法，并把得到的网格流式传输到可视化工具供操作员查看。在一次会话结束时，提取完整的网格，用网格抽取进行简化，并作为静态碰撞网格加载到仿真器中。网格中的孔洞通常意味着未被观测的空间或 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