基于边曲率的网格模型简化算法

王　竣，王修晖

(中国计量学院 信息工程学院，浙江 杭州　310018)



基于边曲率的网格模型简化算法

王竣，王修晖

(中国计量学院 信息工程学院，浙江 杭州310018)

【摘要】网格模型简化在计算机图形学与虚拟现实和生产制造领域有重要的研究意义.针对目前网格简化算法在大规模简化时丢失模型几何特征的问题，提出一种改进的半边折叠网格简化算法.引入边曲率近似度量的概念，同时将边曲率加入到误差测度中，从而改变了网格的半边折叠顺序，使网格模型简化后的细节能够准确地保留.实验结果表明，改进后的算法在同等简化率下能更好地保留原模型的细节特征，并且网格分配合理，执行速度快，误差小.

【关键词】网格简化;半边折叠;边曲率;细节特征

随着扫描设备的日趋成熟和普及，对网格模型高效地存储和传输的研究有着重要的意义.网格模型简化的实质是在尽量保持原来模型形状的前提下，用更少的网格去表示.目前，对于三角形网格的简化策略中，基于几何元素进行删除的方法应用较为广泛.根据在简化中删减几何元素的不同类型,分为点删除、边折叠和面片折叠三种.

1993年，Hoppe[1]等人基于边折叠思想提出了一种网格简化方法，利用一个优化的全局能量函数来确定模型边的折叠次序以及简化后生成新顶点的位置，最终的误差控制在较小的范围,但其算法时间复杂度高.1997年，Garland[2]针对Hoppe的方法缺点，提出一种改进误差测度的边折叠简化算法.该算法简化速度快，生成的网格形变少，但其误差定义为网格顶点到网格平面距离的平方和，单一的距离因素会使最终的简化模型丢失部分几何特征.

国内外近年来涌现出一批卓有成效的研究成果，文献[3]中以二次误差度量的边折叠为基本方法，实现一种面积加权半边折叠三角形网格模型简化算法.文献[4]中算法基于体积保持的多分辨率网格模型构造，误差标准选用了模型的体积改变绝对值，最后用边折叠的方法进行简化.文献[5]将网格顶点的尖锐特征度引入，很好地保留了网格特征，但唯一不足的是尖锐特征度的阈值和惩罚系数需要预先设置好，参数的选取需要通过大量的实验.文献[6]提出一种基于局部体积误差的简化算法，将误差函数定义为半边体积变化的绝对值和网格曲率因子的乘积，而曲率因子的计算较为复杂，新顶点的位置并没有依据网格体积的变化量确定.文献[7]提出一种基于张量投票理论阈值控制算法，具有良好的简化效果.文献[8]提出基于网格纹理信息的简化算法，计算模型几何信息以及纹理信息的全局误差，生成形状和纹理与原始模型相似的简化模型.

本文在计算网格模型的折叠误差的同时，改进原有的基于网格顶点曲率的算法，将边曲率概念引入到折叠误差的计算中，采用半边折叠方法减少简化过程中的存储量.实验结果表明，本文算法与文献[1]、文献[2]和文献[3]中三种算法比较，在相同简化条件下，尤其在简化率为90%～95%的条件下，本文算法不仅执行时间短，误差小而且能很好地保持原始网格模型的轮廓和细节特征.

1网格模型简化算法

1.1边折叠算法

边折叠算法(Edge Collapse)其核心思想是将三角网格中的边简化为一个顶点v′,修改拓扑关系，将与顶点v1、v2相关的边折叠至v′.算法首先计算网格模型中全部边在折叠操作时的折叠代价，按折叠代价递增的顺序排列，每一次只选取网格模型中的一条边进行操作，与其邻接的边将从队列中删除，删除后会重新计算其折叠代价，按边优先级递减的顺序插入到队列里，直到所有边都不满足折叠条件为止，如图1.

图1　边折叠变化比较图Figure 1　Edge collapse changes comparison

与边折叠算法类似，半边折叠算法的思想是将一条边的两个端点其中一个作为折叠操作后的新顶点，降低了计算复杂度，最重要的是折叠后新顶点的位置不需要重新计算，节省了存储开销.本文算法是基于半边折叠方法进行改进的，如图2.

图2　半边折叠前后的变化比较图　　Figure 2　Half edge collapse comparison chart before and after the change

1.2二次误差测度

网格模型简化的关键在于选取合适的边进行折叠操作，使得边折叠带给模型的视觉效果最好．而是否对模型中的边折叠，主要通过计算该边折叠后对模型误差的大小，即折叠代价决定的．每次折叠操作都选取代价最小的边，最终得到的简化模型与原始模型的误差会最小．

