移动立方体算法原理

移动立方体（Marching Cube，MC）算法是一种面绘制算法，该算法也被称为等值面提取（Isosurface Extration）算法。该算法于1987年被W. E. Lorensen提出，主要用于3D医学图像的面绘制[1]；Hoppe[2]和J. C. Carr[3]等人分别于1992年和2001年提出了不同的改进方法，以将其用于点云表面重建。PCL基于1987年的文章实现了marching_cubes抽象类，并进一步根据1992和2001年的文章分别实现了marching_cubes_hoppe和marching_cubes_rbf算法。下面根据上述3篇文章，分别介绍MC算法的原理和相应的改进方法。

首先介绍MC方法的基本原理。在1987年的论文中，3D医学图像被分解为多个体元（Cube），每个Cube包含8个顶点，如下图1所示。具体操作过程如图2所示。

1. 设置表面（surface）对应的数据值iso_level。算法假设表面的数据值是一个常数。

2. 比较iso_level与8个顶点的数据值，大于等于iso_level的设置为1，表示顶点在表面内部；小于iso_level的顶点设置为0，表示顶点在表面内部。若一条边的2个顶点分别为0和1，那么认为表面会通过这条边。因为8个顶点共有0和1两种状态，所以Cube会有2^8=256种情况，论文作者根据对称等方法将这256种情况总结为15种，如图3所示。

3. 查表确定表面会穿过哪些边，并插值计算表面在Cube边上的具体位置。作者提供了边查找表以确定哪些边需要插值，查找表的输入为顶点状态组成的8bit索引，如图4（a）所示；输出为Cube的12条边的状态（表面是否穿过该边）组成的12bit数据，如图4（b）所示。随后使用线性插值方法确定表面在Cube边上的具体位置。

4. 查表确定哪些顶点会形成三角形。作者也提供了三角形查找表以确定哪些顶点会连接成三角形，如图5所示。查找表输入仍为顶点状态组成的8bit索引，输出为构成三角形3条边的索引，其中每种情况最多形成4个三角形。

然后介绍Hoppe等人在1992年对MC算法的改进。在点云表面重建中，无法像3D医学图像那样直接获取Cube顶点的数据值，Hoppe等人使用Cube顶点到点云的有符号距离（signed distance function）来表示该数据值。

1. 设置表面对应的数据值iso_level，一般为0。

2. 计算Cube顶点到点云的有符号距离。首先找到距离Cube顶点最近的数据点n，然后计算Cube顶点到表面在点n处的切平面的距离。实际是计算Cube顶点到点n的向量与切平面法向量的点乘，计算结果保留符号。如图6所示。

3. 使用MC方法确定三角面。

最后介绍J. C. Carr等人在2001年对MC算法的改进。他们使用径向基函数（Radial Basis Function，RBF）生成函数空间，其中在表面处的函数值为0.

要成为RBF函数φ(x)，需要满足条件：对于某一个固定点c，满足，即对于围绕着某固定点c的等距的x，函数值相同[6]。常用的径向函数有高斯函数，二次函数等，其中PCL使用的是。

我们希望找到一个函数f，对于表面上点x，有f(x)=0。这篇文章使用RBF函数的线性组合来表示函数f：[7]

另外为避免在不相关的地方产生f(x)=0，作者沿表面点的曲面法向量生成了一对离面约束点，一个在表面外，一个在表面内，他们距表面的距离为d，从而可以得到另外2组方程f(x)=d和f(x)=-d。其中距离d不能设置的过大，要保证离面约束点到生成他的点的距离是最近的。如图7所示，4个手指处生成的离面约束点不能交叠。

最后上述方程可以组合形成一个线性方程组，求解后即可得到f(x)。然后使用MC方法就可以得到三角化的表面。

算法流程如下：

1. 设置离面约束点距离d

2. 根据现有点云数据，求解线性方程组，得到函数f(x)的参数

3. 使用MC方法确定三角面，其中Cube顶点数据值由f(x)定义

参考文献

1. W. E. Lorensen, H. E. Cline. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics. 1987. 21(4): 163-169

2. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle. Surface Reconstruction from Unorganized Points. Proceedings of the 19th Annual Conference on Computer  Graphics and Interactive Techniques. 1992: 71-78

3. J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, T. R. Evans. Reconstruction and Representation of 3D Objects with Radial Basis Functions. Proceedings of the 28th Annual Conference on Computer  Graphics and Interactive Techniques. 2001: 67-76

4. MC（移动立方体）算法_LV小猪精的博客-CSDN博客_mc算法

5. PCL库中Marching Cubes（移动立方体）算法的解析_y=520（2sinM-sin2M）的博客-CSDN博客_marchingcube

6. 从零开始几何处理：RBF函数 - 知乎 (zhihu.com)

7. 三维重建 - 基于RBF的三维网格重建 - StubbornHuang Blog