1、第20卷第5期2000年10月北京理工大學(xué)學(xué)報(bào)JournalofBeijingInstituteofTechnologyVol.20No.5Oct.2000文章編號(hào):100120645(2000)0520607206基于二次誤差度量的網(wǎng)格簡(jiǎn)化算法吳亞?wèn)|,劉玉樹(shù),高春曉(北京理工大學(xué)計(jì)算機(jī)科學(xué)與工程系,北京100081)摘要:網(wǎng)格簡(jiǎn)化是提高計(jì)算機(jī)處理復(fù)雜模型速度的有效方法,要求算法時(shí)間和空間復(fù)雜性低、簡(jiǎn)化質(zhì)量高且簡(jiǎn)化結(jié)果中三角形緊致性好型的算法算法采用邊折疊為基本操作,低算法的空間復(fù)雜性,在P 上,算法可在12s內(nèi)簡(jiǎn)化含7019的三角形數(shù)為56%關(guān)鍵詞:網(wǎng)格簡(jiǎn)化;P391:A、顯示、存儲(chǔ)與傳輸都

2、是很大的負(fù)擔(dān),網(wǎng)格簡(jiǎn)化是在眾多的網(wǎng)格簡(jiǎn)化算法中,邊折疊的方法得到了廣(Quadricerrormetrics)簡(jiǎn)化算法在時(shí)間復(fù)雜泛的認(rèn)同16,其中,Garland的“二次誤差度量”度和簡(jiǎn)化質(zhì)量?jī)煞矫娑加休^為出色的表現(xiàn)1該算法以邊折疊為基本操作,以點(diǎn)到相關(guān)三角形平面的距離的平方為度量,折疊點(diǎn)的坐標(biāo)由最小化二次誤差確定此后,Lindstrom對(duì)點(diǎn)到平面的距離加權(quán)以三角形的面積,以最優(yōu)化體積的平方求得折疊點(diǎn)的坐標(biāo)2Erikson和Hoppe的幾何誤差簡(jiǎn)化方法也與文獻(xiàn)1類(lèi)似3,4作者提出一種新的基于邊折疊的網(wǎng)格簡(jiǎn)化算法注意到Garland的算法對(duì)空間要求較高,每個(gè)點(diǎn)需10個(gè)浮點(diǎn)數(shù)的歷史記錄,Linds

3、trom算法則不保留任何歷史記錄為降低空間復(fù)雜度,減少簡(jiǎn)化誤差,算法對(duì)每個(gè)點(diǎn)保留了1個(gè)浮點(diǎn)數(shù)的歷史記錄文獻(xiàn)14均采用點(diǎn)到相關(guān)平面的距離的平方為誤差度量,本算法則以點(diǎn)到相關(guān)直線的距離的平方為誤差度量此外,尋求簡(jiǎn)化結(jié)果三角形緊致性更好的算法是網(wǎng)格簡(jiǎn)化的重要任務(wù)之一7實(shí)驗(yàn)表明,作者提出的算法不僅可以產(chǎn)生高質(zhì)量的簡(jiǎn)化結(jié)果,而且簡(jiǎn)化結(jié)構(gòu)網(wǎng)格的三角形緊致性很好1網(wǎng)格簡(jiǎn)化算法111術(shù)語(yǔ)說(shuō)明為敘述方便,先簡(jiǎn)要介紹文中用到的術(shù)語(yǔ)及概念向量均指三維列向量頂點(diǎn)v的坐標(biāo)v=x,y,zT所指的邊均為有向邊,即e=(v0,v1),將邊e寫(xiě)作v0v1=v1-v0把點(diǎn)到邊所在直線的距離簡(jiǎn)稱(chēng)為點(diǎn)到邊的距離v3表示所有與頂點(diǎn)v相

4、鄰的邊的集合,如圖1所示收稿日期:20000313基金項(xiàng)目:高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金資助項(xiàng)目作者簡(jiǎn)介:吳亞?wèn)|,1974年生,博士生608北京理工大學(xué)學(xué)報(bào)第20卷邊折疊操作如圖2所示,邊v0v1折疊為折疊點(diǎn)v引起網(wǎng)格局部形狀的變化,如v0v1不是邊界邊,則一次邊折疊減少2個(gè)三角形、3條邊、1個(gè)頂點(diǎn)1圖1v 與頂點(diǎn)v相鄰的邊的集合*圖2邊折疊操作112誤差度量3見(jiàn)圖2所示,設(shè)邊v0v1折疊為點(diǎn)v,定義v到v30和v1的誤差如圖3所示,點(diǎn)v到邊v0v1的距離的平方r= v0v sin2v0v1-v0v1 )2 0 -(1令s=v0vvv0v2T2TTTTTr=s-st)=ss-s(tt)s=s

