切片厚度加权的二次误差测度网格简化算法

武 帅， 黄庆学， 李宏杰， 张 弛

(1. 太原科技大学 电子信息工程学院, 山西 太原 030024； 2. 太原重型机械装备协同创新中心, 山西 太原 030024；3. 山西省互联网+3D打印协同创新中心, 山西 太原 030024； 4. 太原理工大学 机械工程学院， 山西 太原 030024)

STL(Stereolithography)是快速成型系统应用的标准文件类型之一， 是利用三角网格来显示三维模型. 目前广泛使用的三维数据获得方式有3种： 三维建模、 激光扫描和人像DIY. 随着卫星、 扫描仪、 图像仪器等先进技术的不断完善和发展， 人们可以得到越来越复杂， 越来越精细的模型， 而高精度、 强复杂的模型所需的三角面片数量越多， 对系统的要求也就越高， 因此对三角网格进行简化是必不可少的， 这也是快速重建的核心.

在上述研究的基础上， 本文提出一种切片厚度加权的二次误差测度网格简化算法. 采用半边拓扑结构进行模型重构， 减少模型顶点数及三角面片数， 提高计算性能， 在二次误差测度算法的基础上， 引入切片厚度加权， 准确反映模型表面的细微特征.

1 拓扑关系重构

在实际的应用中高复杂度的网格模型会带来诸多不变， 比如： 在动漫电影中， 网格越多， 最终呈现的速度就越慢； 在表达远近物体时， 远处的模型需要模糊一点， 显示模型的全部网格不仅显得多余， 还增加了系统的内存， 影响计算性能； 在虚拟世界中， 场景的连续转换更是对网格有极高的要求， 为了解决这些问题， 要充分利用网格的简化与重建， 降低网格复杂度， 提高响应速度.

图 1 半边拓扑简化结构Fig.1 Simplified structure of half topology

利用半边数据结构实现网格模型的简化需要获取三维模型网格顶点、 面以及半边数据， 对每一个顶点存储一个外向半边(半边起点)， 对每一个面存储一个边界半边， 对每一个半边确定半边的终点、 半边所属的面、 半边所在面的下一个半边、 半边对应相反的半边以及相反半边所在面的上一个半边.

半边结构在点、 线、 面邻接关系方面有良好的特性， 对网格简化操作有很好的效果， 只需要简单的定位就可以进行重构， 效率更高， 减少了三角形的顶点数和三角面片数， 大大地缩短了时间， 提高了计算性能.

2 简化算法描述

三角网格的简化是把用三角形网格表示的模型用一个近似模型来代替， 让近似模型基本保持原模型的大致形状与结构， 但顶点数目和三角形数目明显少于原始模型. 误差测度是通过量化模型输入、 输出之间的差异， 控制网格简化的方向和力度， 使最终生成的模型误差在用户允许误差范围之内， 因而其在网格简化中被广泛使用.

2.1 边折叠简化

二次误差测度准则存在于多种网格简化算法中， 该算法生成的网格质量较好， 简化速度也较快， 其中边折叠简化方法使用较多， 这是一种几何元素删除法， 研究的重点是如何选择新顶点， 也就是如何保证简化误差最小. 边折叠简化方法是按照一定的准则对网格模型中的边计算折叠误差， 根据折叠代价由小到大的顺序进行折叠操作， 折叠简化的核心是从网格中选定一对顶点v1,v2， 将两者合为一个新的顶点v′， 然后将与v1,v2相连的边连接到新的顶点v′上， 将关联的三角面片删除， 最终得到简化模型， 如图 2 所示.

图 2 边折叠操作Fig.2 Edge collapse

对于折叠代价的计算， 引用Garland[2]二次误差测度折叠简化算法， 将点到平面距离的平方作为误差测度， 具体步骤如下：

1) 将顶点定义为v=[x,y,z,1]T， 并为每个顶点定义一个4×4矩阵Q;

2) 计算二项式顶点初始代价Δ(v)=vTQv;

3) 顶点v1,v2的有效收缩点v′的选择以及边折叠代价Δ(v)=v′T(Q1+Q2)v′，其中：Q1,Q2为折叠前v1,v2的初始矩阵；v′为折叠后的新顶点.

点到平面距离的平方

d2(v)=Q(v)=

∑(pTv)2=∑(vTp)(pTv)=

∑vT(ppT)v=vT(∑Kp)v,

2.2 改进算法

