基于控制点误差控制的网格简化算法

摘要：提出了一种基于控制点误差控制的网格简化算法，以初始网格三角形的中心点作为第一类控制点，以特征边的顶点作为第二类控制点，控制点与受控三角形之间的距离作为简化误差。根据设定的三角形权重，按照顺序进行三角形折叠操作，简化操作后必须满足控制点到受控三角形的距离小于阈值。最后通过实验对算法进行验证。

关键词：控制点；三角形折叠；误差控制

中图分类号： TP391.41

文献标识码：A

0引言

三角形网格简化算法是在尽量保持模型的几何形状和拓扑结构的基础上，通过简化网格三角形和顶点，用简化模型替代初始模型。根据不同简化原理有多种简化算法：区域合并算法［1］，小波分解算法［2］，基于能量优化的边折叠算法［3］，基于二次测量误差的简化算法［4］，引入尖特征度的边折叠算法［5］，基于二次曲面拟合的三角形折叠算法［6］等。

本文提出一种以三角形折叠为基本操作的网格简化算法，以初始网格的三角形的中心点作为第一类控制点，以特征边的顶点作为第二类控制点，在网格内每个控制点有唯一对应的受控制三角形，每个三角形拥有第一类控制点集合与第二类控制点集合。以控制点与受控三角形之间的距离作为简化误差，其中第二类控制点与受控三角形之间的距离为系数距离。根据设定的三角形权重，按照顺序进行三角形折叠操作，通过投射使新顶点保持在原始网格上。简化操作后必须满足控制点到受控三角形的距离小于阈值。

1基本概念

定义1三角形网格M由顶点集合V={v1,v2,…,vn}和三角形集合T={t1,t2,…,tm}所组成的二元组(V,T)来表示, 三角形沿公共边及在顶点处相连接，一条边最多只能被两个三角形共有。初始网格记作M0，初始顶点集合V0={v0,1,v0,2,…,v0,n0}，初始三角形集合T0={t0,1,t0,2,…,t0,m0}。

定义2三角形网格内以vi为顶点的三角形构成的集合称为顶点vi的相关三角形集合C(vi)，以vi为顶点的三角形的数目称为vi的阶，记为ri。

定义3三角形网格内与ti的三个顶点相关的三角形的集合，称为三角形ti的相关三角形集合C(ti)。

定义4三角形ti的相关三角形集合C(ti)有g个三角形，其中三角形tr的法向量为Nr，中心为Xr，面积为Ar，经过中心点X并且法向量为N的平面P(N,X)定义为三角形集合C(ti)的平均平面

2控制点的选取

如图1所示，以初始网格三角形的中点作为第一类控制点，初始三角形t0,i的中心点为控制点vci， vci在初始网格中对应三角形即为t0,i，第一类控制点集合记为VC={vc1,vc2,…,vcm0}。在简化网格内每个控制点有唯一对应的三角形，称为该控制点的受控三角形。每个三角形都有其第一类控制点集合，三角形ti的第一类控制点集合记为, VC(ti)={vcc(1),vcc(2),…,vcc(a)}，其中vcc(r)的受控三角形即为ti，初始三角形t0,i的第一类控制点集合VC(t0,i)={vci}。以集合DC={dc1,dc2,…,dcm0}记录第一类控制点到其受控三角形的距离，其中dci为vci到受控三角形tr的距离。

在网格简化过程中应尽量保持网格特征，以初始网格特征边的顶点为第二类控制点，第二类控制点集合记为VE={ve1,ve2,…,vem2}。如图2所示，初始网格三角形t0,i与t0,r相邻接，如果t0,i与t0,j之间的夹角小于阈值θ，边l(v0.h,v0,k)为特征边，顶点v0.h与v0,k为第二类控制点。将v0.h与v0,k加入t0,i或是t0,r的第二类特征点集合，顶点只能加入一个三角形的第二类特征点集合。

