移動(dòng)立方體（Marching Cube，MC）算法是一種面繪制算法，該算法也被稱為等值面提?。↖sosurface Extration）算法。該算法于1987年被W. E. Lorensen提出，主要用于3D醫(yī)學(xué)圖像的面繪制[1]；Hoppe[2]和J. C. Carr[3]等人分別于1992年和2001年提出了不同的改進(jìn)方法，以將其用于點(diǎn)云表面重建。PCL基于1987年的文章實(shí)現(xiàn)了marching_cubes抽象類，并進(jìn)一步根據(jù)1992和2001年的文章分別實(shí)現(xiàn)了marching_cubes_hoppe和marching_cubes_rbf算法。下面根據(jù)上述3篇文章，分別介紹MC算法的原理和相應(yīng)的改進(jìn)方法。

首先介紹MC方法的基本原理。在1987年的論文中，3D醫(yī)學(xué)圖像被分解為多個(gè)體元（Cube），每個(gè)Cube包含8個(gè)頂點(diǎn)，如下圖1所示。具體操作過(guò)程如圖2所示。

1. 設(shè)置表面（surface）對(duì)應(yīng)的數(shù)據(jù)值iso_level。算法假設(shè)表面的數(shù)據(jù)值是一個(gè)常數(shù)。

2. 比較iso_level與8個(gè)頂點(diǎn)的數(shù)據(jù)值，大于等于iso_level的設(shè)置為1，表示頂點(diǎn)在表面內(nèi)部；小于iso_level的頂點(diǎn)設(shè)置為0，表示頂點(diǎn)在表面內(nèi)部。若一條邊的2個(gè)頂點(diǎn)分別為0和1，那么認(rèn)為表面會(huì)通過(guò)這條邊。因?yàn)?個(gè)頂點(diǎn)共有0和1兩種狀態(tài)，所以Cube會(huì)有2^8=256種情況，論文作者根據(jù)對(duì)稱等方法將這256種情況總結(jié)為15種，如圖3所示。

3. 查表確定表面會(huì)穿過(guò)哪些邊，并插值計(jì)算表面在Cube邊上的具體位置。作者提供了邊查找表以確定哪些邊需要插值，查找表的輸入為頂點(diǎn)狀態(tài)組成的8bit索引，如圖4（a）所示；輸出為Cube的12條邊的狀態(tài)（表面是否穿過(guò)該邊）組成的12bit數(shù)據(jù)，如圖4（b）所示。隨后使用線性插值方法確定表面在Cube邊上的具體位置。

4. 查表確定哪些頂點(diǎn)會(huì)形成三角形。作者也提供了三角形查找表以確定哪些頂點(diǎn)會(huì)連接成三角形，如圖5所示。查找表輸入仍為頂點(diǎn)狀態(tài)組成的8bit索引，輸出為構(gòu)成三角形3條邊的索引，其中每種情況最多形成4個(gè)三角形。

然后介紹Hoppe等人在1992年對(duì)MC算法的改進(jìn)。在點(diǎn)云表面重建中，無(wú)法像3D醫(yī)學(xué)圖像那樣直接獲取Cube頂點(diǎn)的數(shù)據(jù)值，Hoppe等人使用Cube頂點(diǎn)到點(diǎn)云的有符號(hào)距離（signed distance function）來(lái)表示該數(shù)據(jù)值。

1. 設(shè)置表面對(duì)應(yīng)的數(shù)據(jù)值iso_level，一般為0。

2. 計(jì)算Cube頂點(diǎn)到點(diǎn)云的有符號(hào)距離。首先找到距離Cube頂點(diǎn)最近的數(shù)據(jù)點(diǎn)n，然后計(jì)算Cube頂點(diǎn)到表面在點(diǎn)n處的切平面的距離。實(shí)際是計(jì)算Cube頂點(diǎn)到點(diǎn)n的向量與切平面法向量的點(diǎn)乘，計(jì)算結(jié)果保留符號(hào)。如圖6所示。

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

最后介紹J. C. Carr等人在2001年對(duì)MC算法的改進(jìn)。他們使用徑向基函數(shù)（Radial Basis Function，RBF）生成函數(shù)空間，其中在表面處的函數(shù)值為0.

要成為RBF函數(shù)φ(x)，需要滿足條件：對(duì)于某一個(gè)固定點(diǎn)c，滿足，即對(duì)于圍繞著某固定點(diǎn)c的等距的x，函數(shù)值相同[6]。常用的徑向函數(shù)有高斯函數(shù)，二次函數(shù)等，其中PCL使用的是。

我們希望找到一個(gè)函數(shù)f，對(duì)于表面上點(diǎn)x，有f(x)=0。這篇文章使用RBF函數(shù)的線性組合來(lái)表示函數(shù)f：[7]

另外為避免在不相關(guān)的地方產(chǎn)生f(x)=0，作者沿表面點(diǎn)的曲面法向量生成了一對(duì)離面約束點(diǎn)，一個(gè)在表面外，一個(gè)在表面內(nèi)，他們距表面的距離為d，從而可以得到另外2組方程f(x)=d和f(x)=-d。其中距離d不能設(shè)置的過(guò)大，要保證離面約束點(diǎn)到生成他的點(diǎn)的距離是最近的。如圖7所示，4個(gè)手指處生成的離面約束點(diǎn)不能交疊。

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

算法流程如下：

1. 設(shè)置離面約束點(diǎn)距離d

2. 根據(jù)現(xiàn)有點(diǎn)云數(shù)據(jù)，求解線性方程組，得到函數(shù)f(x)的參數(shù)

3. 使用MC方法確定三角面，其中Cube頂點(diǎn)數(shù)據(jù)值由f(x)定義

參考文獻(xiàn)

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（移動(dòng)立方體）算法_LV小豬精的博客-CSDN博客_mc算法

5. PCL庫(kù)中Marching Cubes（移動(dòng)立方體）算法的解析_y=520（2sinM-sin2M）的博客-CSDN博客_marchingcube

6. 從零開(kāi)始幾何處理：RBF函數(shù) - 知乎 (zhihu.com)

7. 三維重建 - 基于RBF的三維網(wǎng)格重建 - StubbornHuang Blog