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

《基于二次误差度量的网格简化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第20卷第5期北京理工大学学报Vol.20No.52000年10月JournalofBeijingInstituteofTechnologyOct.2000文章编号:100120645(2000)0520607206基于二次误差度量的网格简化算法吴亚东,刘玉树,高春晓(北京理工大学计算机科学与工程系,北京100081)摘要:网格简化是提高计算机处理复杂模型速度的有效方法,要求算法时间和空间复杂性低、简化质量高且简化结果中三角形紧致性好Z给出一种简化三角形网格表示的三维模型的算法Z算法采用边折叠为基本操作,以点到相关直线的距离的平方为误差度量Z为降低算

2、法的空间复杂性,简化过程中每个点只保留一个浮点数的历史记录Z实验结果表明,在PË上,算法可在12s内简化含7万个三角形的模型,简化结果中三角形紧致性大于019的三角形数为56%Z关键词:网格简化;误差度量;细节层次;紧致性中图分类号:TP391141文献标识码:A复杂的多边形网格模型对计算机的分析、显示、存储与传输都是很大的负担,网格简化是提高计算机处理复杂模型速度的有效方法Z在众多的网格简化算法中,边折叠的方法得到了广[1～6]泛的认同,其中,Garland的“二次误差度量”(Quadricerrormetrics)简化算法在时间复杂[1]度和简化

3、质量两方面都有较为出色的表现Z该算法以边折叠为基本操作,以点到相关三角形平面的距离的平方为度量,折叠点的坐标由最小化二次误差确定Z此后,Lindstrom对点到平[2]面的距离加权以三角形的面积,以最优化体积的平方求得折叠点的坐标ZErikson和Hoppe[3,4]的几何误差简化方法也与文献[1]类似Z作者提出一种新的基于边折叠的网格简化算法Z注意到Garland的算法对空间要求较高,每个点需10个浮点数的历史记录,Lindstrom算法则不保留任何历史记录Z为降低空间复杂度,减少简化误差,算法对每个点保留了1个浮点数的历史记录Z文献[1～4]均采

4、用点到相关平面的距离的平方为误差度量,本算法则以点到相关直线的距离的平方为误差度量Z此外,寻[7]求简化结果三角形紧致性更好的算法是网格简化的重要任务之一Z实验表明,作者提出的算法不仅可以产生高质量的简化结果,而且简化结构网格的三角形紧致性很好Z1网格简化算法111术语说明为叙述方便,先简要介绍文中用到的术语及概念Z向量均指三维列向量Z顶点v的坐标v=T[x,y,z]Z所指的边均为有向边,即e=(v0,v1),将边e写作v0v1=v1-v0Z把点到边所在直线3的距离简称为点到边的距离Zv表示所有与顶点v相邻的边的集合,如图1所示Z收稿日期:20000

5、313基金项目:高等学校博士学科点专项科研基金资助项目作者简介:吴亚东,1974年生,博士生Z608北京理工大学学报第20卷边折叠操作如图2所示,边v0v1折叠为折叠点v引起网格局部形状的变化,如v0v1不是边界边,则一次边折叠减少2个三角形、3条边、1个顶点Zv0v边折叠vv1*图1v÷与顶点v相邻的边的集合图2边折叠操作112误差度量33见图2所示,设边v0v1折叠为点v,定义v到v0和v1中各边距离的平方和为该折叠操作的误差Z如图3所示,点v到边v0v1的距离的平方222r=ûv0vûsinH=22v0v·v0v1ûv0vû1-=ûv0vûûv

6、0v1û22ûv0vû-((v0v·v0v1)öûv0v1û)Z令s=v0v,t=v0v1öûv0v1û,则2TT2TTTTTr=ss-(st)=ss-s(tt)s=s(I-tt)s.其中I为单位矩阵Z33设s0=v-v0,ti为v0中边的单位向量,则点v到v0中各边距离的平方和nn3TTTTd(v,v0)=∑(s0(I-titi)s0)=s0∑(I-titi)s0Zi=1i=1nT令Q0=∑(I-titi),则i=13Td(v,v0)=s0Q0s0Z(1)3同样,设s1=v-v1,可得点v到v1中各边的距离的平方和3Td(v,v1)=s1Q1s1.

7、(2)33综合式(1)(2),可得如图2中边v0v1折叠为点v,顶点v到v0和v1中各边距离的平方和33TT$(v)=d(v,v0)+d(v,v1)=s0Q0s0+s1Q1s1Z(3)以s0=v-v0,s1=v-v1代入式(3),整理得TTTTT$(v)=v(Q0+Q1)v-2(v0Q0+v1Q1)v+(v0Q0v0+v1Q1v1).TTTTT令A=Q0+Q1,b=v0Q0+v1Q1,c=v0Q0v0+v1Q1v1,则边v0v1折叠为点v的误差TT$(v)=vAv-2bv+cZ(4)113折叠点坐标的确定在采用边折叠操作的简化算法中,选取折叠点坐标的

8、原则是使简化后的网格形状尽可能接近原始网格Z但目前对简化前后网格的相似程度尚没有公认的度量标准Z如边v0v1