5、(I-tt)s.I3設(shè)s0=v-v0,ti為v30中邊的單位向量,則點(diǎn)v到v0中各邊距離的平方和nnv0v1d(v,n3v0)=(si=1T0(I-titi)s0)=sTT0(I-i=1titi)s0T令Q0=(I-i=1titi),則3Td(v,v0)=s0Q0s0T(1)同樣,設(shè)s1=v-v1,可得點(diǎn)v到v31中各邊的距離的平方和3T(2)d(v,v1)=s1Q1s1.3綜合式(1)(2),可得如圖2中邊v0v1折疊為點(diǎn)v,頂點(diǎn)v到v30和v1中各邊距離的平方和33TT(3)(v)=d(v,v0)+d(v,v1)=s0Q0s0+s1Q1s1以s0=v-v0,s1=v-v1代入式(3),整理

6、得TTT(v)=vT(Q0+Q1)v-2(vT0Q0+v1Q1)v+(v0Q0v0+v1Q1v1).TTT令A(yù)=Q0+Q1,bT=vT0Q0+v1Q1,c=v0Q0v0+v1Q1v1,則邊v0v1折疊為點(diǎn)v的誤差TT(4)(v)=vAv-2bv+c113折疊點(diǎn)坐標(biāo)的確定在采用邊折疊操作的簡(jiǎn)化算法中,選取折疊點(diǎn)坐標(biāo)的原則是使簡(jiǎn)化后的網(wǎng)格形狀盡可能接近原始網(wǎng)格但目前對(duì)簡(jiǎn)化前后網(wǎng)格的相似程度尚沒(méi)有公認(rèn)的度量標(biāo)準(zhǔn)如邊v0v1折疊為點(diǎn)v,為簡(jiǎn)單起見(jiàn),一般可選取折疊點(diǎn)v的坐標(biāo)為v0,v1或(v0+v1) 2,但更好的選擇應(yīng)該是不局限于邊v0v1甚至于該局部網(wǎng)格表面這里取使(v)值最小的v作為折疊點(diǎn)v的坐標(biāo)

7、,考慮到所采用的誤差度量方法,這種選擇是很自然的下面推導(dǎo)使(v)值最小的v的值第5期吳亞?wèn)|等:基于二次誤差度量的網(wǎng)格簡(jiǎn)化算法609(v)可寫(xiě)作c由矩陣A的定義知A為對(duì)稱(chēng)矩陣,故Q也為對(duì)稱(chēng)矩陣又由(v)定義知(v)>0(v303v1中各邊所在直線不會(huì)全部共線),故(v)是正定二次型,即Q為對(duì)稱(chēng)正定矩陣,A也為對(duì)稱(chēng)正定矩陣由線性代數(shù)最小原理可知(v)在v=A-1b處取得最小值因A為正定矩陣,故A可-bv=vTAv-2bTv+c=(vT1)AT-bv=PTQP.逆因此,當(dāng)邊v0v1折疊為點(diǎn)v時(shí),點(diǎn)v的坐標(biāo)v=A-1b114邊折疊消耗函數(shù)注意到112中的誤差度量(v)僅表示一次邊折疊前后局部網(wǎng)格

8、的差異,簡(jiǎn)化后網(wǎng)格與原始網(wǎng)格的距離,網(wǎng)格相似程度的度量標(biāo)準(zhǔn),一些文獻(xiàn)中采用的Hau8計(jì)算量,提高簡(jiǎn)化速度,當(dāng)邊v0v1折疊為點(diǎn)v(5)c(v)=v)e0)e其中(v),v0(v1)v0與v1的歷史記錄誤差設(shè)m為常數(shù),的歷史記錄誤差(6)e(v)=mc(v),即在原始網(wǎng)格中,各頂點(diǎn)歷史記錄誤差均為0,即e(vi)=0在,隨著邊折疊操作的進(jìn)行,每次折疊操作誤差的積累,各邊折疊的c(v)值將不斷增大,因此,消耗函數(shù)c(v)即可作為本算法網(wǎng)格簡(jiǎn)化的全局誤差函數(shù)在式(5)中,權(quán)值m決定了頂點(diǎn)v的歷史記錄誤差對(duì)v3中各邊的消耗函數(shù)值的“貢獻(xiàn)”,m值越大,則v3中各邊的消耗函數(shù)值將相應(yīng)增大,v3中各邊折疊的

