面向移动端的渐进网格简化算法

doi:10.11772/j.issn.1001-9081.2019071163

计算机应用 ›› 2020, Vol. 40 ›› Issue (3): 806-811.DOI: 10.11772/j.issn.1001-9081.2019071163

• 虚拟现实与多媒体计算 • 上一篇下一篇

面向移动端的渐进网格简化算法

褚苏荣^1,2, 牛之贤¹, 宋春花¹, 牛保宁¹

1. 太原理工大学信息与计算机学院, 太原 030600;
2. 山西大学商务学院实验实训教学中心, 太原 030031

收稿日期:2019-07-03 修回日期:2019-09-10 出版日期:2020-03-10 发布日期:2019-09-19
通讯作者: 牛之贤
作者简介:褚苏荣(1990-),女,山西太原人,硕士研究生,主要研究方向:计算机图形建模、数据挖掘;牛之贤(1963-),女,山西长治人,副教授,硕士,主要研究方向:信息检索、数据挖掘、计算理论与算法;宋春花(1966-),女,山西大同人,副教授,博士,CCF会员,主要研究方向:计算机图形建模、可视化仿真、数据库建模;牛保宁(1964-),男,山西晋中人,教授,博士,CCF会员,主要研究方向:数据库系统性能管理、自主计算、云计算。
基金资助:
国家自然科学基金资助项目（61572345）。

Progressive mesh simplification algorithm for mobile devices

CHU Surong^1,2, NIU Zhixian¹, SONG Chunhua¹, NIU Baoning¹

1. College of Information and Computer, Taiyuan University of Technology, Taiyuan Shanxi 030600, China;
2. Teaching Center for Experiment and Practical Training, Business College of Shanxi University, Taiyuan Shanxi 030031, China

Received:2019-07-03 Revised:2019-09-10 Online:2020-03-10 Published:2019-09-19
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61572345).

摘要/Abstract

摘要： 针对现有渐进网格（PM）简化算法在网格高度简化时无法保持模型关键特征、简化速度慢、无法适应多种模型等问题，提出一种以可变参数结合二次误差和类曲率特征度的边折叠算法（QFVP），用于构建面向移动端的渐进网格。首先，该算法通过设置可变参数w，调整二次误差和类曲率特征度在边折叠误差中的相对大小，提升了算法的简化质量，扩大了算法的适用范围；其次，训练了一个误差反向传播（BP）神经网络，用于确定模型w值；再次，提出了边折叠过程中法向量线性估算法，提高算法简化速度，与Gouraud估算法相比，平均缩短网格简化时间23.7%。对比实验显示，QFVP简化生成渐进网格的基网格整体误差小于二次误差度量（QEM）算法和Melax算法；简化时间比QEM算法平均延长7.3%，比Melax算法平均缩短54.7%。

关键词: 渐进网格, 网格简化, 二次误差, 边折叠, Hausdorff距离, 误差反向传播神经网络

Abstract: To solve the problems that existing Progressive Mesh (PM) simplification algorithms are facing, such as, loosing key features when meshes are highly simplified, low simplification speed and limited applicability for various models, an edge-collapsing mesh simplification algorithm combining Quadric Error Metric （QEM） and curvature-like Feature value with Variable Parameter (QFVP) was proposed to build progressive meshes for mobile devices. Firstly, the variable parameter w was set to control the relative magnitude of quadratic error and curvature-like value in edge-collapsing error, improving the simplification quality of the algorithm and making the algorithm more applicable. Secondly, an error Back Propagation (BP) neural network was trained to determine the w value of the model. Thirdly, the normal vector linear estimation method in the edge-collapse process was proposed, which shortens the mesh simplification time by 23.7% on average compared to Gouraud estimation method. In the comparison experiments, the PM’s basic meshes generated by QFVP have smaller global error (measured by Hausdorff distance) than those generated by QEM algorithm or Melax algorithm. And QFVP has simplification time about 7.3% longer than QEM algorithm and 54.7% shorter than Melax algorithm.

