基于二次误差度量的网格简化算法(精)

1、第20卷 第5期2000年 10 月北京理工大学学报 JournalofBeijinglnstituteofTechnologyVol.20 No.50ct.2000 文章编号：100120645(2000)0520607206基于二次误差度量的网格简化算法吴亚东，刘玉树，高春晓(北京理工大学计算机科学与工程系，北京100081) 摘要:网格简化是提高计算机处理复杂模型速度的有效方法，要求算法时间和空 间复杂性低、简化质量高且简化结果中三角形紧致性好Z型的算法Z算法采用边折叠为基本操作，低算法的空间复杂性，在P上,算法可在12s内简化含7019的三角 形数为56%Z关键词:网格简化；P391:

2、A二次误、显示、存储与传输都是很大的负担，网格简化是Z在众多的网格简化算法中，边 折叠的方法得到了广(Quadricerrormetrics)简化算法在时间复杂泛的认同16,其中,Garland的，以点到Z此差度量”度和简化质量两方面都有较为出色的表现1 Z亥算法以边折叠为基本操作 相关三角形平面的距离的平方为度量，折叠点的坐标由最小化二次误差确定后,Lindstrom对点到平面的距离加权以三角形的面积，以最优化体积的平方求得折 叠点的坐标2 Z Erikso和Hoppe的几何误差简化方法也与文献1类似3,4 Z 作者提出一种新的基于边折叠的网格简化算法Z注意到Garland的算法对空间要求较

3、高，每个点需10个浮点数的历史记录 丄indstrom算法则不保留任何历史记录 Z 为降低空间复杂度，减少简化误差，算法对每个点保留了 1个浮点数的历史记录Z 文献14均采用点到相关平面的距离的平方为误差度量，本算法则以点到相关直 线的距离的平方为误差度量Z此外,寻求简化结果三角形紧致性更好的算法是网格简化的重要任务之一 7 Z实验表明，作者提出的算法不仅可以产生高质量的简化结 果，而且简化结构网格的三角形紧致性很好Z1网格简化算法111术语说明为叙述方便，先简要介绍文中用到的术语及概念Z向量均指三维列向量Z顶点V的坐标v=x,y,zT所指的边均为有向边，即e=(vO,v1)，将边e写作vOv

4、1=v1-vO Z把点到边所 在直线的距离简称为点到边的距离Zv3表示所有与顶点v相邻的边的集合，如图1所示Z收稿日期:2OOOO313基金项目：高等学校博士学科点专项科研基金资助项目作者简介:吴亚东,1974年生,博士生Z608北京理工大学学报第20卷边折叠操作如图2所示，边vOv1折叠为折叠点v引起网格局部形状的变化，如vOv1 不是边界边,则一次边折叠减少2个三角形、3条边、1个顶点Z1图1v与顶点v相邻的边的集合图2边折叠操作112误差度量3见图2所示,设边vOv1折叠为点V,定义v到v30和v1的误差图3点的距离尸Z如图3所示,点V到边vOv1的距离的平方r= vOv sin2vOv

5、1-vOv1 )2 Z -0(1 令 s=v0vvv0v2T2TTTTTr=s-st)=ss-s(tt)s=s(l-tt)s.I Z3设sO=v-vO,ti为v3O中边的单位向量，则点v到vO中各边距离的平方和 nv0v1d(v,n3v0)=刀(si=1T0(l-titi)s0)=sTT0刀(-i=1titi)s0 ZT令Q0=刀(-i=1titi),则3Td(v,v0)=s0Q0s0 ZT(1)同样,设s1=v-v1,可得点v到v31中各边的距离的平方和3T(2)d(v,v1)=s1Q1s1.3综合式(1)(2),可得如图2中边v0v1折叠为点v,顶点v到v30和v1中各边距离的平 方和33

6、TT？(v)=d(v,v0)+d(v,v1)=s0Q0s0+s1Q1s1Z以s0=v-v0,s1=v-v1代入式(3),整理得? (v)=vT(Q0+Q1)v-2(vT0Q0+v1Q1)v+(v0Q0v0+v1Q1v1).令 A=Q0+Q1,bT=vT0Q0+v1Q1,c=v0Q0v0+v1Q1v1,则边 v0v1 折叠为点 v 的误差TT？ (v)=vAv- 2bv+c Z113折叠点坐标的确定在采用边折叠操作的简化算法中，选取折叠点坐标的原则是使简化后的网格形状尽 可能接近原始网格Z但目前对简化前后网格的相似程度尚没有公认的度量标准Z如边v0v1折叠为点V,为简单起见，一般可选取折叠点V的

