MarchingCube算法地综述

1、实用标准文案精彩文档Marching Cubes 算法Marchi ng Cubes 算法是三维规则数据场等值面生成的经典算法，于1987 年由Lorensen 和 Cline 两人在Siggraph Proceedings (pp. -169)提出。处理的对象一般是断层扫描(CT)，或是核磁共振成像(MRI )等产生的图像。、基本概念在 Marching Cube算法中，体素是以逻辑上的六面体，由相邻层上的各四个像素组成的立方体上的八个顶点。等值面是空间中所有具有某个相同值的点的集合。它可以表示成(塢”刃 |= c. c是常数这里的 c 是我们在三维重构过程中给定的阈值。二、算法简介算法的基

2、本思想是逐个处理数据场中的立方体(体素)，分类出与等值面相交的立方体，采用插值计算出等值面与立方体边的交点。根据立方体每一顶点与等值面的相对位置，将等值面与立方体边的交点按一定方式连接生成等值面，作为等值面在该立方体的一个逼近表示。之所以这样，是由于Marching Cubes 有个基本假设：沿六面体边的数据场呈连续性变化。也就是讲，如果一条边的两个顶点分别大于或小于等值面的值，则在该条边上有且仅有一点是这条边与等值面的交点。为了说明一下算法，先从 2D 图像开始。图 1 (a)是一像素灰度值为 03 的图像。给 定阈值 1.5，实用标准文案精彩文档黑色的点表示像素值大于1.5 的像素。图 1

3、 ( b ) ( c)描述了等值线的抽取过实用标准文案精彩文档对于某棱边，如果它的两个端点v1、v2 标记不同，那么等值面一定与此棱边相交。且交点坐标为：P=P1 + (isovalue - V1 ) (P2 - P1 ) / (V 2 - V 1 )其中 P 代表等值点坐标，P1、P2 代表两个端点的坐标，VI、V2 代表两个端点的灰度值，isovalue代表阈值。对于每个四边形来说，每个顶点两种情况(大于或小于)，4 个顶点共 16 种情况(图2a),考虑到旋转对称性，从新分类后可得4 种基本模式(图 2b )。程。等值线与这条边相交出交点位置实用标准文案精彩文档Configuration

4、s(a)Patterns(b)这些 2D 图像正是 3D Marching Cubes算法中立方体各个表面的等值线抽取情况。在 3D 中，由于每一立方体共有 8 个顶点，每个顶点共有 2 个状态（物体和物体外）， 因此共有256 种组合状态，分析立方体体素的2 种对称性：（1 ）顶点状态反转，等值三角面片的拓扑结构不变，也就是讲，大于等值面与小于等 值面的点是可以相互替换的。12实用标准文案精彩文档(2)旋转对称性，经过适当旋转，有许多状态是一致的。这样，可归纳出 15 种模式(见图 3a)。对于模式 0 7,其补充模式见图 3b，而模式 8 14，由于有 4 个顶点，本身就包括了 自己的互补

5、模式。图 3a 15 种模式实用标准文案精彩文档图 3b 0-7 的补充模式实用标准文案精彩文档在实现时，可按照立方体顶点状态构造等值面连接模式的查找表，并可直接由立方体各顶点的状态检索出其中等值面的分布模式，确定该立方体体素的等值面三角片连接方式。三、算法歧义性及其解决Marchi ng Cubes算法提出不久，就有人发现了它的歧义性。跟上面一样，还是从2D开始说起。先看一下图 2b 中的 Pattern 3。对这种 Pattern ，等值线的连接方式除了上图所 标识的外，还有另外一种（见图 4a）。(b) Alternate(u) DirectReverse*Direct了木丫/KIRan

6、dom实用标准文案精彩文档对图 4a 的两种连接方式的不同选择，在同一图像上可导致完全不同的结果（见图 4b ） 。经过观察我们可知，这种歧义性只发生在：一个面上，如果一条对角线的两端点大于阈值，实用标准文案精彩文档另一条对角线的两端点小于阈值的情况。在立方体中，我们把这种面称作歧义面。把这个问题放到 3D 上就产生了 Hole 问题。先回头看图 3 中的 Patten 3 和它的补充模式 3c。按上面的歧义面定义可知， Pattern 3 的底面 Direct 类型，而 Pattern 3c 是 Reverse类型。当我们把 Pattern 3c 倒过来以后放到 Pattern 3 下面就会

7、产生下图最左边所示情况:图 5 还显示了 Pattern 10 在 Pattern 6c 上面（中间）和 Pattern 6 在 Pattern 3c 上面的情况。这种歧义性导致的结果可见图6。从上面可知，产生歧义性的原因是我们把3c 等这些补充模式等同于对应的基本模式，从而导致在歧义面上Direct 类型和 Reverse 类型交错使用。为了解决这个问题，提出两种扩展的 Marching Cubes算法。图 5图 6实用标准文案精彩文档第一种是把所有的歧义面都按Direct 类型来连接。这样产生了23 中模式（图 7 ）。另一种刚好相反，所有歧义面都为Reverse 类型，也有 23 中模式

8、。图 8 和图 9 分别显示了产用上面两种扩展算法后，对应于图5 和图 6 的结果:实用标准文案精彩文档(b)llirect图 8实用标准文案精彩文档扩展的 Marching Cubes 算法虽然解决了 Hole 问题， 但并没有解决歧义性问题。 因 为无论是 Direct还是 Reverse 都是强制性的，并没有从图形本身出发。为此，G.M.Nielson等人提出了渐近线判别法。它通过计算等值面与体素边界面的交线(双曲线)的渐进线与体素的边界面的相互位置关系来判断等值面的正确连接方式。在一般情况下，等值面与体素边界面的交线是双曲线。该双曲线的两支及其渐近线与体素的一个边界的相互位置关系可用图

9、10 来表示。在该图所列的 4 种状态中，当双曲线的两支均与某边界面相交时， 就产生了连接方式的二义性。此时，双曲线的两支将边界面划分为3 个区域，可见，双曲线中两条渐近线的交点必然与边界面中位于对角线上的一对交点落在 同一个区域。图 10 :双曲线与体素边界的相互位置关系设双曲线的两条渐近线的交点坐标为(x, y, z)。当出现二义性时，需要计算f(x, y, z)的值。如果 f(x, y, z) c，则渐近线的交点应与其函数值大于c 的一对角点(立方体的顶点)落在同一区域。如果 f(x, y, z) c，则渐近线的交点应与其函数值小于c 的一对角点落在实用标准文案精彩文档同一区域。这就是当

10、出现二义性时，交点之间的连接准则，如图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的算法中，根据每种模式的歧义面情况，对各个模式进行了细化。以Pattern

11、 3 和 Pattern 10 为例。Pattern 3 有一个歧义面，可细化为2 种情况:实用标准文案精彩文档Pattern 10 有两个歧义面，可细化为4 种情况:图 12实用标准文案精彩文档立方体中间那点是为了连接成三角面片而加上去的，位置依赖于8 个顶点的情况。将以上 15 种模式的各种情况加在一起，共有 93 种不同的连接方式，除去对称的和相 同的方式，共有 34 种不同的连接方式Nielson91a。所以，虽然这种方法可以正确地修正 二义性，但是需要额外的计算，并且比较繁琐。四、Marching tetrahedrons（移动四面体）算法简介这是解决歧义性的较简单的一种算法。算法把一个立方体分割为若干个四面体，再在每个四面体上提取等值面。对于一个四面体，共有 4 个顶点、16 中情况。由于对成性，最后只有 3 种基本模式、2 种补充模式（图 14 ）。实用标准文案精彩文档图 14实用标准文案精彩文档从上图可知，March ing tetrahedro ns算法没有歧义性。把一个立方体划分为多个四面体有多种方法，图 15 展示了分为 5 个四面体的两种情况。图 16 展示了 8 个立方体中只有它们的共用点大于域值的等值面抽取情况（分别对应于图