基于n边形折叠的网格简化算法

A Mesh Simplification Algorithm Based on n-Edges-Mesh Collapse

提出在三角网格中利用多个三角形组合及检索n边形(n为正整数)的规则,并提出一种具有相似折叠规律的n边形折叠的网格简化算法,该算法以n边形折叠为基本简化操作,并以二次误差作为误差度量,每次n边形折叠操作可以减少n-1个顶点以及2(n-1)个三角形,n越大达到某一简化目标所需的折叠次数越少,因此简化速度也可能越快.通过选取适当的n值及新顶点位置,新算法可以转化成顶点删除、边折叠及三角形折叠3种已知的几何元素删除算法,因此也可以视做为基于二次误差度量的几何元素删除简化算法的总括算法.最后分别对几种n取值情况列举实验数据,说明该算法的有效性.

Two rules to define and search the n-edges-mesh （‘n’ is a positive integer ） in triangle meshes are presented and a new mesh simplification algorithm based on the n-edges-mesh collapse is put forward, which has the same law of collapse in different n cases. The proposed algorithm utilizes iterative n-edges-mesh collapse to simplify meshes. Surface error approximations are maintained using quadric errors metrics. There are n-1 vertices and 2n-2 faces to be collapsed during every simplification, so fewer collapses times are need to reach a target simplified model with a certain number of triangles when n is assigned a relatively large value. And that means the time of the simplification process can be reduced. Furthermore, by choosing the proper ‘n’ and the position of the new vertex, the new algorithm can be transformed into the known geometry element collapse （remove） algorithm which is based on the vertex decimation process, the edge collapse process, or the triangle collapse process. Thus the proposed algorithm can be regarded as the summarized algorithm of mesh simplification based on the geometry element collapse. Different n cases are involved in the experiment, and the results demonstrate the efficiency of the algorithm.