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