移动立方体算法面二义性问题研究

王铮　李瑞明

摘 要：在三维表面建模技术中，Marching Cubes算法是应用最为广泛的方法之一。该算法简单高效，但是也存在一定的不足之处，比如面的二义性问题。构造等值面时，在特定情况下对相同的等值点可以采取不同的连接方式，就会产生二义性，这将使得生成的等值面拓扑结构不一致，导致物体表面模型有孔洞。针对这一问题，本文提出了一种基于插值点连线交点的解决方法，通过计算插值点连线交点的场函数值，唯一确定二义性面上等值线的连接方式，解决了面二义性，保证了等值面拓扑结构的一致。

关键词：三维表面建模；Marching Cubes算法；二义性

中图分类号：TP311 文献标识码：A

Abstract：In the 3D surface modeling technology，Marching Cubes is one of the most widely used algorithms.The algorithm is simple and efficient，but there are also some shortcomings，such as the ambiguous cases.When constructing the isosurface，if different connection methods are applied on the same equivalent point in the specific case，ambiguity will be produced，which will cause the inconsistency of the generated isosurface topological structure，and eventually produce holes on the object surface.To solve this problem，this paper proposes a solution based on the intersection of interpolation points.By calculating the field function values of the intersection of interpolation points，the connection method of the isolines can be uniquely determined，which solves the ambiguity problem and guarantees the consistency of the isosurface topological structure.

Keywords：3D surface modeling；Marching Cubes algorithm；ambiguous cases

1 引言（Introduction）

三維表面建模是运用计算机图形学和图像处理技术，将科学计算过程中产生的数据及计算结果转换为物体的表面图形和图像显示出来，并进行交互处理的理论、方法和技术。随着科学计算可视化的发展，加之图形硬件的更新换代，三维建模技术越来越多的应用于生活、工程和科研领域[1]。作为三维表面建模技术的经典算法之一，Marching Cubes算法至今仍然被广泛使用，而针对算法存在的不足之处，也不断有学者和研究人员进行研究和改进[2]。本文首先介绍了Marching Cubes算法的基本原理，然后分析了面二义性问题并且介绍了两种经典的解决方案——四面体剖分法和双曲线渐近线法，最后借鉴双曲线渐近线法的思路提出了一种基于插值点连线交点的新方法，在解决面二义性问题的同时简化了计算步骤，缩短了运行时间。

2 Marching Cubes算法原理（The principle of

Marching Cubes algorithm）

Marching Cubes算法是目前三维表面重建中基于等值面抽取中最常用的方法。它在体素中提取等值面，通过逐个处理体素，对于与等值面相交的体素，用三角片近似表示其内部的等值面片。由于算法在构造等值面的过程中会依次处理每个体素，就好像沿着体素向前移动，这是算法得名的原因。

以三维矿体建模为例，Marching Cubes算法的步骤如下：

（1）读取相邻两层切片数据。

（2）体素化切片数据，将两切片对应的相邻四个像素构成一个立方体。

（3）按顺序逐个处理体素，确定每个体素内三角面片的剖分方式。首先要确定等值面的值，即阈值，通过比较体素顶点场函数值与阈值的大小关系确定体素是否和等值面相交。顶点与等值面的关系有两种，要么在等值面内（包括在等值面上），要么在等值面外，因此8个顶点与等值面的关系情况就有28即256种，即一个体素和等值面相交的情况有256种。接下来根据连接方式的互补对称性和旋转对称性，将256种相交情况进行化解，最终得到15种[3]体素内等值面的连接方式。

（4）求体素与等值面的交点。

（5）计算表面法向量，形成光照。

3 面二义性问题（The problem of ambiguous cases）

Marching Cubes算法的面二义性问题由J.Durst首先提出[4]。在一个和等值面相交的体素中，假设其中一个面与等值面有交线，在该面的四个顶点中，如果位于一条对角线上的一对顶点的场函数值都大于等值面阈值，而另外一条对角线上的两个顶点的场函数值都小于等值面阈值，那么此时等值线的连接方法有两种，这就是二义性问题，这样的面称为二义性面，如图2所示。如果二义性面刚好是两个相邻体素的公共面，在连接三角形面片的时候，一个体素采取图2（a）的连接方式，而另外一个体素采取了图2（b）的连接方式，此时就出现了相邻体素在公共面上等值面连接方式不一致的情况，最终会导致生成的物体表面出现“孔洞”，不能保证曲面的封闭性。endprint