每个三角形有第二类控制点集合，ti的第二类控制点集合记为VE(ti)={vee(1),vee(2),…,vee(b)}，集合内的vee(r)的受控三角形即为ti。以集合DE={de1,de2,…,dem2}记录第二类控制点到受控三角形的系数距离，其中dei为vei到其受控三角形tr的系数距离。如果vei到其受控三角形tr的欧式距离为de′i，系数距离dei=de′i•c，其中c是特征系数，有c≥1。

以控制点到受控三角形的距离作为初始网格与简化网格之间的误差，设定误差阈值dhold，在网格简化过程中必须有dci≤dhold、dei≤dhold。在网格简化的过程中， 控制点与受控三角形之间的对应关系，将随着网格的简化不断调整。

3三角形折叠操作

三角形的折叠顺序是影响网格简化效果的关键之一，对网格内三角形设定一个权重，将三角形按权重进行排序得到折叠顺序队列Lcollapse，权重小的三角形将首先被折叠。三角形ti的权重系数为Wi

Wi=Ai•(wα•αi+wv•rci+wd•di,max) （3）

Ai为ti的面积；wα、wv和wd是权重系数，0≤wα,wv,we≤1；等角度权重αi=2•(∑3k=1cos βk－1)，其中βk是三角形ti的内角；阶权重rci=rnew－612，rnew是三角形折叠后目标顶点的阶，算法中认为顶点的阶的最佳值为6；误差权重di,max，是ti的第一类控制点到ti的距离与第二类控制点到ti的系数距离的最大值。

取折叠顺序队列Lcollapse的头部三角形记为ti，ti为目标三角形， ti的相关三角形集合为C(ti)， C(ti)的第一类控制点集合VC(C(ti))={vcc(1),vcc(2),…,vcc(A)}， 第二类控制点的集合VE(C(ti))={vee(1),vee(2),…,vee(B)}，C(ti)的控制点集合是C(ti)内各个三角形控制点集合的并集。VC(C(ti))对应初始网格上的三角形集合为T(C(ti))={t0,c(1),t0,c(2),…,t0,c(A)}。计算得到三角形集合C(ti)的平均平面P(N,X)，过点X，沿法线N方向的直线为L(N,X)，直线L(N,X)与三角形集合T(C(ti))内的三角形的交点即为目标顶点vnew。将ti折叠到目标顶点vnew得到三角形集合C(vnew)。

计算VC(C(ti))内各个控制点到C(vnew)内各个三角形的距离， 得到集合DC(C(vnew))={(dc(1),th(1)),…,(dc(A),th(A))}，其中(dc(r),th(r))为记录控制点vcc(r)到三角形集合C(vnew)内三角形th(r)的距离最近，距离为dc(r)。dc(1)、dc(2)、…、dc(A)中最大值记为dc,max。

计算VE(C(ti))内各个控制点到C(vnew)内各个三角形的系数距离，得到集合DE(C(vnew))={(de(1),tk(1)),…,(de(B),tk(B))}，其中(de(r),tk(r))为记录控制点vee(r)到三角形集合C(vnew)中三角形tk(r)的系数距离最近，系数距离为de(j)。de(1)、de(2)、…、de(B)中最大值记为de,max。

如果dc,max≤dhold并且de,max≤dhold，表明折叠操作形成的误差在阈值范围内；如果dc,max>dhold或者de,max>dhold，表明折叠操作形成的误差超出阈值范围，三角形ti折叠操作不合法，目标三角形ti的权重Wi=Wi*p，其中p为惩罚系数，p>1，将三角形ti按照新权重插入折叠顺序队列Lcollapse。

如图4所示，如果目标三角形ti邻接环结构loop(t2,t3,t4)，ti折叠后会造成t3与t4重合，这将破坏网格的拓扑结构。如果ti邻接环结构，ti权重Wi=Wi×p，将ti按照新权重插入折叠顺序队列Lcollapse。