(1)

其中,

(2)

(3)

(4)

2基于边曲率的改进算法

为了有效地降低模型的简化误差，网格模型在进行半边折叠操作时总是要删除折叠代价小的边，而误差在计算中仅考虑距离这一因素.使得简化后网格分布十分均匀，在经过大规模的简化后(简化率为90%～95%)，原始模型将失去重要的几何特征.研究发现人的视觉特征对网格模型的细节特征比较敏感，因此在模型简化中应保留这些特征，算法要对网格区域进行合理划分.

2.1网格模型的曲率

基于近平面的合并简化主要是将位于同一个平面上的邻接三角形进行合并，目的是用数目较少的三角形网格表示更多的信息.首先选择一个初始三角形，对这个初始三角形邻接的三角形进行近似平面的判断.如图3，N1和N2分别为相邻两个三角形平面的法向量.拟定近平面参数μ(阈值)，若满足|N1×N2|<μ，即两个相邻三角面片近似共面.而实际上，网格模型是由一系列三角形面片所组成，并不存在曲率的概念，但是可以用其光滑表面的分段近似去近似得到曲率.

图3　近似平面判断Figure 3　Approximate plane judgment

文献[9]用离散曲率K表示顶点v的弯曲程度，定义如下：

(5)

其中vj表示离散曲面上与v相邻的顶点.Desbrun[10]等人提出一种计算网格顶点v处平均曲率更加精确的算法，定义如下：

(6)

文献[9]和文献[10]根据各自提出的近似顶点曲率计算方法，在二次误差项中加入后使得最终的简化结果保持了原有网格模型的几何特征.曲线的曲率度量了其方向向量转动的快慢程度，用近似曲率来描述离散网格的变化幅度，能够很好地反映网格的表面特征.网格在比较平坦的区域曲率值较小而对于棱角、棱边等细节明显区域曲率值较大.因此网格的顶点曲率对于保持简化后的几何特征具有十分重要的作用.

2.2改进算法描述

采取半边折叠方法时优先删除折叠代价小的边可以降低简化误差.而网格点的高斯曲率和平均曲率计算复杂，时间复杂度高，并不能达到快速简化的目的.

对于在同一个平面的表面，在对其表示时也仅需要较少的多边形，弯曲的曲面则需要更多的多边形去表示.在文献[2]中提出了用边曲率近似衡量半边折叠代价的方法，但由于其定义折叠权重因素没有考虑到折叠点周围的信息和折叠边长的长度，而实际上，被删除点的邻接三角形个数越多，包含的模型信息量就越多，将该点删除后会对整体网格的影响较大，而折叠的边长度越长，在模型中的重要程度就越高.由此，基于文献[2]的方法定义改进的半边折叠代价权重为

Cost(u,v)=

(7)

目前研究的三维几何模型都存在边界，一个良好的简化算法应能保持简化率的前提下尽量保持模型的边界特征.本文为了避免边界在简化过程中退化，通过提前为边界点设定一个趋向无穷大的误差权值，使边界边的折叠代价排在队列后面，以此避免折叠.该方法简单有效，对于边界特征的保持有很好的作用.

3算法执行流程

算法要处理的简化模型数据量大，同时需要算法有较快的执行速度，因此需要设计合理的数据存储结构，首先定义了顶点类，其中包括网格顶点的位置、索引值(ID)、顶点法向量、顶点邻接点、顶点的折叠误差、与该点相关联的三角形集合和处理函数.然后定义了三角形类，包括三角形顶点索引值、法向量、相关函数(半边折叠等).最后定义了网格类，包括三角形网格数据(Ply格式)，数据中包含顶点表和三角形表.

算法步骤如下：

Step1.将原始网格模型中顶点、三角网格数据读入,并对网格模型数据结构初始化.

Step2.用户输入期望简化率.

Step3.计算网格中每个三角面片的法向量,根据半边折叠代价公式(7)，计算半边的折叠代价Cost，按折叠代价递增顺序对半边进行排序，放入到优先队列中.

Step4.从优先队列中取出折叠代价最小的半边e进行半边折叠操作，检查e所在边E是否被删除，如果半边所在边E被删除，执行Step5，否则执行Step6.

Step5.按照顺序取出折叠代价小的半边e，检查其邻接边E是否已经被删除，直到取出的半边e所在边E没有被删除.

Step6.检查当前取出的半边e的折叠代价是否小于设定的阈值(期望的简化率)，如果小于阈值则结束Step3，如果大于阈值则进行半边折叠操作.