4 经典解决方法（Classic solutions）

为了解决面二义性问题，不少学者进行了研究分析，得出了一些方法，下面就其中比较典型的方法进行介绍。

（1）四面体剖分法

四面体剖分是解决面二义性问题比较简单的一种方法。算法的思想就是把一个体素进行分割，将其分成几个四面体，然后在每个四面体内求取与等值面的交点、提取等值面。与立方体体素相比，四面体的面都是三角形，而三角形中等值线的连接方式是唯一的。对于每个四面体，每个顶点有两种状态，四个顶点一共有16种状态，根据对称性和反转性进行化解，最终等值面构型只有三种，如图3（a）所示。四面体与等值面是否相交的判断方法和立方体体素一样，都是根据顶点场函数值与等值面阈值的关系进行判断。如果顶点场函数值全部大于或者全部小于等值面值，那么该四面体与等值面不相交，如图3（a）所示；如果一个顶点场函数值大于等值面值而另外三个顶点的场函数值小于等值面值，或者相反，一个顶点场函数值小于等值面值而另外三个顶点场函数值大于等值面值，则四面体与等值面相交，如图3（b）所示；当四面体两个顶点场函数值大于等值面值而另外两个顶点的场函数值小于等值面值时，等值面构造如图3（c）所示。

四面体剖分有很多种方式，可以将立方体体素分为5个、6个或更多个四面体，分割的数量不同，产生的四面体形态也不同，比如当把立方体素剖分为5个四面体时形成的四面体并不全部相同，而剖分为24个四面体时形成的四面体是全部相同的。不同的划分方式有不同的特点，分成5个四面体时产生的三角面片较少，但是由于是不全等划分，处理起来比较复杂。分成24个全等四面体会产生较多的三角面片，但是插值计算过程比较容易。另外，在一个立方体体素中采用不同的方式剖分四面体生成的等值面构型[5]也不同，如图4所示。综上所述，虽然四面体剖分法可以解决二义性问题，而且生成的物体表面比较光滑，但是由于算法过程相对比较复杂，生成的三角面片较多，因此结果不是非常理想。

（2）双曲线渐近线法

双曲线渐近线方法是由G.M.Nielson[6]等提出的，该方法是面二义性问题最经典的解决方法。通常情况，体素表面与等值面的交线是双曲线。在二义性面上，交线的两个分支将体素平面分成三部分，不管如何划分，渐近线的交点都会和一条对角线上的两个顶点在同一个部分。如果渐近线交点的场函数值大于等值面的场函数值，则交点与场函数值大于等值面值的两个顶点在相同区域；如果渐近线交点的场函数值小于等值面的场函数值，则交点与场函数值小于等值面值的两个顶点在相同区域。这是双曲线渐近线方法的基本思想。

等值面与体素表面的相交关系有六种情况，相交产生的交点数量五种情况，其中交点数为2时相交关系有两种，如图5所示。相比四面体剖分法，双曲线渐近线法没有增加额外存储空间，而且算法效率比较高。

MC算法的面二义性问题会导致生成的物体表面出现孔洞，也就是生成的表面模型不正确。针对这一问题，本文借鉴双曲线渐近线的判别方法，提出一种解决方法，首先分别连接二义性面上处于对边的一对交點，两条连线会有一个交点，然后比较该交点场函数值与该面四个顶点的场函数值的关系来确定二义性面的连接方式。

（1）基本思想

Marching Cubes算法的前提是数据场沿着体素棱边呈线性变化，即立方体网格的每条棱边和等值面的交点最多为一个，每个面与等值面的交点最多为四个，其中与等值面交点为4的面是二义性面。重建物体表面时，等值点的连接是以直线段近似代替曲线的。因此一个二义性面上，两条等值线将把该面分为三个区域，如图6所示，而相对边插值点连线的交点一定和其中一对相对顶点处于同一区域。

假设图中实心点的场函数值大于给定的等值面阈值，在等值面内，而空心顶点的场函数值小于等值面阈值，在等值面外，此时只要计算对边插值点连线交点的场函数值，如果其值大于阈值，则该点也在等值面内，可以确定其与两个实心顶点在同一区域，如图6（a）所示，此时二义性面上中间的六边形区域在等值面内，两边的两个三角形区域在等值面外。相反，若对边插值点连线交点的场函数值小于等值面阈值，则其在等值面外，如图6（b）所示，此时二义性面两边的两个三角形区域在等值面内。因此通过计算对边插值点连线交点的场函数值即可确定二义性面的等值线连接方式。

（2）算法步骤

为了方便寻找二义性面，在算法实现过程中，除了要定义点类（CPoint）、边类（CEdge）和体素类（CCube）之外，还定义了面类（CSquare），以计算一个面与等值面的交点个数，从而判断是否是二义性面。在一个体素中使用插值点连线交点法确定二义性面连接方法的步骤如下：

a.读取一个体素；

b.读取第i++个面；

c.如果i<=5，则执行4，否则执行步骤e；

d.如果该面与等值面的交点个数n=4，则计算该面上对边插值点连线交点的场函数值，根据场函数值结果选择相应的连接方式，否则转到步骤b；

e.读取下一个体元数据。

在一个体元中查找面和查找一个面与等值面的交点数目n时，都要增加判断条件，当前体元六个面全部查找完毕后，要重新读取下一个体元数据；当前面不是二义性面或者是二义性面但是已经处理完毕后，要继续查找下个面。

（3）算法效果

本算法是借鉴双曲线渐近线算法得出的，双曲线渐近线算法已经解决了面二义性问题，而本算法在解决面二义性问题的前提下，相对双曲线渐近线算法而言，计算量较小，等值面与四条棱边的交点可以通过顶点坐标插值计算求得，因此其连线交点比计算双曲线渐近线交点要容易一些，当然算法的前提是在重建过程中以直线段近似代替双曲线。

由图7可见，比起双曲线渐近线法，基于插值点连线交点的方法重建结果也可以达到预期效果，没有出现由面二义性导致的表面孔洞现象。而二者的差别主要在计算量上，重建上述图形所需时间上表所示，使用插值点连线交点法重建三维表面所需时间少于双曲线渐近线法，而随着数据场规模的增大，这一特点将表现得更为明显。endprint

6 结论（Conclusion）

Marching Cubes算法的面二义性问题是因为连接方式不确定导致的。当两个相邻体素的公共面是二义性面时，只要保证两个体素在公共面上的等值线连接方式一样，就可以解决这一问题。本文借鉴了双曲线渐近线方法的思路，通过将二义性面进行区域划分来确定一种唯一的连接方式，不但解决了面二义性问题，而且因为计算简单，使得算法更加简洁高效，取得了较好的效果。

参考文献（References）

[1] Minho Chang，et al.Interactive marching cubes algorithm for intraoral scanners[J].The International Journal of Advanced Manufacturing Technology，2017，89（5-8）：2053-2062.

[2] Seungki Kim，et al.A Novel Interpolation Scheme for Dual Marching Cubes on Octree Volume Fraction Data[J].Computers & Graphics，2017，66（8）：169-178.

[3] Adriano Lopes and Ken Brodlie.Improving the Robustness and Accuracy of the Marching Cubes Algorithm for Isosurface[J].IEEE Transactions on Visualization and Computer Graphics，2003，9（1）：l6-29.

[4] Durst，M.J.Additional reference to Marching cubes[J].Comput.Graph，1988，22（2）：72-73.

[5] P.Cignoni，et al.Reconstruction of topologically correct and adaptive trilinear surfaces. Computers and Graphics，2000，24（3）：399-418.

[6] Nielson G，Hamann B.The asymptotic decider：resolving the ambiguity in marching cubes[C].Proceedings of Visualization' 91，Los Alamitos CA，1991.

作者簡介：

王 铮（1985-），男，硕士，助教.研究领域：计算机图形学.

李瑞明（1989-），男，硕士，助教.研究领域：算法研究.endprint