三角网格模型简化算法的研究现状

张茹　胡世昌

摘要：模型的精细程度在计算机图形的真实感显示中非常重要，而庞大的数据量对计算机的存储、显示和传输带来了巨大的挑战，因此三维模型的简化算法越来越受到学者的关注，文中对三角网格算法展开了系统的研究，总结归纳了元素折叠法和误差度量的基本思想及其优缺点，并展望了模型简化领域未来的研究方向。

关键词：三角网格；网格简化；边折叠；三角形折叠

中图分类号：TP391.4 文献标识码：A 文章编号：1007-9416（2018）01-0128-02

随着三维激光扫描技术的发展，三角网格模型的获取精度大幅度提高。庞大的网格数据虽可以保持物体的细节特征，却给计算机的存储、显示和传输带来了困难。为减轻计算机处理数据的压力，方法之一就是简化模型。计算机图形学中的三维模型常采用多边形网格进行描述，空间中三个点确定一个平面，因此三角形是多边形网格中最常用到的多边形，所以，此次网格模型简化研究中，我们仅针对三角网格模型。

1 三角网格简化相关算法

目前网格简化方法一般可以分为三类：元素删除法、网格重绘法和元素折叠法。元素删除法包括点删除和三角形删除，根据网格模型的几何性质和拓扑关系来删除顶点，但该方法对原网格模型的特征保持较差。网格重绘法是在原网格模型的基础上重新绘制顶点数更少的模型，但这种方法对于细节特征较多的模型，计算量和误差都较大。相比来说，元素折叠法具有更高的稳定性和简化速度，其主要分为边折叠和三角形折叠，下面将对这两种方法进行论述。

1.1 边折叠

边折叠算法首先由Hoppe[1]提出，其基本思想是將三角网格中一条满足条件的边，简化为一个顶点，同时将与该边两个端点相邻的所有顶点都和新顶点相连，并删除所有退化的边和面，如图1所示，可通过三个步骤来完成一次边折叠操作：

（1）将顶点移动至新顶点；（2）将所有与顶点相关的边连接到顶点；（3）删除顶点以及所有失效的边和三角形。

如图1所示，一次非边界边折叠操作可减少三条边、两个三角形、一个顶点；如图2所示，一次边界边折叠操作可减少两条边、一个三角形、一个顶点。对于封闭的模型来说，所有的边都由两个三角面片包含，但是对于不封闭的模型而言，有些边只被一个三角面片包含，称之为边界边。边界边往往含有模型的边界特征，因此在讨论模型简化算法时要注意将边界边和非边界边分开讨论。

1.2 三角形折叠

Hamann[2]提出一种基于三角形折叠的网格简化算法，三角形折叠操作与边折叠操作类似，将边折叠中的边换成了三角形，折叠过程如图3所示：将三角形折叠成一个顶点，并将与该三角形三个顶点相连的所有顶点都与新顶点相连，删除与此三角形有公共边的三角形。

如图3所示，一次非边界三角形折叠操作减少六条边、四个三角形、两个顶点；如图4所示，一次边界三角形折叠操作减少五条边、三个三角形、两个顶点。

从几何元素数量上分析，一次三角形折叠减少的数量是一次边折叠的两倍，因此，在简化率相同的情况下，三角形折叠具体更高的简化速度。

2 新顶点位置的确定

新顶点的位置直接影响到简化后模型的形状，确定新顶点无疑是简化方法中的一个难点，Garland，等[3]通过二次误差矩阵（Quadric Error Metrics，QEM）来确定边折叠点的位置，该方法虽然计算简单，但得到的模型过于均匀；张霞，等[4]运用顶点投影法来确定三角形折叠点的位置，充分利用了折叠区域的几何信息，但存在简化误差阈值不易控制，忽视网格连续性的问题；段黎明，等[5]在√3网格细分法的基础上确定三角形折叠后的坐标，在简化比例较大时能较好地保持网格特征和连续性，但对于一些特征三角形比较集中的模型，容易出现过共顶点的现象。每种方法都有其不足之处，这就促使着我们去深入研究，不断的改进，以取得更好的效果。

3 误差度量

模型简化的根本目的在于保持模型细节基本不变的情况下尽可能减少面片的数量，一条边或者三角形能否被折叠是由其误差的大小来决定的，合理的误差度量方法可以有效的控制简化后模型的质量，使模型外观在一个能够接受的范围内。

3.1 二次误差度量

二次误差度量是用新顶点到折叠边所关联平面的距离平方和作为误差标准，只考虑了模型简化前后的距离误差，没有考虑到模型的细节特征，使网格过于均匀，但其简化速度快，且在简化率较低时效果较好，因此后来的很多算法都是在此基础上加以改进的。

3.2 体积误差度量

体积误差是模型简化前后的体积变化值，误差越小代表简化算法越好，但三维空间中各个面的法向量的存在，使得算出来的体积变化可正可负，其正负情况反映了简化模型相对于初始模型的凹凸情况，但也可能出现网格模型变化了但体积误差为零的情况，因此后人多使用体积的平方误差度量方法，如文献[4]。

3.3 顶点重要度

顶点的重要度亦是我们需要考虑的一个因素，当我们观察物体时，对棱角、棱边、轮廓等关键细节较敏感，对平坦区域的感知力较弱，顶点处的起伏变化越大，去除该点后对网格模型的影响就越大，即顶点的重要度越大。在模型同等的简化率时，我们就要首先考虑删除顶点重要度低的点，保留顶点重要度高的点。

董艳，等[6]将顶点的重要度作为权重引入折叠代价中，从而影响边的折叠顺序，取得较好的结果，但仍有简化效率不高的缺点。

这里只介绍了几种常用的误差度量方法，除此之外，还有点的曲率[7]、局部区域平均面积等[8]，更多有效的方法有待我们去发掘和验证。

4 结语

模型简化一般要遵循两个原则，最少的顶点数和最小的误差。不断提高模型简化质量和速度是我们一直努力的方向，在此基础上，我们可以从以下几个方面进一步研究：

（1）我们经常见到的模型都是带有颜色、纹理等属性的，这些简化算法是否对所有带属性的模型具有较好的简化质量。（2）从视点出发，不同分辨率的模型是否能够随视点的远近自适应的变换并有较高的转换效率。（3）三角网格模型是用多个三角形面片来逼近模型，相对来说二次曲面有更好的表达曲面的能力，用二次曲面代替部分三角网格来逼近模型是否有更高的效率和质量。

参考文献

[1]Hoppe H， DeRose T， Duchamp T， McDonald J， Stuetzle W. Mesh optimization. Proc. of the Computer Graphics，1993，（27）：19-26.

[2]Hamann B. A data reduction scheme for triangulated surface[J].Computer Aided Geometric Design，1994，（2）：197-214.

[3]Garland M， Heckbert PS. Surface simplification using quadric error metrics. Proc. of the Computer Graphics，1997，（31）：209-216.

[4]張霞，段黎明，刘璐.保持特征的高质量三角网格简化方法[J].计算机集成制造系统，2014，（3）：486-493.

[5]段黎明，邵辉，等.高效率的三角网格模型保特征简化方法[J].光学精密工程，2017，（2）：460-468.

[6]董艳，张志毅，杨客.基于顶点重要度的保形网格简化方法研究[J].计算机工程与设计，2013，（5）：1889-1895.

[7]Zhou M D，Michael Y W.Engineered model simplification for simulation based structural design[J]. Computer Aided Design and Applications，2012，（1）：87-94.

[8]贾琪.基于改进二次误差测度的网格简化算法研究[D].秦皇岛：燕山大学，2014.