结合边折叠和局部优化的网格简化算法

doi:10.11772/j.issn.1001-9081.2016.02.0535

计算机应用 ›› 2016, Vol. 36 ›› Issue (2): 535-540.DOI: 10.11772/j.issn.1001-9081.2016.02.0535

结合边折叠和局部优化的网格简化算法

刘峻^1,2,3, 范豪¹, 孙宇^1,2, 陆向艳^1,2, 刘艳⁴

1. 广西大学计算机与电子信息学院, 南宁 530004;
2. 广西信息科学实验中心, 广西桂林 541004;
3. 广西多媒体通信与网络技术重点实验室培育基地(广西大学), 南宁 530004;
4. 国家气象中心, 北京 100081

收稿日期:2015-07-16 修回日期:2015-08-31 出版日期:2016-02-10 发布日期:2016-02-03
通讯作者: 刘峻(1974-),男,广西贵港人,副教授,博士,主要研究方向:虚拟现实、并行计算。
作者简介:范豪(1990-),男,河南信阳人,硕士研究生,主要研究方向:图形图像处理、分布式仿真;孙宇(1981-),女,广西南宁人,讲师,博士,主要研究方向:智能计算;陆向艳(1973-),女,广西隆安人,副教授,硕士,主要研究方向:并行计算;刘艳(1972-),女,广西南宁人,副研究员,博士,主要研究方向:计算机仿真。
基金资助:
南宁市科学研究与技术开发计划项目(20156197);广西高校科研项目(KY2015YB008)。

Mesh simplification algorithm combined with edge collapse and local optimization

LIU Jun^1,2,3, FAN Hao¹, SUN Yu^1,2, LU Xiangyan^1,2, LIU Yan⁴

1. School of Computer and Electronic Information, Guangxi University, Nanning Guangxi 530004, China;
2. Guangxi Experiment Center of Information Science, Guilin Guangxi 541004, China;
3. Guangxi Key Laboratory of Multimedia Communications and Network Technology(Guangxi University), Nanning Guangxi 530004, China;
4. National Meteorological Center, Beijing 100081, China

Received:2015-07-16 Revised:2015-08-31 Online:2016-02-10 Published:2016-02-03

摘要/Abstract

摘要： 针对目前网格简化算法在将三维模型简化到较低分辨率时,网格模型的细节特征丢失、网格质量不佳的问题,提出一种保持特征的高质量网格简化算法。引入顶点近似曲率的概念,并将其与边折叠的误差矩阵结合,使得简化模型的细节特征在最大限度上得到保持。同时分析简化后三角网格的质量,对三角网格作局部优化处理,减少狭长三角形的数量,提高简化模型的网格质量。使用Apple模型和Horse模型进行实验,并与一种经典的基于边折叠的网格简化算法以及其改进算法之一进行对比。实验结果显示,两种对比算法三角网格分布过于均匀,局部细节模糊不清,而所提算法的三角网格在曲率大的区域稠密,在平坦处稀疏,细节特征清晰可辨;简化模型的几何误差的数量值与两种对比算法处于同一数量级;所提算法的简化网格的平均质量远高于两种对比算法。实验结果表明,在不扩大几何误差的情况下,所提算法不仅具有较强的细节特征保持能力,而且简化模型的网格质量较高,视觉效果较好。

关键词: 网格简化, 边折叠, 误差矩阵, 局部优化, 网格质量

Abstract: Aiming at the problems that the detail features of the mesh models are lost and the qualities of meshes are bad when the three-dimensional models are simplified to a lower resolution with the mesh simplification algorithms, a high quality mesh simplification algorithm was proposed based on feature preserving. By introducing the concept of approximate curvature of the vertex and combining it with the error matrix of the edge collapse in the algorithm, the detail features of the simplified model were reserved to a great extent. At the same time, by analyzing the quality of simplified triangular mesh, optimizing triangular mesh locally, reducing the amount of narrow triangles, the quality of simplified model was improved. The proposed algorithm was tested on Apple model and Horse model, and compared with two algorithms, one of them is a classical mesh simplification algorithm based on edge collapse, the other is an improved algorithm of the classical one. The experimental results show that when the models are simplified to a lower resolution, the triangular meshes of two contrast algorithms are too evenly distributed, and the local details are not clear, while the triangular meshes of the proposed algorithm are intensive in the areas with large curvature but sparse in the flat areas, and the local details are legible. Compared with the two contrast algorithms, the geometric errors of the simplified model in the proposed algorithm are of the same magnitude; the average qualities of the simplified meshes in the proposed algorithm are much higher than those of two contrast algorithms. The results verify that not only the proposed algorithm can efficiently maintain the detail features of the original model, but also the simplified model has high quality and looks better.

Key words: mesh simplification, edge collapse, error matrix, local optimization, mesh quality

中图分类号:

刘峻, 范豪, 孙宇, 陆向艳, 刘艳. 结合边折叠和局部优化的网格简化算法[J]. 计算机应用, 2016, 36(2): 535-540.

LIU Jun, FAN Hao, SUN Yu, LU Xiangyan, LIU Yan. Mesh simplification algorithm combined with edge collapse and local optimization[J]. Journal of Computer Applications, 2016, 36(2): 535-540.

参考文献

