LabVIEW Marching Cubes算法实现

MarchingCubes(MC)算法是面绘制算法中的经典算法，它是W.Lorensen等人于1987年提出来的一种体素级重建方法。MC算法也被称为“等值面提取”(IsosurfaceExtraction)算法。LabVIEW之前发布过一个生物医学工具包“NI Biomedical Startup Kit 3.0”，其中医学图像的重建是基于MarchingCubes算法开发的，但数据类型是断层扫描的医学图像，对于点云重建无法适应，且只有32位版本，内存的使用要求很严苛，无法满足海量点云重建需求。 但Marching Cubes算法在点云重建算法里面是比较典型的，为此作者开了基于LabVIEW的Marching Cubes算法工具包。

Marching Squares算法

为了更好的理解Marching Cubes算法，先从2D图像的“Marching Squares”算法谈起，给定一个2D对象，如图1所示。

1）让我们用网格将其分隔，如图2所示：

2）接下来我们区分哪些网格交点在对象内，哪些网格交点在对象外，红点在对象内，蓝点在对象外，如图3所示。

3）寻找对象与网格的边界的相交边，并取边的中点（粉色点）如图4所示。

4）依次连接粉色点，构成粉色轮廓，该轮廓就近似逼近该对象的外部轮廓，如图5所示。

基于以上方法，网格划分越细，得到的轮廓越逼近对象的真实轮廓，当然计算量也就越大。

Marching Cubes算法

Marching Cubes算法与Marching Squares算法原理类似，也是基于网格划分。三维点云的划分用“体素”来划分，体素我以前的文章有讲过，可以翻阅“LabVIEW三维点云K邻域”这篇文章，详细介绍了”体素“及LabVIEW构建体素数据结构的方法,如图6所示.

每一个体素单元格都有8个顶点、12条边，如图7所示。

举例说明，假设顶点3在等值面之下，其余顶点在等值面上面，我们可以确定，2、3和11号边与等值面相交，既（3，2）、（3，0）、（3，7）,如图8所示。

这个相交的可能性前人总结过一共”256“中可能，并整理了顶点索引表，具体查看http://paulbourke.net/geometry/polygonise/，这里就不详细贴索引表了。

如何确定等值面

所谓等值面是指空间中的一个曲面，在该曲面上函数F(x, y, z)的值等于某一给定值Ft，即等值面是由所有点S = {(x, y, z)：F(x, y, z) = Ft}组成的一个曲面。

点云的重建是”体素“内部找到等值面，按照一定规则将等值面用多个三角形连接近似逼近该曲面。该原理的假设是三维点云表面是连续变化的（也就是点云的”法向“是连续变化的）。算法步骤如下：

1）计算”体素“内部点的法向，采用邻域点（主成分析法）估算每个点的法向，并一致朝外，如图9.

图9：计算点云法向并一致朝外

2）基于点的法向及体素内的点构建平面与立方体相交，并根据索引表构建三角形。

3）输出三角形顶点及三角形索引值。

以上简单介绍了MarchingCubes的算法原理。

LabVIEW Marhing Cubes算法

 LabVIEW Marhing Cubes基于以上算法原理，通过大量优化，并封装成一个VI,合并到”LabVIEW 3D Vision Advenced Toolkit“中，使该工具包重建方法不仅有”贪婪“点云三维重建，而且丰富了Marhing Cubes点云三维重建算子，如图10所示，计算完成后，存PLY三维文件。通过Geomagic Studio 打开文件查看重建质量（若存在孔洞、重叠等问题，该软件会在三维模型上标出）。如图11所示，重建质量相当不错（没有任何问题标出）！

2019年事情比较多，文章更新比较少，2020年刚好年假+武汉疫情爆发之际，宅在家里面，整理下算法思路，记录下来！

参考文献：

1. Marton, Z.C., Rusu, R.B., Beetz, M. 2009.On Fast Surface Reconstruction Methods for Large and Noisy Datasets. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Kobe, Japan.
2. Fabio, R. FROM POINT CLOUD TO SURFACE: THE MODELING AND VISUALIZATION PROBLEM. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXIV-5/W10, Zurich, Switzerland.
3. Lorensen, W. , Cline., H. 1987. MARCHING CUBES: A HIGH RESOLUTION 3D SURFACE CONSTRUCTION ALGORITHM. Computer Graphics (Proceedings of SIGGRAPH ’87), Vol. 21, No. 4, pp. 163-169.
4. Bourke, P. 1994. Polygonising a scalar field. University of Western Australia. Available from : http://paulbourke.net/geometry/polygonise/
5. Sharman, J. The Marching Cubes Algorithm. Available from: http://www.exaflop.org/docs/marchcubes/
6. Nguyen, T. Nearest Neighbor Search. Oregon State University. Available from: http://andrewd.ces.clemson.edu/courses/cpsc805/references/nearest_search.pdf
7. Christopher S. 2011. k-D Tree Nearest Neighbor Search. University of Akron, US. Available from: http://www.christopherstoll.org/2011/09/k-d-tree-nearest-neighbor-search.html
8. Bentley, J. Multidimensional Divide-and-Conquer. Carnegie-Mellon University. . Available from : http://www.cs.uiuc.edu/class/fa05/cs473ug/hw/p214-bentley.pdf
9. R. Mencl and H. Muller. Interpolation and approximation of surfaces from three-dimensional scattered data points. In: State of the Art Reports, Eurographics ’98, 1998, pp. 51–67.
10. H. Hoppe, T. Derose, T. Duchamp, J. McDonald, and W. Stuetzle.1992. Surface reconstruction from unorganized point clouds. In ACM Siggraph pp 71–78.
11. M. Gopi and S. Krishnan. 2002. A Fast and Efficient Projection-Based Approach for Surface Reconstruction.In: SIGGRAPH ’02: Proceedings of the 15th Brazilian Symposium on Computer Graphics and Image Processing, 2002, pp. 179–186.
12. Lecture 15: Principal Component Analysis. In: DOC493: Intelligent Data Analysis and Probabilistic Inference Lecture 15. Imperial College London. Available from: http://www.doc.ic.ac.uk/~dfg/ProbabilisticInference/IDAPILecture15.pdf
13. Smith, L. 2002. A tutorial on Principal Components Analysis. Available from : http://www.cs.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf
14. Vaillant, R. 2007. Recipe for Implicit surface reconstruction with HRBF. Available from : http://www.irit.fr/~Rodolphe.Vaillant/?e=12 .
15. Macedo, I. Gois, J.P., Velho, L. Hermite Interpolation of Implicit Surfaces with Radial Basis Functions. Vision and Graphics Laboratory, Instituto Nacional de Matematica Pura e Aplicada (IMPA), Rio de Janeiro, RJ, Brazil. Available from: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.1019.
16. F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva, and G. Taublin. 1999. The ballpivoting algorithm for surface reconstruction. IEEE Trans. on Visualization and Computer Graphics, 5(4):349–359.
    Page 32 of 32
17. H. Edelsbrunner and E. Muche. 1994.T hree-dimensional alpha shapes. ACM Trans. on Grphics
18. N. Amenta, M. Bern, and M. Kamvysselis. 1998. A new voronoi-based surface reconstruction algorithm. SIGGRAPH, pages 415–421,
19. H. Dinh, G. Turk, and G. Slabaugh. 2002.Reconstructing surfaces by volumetric regularization using radial basis functions. IEEE Trans. on Pattern Analysis and Machine Intelligence.
20. L. Fang and D. Gossard. 1995. Multidimensional curve fitting to unorganized data points by nonlinear minimization. Computer-Aided Design, 21(1):48–58.

=========================

有任何问题欢迎交流：