9、概率將會(huì)減小(在邊折疊優(yōu)先隊(duì)列中位置靠后),即v3所在的局部區(qū)域不會(huì)很快再次被簡(jiǎn)化實(shí)驗(yàn)中取m=1,可得到很好的簡(jiǎn)化結(jié)果115算法流程本算法以邊折疊為基本操作,以點(diǎn)到相關(guān)直線的距離的平方為誤差度量,按邊折疊消耗函數(shù)值的大小將所有邊排為升序優(yōu)先隊(duì)列,取隊(duì)首元素執(zhí)行邊折疊操作,刪除隊(duì)列中無(wú)效的邊,并重新計(jì)算與折疊點(diǎn)相鄰的邊的消耗函數(shù)值,將其插入隊(duì)列算法執(zhí)行過(guò)程如下:初始化網(wǎng)格中所有點(diǎn)的歷史記錄誤差e(vi)=0;計(jì)算網(wǎng)格中所有邊的折疊誤差(v)及折疊點(diǎn)v的坐標(biāo)v,計(jì)算邊折疊的消耗值c(v),按c(v)大小將所有邊排為升序優(yōu)先隊(duì)列;取隊(duì)首消耗值最小的邊vivj執(zhí)行折疊操作,折疊點(diǎn)v的歷史記錄誤差e(v

10、)=c(vivj);3刪除隊(duì)列中所有因該邊折疊而導(dǎo)致消失的邊v3ivj;計(jì)算v3中各邊的折疊誤差及其折疊后點(diǎn)的坐標(biāo)v,并計(jì)算其消耗值,然后把該邊插入隊(duì)列;如此時(shí)網(wǎng)格的三角形個(gè)數(shù)多于用戶(hù)指定的數(shù)目,轉(zhuǎn)至執(zhí)行下一個(gè)邊折疊操作116三角形緊致性在網(wǎng)格中,緊致性差的三角形會(huì)引起光照處理時(shí)的不連續(xù)現(xiàn)象,并可能導(dǎo)致某些繪制方法速度下降,對(duì)模型的其他處理結(jié)果有很大影響9,因此網(wǎng)格中應(yīng)盡量避免緊致性差的三角形610北京理工大學(xué)學(xué)報(bào)第20卷Delaunary三角剖分的廣泛應(yīng)用在很大程度上正是因?yàn)樗梢援a(chǎn)生緊致性較好的三角形文獻(xiàn)2,6中均對(duì)網(wǎng)格中三角形的緊致性做了處理其中文獻(xiàn)2是在算法規(guī)定的約束不能夠確定折疊點(diǎn)的

11、坐標(biāo)時(shí),才考慮到三角形的形狀文獻(xiàn)6則在簡(jiǎn)化過(guò)程中,對(duì)邊折疊前后局部三角形的形狀進(jìn)行比較,如邊折疊后的三角形形狀不滿(mǎn)足要求,則放棄該邊折疊操作作者采用文獻(xiàn)6中對(duì)三角形緊致性的評(píng)估方法,即三角形的緊致性c=222,l0+l1+l2(7)其中A為三角形的面積,li為邊的長(zhǎng)度當(dāng)三角形為等邊三角形時(shí),c為1;0時(shí),c=0本算法并未對(duì)網(wǎng)格中三角形形狀做任何特殊處理,2實(shí)驗(yàn)結(jié)果作者在P 450上用C+,表1為與文獻(xiàn)1(a)原始模型(b)簡(jiǎn)化結(jié)果圖4兔子模型簡(jiǎn)化結(jié)果,簡(jiǎn)化98%(a)原始模型(b)簡(jiǎn)化結(jié)果圖5手模型簡(jiǎn)化結(jié)果,簡(jiǎn)化98%本算法的時(shí)間復(fù)雜度與文獻(xiàn)1相同,為O(nlgn)由于這類(lèi)算法本身比較簡(jiǎn)潔,其