Key words: Progressive Mesh (PM), mesh simplification, quadric error, edge-collapsing, Hausdorff distance, error Back Propagation (BP) neural network

中图分类号:

TP391.41

褚苏荣, 牛之贤, 宋春花, 牛保宁. 面向移动端的渐进网格简化算法[J]. 计算机应用, 2020, 40(3): 806-811.

CHU Surong, NIU Zhixian, SONG Chunhua, NIU Baoning. Progressive mesh simplification algorithm for mobile devices[J]. Journal of Computer Applications, 2020, 40(3): 806-811.

参考文献

[1] HOPPE H. Progressive meshes[C]//Proceedings of the 23rd Annual Conference on Graphics and Interactive Techniques. New York:ACM,1996:99-108.
[2] BILJECKI F,LEDOUX H,STOTER J. An improved LOD specification for 3D building models[J]. Computers,Environment and Urban Systems,2016,59:25-37.
[3] GARLAND M. Quadric-based polygonal surface simplification[D]. Pittsburgh,PA:Carnegie Mellon University,1999:35-82.
[4] 周元峰, 张彩明, 贺平. 体积平方度量下的特征保持网格简化方法[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.)
[5] 方惠兰, 王国瑾. 三角网格曲面上离散曲率估算方法的比较与分析[J]. 计算机辅助设计与图形学学报,2005,17(11):2500-2507. (FANG H L,WANG G J. Comparison and analysis of discrete curvatures estimation methods for triangular meshes[J]. Journal of Computer-Aided Design and Computer Graphics,2005,17(11):2500-2507.)
[6] 偶春生, 张佑生. 基于特征保持的曲面网格简化[J]. 计算机应用研究,2013,30(10):3162-3164,3168. (OU C S,ZHANG Y S. Mesh simplification method based on preserving shape features[J]. Application Research of Computers,2013,30(10):3162-3164,3168.)
[7] MELAX S. A simple,fast and effective polygon reduction algorithm[J]. Game Developer,1998,11:44-49.
[8] HOPPE H,DEROSE T,DUCHAMPY T,et al. Mesh optimization[C]//Proceedings of the 20th Annual Conference on Graphics and Interactive Techniques. New York:ACM,1993:19-26.
[9] 李红波, 刘昱晟, 吴渝, 等. 基于二次误差度量的大型网格模型简化算法[J]. 计算机工程与设计,2013,34(9):3158-3162.(LI H B,LIU Y S,WU Y,et al. Simplification algorithm for large mesh models based on quadric error metrics[J]. Computer Engineering and Design,2013,34(9):3158-3162.)
[10] 刘峻, 范豪, 孙宇, 等. 结合边折叠和局部优化的网格简化算法[J]. 计算机应用,2016,36(2):535-540.(LIU J,FAN H,SUN Y,et al. Mesh simplification algorithm combined with edge collapse and local optimization[J]. Journal of Computer Applications,2016,36(2):535-540.)
[11] 黄佳, 温佩芝, 李丽芳, 等. 保持细节特性的局部误差渐进网格简化算法[J]. 计算机应用,2016,36(6):1704-1708.(HUANG J,WEN P Z,LI L F,et al. Local error progressive mesh simplification algorithm for keeping detail features[J]. Journal of Computer Applications,2016, 36(6):1704-1708.)
[12] 焦越, 王慧青, 吴煜豪, 等. 结合面积度量和误差校正的网格简化算法[J]. 计算机工程与应用,2019,55(17):221-226.(JIAO Y, WANG H Q,WU Y H,et al. Mesh simplification algorithm combined with area measurement and error correction[J]. Computer Engineering and Applications, 2019, 55(17):221-226.)
[13] 段黎明, 杨尚朋, 张霞, 等. 基于遗传算法的三角网格折叠简化[J]. 光学精密工程,2018,26(6):1489-1496.(DUAN L M, YANG S P,ZHANG X,et al. Collapsing simplification of triangular mesh based on genetic algorithm[J]. Optics and Precision Engineering,2018,26(6):1489-1496.)
[14] 张德军, 何发智, 田龙, 等. 基于Z线和八叉树的高效Hausdorff距离计算方法[J]. 计算机辅助设计与图形学学报,2018,30(10):1794-1800.(ZHANG D J,HE F Z,TIAN L,et al. Efficient Hausdorff distance calculation algorithm based on Z-order and octree[J]. Journal of Computer-Aided Design and Computer Graphics,2018,30(10):1794-1800.)
[15] 朱苗苗, 潘伟杰, 刘翔, 等.基于BP神经网络代理模型的交互式遗传算法[J/OL].计算机工程与应用:1-8.[2019-02-27] http://kns.cnki.net/kcms/detail/11.2127.tp.20190225.1624.006.html. (ZHU M M,(PAN W J,LIU X,et al. The interactive genetic algorithm based on BP neural network and user cognitive surrogate model[J/OL]. Computer Engineering and Applications:1-8.[2019-02-27]. http://kns.cnki.net/kcms/detail/11.2127.tp.20190225.1624.006.html.)
[16] 彭育辉, 高诚辉. 基于形状修正的三角网格模型顶点法矢估算方法[J]. 中国图象图形学报,2010,15(1):142-148. (PENG Y H,GAO C H. An improved algorithm for vertex normal computation of triangular meshes based on shape correction[J]. Journal of Image and Graphics,2010,15(1):142-148.)