[1] SCHROEDER W, ZARGE J, LORENSEN W. Decimation of triangle meshes[J]. Computer Graphics, 1992, 26(2): 65-70.
[2] 周元峰,张彩明,贺平.体积平方度量下的特征保持网格简化方法[J].计算机学报,2009,32(2):203-212.(ZHOU Y F, ZHANG C M, HE P. Feature preserving mesh simplification algorithm based on square volume measure[J]. Chinese Journal of Computers, 2009, 32(2): 203-212.)
[3] 张霞,段黎明,刘璐.保持特征的高质量三角网格简化方法[J].计算机集成制造系统,2014,3(3):486-493.(ZHANG X, DUAN L M, LIU L. High quality triangular mesh simplification with feature preserving[J]. Computer Integrated Manufacturing Systems, 2014, 3(3): 486-493.)
[4] 易兵,刘振宇,谭建荣.边界特征保持的网格模型分级二次误差简化算法[J].计算机辅助设计与图形学学报,2012,24(4):428-434.(YI B, LIU Z Y, TAN J R. New quadric metric for simplifying meshes to retain the feature edge[J]. Journal of Computer-Aided Design& Computer Graphics, 2012, 24(4): 428-434.)
[5] 王海玲,王建,印桂生,等.多特征融合的网格模型简化方法[J].计算机应用,2013,33(11):3167-3171.(WANG H L, WANG J, YIN G S, et al. Multi-feature fusion method for mesh simplification[J]. Journal of Computer Applications, 2013, 33(11): 3167-3171.)
[6] GARLAND M, HECKBERT P. Surface simplification using quadric error metrics[C]//Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1997: 209-216.
[7] LI L, HE M, WANG P. Mesh simplification algorithm based on absolute curvature-weighted quadric error metrics[C]//Proceedings of 2010 the 5th IEEE Conference on Industrial Electronics and Applications. Piscataway, NJ: IEEE, 2010: 399-403.
[8] 赵晔,周畅,王昌.一种随机采样的特征保持的网格简化算法[J].计算机科学,2011,38(5):249-251.(ZHAO Y, ZHOU C, WANG C. Feature preserved mesh simplification algorithm based on stochastic sampling[J]. Computer Science, 2011, 38(5): 249-251.)
[9] UNGVICHIAN V, KANONGCHAIYOS P. Mesh simplification method using principal curvatures and directions[J]. Computer Modeling in Engineering & Sciences, 2011, 77(3): 201-219.
[10] TSENG J, LIN Y. 3D Surface simplification based on extended shape operator[J]. WSEAS Transactions on Computers, 2013, 12(8): 320-330.
[11] LEE Y, MARSHALL D. Curvature based normalized 3D compo-nent facial image recognition using fuzzy integral[J]. Applied Mathematics and Computation, 2008, 205(2): 815-823.
[12] 同济大学数学系.高等数学[M].6版.北京:高等教育出版社,2007:170-174.(Department of Mathematics of Tongji University. Higher mathematics[M]. 6th ed. Beijing: Higher Education Press, 2007:170-174.)
[13] CIGNONI P, ROCCHINI C, SCOPIGNO R. Metro: measuring error on simplified surfaces[J]. Computer Graphics Forum, 1998, 17(2): 167-174.
[14] CHEN C, CHENG K. A sharpness-dependent filter for recovering sharp features in repaired 3D mesh models[J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 14(1): 200-212.

结合边折叠和局部优化的网格简化算法

Mesh simplification algorithm combined with edge collapse and local optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

[1]	褚苏荣, 牛之贤, 宋春花, 牛保宁. 面向移动端的渐进网格简化算法[J]. 计算机应用, 2020, 40(3): 806-811.
[2]	郑卓然, 郑向伟, 田杰. 基于惩罚误差矩阵的同步预测无线体域网节能方法[J]. 计算机应用, 2019, 39(2): 513-517.
[3]	任帅, 张弢, 徐振超, 王震, 贺媛, 柳雨农. 特征点标注与聚类的三维模型信息隐藏算法[J]. 计算机应用, 2018, 38(4): 1017-1022.
[4]	许凯波, 鲁海燕, 程毕芸, 黄洋. 求解TSP的改进信息素二次更新与局部优化蚁群算法[J]. 计算机应用, 2017, 37(6): 1686-1691.
[5]	高国栋, 林明, 许兰. 基于似然分布调整的粒子群优化粒子滤波新方法[J]. 计算机应用, 2017, 37(4): 980-985.
[6]	倪志伟, 方清华, 李蓉蓉, 李一鸣. 改进蚁群算法在基于服务质量的Web服务组合优化中的应用[J]. 计算机应用, 2015, 35(8): 2238-2243.
[7]	何林知, 赵建民, 朱信忠, 吴建斌, 杨凡, 郑忠龙. 基于低秩矩阵恢复与协同表征的人脸识别算法[J]. 计算机应用, 2015, 35(3): 779-782.
[8]	陈燕薛原杨若瑜. 任意衣物和人体的3D试穿实时仿真[J]. 计算机应用, 2014, 34(1): 124-128.
[9]	金文标王旭松张智丰. 基于特征的图像网格生成方法[J]. 计算机应用, 2010, 30(9): 2427-2430.
[10]	薛峰袁成凤. 保持外形特征的网格简化算法[J]. 计算机应用, 2010, 30(9): 2431-2433.
[11]	张果刘旭敏关永. 一种基于曲率的边折叠简化算法[J]. 计算机应用, 2009, 29(3): 729-731.
[12]	陈华鸿周莎曹顺艇. 基于移动终端屏幕分辨精度的网格简化算法[J]. 计算机应用, 2008, 28(5): 1225-1228.
[13]	童晶关华勇. 面向影视动画的真实感三维人脸快速建模算法[J]. 计算机应用, 2007, 27(4): 1013-1016.