Garland二次误差算法中误差测度Q是对所有三角面片进行求和得到的， 误差测度标准过于单一， 没有很好地反映出模型重构后表面的细微特征， 因此不少学者在这方面提出了自己的方案. 张文新等[9]提出将顶点曲率和三角形面积引入二次误差测度中， 较好地保留模型的细节特征. 刘峻等[10]提出将边折叠与局部优化进行结合的网格简化算法， 将顶点近似曲率引入到二次误差测度中， 对三角网格进行局部优化处理， 减少了狭长三角形的数量， 但几何误差有一定的限制. 李红波等[11]提出采用八叉树划分模型， 在经典二次误差测度的基础上， 引入顶点法向量夹角与边长作为权值的模型简化， 较好地保留了模型表面的细微特征， 但时间复杂度基本没有改变. V.Ungvichian等[12]提出的使用主曲率和方向进行网格简化， 在简化到较低分辨时， 模型的部分细节特征丢失严重. JL Tseng等[13]提出的基于扩展形状算子的三维曲面网格简化， 在二次误差测度算法上加以改进， 虽然其细节特征保持能力较强， 但是简化模型的狭长三角形较多.

在二次误差测度网格简化算法中， 边折叠的顺序和新顶点的位置是由原始模型三角面片的二次型误差决定的， 因此在每个三角面片的二次型误差上乘上权值将会改变边折叠的顺序， 影响新顶点的位置.

Garland二次误差算法是对整个网格进行简化， 网格模型由n个三角面片组成， 经分层后得到m个层， 由图 3 可以看出， 切片厚度较大时， 小的三角面片没有被切中， 造成模型特征的丢失， 切片厚度较小时， 层数增多， 降低算法的效率. 因而， 使用基于切片厚度因子加权的网格简化， 需考虑一个权因子Z， 满足随模型表面轮廓变化而变化.

Z=Zmin+(Zmax-Zmin)sinα,

式中：α为单位法向量与切平面Z轴的夹角；Zmin为最小切片厚度；Zmax为最大切片厚度.

图 3 分层切片Fig.3 Slicing

2.3 算法描述

采用半边数据结构在模型拓扑重建时可以快速构建出网格模型， 三角形顶点、 边和面的简化要充分考虑该顶点到相邻三角形平面的距离， 通过分析距离和最终分层切片的厚度关系是否影响到外部轮廓特征来决定简化操作. 将点到相邻平面距离的平方(d2)作为误差测度， 引入切片厚度因子Z， 改变折叠代价， 从而减少阶梯面的形成， 达到更好地保留模型表面细微特征的要求.

误差测度公式为

Q′(v)=(∑Z·Qi)(v).

算法实现的一般步骤如下： ① 读取三维网格模型数据， 并构建半边数据结构； ② 提取模型Z轴最高点和最低点的坐标值； ③ 按照最低点坐标值进行排序； ④ 计算各边的二次误差矩阵； ⑤ 计算边折叠代价并构造新顶点； ⑥ 将折叠代价按照从小到大的顺序进行排列； ⑦ 简化掉折叠代价的最小边； ⑧ 判断最终简化是否达到要求， 若达到， 则简化结束， 若没有达到， 返回第⑦步.

2.4 边界处理

模型简化时要先确定三角网格模型的边界， 在半边数据结构中， 一个边应当对应两个半边， 如果某一条边只对应一个半边， 则可以判定该边是一个边界边. 根据边界边寻找正确的边界面. 以面为特征， 构建STL模型的面法向量索引矩阵， 使得模型的边界得以很好的保持.

3 实验结果分析

在一台普通的PC(2.60 GHz CPU， 4.00 GB内存， Windows 7系统)上对本文算法进行验证， 测试几个STL文件格式的实例. 分别使用Garland网格简化算法、 文献[9]简化算法与本文的改进QEM网格简化算法进行对比.

表 1 给出了Garland算法与本文算法在运行方面的比较.

表 1 算法比较

图 4 所示的是对顶点数为3 474， 面片数为5 804 的牛模型的简化.

图 4 牛模型简化效果Fig.4 Simplified effect of cow model

图 4(a) 所示的是牛的原始模型， 图4(b)～(d)所示的是采用Garland算法对牛模型的简化， 图 4(e)～(g) 所示的是采用文献[9]算法对牛模型的简化， 图 4(h)～(j) 所示的是采用本文算法对牛模型的简化， 简化剩余的三角面片数分别为3 000， 1 484以及618.

图 5 所示的是对顶点数为35 016， 面片数为69 451的兔子模型的简化. 由于兔子模型三角面片数较多不易观察， 对每一个简化算法使用光照显示. 图5(a)所示的是兔子的原始模型， 图5(b)～(d) 所示的是采用Garland算法对兔子模型的简化， 图5(e)～(g)所示的是采用文献[9]算法对兔子模型的简化， 图5(h)～(j)所示的是采用本文算法对兔子模型的简化， 简化剩余的三角面片数分别为34 635， 13 800以及3 412.

图 5 兔子模型简化效果Fig.5 Simplified effect of bunny model

