基于MT算法的地质数据绘制
中图分类号：TP391.41文献标识码：A文章编号：10053824（2014）04-0035-04
0引言
科学计算可视化是指通过使用计算机图形学的方法将一些大规模数据转换为图形或者图像，使得它能以更直观的方式表现出来。三维空间数据场的可视化是它的核心[1]。对于三维空间数据场的成像，主要包括两类绘制方式：面绘制与体绘制。体绘制所得出来的图像不用进行分割就能直接绘制，能保留许多细节信息，所成的图像还更贴近真实；缺点是对每一个像素都需要进行处理，计算量偏大，降低了绘制图像的效率。相比较于前者，面绘制在确保能得到高质量图像的同时，还具有原理简单，易于实现等优点。且从现有硬件条件来说，面绘制的效率以及交互性能要优于体绘制[2]。
面绘制技术之中最具有影响力的是MC算法。MC算法虽然在很多时候能完成任务，但是该算法本身存在着一些缺点，例如它的面、体二义性等。如果不能解决这些问题，则会导致结果不能正确地反映出真实的图像。本文通过分析MC算法中生成等值面时产生的二义性问题，提出一种改进算法――移动四面体算法。该算法在把一个立方体分解成为多个四面体的同时，将二义面进行了分割，消除了连接方式上的二义性；然后，在保证公共面上的剖分一致性的前提下，维持了所有三角片拓扑结构的一致性，很好地消除了相邻面可能出现的空洞问题。因此，该算法不仅简化了处理，同时还保证了图像的质量。
1基本概念
1）体素。
在面绘制中，体素被定义为相邻层之间的8个点所组成的数据单元，每个由相邻的8个采样点所组成的立方体被称为一个体素。
在三维空间某一区域内进行采样，如果采样点在x，y，z 3个方向上的分布是均匀的，采样间距分别为dx，dy，dz，那么规则的体数据可以用三维数字矩阵来表示，即m（i，j，k）。
2）等值面。
等值面是空间具有某个相同属性值的一群点的集合。可以把它表示为
等值面的本质是一个三次曲面，它可以通过三角面来拟合而成。事实上并不是所有的体素内都有等值面，当8个角点的属性值都大于或者小于p的时候，这时在体素内是不存在等值面的；只有当该体素的一部分角点的属性值大于（或者小于）p时，且另一部分相反时，这个体素内才有等值面，且称这些体素为边界体素。
2MC算法及其二义性
2.1MC算法
移动立方体算法也被称为MC算法，该算法是由W.Lorenson在1987年提出来的[4]，也被称之为“等值面提取”算法。在使用它求取等值面的时候，需要预先设定一个阀值，然后依次比较每个小立方体的8个角点的属性值与阀值的大小。假设1个角点的属性值比阀值大的时候，设这个角点的状态值为0，若是小于或者等于阀值，则设该角点的状态值为1。由此可以得到，等值面与体素的相交情况共有28=256种，然后根据互补对称性和旋转对称性简化后，可以得到相交情况共15种结构[5]。其中，旋转对称性是指立方体素在3个方向上旋转90°的倍数，体素内的三角形拓扑结构不变。互补对称性是指等值面正反面互换与体素的每个顶点与等值面的关系同时逆转，不会影响等值面的三角片的拓扑结构，如图1所示。
MC算法的实现比较直接且简单，最后得到的图像也算不错。不过它也还存在着一些缺点，比如拓扑结构不一致，计算效率低等。其中，拓扑结构不一致的问题主要是因为在交点连接成三角片的时候存在着多种连接方式，这样就导致了三角片的拓扑结构不统一，出现拓扑结构不一致的情况[6]，称之为连接二义性。
2.2MC方法的二义性问题
MC算法中的连接二义性包括2种：一种是面二义性，另外一种被称为体二义性。
首先来看面二义性，所谓面二义性即是指根据三线性插值原理，可以得知等值面是一个双曲抛物面。所以，一般情况下等值面与体素的表面的交线是一对双曲线。如果双曲线的两边都同时与体素的边界面相交的话，那么就会产生4个交点，就会产生2种连接方式，如图2[7]，这时就会产生连接二义性。如果不能解决这种二义性，就会使得最后输出的图像产生裂缝。
然而除了体素边界面上的面二义性外，还有体二义性。体二义性是指即使在体素的表面没有二义性，三角形连接也没问题，但是在体素中还是可能存在连接二义性。当体元的一对体对角点的属性值都同时大于或者小于阀值时，这2个点可能相互分离，也可能相互连通，这就会导致连接方式上的二义性，如图3所示。
3MT算法及其实现
在MC方法中，最后交点连接时所产生的二义性如果处理不好的话就会导致结果出现很大的误差，那么如何才能有效地解决这个问题呢。接下来将介绍一种实用的解决算法――移动四面体算法。
移动四面体算法又叫MT（marching tetrahedral）算法，该方法是对MC算法进行改进得到的，主要是用于解决MC算法中的体二义性问题。MT算法将立方体剖分成为四面体，然后在各个四面体中来构造等值面。下面将先介绍剖分方法。
3.1立方体的剖分
在这里常用的剖分方法有将立方体剖分成5个四面体、6个四面体或者24个四面体等3种。其中：剖分成5个四面体有2种方式，剖分成6个四面体一共有4种剖分方式。在使用MT算法的时候一定要注意，MT算法是通过在将立方体剖分成四面体的同时使得二义面被分割线分割为2个三角形，分解后的三角形的拓扑结构与它的分割线相关。因此，在这里四面体的分割方式非常重要。不同的分割方式将会导致不同的三角形拓扑结构。虽然分割后每一个四面体体元中的三角片连接方式没二义性，但是如果划分四面体不合理的话，就会导致在所有三角片连接起来的时候出现缝隙。本文采用的是剖分成6个四面体的方式， 如图4。 这种方式合理地将立方体划分成了6个四面体，保证了相邻四面体公共面上的一致性，使得相邻面之间不会出现空洞。最后是剖分成24个四面体，这种方式是唯一剖分方式，没有剖分二义性。 3.2MT算法的具体实现
该算法的具体实现主要从MT算法中要用到的数据结构和MT算法的步骤2个方面来说明。
3.2.1MT算法中的数据结构
MT算法中主要需要用到的数据结构包括点状态值存储VerS、立方体剖分索引CST、点的属性值、点的坐标值、四面体顶点与边之间对应的PBC，以及等值点连接索引CMT。
首先是点状态值的存储VerS，在这里用的是一个长度为8的int型数组，其中里面存储的是一个六面体体素的8个顶点与阀值的关系，其中点属性值比阀值小的设为1，其余的设为0，该数组的顺序与立方体体素点编号顺序一样。
其次是属性值P2，P2是一个三维数组，是分别存储记录的每一个点的属性值。
立方体剖分索引CST，用一个6×4的二维数组表示，即是将一个立方体剖分成6个四面体，其中每一行存储的是一个四面体4个顶点的编号。
四面体边与顶点对应表PBC，PBC＼[i，j＼]是一个int型的二维数组，用于记录每条边相对应的2个顶点的顶点号。一个四面体是有6条边，其中i的取值范围是0-5，分别标识四面体的6条边。而每条边有2个端点，j的取值范围是0-1，其中0表示的这条边的起始点，1表示的是这条边的末端点。例如PCB＼[0＼]＼[1＼]表示的是第1条边的末端点点号，PCB＼[1＼]＼[0＼]表示第二条边的起始点点号。点号即是一个四面体的4个顶点的编号，是一个范围0-3的整数。
最后是等值点连接索引CMT，CMT[67]是一个16×7的二维数组，它的每一组值表示的是四面体内一种等值面点的连接方式，例如，CMT[i][j]，每当i变化的时候，都表示一种不同的连接方式。在CMT[i][j]中，j中的7个元素表示的是哪些边与等值面有交点。例如，CMT[1]= { 0，3，2，-1，-1，-1，-1}，表示第一种连接方式中，四面体的第0条、第3条和第2条边与等值面有交点，并且按0，3，2的顺序连接起来。
3.2.2MT算法的步骤
具体过程：
1） 从CST一次读取数据，每次读入4个元素，即为立方体划分后的四面体的顶点的编号。
2） 计算出这个四面体中的4个点的坐标，从P2中读取这4个点的属性值，从VerS中读取它们的状态值，并将这4个点的状态值存入state数组中。
3） 根据这4个点的状态值计算得到choosestyle，在这里这个变量主要是存储边与等值面相交情况索引，公式如下：∑3i=0state[i]*pow（2，i）， 其中pow（2，i）表示的是2的i次方，而state为存储该四面体4个顶点状态值的一个一维数组。
4） 根据边与等值面相交情况索引求出交点。
5） 根据choosestyle的值进入CMT，得到等值点连接方式索引，连接出三角片。
6） 再次读入CST的一组数据，对它们做25的步骤。
7） 依次遍历所有立方体，对它们重复上面的步骤。
在这里绘制三角片的时候，并不是单独地画每一个三角片，而是将所有交点按某种顺序依次存入了点数组TetrahedronInterction中，然后再一起进行绘制。最后在画三角片的时候为了减少内存开销，进行了一些轻微处理。通过建立一个新的索引，将许多距离较近的点合为一个点，减少了索引点的数量，达到了减少内存开销的目的。另外，在这里并不是采用线性插值的方法来计算等值面点的法向量，而是先计算出所有三角形的法向量，然后再建立一个索引，计算出每个点所在的三角形编号。最后将该点所在的所有三角形的法向量做平均，即得到了该点的法向量。
4实验结果
本次实验是通过绘制地质数据来完成的，其中图5和图6分别是取2种不同的阀值所绘制出来的图像。左边的是采用MC算法所绘制出来的图像，右边的是采用MT算法所绘制出来的图像。最后使用OPENGL工具包来进行三维显示。
5结语
本文主要以MC算法在三维空间绘图中产生的二义性为出发点，提出了它的改进算法―MT算法。该算法将立方体划分成四面体，把其中的二义面进行了分割。在保证剖分后相邻公共面的一致性的同时，相邻面之间也不会出现空洞。同时该算法与MC算法相比，简化了处理流程，计算量明显减小，提高了算法效率。最后通过绘制地质数据实验证明，MT算法能解决MC算法中的连接二义性问题，绘制出高精度的图像。