Step7.检查简化是否达到要求，如果没有达到，转到Step4.

Step8.算法终止：没有可折叠的边或存在可折叠的边，输出简化模型和简化时间.

4实验结果与分析

本文算法的实验环境为VisualStudio2013,运行在联想ThinkCentreM4500t系列台式机，配置为Intelcorei3-4150 3.50GHz双核、内存为4GB，显卡IntelHDGraphics4000.

本文提出的网格简化算法是基于三角形网格的半边折叠算法，用文献[1]算法、文献[2]中基于边曲率近似边折叠简化方法和文献[3]中基于QEM的面积加权简化方法同本文算法进行比较.图4是QEM算法[1]、边曲率近似折叠简化方法[2]和基于QEM的面积加权简化方法[3]和本文算法对一个拓扑比较简单的网格模型Cow(5 804个面、2 903个顶点)简化的结果.

采用二次误差测度算法得到的简化网格模型均匀，平坦的区域往往占用更多的网格.从图4可以看出，本文算法得到的简化模型对于牛身等平坦区域，使用的三角形网格数量相对较少，而对于牛眼、牛鼻和腹部等细节特征明显的区域，使用的三角形网格数量相对较多,本文简化算法仍能保留上述细节特征.按照网格表面曲率的变化较为合理地分配了网格，平坦区域的网格更加稀疏，在曲率值变化较大的区域稠密，从视觉上看比文献[1]、文献[2]和文献[3]中方法得到的简化网格更加均匀，如图4对比所示.

图4　Cow模型简化结果比较Figure 4　Comparison of Cow model simplified results

图5是使用文献[2]、文献[3]和本文算法得到的简化网格模型.当Car模型被文献[2]中算法简化到209个面片的时候开始失去了部分的几何特征(车轮已经不明显)，但采用本文算法得到的Car简化模型在只有209个面片的时候仍然保留了汽车外部轮廓，车轮等细节特征较好地保留.

本文算法在低分辨率的情况下仍能够保持模

型重要的几何特征，即在减少顶点和三角形面片的时候尽量保持原模型的特征.表1～3比较了本文算法和文献[2]、文献[3]算法，在简化率为80%、90%和95%所花费的时间，对比三种算法简化的时间，可以得出结论：简化时间与模型的复杂度和三角形面片数成正比，本文算法在同等简化率的条件下简化速度上均优于文献[2]和文献[3]的算法.

表1　三种算法简化80%时间对比(简化到20%)

表2　三种算法简化90%时间对比(简化到10%)

表3　三种算法简化95%时间对比(简化5%)

图5　Car模型简化对比图Figure 5　Comparison of car model simplified

图6中Bunny实体模型(69 451个三角面片，35 947个网格顶点)来自斯坦福大学.用本文方法和文献[1]、文献[2]中的方法将模型分别简化60%(简化后网格数量为27 780)和90%(简化后网格数量为6 945)，其中图6(b)和图6(c)为文献[1]的结果，图6(d)和图6(e)为文献[2]的结果，图6(f)和图6(g)为本文方法的简化结果.

针对误差分析，本文采用Cignoni提出的方法[11]对简化后的网格误差进行估计,见表4.从表4可以看出，本文算法在运行时间和简化误差都比文献[1]和文献[2]算法有优势,最大优点在于即使经过90%～95%的大规模简化后，模型保留

了大部分细节特征，算法运行时间要略优于文献[1]算法和文献[2]算法.通过对Cow、Car和Bunny模型的简化实验总结可得：本文算法在简化时间与几何属性保持(细节特征)上具有优越性.

表4　Bunny模型的简化误差结果(简化90%)对比

图6　Bunny模型简化对比图Figure 6　Comparison of bunny model simplified

5结语

本文基于半边折叠思想提出一种改进的网格简化算法，加入了边曲率近似计算和被删除顶点相关三角形等信息，考虑边的近似曲率和半边顶点相关联的三角面片，在快速有效地简化网格的同时，又不丢失网格主要的细节特征.实验结果表明改进后的算法不仅具有运行速度快、效率高的特点，而且有效保留了网格的细节特征，具有一定的实际应用价值.由于本文侧重考虑曲率因素对于简化的影响，没有将网格简化过程中体积引起的变化和模型的特征点与特征线考虑进来，因此今后将在曲率的基础上加入上述因素，以便使得算法效果更好.

【参考文献】

[1]HOPPE H,DEROSE T. Mesh optimization[J]. Computer Graphics， 1993, 27(1): 19-26.

[2]GARLAND M, HECKBERT P S. Surface simplification using quadric error metrics[C]// Proc of the Computer Graphics.[s.l]:[s.n.]，1997: 209-216.