12、速度與其他類(lèi)型的算法相比是很快的,這一點(diǎn)已為文獻(xiàn)1,2所證實(shí)本算法空間復(fù)雜度小于文獻(xiàn)1的算法在簡(jiǎn)化三角形數(shù)很多的模型時(shí),由于內(nèi)存的限制,程序要進(jìn)行頻繁的磁盤(pán)交換,此時(shí)本算法的優(yōu)點(diǎn)表現(xiàn)得相當(dāng)明顯第5期吳亞?wèn)|等:基于二次誤差度量的網(wǎng)格簡(jiǎn)化算法表1與文獻(xiàn)1算法實(shí)驗(yàn)數(shù)據(jù)比較611模型類(lèi)型兔子手原始模型三角形個(gè)數(shù)69451654666簡(jiǎn)化模型三角形個(gè)數(shù)150010000Qslim2101t sQslim2102簡(jiǎn)化結(jié)構(gòu)中%c>019的三角形個(gè)數(shù)本算法t s本算法簡(jiǎn)化結(jié)果中%c>019的三角形個(gè)數(shù)56548141862821129613值得注意的是,用本算法簡(jiǎn)化后的網(wǎng)格的三角形緊致性較好事實(shí)上

13、,利用本算法簡(jiǎn)化結(jié)果中c>018的三角形數(shù)達(dá)82%,而c<016的三角形數(shù)不足2%在所有的實(shí)驗(yàn)結(jié)果中,簡(jiǎn)化結(jié)果中c>019的三角形數(shù)所占比例均大于50%,而文獻(xiàn)6中給出的結(jié)果為39%作者對(duì)不保留歷史記錄的情況也做了實(shí)驗(yàn)e(vi)始終為0時(shí),簡(jiǎn)化結(jié)果的三角形形狀更為規(guī)則1500個(gè)三角形,c>019的三角形數(shù)達(dá)65%,3結(jié)論,以點(diǎn)到相關(guān)直線的距離的平方為誤差度量,算法按邊折疊的消耗函數(shù)值對(duì)網(wǎng)格中,依次取消耗值最小的邊執(zhí)行折疊操作,直至網(wǎng)格中的三角形數(shù)達(dá)到用戶(hù)指定的算法速度快,空間復(fù)雜度小,簡(jiǎn)化結(jié)果質(zhì)量較高,此外,算法所用的誤差度量方法可以獲得三角形緊致性很好的簡(jiǎn)化結(jié)果該算法

14、可用于交互可視化中的多細(xì)節(jié)層次場(chǎng)景的自動(dòng)生成和有限元模擬進(jìn)一步的工作包括改進(jìn)算法以使其能夠更好地處理邊界邊,并提供對(duì)模型法向量和紋理屬性簡(jiǎn)化的支持參考文獻(xiàn):1GarlandM,HeckbertP.SurfacesimplificationusingquadricerrormetricsA.WhittedT.ProceedingsofSIGGRAPH97,ComputerGraphicsProceedings,AnnualConferenceSeriesC.LosAngeles:AddisonWesley,1997.209-216.2LindstromP,TurkG.Fastandmemorye

15、fficientpolygonalsimplificationA.EbertD,98C.NorthCarolina:IEEE,1998.279-286.HagenH,RushmeierH.IEEEVisualization3EriksonC,ManochaD.GAPS:GeneralandautomaticpolygonalsimplificationA.HodginsJ,FoleyJ.1999ACMSymposiumonInteractive3DGraphicsC.Atlanta:ACM,1999.79-88.4HoppeH.Newquadricmetricforsimplifyingmes

16、heswithappearanceattibutesA.EbertD,99C.SanFrancisco:IEEE,1999.59-66.GrossM,HamannB.IEEEVisualization5HoppeH.ProgressivemeshesA.RushmeierH.ProceedingsofSIGGRAPH96,ComputerGraphicsProceedings,AnnualConferenceSeriesC.NewOrleans:AddisonWesley,1996.99-108.6GuéziecA.Locallytolerancedsurfacesimplifica

17、tionJ.IEEETransactionsonVisualizationandComputerGraphics,1999,5(2):168-189.7HeckbertP,GarlandM.Optimaltriangulationandquadric2basedsurfacesimplificationJ.612北京理工大學(xué)學(xué)報(bào)第20卷JournalofComputationalGeometry:TheoryandApplications,1999,14(1-3):49-65.8KleinR,LiebichG,StraerW.MeshreductionwitherrorcontrolA.Yag

18、elR,NielsonG.96C.SanFrancisco:IEEE,1996.311-318.IEEEVisualization9.Skin:aconstructiveapproachtomodelingfree2formMarkosianL,CohenJ,CrulliT,etalWUYa2dong,LIUYu2shu,GAO2x(DepartmentofComputerScienceandEngineering,T,)Abstract:Meshsimplificationcanirocessingspeedofcomplex3Dmodelsbycom.pireslowtimeandspacecomplexity,highpactness.Anewalgorithmtosimplifydensem.rithmusesedgecollapseanderrormetricsbasedfromvertextoassociatedlines.Toreducethememoryon,itkeepsonefloatnumberforea