7、坐标为v0,v1或(v0+v1) 2, 但更好的选择应该是不局限于边 v0v1甚至于该局部网格表面 Z这里取使？(V)值最小的v作为折叠点v的坐标，考虑到 所采用的误差度量方法，这种选择是很自然的Z下面推导使？(v)值最小的V的值Z 第5期吴亚东等：基于二次误差度量的网格简化算法 609?(V)可写作c由矩阵A的定义知A为对称矩阵，故Q也为对称矩阵Z又由？(V)定义知? (v)>0(v30 U 3v1中各边所在直线不会全部共线)，故？(V)是正定二次型，即Q为对 称正定矩阵,A也为对称正定矩阵Z由线性代数最小原理可知？(V)在v=A-1b处取 得最小值 Z因 A 为正定矩阵，故 A 可-

8、b? v=vTAv-2bTv+c=(vT 1) AT-bv=PTQP. 逆Z因此，当边v0v1折叠为点V时，点V的坐标v=A- 1bZ114边折叠消耗函数注意到112中的误差度量？(v)仅表示一次边折叠前后局部网格的差异，简化后网格 与原始网格的距离，网格相似程度的度量标准，一些文献中采用的Hau8计算量，提 高简化速度，当边v0v1折叠为点v(5)c(v)=v)e0)e其中 ？ (v),v0(v1)v0与v1的历史 记录误差Z设m为常数,的历史记录误差(6)e(v)=mc(v) Z，即在原始网格中，各顶点历史记录误差均为0,即e(vi)=0在，随着边折叠操作的进 行，每次折叠操作误差的积累，

9、各边折叠的c(v)值将不断增大，因此，消耗函数c(v)即 可作为本算法网格简化的全局误差函数 Z在式(5)中，权值m决定了顶点V的历史记录误差对v3中各边的消耗函数值的 贡 献”，n值越大，则v3中各边的消耗函数值将相应增大，v3中各边折叠的概率将会减 小(在边折叠优先队列中位置靠后),即v3所在的局部区域不会很快再次被简化 Z 实验中取m=1,可得到很好的简化结果Z115算法流程本算法以边折叠为基本操作，以点到相关直线的距离的平方为误差度量，按边折叠 消耗函数值的大小将所有边排为升序优先队列，取队首元素执行边折叠操作，删除 队列中无效的边，并重新计算与折叠点相邻的边的消耗函数值，将其插入队列

10、Z算 法执行过程如下： 初始化网格中所有点的历史记录误差e(vi)=0; 计算网格中所有边的折叠误差？(v)及折叠点V的坐标V,计算边折叠的消耗值 c(v),按 c(v)大小将所有边排为升序优先队列；v3i U vj;v'并计算其消耗值，然后把该边 取队首消耗值最小的边vivj执行折叠操作，折叠点V的历史记录误差e(v)=c(vivj); 3删除队列中所有因该边折叠而导致消失的边,转至执行下一个边折叠操作 计算v3中各边的折叠误差及其折叠后点的坐标 插入队列； 如此时网格的三角形个数多于用户指定的数目Z 116三角形紧致性 在网格中，紧致性差的三角形会引起光照处理时的不连续现象，并可能

11、导致某些绘 制方法速度下降,对模型的其他处理结果有很大影响9,因此网格中应尽量避免紧致性差 的三角形Z610北京理工大学学报第20卷 Delaunary三角剖分的广泛应用在很大程度上正 是因为它可以产生紧致性较好的三角形Z文献2,6中均对网格中三角形的紧致性做了处理Z其中文献2是在算法规定的约束不能够确定折叠点的坐标时，才考虑 到三角形的形状Z文献6则在简化过程中，对边折叠前后局部三角形的形状进行 比较,如边折叠后的三角形形状不满足要求，则放弃该边折叠操作Z作者采用文献 中对三角形紧致性的评估方法，即三角形的紧致性C=222,IO+I1+I2(7)其中 A为三角形的面积,li为边的长度Z当三角