从图 5 可以看出， 在相同的简化条件下， 本文算法比Garland简化算法能更好地反映模型的细节特征， 相比文献[9]简化算法效率更高. 在经过大规模的简化后， 本文算法仍能保持模型的整体形状. 图4中在大规模简化条件下， 可以看到采用Garland简化算法牛的两个角部分特征丢失， 采用文献[9]简化算法虽然细节特征有所保持， 但会出现少量狭长的三角面片， 采用本文算法三角面片分布较合理， 在平坦的地方三角面片较少， 在变化大的地方三角面片较多； 图5中在大规模简化条件下， 可以看到采用Garland简化算法兔子的眼睛部位有点模糊， 采用文献[9]简化算法兔子的脚部分细节特征不完整， 这些信息在分辨率低时就很容易丢失， 采用本文算法细节特征基本还可以较好地体现出来.

4 结 论

从实验结果可以看出， 与Garland算法相比， 采用半边数据结构使得模型在简化时可以直接确定邻接关系， 使得拓扑重构的速度更快； 采用点到相邻平面距离的平方作为误差测度， 引入切片厚度加权来简化模型， 可以较好地反应模型的细节特征， 降低算法运行时间， 同时保持了模型较好的视觉效果， 提高了计算性能.

[1]Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization[J]. ACM Siggraph Computer Graphics, 1993, 27： 19-26.

[2]Garland M, Heckbert P S. Surface simplification using quadric error metrics[C]. Proceedings of the 24th Annual Conference on Computer Graphics and Interative Techniques, 1997： 209-216.

[3]Ozaki H, Kyota F, Kanai T. Out-of-core framework for QEM-based mesh simplification[C]. Eurographics Symposium on Parallel Graphics & Visualization Eurographics Association, 2015： 87-96.

[4]Jia Q, Liu Y, Gu X. Edge collapse mesh simplification algorithm based on detail features preserving[J]. Journal of Computational Information Systems, 2014,10(7)： 2883-2890.

[5]段黎明， 邵辉， 李中明. 高效率的三角网格模型保特征简化方法[J]. 光学精密工程， 2017, 25(2)： 460-468. Duan Liming, Shao Hui, Li Zhongming. Simplification method for feature preserving of efficient triangular mesh model[J]. Optics and Precision Engineering, 2017, 25(2)： 460-468. (in Chinese)

[6]吕书明， 张明磊， 孙树立. 基于简化和细分技术的三角形网格拓扑优化方法[J]. 计算机辅助设计与图形学学报， 2014, 26(8)： 1225-1231. Lü Shuming, Zhang Minglei, Sun Shuli. Topological optimization for triangular mesh based on simplification and subdivision[J]. Journal of Computer Aided Design and Computer Graphics, 2014, 26(8)： 1225-1231. (in Chinese)

[7]易兵， 刘振宇. 边界特征保持的网格模型分级二次误差简化算法[J]. 计算机辅助设计与图形学学报， 2012, 24(4)： 427-434. Yi Bing, Liu Zhenyu. New quadric metric for simplifying meshes to retain the feature edge[J]. Journal of Computer-Aided Design and Computer Graphics, 2012, 24(4)： 427-434. (in Chinese)

[8]张霞， 段黎明， 刘璐. 保持特征的高质量三角网格简化方法[J]. 计算机集成制造系统， 2014, 20(3)： 486-493. Zhang Xia, Duan Liming, Liu Lu. High quality triangular mesh simplification with feature-preserving[J]. Computer Integrated Manufacturing Systems, 2014, 20(3)： 486-493. (in Chinese)

[9]张文新， 温佩芝， 黄佳， 等. 一种改进的二次误差测度简化算法[J]. 桂林电子科技大学学报， 2015, 35(1)： 59-63. Zhang Wenxin, Wen Peizhi, Huang Jia, et al. An improved quadric error metric mesh simplification algorithm[J]. Journal of Guilin University of Electronic Technology, 2015, 35(1)： 59-63. (in Chinese)

[10]刘峻， 范豪， 孙宇， 等. 结合边折叠和局部优化的网格简化算法[J]. 计算机应用， 2016, 36(2)： 535-540. Liu Jun, Fan Hao, Sun Yu, et al. Mesh simplification algorithm combined with edge collapse and local optimization[J]. Journal of Computer Applications, 2016, 36(2)： 535-540. (in Chinese)

[11]李红波， 刘昱晟， 吴渝， 等. 基于二次误差度量的大型网格模型简化算法[J].计算机工程与设计， 2013, 34(9)： 3158-3162. Li Hongbo, Liu Yusheng, Wu Yu, et al. Simplification algorithm for large mesh models based on quadric error metrics[J]. Computer Engineering and Design, 2013, 34(9)： 3158-3162. (in Chinese)

[12]Ungvichian V, Kanongchaiyos P. Mesh simplification method using principal curvatures and directions[J]. Computer Modeling in Engineering & Sciences, 2011, 77(3)： 201-219.

[13]Tseng J, Lin Y. 3D Surface simplification based on extended shape operator[J]. Wseas Transactions on Computers, 2013, 12(8)： 320-330.