基于MC算法的MEMS光刻仿真的三维重建方法研究
Flash
基于MC算法的MEMS光刻仿真的三维重建方法研究
王晓东, 范明聪, 沈连婠
中国科学技术大学 精密机械与精密仪器系,合肥 230027
摘 要: 以MC（marching cubes）算法为基础，提出了一种补全重建后生成的三维形体表面出现空洞的方法，使用该方法进行三维重建生成的三维形体具有完整的外表面和良好的可视化效果。提出了一种三维重建时对多个形体进行布尔运算的新方法，该方法以MC算法为基础，将三维重建和布尔运算相结合，可以简单、方便、高效的进行三维重建时的布尔运算。另外还介绍了三维重建后生成的三维形体的文件输出格式。
关键词: marching cubes；三维重建；空洞补全；布尔运算；文件输出
文献标示码: A 中图分类号: TP301.6
3D Reconstruction, Boolean Operation and File Export based on MC Algorithm
WANG Xiao-dong, FAN Ming-cong, SHEN Lian-guan
Department of Precision Machinery and Precision Instrumentation, University of Science and Technology of China, Hefei 230027, China
Abstract: Based on MC (marching Cubes) algorithm, this paper applied a method that can cap holes in the object surfaces generated by 3D reconstruction. The object generated by this method has complete outer surfaces and good visual effects. This paper applied a new method that can do Boolean operations between several objects in 3D reconstruction, the method bases on MC algorithm, combines 3D reconstruction and Boolean operation, can simply, conveniently and efficiently do Boolean operation in 3D reconstruction. This paper also introduced file export format for objects generated by 3D reconstruction.
Keywords: marching cubes; 3D reconstruction; cap holes; Boolean operation; file export
1 引言
自20世纪90年代以来，综合了计算机图像处理与分析、真实感计算机图形学、虚拟现实等技术的三维重建和可视化技术一直是国内外研究与应用的热点。三维重建通过处理二维图像序列或者三维数据点云，生成三维形体，使重建后的三维形体能真实地再现物体的表面轮廓，改善可视化的质量。[1,2]
我们开发的MEMS（Micro Electromechanical System，即微电子机械系统）光刻仿真软件大量应用了三维重建与可视化技术，用来显示MEMS器件的立体图形和仿真运算结果。软件的系统结构如图1所示：对掩膜图形进行光学计算，得到理想的MEMS器件立体图形和光刻胶内部的光强分布；对光刻胶内部的光强分布数据进行三维重建，得到MEMS器件的仿真立体图形；理想的MEMS器件立体图形和MEMS器件的仿真图形进行布尔运算，可以求出两者之间的形状误差。可见软件重点包含了两个模块，即光学计算模块和可视化模块，可视化模块重点实现了三维重建和布尔运算的功能。MC（Marching Cubes，移动立方体）算法是三维重建中构造等值面的方法里最具代表性的方法之一，在软件的可视化模块中，我们就是以MC算法为基础，来实现三维重建和布尔运算功能的。
图1 MEMS光刻仿真软件的系统结构
MC算法主要用来绘制等值面，当等值面与数据场边界相交时，重建生成的三维形体外表面在数据场边界处会产生空洞，我们提出了一种可以将这些空洞补全的方法，使用该方法进行三维重建生成的三维形体具有完整的外表面和良好的可视化效果。在三维重建的过程中，我们提出了一种以MC算法为基础，可以对多个物体进行布尔运算的新方法，该方法以MC算法为基础，将三维重建和布尔运算相结合，可以简单、方便、高效的进行三维重建时的布尔运算。。为了方便数据的存储、共享和加工，我们三维重建生成的三维形体的文件输出格式也做了一定的研究。
2 Marching Cubes算法
MC算法是W.E.Lorrenson在1987年提出的,它被认为是迄今为止应用最广的面重建算法之一。[3,4] 在MC算法中，假定原始数据是离散的均匀三维数据点云，数学上可以表示为一个三维数据矩阵A（l×m×n）。我们将每相邻上下两层的4个对应数据点（共8个数据点）所组成的立方体看作一个体素，利用8个数据点的数值和等值面值的关系，判断这个立方体是否与等值面相交。如果相交则采用线性插值的方法计算出等值面与立方体边的交点，根据立方体每一顶点与等值面的相对位置，将等值面与立方体边的交点按一定方式连接成三角形，作为等值面在该立方体内的逼近表示。由于每一体素共有8个顶点，每个顶点有2种状态，因此一个体素共有256种组合状态。根据互补对称性和旋转对称性，可将这256种状态进一步简化成如图2所示的15种。逐个地处理三维数据场中的立方体(体素)，就可以得到一系列这样的三角形，处理完所有立方体之后，就可以得到三维数据场中逼近的等值面。
图2 15种基本的立方体状态
3 从等值面到三维形体
等值面是空间数据场中等于某个值的所有点的集合，空间数据场中大于等于（或者小于等于）该值的所有点的集合是一个三维形体，这个三维形体的外表面等于等值面再加上空间数据场边界表面上所有大于等于（或者小于等于）该值的点的集合。重建三维形体，或者说重建三维形体的外表面是三维重建的最终目的。MC算法主要用来绘制等值面，当等值面都在数据场的内部，或者说等值面与数据场边界不相交时，等值面和三维形体的外表面是一致的，如图3所示；但是当等值面与数据场边界相交时，等值面并不等于三维形体的外表面，而是少了数据场边界表面上所有大于等于（或者小于等于）等值面值的那部分点集，以上情况在图形上表现为三维形体外表面在数据场边界处会产生空洞，如图4所示。为了生成完整的三维形体外表面，必须把这些空洞补全，也即把数据场边界表面上大于等于（或者小于等于）等值面值的那部分点集形成的表面给绘制出来，如图5所示。
图3 与边界不相交时的等值面图
图4 与边界相交的等值面图
图5 补全空洞后生成的三维形体
在实践中，我们找到了一个比较简单方便的补全空洞，生成完整的三维形体外表面的方法。在MC算法中，假定原始数据是离散的均匀三维数据点云，数学上可以表示为一个三维数据矩阵A（l×m×n），设矩阵A中元素的最小值是amin，最大值是amax。根据MC算法的特性，当体素立方体中的八个顶点值跨越了等值面值时，说明这个体素立方体中有等值面。当等值面与空间数据场的某个边界表面相交时，把这个边界表面上的数据点取出来，形成一个二维数据网格。考虑如图6所示的典型情况，黑色的点表示数据值大于等值面值的点，白色的点表示数据值小于等值面值的点，在图中绘出了边界表面上的等值线，等值线所围成的区域就是三维形体外表面上的空洞。如果在这个二维数据网格外面再加上一层数据网格，令这些新加上的数据网格的数据点值取一个远小于等值面值的数值（这里我们取矩阵A中元素的最小值amin），对于这个新形成的三维数据网格，利用MC算法绘制等值面，边界表面上的空洞会被自动补全，如图7所示。
图6 边界面上的数据点和等值线
图7 边界面上的空洞补全
考虑更普遍的情况，如果等值面与空间数据场的六个边界表面都相交，如图8所示。可以在原始三维数据网格的上下左右前后六个方向上各加上一层数据网格，即将原始三维数据矩阵A（l×m×n）扩展为B（（l+2）×（m＋2）×（n＋2）），并且令这些新加上的数据点的数值取原始三维数据矩阵A中元素的最小值amin，见公式1，那么对这个新形成的三维数据矩阵，使用MC算法进行三维重建，边界上的空洞会被自动补全，从而形成三维形体外表面，如图9所示。
(公式1)
图8 与边界表面都相交的等值面图
图9 补全空洞后生成的三维形体
利用这种方法生成的三维形体外表面存在一定的误差，如果空间数据场的采样数据足够多的话，误差一般在可以接受的范围之内。
4 布尔运算
在三维重建的过程中，可以对多个物体进行布尔运算。布尔运算通过对两个以上的物体进行并集、差集、交集的运算，从而得到新的物体形态。这里考虑最简单的情况，两个物体进行布尔运算。已知两个三维数据矩阵A和B，A和B行列数相同，例如都是l×m×n矩阵，矩阵A中元素的最小值为amin，最大值为amin。如果两个矩阵行列数不同，可以通过线性插值将两个矩阵变换为具有相同的行列数的矩阵。
传统的布尔运算过程如图10所示：利用MC算法对三维数据矩阵A进行三维重建得到三维形体a，对三维数据矩阵B进行三维重建得到三维形体b，然后a和b之间进行传统的三维形体布尔运算，得到一个新的三维形体c。
图10 传统的布尔运算过程
在实践中我们提出了一种新的布尔运算方法，过程如图11所示：先将三维数据矩阵A与B进行布尔运算，得到一个新的三维数据矩阵D，然后对这个新的三维数据矩阵D使用MC算法进行三维重建，得到一个新的形体d。可以通过理论和实践证明，传统的布尔运算得到的形体c和使用新方法得到的形体d是相同的。
图11 新的布尔运算方法
下面举例来说明三维数据矩阵A与B进行布尔运算的过程。例如，求三维数据矩阵A与B的差集，即进行“A减B”的布尔运算，取出A与B中的对应元素ai,j,k和bi,j,k，分下面4种情况进行讨论：
① 如果ai,j,k≥等值面值Ia，bi,j,k≥等值面值Ib，从几何学上来看，空间数据场中这点位于A和B生成的等值面的内部，三维形体进行布尔运算后这点应该位于新形体的外部；从代数学上来看，布尔运算1-1=0，最终将三维数据矩阵D中的对应元素di,j,k的数值设为矩阵A中的元素最小值amin。
② 如果ai,j,k≥等值面值Ia，bi,j,k＜等值面值Ib，从几何学上来看，空间数据场中这点位于A生成的等值面的内部，B生成的等值面的外部，三维形体进行布尔运算后这点应该位于新形体的内部；从代数学上来看，布尔运算1-0=1，最终将三维数据矩阵D中的对应元素di,j,k的数值设为矩阵A中的对应元素ai,j,k的值。
③ 如果ai,j,k＜等值面值Ia，bi,j,k≥等值面值Ib，从几何学上来看，空间数据场中这点位于A生成的等值面的外部，B生成的等值面的内部，三维形体进行布尔运算后这点应该位于新形体的外部；从代数学上来看，布尔运算0-1=0，最终将三维数据矩阵D中的对应元素di,j,k的数值设为矩阵A中的元素最小值amin。
④ 如果ai,j,k＜等值面值Ia，bi,j,k＜等值面值Ib，从几何学上来看，空间数据场中这点位于A和B生成的等值面的外部，三维形体进行布尔运算后这点应该位于新形体的外部；从代数学上来看，布尔运算0-0=0，最终将三维数据矩阵D中的对应元素di,j,k的数值设为矩阵A中的元素最小值amin。
经过以上布尔运算之后得到一个新的矩阵D， D中元素的值全部取自A中的元素的值，对矩阵D使用MC算法以Ia作为等值面值进行三维重建之后就得到了一个新的形体d。可以看出，矩阵D中的元素都是用矩阵A中的对应元素ai,j,k，元素最小值amin或者元素最大值amax经过重组之后得到的。D中元素的值也可以全部取自B中的元素的值，然后以Ib作为等值面值进行三维重建，得到的结果是相同的。并集和交集的布尔运算与上面所讲的差集的方法类似。
以MC算法为基础，在三维重建的过程中，新的布尔运算方法和传统的布尔运算方法相比较具有很大的优势。传统的布尔运算方法中三维形体间的布尔运算的算法极其复杂，难以掌握，而新方法中三维数据矩阵间的布尔运算则简单的多，相当于数值与数值的布尔运算，效率很高。新的布尔运算方法生成的三维形体存在一定的误差，如果空间数据场的采样数据足够多的话，误差一般在可以接受的范围之内。图12、图13、图14是利用新方法进行布尔运算的一个示例。
图12 两个原始形体
图13 布尔运算——差集，交集
图14 布尔运算——并集
5 文件输出
为了方便数据的存储、共享和加工，三维重建生成的三维形体可以输出为文件。虽然用来存储三维形体的文件类型很多，但是考虑到利用MC算法三维重建生成的三维形体是由大量三角面片组成的这种特性，使用STL文件格式或者VRML文件格式来存储更具有优势。
STL（Stereolithography，三角网格模型）文件是一种三维实体表述文件，广泛的应用于快速成型以及其它领域。STL文件由多个三角形面片的定义组成，每个三角形面片的定义包括三角形各个顶点的三维坐标，三角形面片的法矢量。三角形顶点的排列顺序遵循右手法则，三角形面片的个数按照STL文件的类型，有直接给出的，也有不给出的。STL文件中还包括其它一些信息，如文件名，文件描述等等。
按照上述格式把三维重建生成的三维形体存储为STL文件，就可以用于数据的存储、共享和加工了。图15表示将三维重建生成的三维形体存储为STL文件之后，在Unigraphics NX 3.0软件中打开的情形。
图15 在UG中打开生成的STL文件
VRML（Virtual Reality Modeling Language，虚拟现实建模语言）是一种专为万维网而设计的三维图像标记语言，也可以用于数据存储、共享和加工。VRML的扩展名是.wrl，整个VRML文件由多个节点组成，我们可以利用其中的IndexedFaceSet节点来存储三角面片。图16表示将三维重建生成的三维形体存储为VRML文件之后，用VRML浏览器观看该VRML文件的情形。
图16 浏览生成的VRML文件
6 结论
在开发MEMS光刻仿真软件可视化模块的过程中，我们以MC（marching cubes）算法为基础，提出了一种补全重建后生成的三维形体表面出现空洞的方法，使用该方法进行三维重建生成的三维形体具有完整的外表面和良好的可视化效果。提出了一种三维重建时对多个形体进行布尔运算的新方法，该方法以MC算法为基础，将三维重建和布尔运算相结合，可以简单、方便、高效的进行三维重建时的布尔运算。另外还研究了三维重建后生成的三维形体的文件输出格式。
参考文献:
[1] 田捷,包尚联,周明全. 医学影像处理与分析[M]. 北京:电子工业出版社,2003.
[2] 张季,王宜杰. 医学图像三维重建方法的比较研究[J]. 医学信息,2006,19(5),948-950
[3] Lorensen WE, Cline HE. Marching cubes: a high resolution 3D surface construction algorithm [J]. Computer Graphics, 1987, 21(4): 163-169.
[4] Cline HE, Lorensen WE, Ludke S, et al. Two algorithms for the re-construction of surfaces from tomograms [J]. Medical Physics, 1988, 15 (3): 320-327.
[5] 唐泽圣. 三维数据场可视化[M]. 北京:清华大学出版社,1999.
[6] 徐晓玲,李现民. 体素重建中的快速移动立方体方法[J]. 系统仿真学报, 2002, 14(4): 509 – 513
[7] 许寒,刘希顺. 三维空间规则数据场体可视化系统设计[J]. 计算机应用研究, 2003(1): 96 – 98