面向移动端的渐进网格简化算法

Progressive mesh simplification algorithm for mobile devices

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	吴孟桦, 胡晓兵, 李航, 江代渝. 基于图像配准的零件轮廓修正方法[J]. 计算机应用, 2020, 40(4): 1144-1150.
[2]	任帅, 张弢, 徐振超, 王震, 贺媛, 柳雨农. 特征点标注与聚类的三维模型信息隐藏算法[J]. 计算机应用, 2018, 38(4): 1017-1022.
[3]	黄佳, 温佩芝, 李丽芳, 朱立坤. 保持细节特性的局部误差渐进网格简化算法[J]. 计算机应用, 2016, 36(6): 1704-1708.
[4]	刘峻, 范豪, 孙宇, 陆向艳, 刘艳. 结合边折叠和局部优化的网格简化算法[J]. 计算机应用, 2016, 36(2): 535-540.
[5]	陈燕薛原杨若瑜. 任意衣物和人体的3D试穿实时仿真[J]. 计算机应用, 2014, 34(1): 124-128.
[6]	朱煜康宝生李洪安史芳玲. 一种改进的点云数据精简方法[J]. 计算机应用, 2012, 32(02): 521-544.
[7]	高晶孙继银刘婧. 基于邻域灰度信息的Hausdorff距离图像匹配方法[J]. 计算机应用, 2011, 31(03): 741-744.
[8]	薛峰袁成凤. 保持外形特征的网格简化算法[J]. 计算机应用, 2010, 30(9): 2431-2433.
[9]	冯立颖赵静杨莹. 基于轮廓特征点的三维模型相似性匹配算法[J]. 计算机应用, 2010, 30(4): 914-916.
[10]	张果刘旭敏关永. 一种基于曲率的边折叠简化算法[J]. 计算机应用, 2009, 29(3): 729-731.
[11]	周志强汪渤. 一种基于鲁棒Hausdorff距离的目标匹配算法[J]. 计算机应用, 2009, 29(1): 86-88.
[12]	张宏斌贾志新. 基于逆向思维的系统可靠性精确分配模型[J]. 计算机应用, 2009, 29(09): 2468-2470.
[13]	董方敏刘勇肖人彬. 一种改进的基于形状特征保持的QEM简化算法[J]. 计算机应用, 2008, 28(8): 2040-2042.
[14]	李嵩刘党辉沈兰荪. 基于ASM和线段Hausdorff距离的人脸识别[J]. 计算机应用, 2008, 28(5): 1217-1220.
[15]	陈华鸿周莎曹顺艇. 基于移动终端屏幕分辨精度的网格简化算法[J]. 计算机应用, 2008, 28(5): 1225-1228.