Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (3): 806-811.DOI: 10.11772/j.issn.1001-9081.2019071163

• Virtual reality and multimedia computing • Previous Articles     Next Articles

Progressive mesh simplification algorithm for mobile devices

CHU Surong1,2, NIU Zhixian1, SONG Chunhua1, NIU Baoning1   

  1. 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).

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

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

  1. 1. 太原理工大学 信息与计算机学院, 太原 030600;
    2. 山西大学商务学院 实验实训教学中心, 太原 030031
  • 通讯作者: 牛之贤
  • 作者简介:褚苏荣(1990-),女,山西太原人,硕士研究生,主要研究方向:计算机图形建模、数据挖掘;牛之贤(1963-),女,山西长治人,副教授,硕士,主要研究方向:信息检索、数据挖掘、计算理论与算法;宋春花(1966-),女,山西大同人,副教授,博士,CCF会员,主要研究方向:计算机图形建模、可视化仿真、数据库建模;牛保宁(1964-),男,山西晋中人,教授,博士,CCF会员,主要研究方向:数据库系统性能管理、自主计算、云计算。
  • 基金资助:
    国家自然科学基金资助项目(61572345)。

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

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

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

CLC Number: