MacrhingCubes算法存在的问题及改进

我在MarchingCubes算法提取等值面的基本原理一文中简单的介绍了MacrhingCubes算法，但是这个这个算法也不是完美的，有很多缺陷。

缺陷一：拓扑连接二义性

MacrhingCubeS算法虽然是等值面提取的经典算法，但它也不是没有缺陷，其最大的缺陷就是六面体内三角面拓扑连接的二义性。在单元体的一个面上，如果值为0和为1的顶点分别位于对角线的两端，那么就会有两种可能的连接方式，此称之为拓扑连接的二义性，如图(4.1.2.1)所示。如果两个包含二义性面的单元体相邻的话，并且两个面的拓扑连接选择不一致的时候，就会出现/空洞/现象：

改进MacrhingCubeS算法，二义性的消除

MarehingCubeS算法二义性的消除，最为常见的方法就是采用渐近线方法。根据关系式：

F(x，y，z)=a0+a1x+a2y+a3Z+a4xy+a5yz+a6xz+a7xyz

我们可以方便的求出某等值面与单元体边界面的交线。假设某边界面所在的平面方程为z=z0，代入式F(x，y，z)=a0+a1x+a2y+a3Z+a4xy+a5yz+a6xz+a7xyz可以得到：

b0+b1x+b2y+b3xy=C0

很显然，等值面与单元体边界面平面的交线是双曲线。该双曲线的两支及其渐近线与单元体的一个边界的相互位置关系可用图(4.1.2.2)来表示。在该图所列的4种状态中，当双曲线的两支均与某边界面相交时，就产生了连接方式的二义性。此时，双曲线的两支将边界面划分为3个区域，可见双曲线中两条渐近线的交点必然与边界面中位于对角线上的一对交点落在同一个区域内。

方程式b0+b1x+b2y+b3xy=C0所示意的双曲线的两条渐近线的交点坐标为：

当出现二义性时,需要计算f(x,y,z0)的值。如果f(x,y,z0)>=C0，则渐近线的交点应与其函数值大于C的一对顶点落在同一区域内。如果f(x,y,z0)<=C0则渐近线的交点应与其函数值小于C的一对顶点落在同一区域内。这就是当出现二义性时，交点之间的连接准则，如图(4.1.2.3)所示：

缺陷二：效率低下

MarchingCubes算法的另一个缺点就是计算效率很低。在抽取一个等值面的过程中，有超过9%0的时间花在了对空单元体的检测上，同时它也没有一个好的数据缓冲方法，可以对相邻单元体之间所共享的信息进行重复利用。

改进计算效率：

(1)采用八叉树的分层结构来快速检测空单元体进行加速，它需要先建立一个八叉树，每个节点记录了输入数据中对应范围中的最大最小值，然后在抽取等值面的过程中，就可以快速地找到非空的单元体。

(2)等值面跟踪找到了一个非空的单元体以后，它的邻居的非空单元体也同时能够得到，利用这些信息可以大大地提高等值面的生成速度。

(3)并行计算MarchingCubeS算法对单个单元体处理过程是相当独立的，因此可以很容易地改造为并行算法。可以将原始的数据体集划分为几个互不相交的子集，然后就可以分发给几台联网的计算机，按照一定的通信协议开始并行计算，这样也将极大地提高等值面生成速度。