[3]刘焕敏，杨克俭，王玉华.一种面积加权的半边折叠网格简化算法及其递进网格构造[J].武汉理工大学学报(交通科学与工程版),2005，29 (1): 76-78，82.LIU Huanmin, YANG Kejian, WANG Yuhua. A mesh

simplification algorithm with area-weighted half edge collapse and progressive mesh construct[J]. Journal of Wuhan University of Technology(Transportation Science & Engineering), 2005, 29(1): 76-78, 82.

[4]刘新国，鲍虎军，王平安，等.体积保持的多分辨率多边形网格的光顾造型[J].计算机学报，2000 (9): 905-910.

LIU Xinguo, BAO Hujun, WANG Pingan,et al. Volume preserved multiresolution mesh modeling[J]. Chinese Journal of Computers, 2000(9): 905-910.

[5]刘晓利，刘则毅，高鹏东，等.基于尖特征度的边折叠简化算法[J].软件学报，2005，16(5): 669-675.

LIU Xiaoli, LIU Zeyi, GAO Pengdong, et al. Edge collapse simplification based on sharp degree[J]. Journal of Software, 2005, 16(5): 669-675.

[6]计忠平，刘利刚，王国瑾.基于割角的保特征网格简化算法[J].计算机研究与发展,2006, 43(12): 2144-2151.

JI Zhongping, LIU Ligang, WANG Guojin. Feature preserving mesh simplification based on corner cutting[J]. Journal of Computer Research and Development, 2006, 43(12): 2144-2151.

[7]张慧娟，耿博，汪国平.采用张量投票理论的三角网格特征边提取算法[J].计算机辅助设计与图形学学报，2011，23(1): 62-70.

ZHANG Huiuan, GENG Bo, WANG Guoping. Feature edge extraction method of triangle meshes based on tensor voting theory[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(1): 62-70.

[8]冯翔，周明全.带纹理的三维模型简化算法[J].计算机辅助设计与图形学学报，2009，21(6):842-846，852.FENG Xiang, ZHOU Mingquan. An algorithm for simplification of 3D models with texture[J]. Journal of Computer-Aided Design & Computer Graphics,2009,21(6):842-846,852.

[9]郝娟儿，唐莉萍，曾培峰.基于曲率和面积的二次误差测 度网格简化算法[J].东华大学学报(自然科学版),2012，38(3): 318-322.

HAO Juaner, TANG Liping, ZENG Peifeng. A simplification algorithm for curvature and area-weighted quadric error metrics mesh[J]. Journal of Donghua University(Natural Science Edition), 2012, 38(3): 318-322.

[10]ISLER V, GREEN M. Real-time multiresolution modeling for complex virtual environments[C]//Proceeding of the ACM Symposium on Virtual Reality Software and Technology.[s.l.]:[s.n.],1996:11-19.

[11]CIGNONI P, ROCCHINI C, SCOPIGNO R. Metro:mea-suring error on simplified surfaces[J]. Computer Grap-hics Forum, 1998, 17(2): 167-174.

[12]WEI Jin,LOU Yu. Feature preserving mesh simplification using feature sensitive metric[J]. Journal of Computer Science and Technology,2010,25(3):595-605.

Mesh simplification algorithms based on edge curvature metrics

WANG Jun, WANG Xiuhui

(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

Abstract:Mesh model simplification is of importance in the computer graphics, virtual reality and manufacturing areas. Aiming at the problem that the geometric features of the model were lost when the mesh simplification algorithm was simplified, an improved half edge collapse mesh simplification algorithm was proposed. The concept of boundary curvature approximation measurement was introduced. Adding the edge curvature to the error metrics changed the grid of half edge sequence, simplified the grid model and retained the details accurately. The experimental results show that the improved algorithm can better retain the inherent characteristics of the original model under the same reduced rate. The grid has reasonable distribution, fast speed and small errors.

Key words:mesh simplification; half edge collapse; edge curvature; detail features

【文章编号】1004-1540(2015)01-0073-07

DOI:10.3969/j.issn.1004-1540.2016.01.014

【收稿日期】2015-11-30《中国计量学院学报》网址：zgjl.cbpt.cnki.net

【基金项目】国家自然科学基金资助项目(No.61303146).

【作者简介】王竣(1991-)，男，吉林省吉林人，硕士研究生，主要研究方向为计算机图形和图像处理. E-mail:846411409@qq.com

【中图分类号】TP301.6

【文献标志码】A

通信联系人：王修晖,男，副教授.E-mail: wangxiuhui@cjlu.edu.cn