网格生成之marching cube算法学习笔记

本博客内容来源于网络以及其他书籍，结合自己学习的心得进行重编辑，因为看了很多文章不便一一标注引用，如图片文字等侵权，请告知删除。

传统2D计算机视觉学习笔记目录------->传送门 传统3D计算机视觉学习笔记目录------->传送门

在学习网格生成算法的计划中，建议大家先了解Marching Cube（MC），为什么呢，他也不是一个端到端的网格生成算法？因为很多连续算法在最后提取等值面的时候都会采用marching cube或其改进版本，可以说是很多算法的最后一步。如果不理解这一步怎么做的，也很难理解其他算法之前的那么多计算的目的是什么。除此之外可以大大简化其他算法的解释过程，最后一步，就可以忽略不解释了。所以我们大家开始吧。

在前言中，我们提到了一个名词，叫做等值面，这是一个很重要的概念，在解释MC算法前，我们先来解释一下等值面。

等值面是什么？ 首先等值面是空间中的一个曲面，我们规定空间中每一个点都有一个属性值，属性值相等连续空间组成的曲面，我们称之为等值面。可能还是不太直接，跟我们网格生成有什么关系，我们接下来看。

那么真正的面在哪里呢？ 假如一个点在面的前方，我们标记为+1，一个点在真实面的后方，标记为-1，我们可以认为这个真正的面就在这两个点的中间。

我们还可以这么认为，就是空间内真正的面，会产生一个场，场内有无数个等值面，这个值我们暂且称之为空间场值，空间场值在面的前方为正值，后方为负值。离真实面越近，空间场值的绝对值越小，真实面的空间场值为0（暂定为0，也可以是其他的）。我们的目的就是在对这个场进行采样后，找到空间内真正的面，数值怎么获得我们这篇文章暂不关注。

我们大概介绍了等值面，那么怎么提取等值面呢？这就是Marching Cube算法的功能以及目的。 MC是 W.Lorensen等人于1987年提出来的一种体素级重建方法。MC算法也被称为“等值面提取”(Iso surface Extraction)算法。

下面我们一起开看看Marching Cube的算法思路，可能会对理解更有帮助，前提记住Marching Cube是为了提取空间中的等值面，并用三角面近似表示出来。

求出该六面体的边与0等值面（0等值面就是空间场值为0的等值面）的交点，将这些交点按照一定的拓扑连接关系连接起来，作为0等值面在该六面体网格中的近似表示。注意是近似表示，我们采用三角形。 简单的介绍完，可能还有很多的不明白的地方，我们罗列出来一个一个的解释：

前面我们提到过，我们有很多的已知采样点，并且知道这些点在空间中的空间场值，现在我们将空间分为很多个小格子，每个小格子都有8个顶点，我们通过计算8个顶点周围（范围与六面体的大小相关）的采样点，近似计算出8个顶点的空间场值（加权评价等方法）。我们就可以对六面体做以下分类，我们分析一下以下情况：

我们上面展示了等值面与六面体相交的情况一共就这样15种，其中还有一个没有交点的，也可以说14种。现在我们就需要精算出来，这个交点的具体的位置，下面我们举一个例子：

我们将交点坐标用P表示，P1、P2代表边上两个端点的坐标，V1、V2代表这两个端点上的值，V代表等值面值，那么交点坐标的计算公式如下（就是简单的线性差值，当然还有很多种方法，先简单介绍一个简单的线性插值）：

P = P1 + (V – V1)·(P2 – P1)/(V2 – V1)

那么现在我们对所有的含有等值面的六面体计算出了其与等值面的角点。下一步也就是最后一步，就是将这些角点链接成三角形就好了。我们来看看怎么做的。

其实这些拓扑结构，也在我们上图15中情况中，都花了出来，只要按照上图的表中已经记录好的连接关系，将三角形连接好就行了。这有点像废话，其实第一张连接关系的表不是计算机生成的，而是在较早的时候有人手动统计的，他考察了所有256种情况的体元配置并画出其中的三角形，这是何等的耐心。那通过算法该怎么生成呢？不知道Leetcode里面是否有这样的考题，(@ο@) ～

我们现在应该基本上理解了算法的思路，下面我们整理一下算法的流程。

而且Marching Cube的效率不是特别高，需要借助分层结构和并行计算。 而且Marching Cube生成面片的大小与六面体的大小相关，过大则会导致模型模糊，细节消失，过小会导致面片的数目过多。

但是从1987年提出Marching Cube至今，已经对其有了很多的改进和优化算法，在处理时间，减少内存开销，分辨率方面都有很大的优化。我们再在其他文章中进行介绍。

Marching Cube 作为提取等值面的最基本的方法，可以说是在研究网格生成里面最基础的算法，也是不可不知的算法。在了解该算法的基础上，对于接下来的几篇文章的理解会有很大的帮助。

重要的事情说三遍：

传统2D计算机视觉学习笔记目录------->传送门 传统3D计算机视觉学习笔记目录------->传送门

任何人或团体、机构全部转载或者部分转载、摘录，请保留本博客链接或标注来源。博客地址：开飞机的乔巴

作者简介：开飞机的乔巴（WeChat：zhangzheng-thu），现主要从事机器人抓取视觉系统以及三维重建等3D视觉相关方面，另外对slam以及深度学习技术也颇感兴趣，欢迎加我微信或留言交流相关工作。