12、形为等边三角形时,c为1;0时,c=0 Z本算法并未对网格中三角形形状做任何特殊处理，Z2实验结果作者在P 450上用C+，表1为与文献1(a)原始模型(b)简化结果图4兔子模型简化结果，简化98%(a)原始模型(b)简化结果图5手模型简化结果，简化98%本算法的时间复杂度与文献1相同，为0(nign) Z由于这类算法本身比较简洁，其速 度与其他类型的算法相比是很快的，这一点已为文献1,2所证实Z本算法空间复杂度小于文献1的算法Z在简化三角形数很多的模型时，由于内存的限制，程序要进行频繁的磁 盘交换，此时本算法的优点表现得相当明显Z第5期吴亚东等：基于二次误差度量的网格简化算法表1与文献1算法

13、实验数据比较611模型类型兔子手原始模型三角形个数69451654666简化模型三角形个数150010000Qslim2101t sQslim2102简化结构中c>019的三角形个数本算法t s本算法简化结果中%c>019的三角形个数56548141862821129613值得注意的是，用本算法简化后的网格的三角形紧致性较好Z事实上，利用本算法简化结果中c>018的三角形数达82%,而c<016的三角形数不足2%Z在所有的实 验结果中，简化结果中c>019的三角形数所占比例均大于50%,而文献中给出的 结果为39%作者对不保留历史记录的情况也做了实验Z e(vi始

14、终为0时，简化结果的三角形形状更为规则 Z 150(个三角形,c>019的三角形数达65%Z , Z3结论，以点到相关直线的距离的平方为误差度量，Z算法按边折叠的消耗函数值对网格中， 依次取消耗值最小的边执行折叠操作，直至网格中的三角形数达到用户指定的Z算法速度快,空间复杂度小，简化结果质量较高，此外，算法所用的误差度量方法 可以获得三角形紧致性很好的简化结果Z该算法可用于交互可视化中的多细节层次场景的自动生成和有限元模拟 Z进一步的工作包括改进算法以使其能够更好地 处理边界边,并提供对模型法向量和纹理属性简化的支持Z参考文献：1 Garla ndM,Heckbert P.Sufaces

15、i mp lificatio nusin gquadncerrormetricsA.WhittedT.P roceedi ngsofSIGGRA PH 97,Co mp uterGra phics Proceedi ngs,A nnu alC onferen ceSeries C丄 osA ngeles:Addiso nWesley,1997.209-216.2 Lin dstro mP ,TurkG.Fasta ndmemoryefficie ntp olyg on alsim plificati on A.EbertD,98C.NorthCaroli na:IEEE,1998.279-28

16、6.Hage nH,RushmeierH.IEEEVisualizatio n3Eriks on C,Ma no chaD.GA PS:Ge nerala ndautomatic polyg on alsim plificatio n A.Hodgi ns J,FoleyJ.1999ACMSy mp osiumo nin teractive3DGra phicsC.Atla nta:ACM,1999.79-88.4Hopp eH.Newquadricmetricforsi mp lifyi ngmesheswitha pp eara nceattibutesA.EbertD,99C.Sa nF

17、ran cisco:IEEE,1999.5966.GrossM,Hama nn B.IEEEVisualizatio nHopp eH. ProgressivemeshesA.RushmeierH. Proceedi ngsofSIGGRA PH 96,Co mp uterGrap hics Proceedi ngs,A nn ualCo nferen ceSeriesC.NewOrlea ns:Addiso nWesley,1996.9 9-108.GueziecA Locallytolera ncedsufacesi mp lificatio n J.IEEETra nsactio nso

18、n Visualizatio n an dCo mp uterGra phics,1999,5(2):168-189.7Heckbert P,Garla ndM.Op timaltria ngulatio nan dquadric2basedsurfacesi mp lificatio n J. 612北京理工大学学报第20卷JournalofCo mp utatio nalGeometry:Theorya ndA pp licatio ns,1999,14(1-3):49-65.8 KleinR,LiebichG,StraB erW.MeshreductionwitherrorolA.Yag

19、elR,NielsonG.96C.Sa nFran cisco:IEEE,1996.311318.IEEEVisualizati on9 .Sk in:ac on structivea pp roachtomodeli ngfree2formMarkosia nL,Cohe nJ,CrulliT,etalsha pesA . RockwoodA. Proceedi ngsofSIGGRA PH 99,Com pu terGra phics Proceedi ngs,A nnu alCo nferen ceSenesC.LosA ngeles:Addis on WesleyL on gma n,1999.393- 4OO.MeshSim plificatio nBasedo nQuadricErrorMetricsWUYa2d on g, LIUYu2shu,GAO2x(De partme ntofC