如图5所示，如果折叠三角形ti到新顶点vnew会造成三角形t2翻转，这将破坏网格的拓扑结构，这就需要在进行三角形折叠后，计算vnew邻接的三角形的法向是否发生大的偏转，如果偏转过大，取消三角形折叠操作， ti权重Wi=Wi×p，将ti按照新权重插入折叠顺序队列Lcollapse。

若三角形ti折叠操作合法，需要重新分配控制点。将第一类控制点集合VC(C(ti))内的各个控制点分配给三角形集合C(vnew)内的三角形根据集合DC(C(vnew))内的记录(dc(r),th(r))，将控制点vcc(r)加入三角形th(r)的第一类控制点集，在集合DC内dcc(r)=dc(r)。将第二类控制点集合VE(C(ti))内的各个控制点分配给三角形集合C(vnew)内的三角形的第二类控制点集合，根据集合DE(C(vnew))内的记录(de(r),tk(r))，将控制点vee(r)加入三角形tk(r)，在集合DE内dee(r)=de(r)。计算C(vnew)相关区域内三角形的权重，相关区域包括C(vnew)内三角形以及与C(vnew)内三角形相连接的三角形，将相关区域内三角形按照权重插入折叠顺序队列Lcollapse。

基于控制点误差控制的网格简化算法步骤：

步骤1：取得初始网格的第一类控制点集合与第二类控制点集合，并将控制点分配给三角形；

步骤2：计算初始网格内各个三角形的权重，得到折叠顺序队列Lcollapse；

步骤3：由折叠顺序队列Lcollapse头部取三角形作为目标三角形；

步骤4：检测目标三角形是否邻接环结构，如果邻接环结构，将目标三角形权重乘以惩罚系数后重新插入折叠顺序队列，转步骤3；

步骤5：计算得到目标顶点，折叠目标三角形到目标顶点；

步骤6：进行翻转检测，如果有翻转现象，取消折叠操作，将目标三角形权重乘以惩罚系数后重新插入折叠顺序队列，转步骤3；

步骤7：计算第一类控制点与第二类控制点到三角形距离，如果最大距离小于阈值，折叠操作成立；否则，取消折叠操作，目标三角形权重乘以惩罚系数，将三角形重新插入折叠顺序队列，转步骤3;

步骤8：重新分配第一类控制点与第二类控制点，重新计算相关区域三角形权重，将相关三角形插入队列，判断是否满足结束条件，如满足，结束程序；否则，转步骤3。

4误差的度量

Cignoni在1998年提出的算法［7］对模型之间的误差进行度量，两个模型表面S1与S2，最大误差（max error）为:Emax(S1,S2)=max(q(v,S2)),v∈M0

平均误差（mean error）为:

Emean(S1,S2)=∫q(v,S2)•dsS1

其中q(v,S2),v∈S1为面S1上点v到面S2的距离，S1为面S1的面积。在本文中

Emax(M0,M)=max(dci)（4）

Emean(M0,M)=∑m0i=1(dci•A0,i)∑m0i=1A0,i（5）

其中dci为第一类控制点vci到其对应受控三角形tk的距离，A0,i为初始网格三角形t0,i的面积，∑m0i=1A0,i为初始网格的面积。本文中最大误差即为阈值dhold。

5实验结果

采用VC++6.0实现了算法，并进行了数据实验。原始数据为68×512×512的螺旋CT扫描数据，数据的层距3mm，同层数据点间距0.4 mm，采用MC算法生成的原始等值面如图6(a)所示，网格内有439B852个三角形以及219B554个顶点。取特征边的角度阈值θ为0.6，特征系数为c=3，惩罚系数p=5，权重系数wα,wv,we=1。

本文提出一种基于控制点误差控制的网格简化算法，在初始网格内提取第一类与第二类特征点，以特征点与受控三角形之间的距离作为简化误差。根据设定的三角形折叠权重，按照顺序进行三角形折叠操作。三角形折叠的目标顶点保持在原始网格上，实验表明算法可以有效地进行网格简化，并保持原始模型的拓扑结构。考虑到模型的多样性，算法需要进一步改进和完善，如自适应地选取阈值和特征系数等。