计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (15): 75-79.

• 网络、通信、安全 • 上一篇    下一篇

一种均衡代价的网格简化方法

陈忆群1,2,曹瑾音3,林淑金2   

  1. 1.广东第二师范学院, 广州 510303
    2.中山大学,广州 510275
    3.中山大学 附属第一医院,广州 510080
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-21 发布日期:2011-05-21

Mesh simplification algorithm based on balanced cost

CHEN Yiqun1,2,CAO Jinyin3,LIN Shujin2   

  1. 1.Guangdong University of Education,Guangzhou 510303,China
    2.Sun Yat-Sen University,Guangzhou 510275,China
    3.The First Affiliated Hospital of Sun Yat-Sen University,Guangzhou 510080,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-05-21 Published:2011-05-21

摘要: 由于移动设备要求计算量小,一些经典的算法保形效果好,但计算量大,不太适合移动环境;而通用取中点的收缩方法虽然非常简化,但保形性不好。设计了一个在保持模型外观的基础上对网格模型进行简化和简化后的模型恢复的完整算法。首先设计了综合平均曲率大小和曲率变化量大小的特征保留折叠代价策略。平均曲率大小是利用边的两个顶点所邻接三角形片的两两法向夹角的平均值来计算特征保留折叠代价队列;同时考虑到存在的一些特殊情况提出加入曲率变化量来判断特征片面的特征保留策略。为了避免综合判断带来的计算量的增加,所设计的平均曲率代价和曲率变化量代价均是同一个Cost函数的线性组合。此外,还设计了基于权重代价的在折叠边上快速计算该边的收缩点位置的有效方法,基于Cost函数的线性计算,由于Cost函数在整个算法中可重复利用,因此在没有增加计算量的情况下又提高了保形性,在计算效率和简化质量两者之间取得了一个均衡。实验证明,该算法可以在保持模型外观的同时有效地降低模型规模并计算量较小,适用于计算能力低的移动设备运算环境。

关键词: 网格简化, 三角形网格, 二次误差测度, 移动环境

Abstract: Due to the requirements of small amount of computation in mobile devices,some classical algorithms perform good effect while large amount of computation is required which is unsuitable in mobile environment;general midpoint contraction is very simple,but is weak of shape preserving.This paper designs a complete algorithm for mesh simplification and model recoverage with reserving their original shapes and making them adaptable for display on mobile devices.This algorithm computes edge elapses cost with the normal angles of each two triangles adjacent to the two vertices of the edge,also provides a feature reservation strategy to identify the feature faces with the change of adjacent faces curvature.The strategy can effectively maintain the appearance and make full use of the cost function which reduce the amount of computation.Experiment shows that this algorithm is an effective method to compute contraction position for the folded edge,with higher calculation speed and better shape preserving for mobile device.

Key words: mesh simplification, triangle mesh, Quadric Error Metrics(QEM), mobile device