搜索
MarchingCubes算法MarchingCubes算法是三维规则数据场等值面生成的经典算法，于1987年由Lorensen和Cline两人在SiggraphProceedings(pp.163-169)提出。处理的对象一般是断层扫描（CT），或是核磁共振成像（MRI）等产生的图像。一、基本概念在MarchingCube算法中，体素是以逻辑上的六面体，由相邻层上的各四个像素组成的立方体上的八个顶点。等值面是空间中所有具有某个相同值的点的集合。它可以表示成这里的c是我们在三维重构过程中给定的阈值。二、算法简介算法的基本思想是逐个处理数据场中的立方体（体素），分类出与等值面相交的立方体，采用插值计算出等值面与立方体边的交点。根据立方体每一顶点与等值面的相对位置，将等值面与立方体边的交点按一定方式连接生成等值面，作为等值面在该立方体内的一个逼近表示。之所以这样，是由于MarchingCubes有个基本假设：沿六面体边的数据场呈连续性变化。也就是讲，如果一条边的两个顶点分别大于或小于等值面的值，则在该条边上有且仅有一点是这条边与等值面的交点。为了说明一下算法，先从2D图像开始。图1（a）是一张像素灰度值为0～3的图像。给定阈值1.5，黑色的点表示像素值大于1.5的像素。图1（b）（c）描述了等值线的抽取过程。图1（a）图1（b）：用空心小圈表示图1（c）：进行线性插值，求等值线与这条边相交出交点位置对于某棱边，如果它的两个端点v1、v2标记不同，那么等值面一定与此棱边相交。且交点坐标为：P=P1+(isovalue-V1)(P2-P1)/(V2-V1)其中P代表等值点坐标，P1、P2代表两个端点的坐标，V1、V2代表两个端点的灰度值，isovalue代表阈值。对于每个四边形来说，每个顶点两种情况（大于或小于），4个顶点共16种情况（图2a），考虑到旋转对称性，从新分类后可得4种基本模式（图2b）。图2这些2D图像正是3DMarchingCubes算法中立方体各个表面的等值线抽取情况。在3D中，由于每一立方体共有8个顶点，每个顶点共有2个状态（物体内和物体外），因此共有256种组合状态，分析立方体体素的2种对称性：（1）顶点状态反转，等值三角面片的拓扑结构不变，也就是讲，大于等值面与小于等值面的点是可以相互替换的。（2）旋转对称性，经过适当旋转，有许多状态是一致的。这样，可归纳出15种模式（见图3a）。对于模式0－7，其补充模式见图3b，而模式8－14，由于有4个顶点，本身就包括了自己的互补模式。图3a15种模式图3b0-7的补充模式在实现时，可按照立方体顶点状态构造等值面连接模式的查找表，并可直接由立方体各顶点的状态检索出其中等值面的分布模式，确定该立方体体素内的等值面三角片连接方式。三、算法歧义性及其解决MarchingCubes算法提出不久，就有人发现了它的歧义性。跟上面一样，还是从2D开始说起。先看一下图2b中的Pattern3。对这种Pattern，等值线的连接方式除了上图所标识的外，还有另外一种（见图4a）。图4对图4a的两种连接方式的不同选择，在同一张图像上可导致完全不同的结果（见图4b）。经过观察我们可知，这种歧义性只发生在：一个面上，如果一条对角线的两端点大于阈值，另一条对角线的两端点小于阈值的情况。在立方体中，我们把这种面称作歧义面。把这个问题放到3D上就产生了Hole问题。先回头看图3中的Patten3和它的补充模式3c。按上面的歧义面定义可知，Pattern3的底面Direct类型，而Pattern3c是Reverse类型。当我们把Pattern3c倒过来以后放到Pattern3下面就会产生下图最左边所示情况：图5图5还显示了Pattern10在Pattern6c上面（中间）和Pattern6在Pattern3c上面的情况。这种歧义性导致的结果可见图6。图6从上面可知，产生歧义性的原因是我们把3c等这些补充模式等同于对应的基本模式，从而导致在歧义面上Direct类型和Reverse类型交错使用。为了解决这个问题，提出两种扩展的MarchingCubes算法。第一种是把所有的歧义面都按Direct类型来连接。这样产生了23中模式（图7）。图7另一种刚好相反，所有歧义面都为Reverse类型，也有23中模式。图8和图9分别显示了产用上面两种扩展算法后，对应于图5和图6的结果：图8图9扩展的MarchingCubes算法虽然解决了Hole问题，但并没有解决歧义性问题。因为无论是Direct还是Reverse都是强制性的，并没有从图形本身出发。为此，G.M.Nielson等人提出了渐近线判别法。它通过计算等值面与体素边界面的交线（双曲线）的渐进线与体素的边界面的相互位置关系来判断等值面的正确连接方式。在一般情况下，等值面与体素边界面的交线是双曲线。该双曲线的两支及其渐近线与体素的一个边界的相互位置关系可用图10来表示。在该图所列的4种状态中，当双曲线的两支均与某边界面相交时，就产生了连接方式的二义性。此时，双曲线的两支将边界面划分为3个区域，可见，双曲线中两条渐近线的交点必然与边界面中位于对角线上的一对交点落在同一个区域内。图10：双曲线与体素边界的相互位置关系设双曲线的两条渐近线的交点坐标为(x,y,z)。当出现二义性时，需要计算f(x,y,z)的值。如果f(x,y,z)c，则渐近线的交点应与其函数值大于c的一对角点（立方体的顶点）落在同一区域内。如果f(x,y,z)c，则渐近线的交点应与其函数值小于c的一对角点落在同一区域内。这就是当出现二义性时，交点之间的连接准则，如图11所示。图11：二义性等值面判定在15种基本模式中，第0,1,2,4,5,8,9,11,14等9种不存在二义性面，因为它们只存在1种连接方式。第3,6两种模式，各存在一个二义性面，因此各有两种连接方式。第10,12两种模式，各存在两个二义性面，因而各有4种连接方式。第7种模式存在3个二义性面，因而各有8种连接方式。第13种模式存在6个二义性面，因而各有64种连接方式。在G.M.Nielson的算法中，根据每种模式的歧义面情况，对各个模式进行了细化。以Pattern3和Pattern10为例。Pattern3有一个歧义面，可细化为2种情况：图12Pattern10有两个歧义面，可细化为4种情况：图13立方体中间那点是为了连接成三角面片而加上去的，位置依赖于8个顶点的情况。将以上15种模式的各种情况加在一起，共有93种不同的连接方式，除去对称的和相同的方式，共有34种不同的连接方式[Nielson91a]。所以，虽然这种方法可以正确地修正二义性，但是需要额外的计算，并且比较繁琐。四、Marchingtetrahedrons（移动四面体）算法简介这是解决歧义性的较简单的一种算法。算法把一个立方体分割为若干个四面体，再在每个四面体上提取等值面。对于一个四面体，共有4个顶点、16中情况。由于对成性，最后只有3种基本模式、2种补充模式（图14）。图14从上图可知，Marchingtetrahedrons算法没有歧义性。把一个立方体划分为多个四面体有多种方法，图15展示了分为5个四面体的两种情况。图15图16展示了8个立方体中只有它们的共用点大于域值的等值面抽取情况（分别对应于图15的两种划分方法）。图16当然，我们也可以把立方体划分为6个四面体或更多。图17展示了划分为6个的情况及其等值面的抽取结果（对应于图16）。图17这种算法产生的3D表面要比MarchingCubes光滑，而且解决了歧义性问题。但同时产生了比MarchingCubes算法多得多的三角面片。