三維模型簡化

1、基于Garland的邊收縮算法的一種實(shí)現(xiàn)0引言隨著科學(xué)技術(shù)的進(jìn)步，在計算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)、地理信息系統(tǒng)、醫(yī)學(xué)圖像系統(tǒng)等領(lǐng)域所構(gòu)造和使用的模型越來越精細(xì)、越來越復(fù)雜。這些復(fù)雜的模型不但對計算機(jī)的存儲容量、 處理速度提出了很高的要求、而且成為實(shí)時繪制、網(wǎng)絡(luò)傳輸?shù)钠款i。因此模型簡化成為非常 重要的研究課題。模型簡化是指在保持原模型幾何形狀基本不變的前提下，采用適當(dāng)?shù)乃惴p少該模型的面片數(shù)、頂點(diǎn)數(shù)和邊數(shù)。近年來，出現(xiàn)了很多有代表性的模型簡化算法，其中Gala nd的基于二次誤差度量的邊收縮算法是目前最常采用且有效的算法。其基本思想是以頂點(diǎn)到相關(guān)三角形平面的距離的平方和為誤差度量，通過重復(fù)的邊收縮操作

2、對模型進(jìn)行簡化。1算法分析與設(shè)計1.1基本概念：定義1三角網(wǎng)格是由三位空間中的三角形通過邊和頂點(diǎn)連接而成的分段線性曲面。三角網(wǎng)格 M可由頂點(diǎn)集 V=v1,v2.vm和三角集合 F=f1.f2.fn組成的二元組 M=(V,F)來表示定義2對M種任一頂點(diǎn)vi，與頂點(diǎn)vi相關(guān)的三角形集合記作Planes(i)，與邊(vi,vj)關(guān)聯(lián)的三角形集合記作Planes(i,j)，所有與vi關(guān)聯(lián)的邊構(gòu)成的集合 Edge(i)。1.2基于二次誤差度量的邊收縮算法基于二次誤差度量的邊收縮算法是通過不斷選擇模型中的一條邊進(jìn)行收縮，達(dá)到對模型的簡化。每收縮一條非邊界邊， 模型減少2個三角形、1個頂點(diǎn)、三條邊；收縮一條

3、邊界邊， 模型減少1個三角形、1個頂點(diǎn)、倆條邊。1.2.1誤差度量簡化模型必須與原網(wǎng)格盡量相似，這取決于邊收縮的順序和邊收縮后生成的新點(diǎn)的位 置。如何選擇合適的邊進(jìn)行收縮及如何生成新的頂點(diǎn)，有一個選擇誤差度量標(biāo)準(zhǔn)的問題。 Garland算法以點(diǎn)到平面的距離為誤差度量標(biāo)準(zhǔn)。設(shè)對邊(vi,vj)進(jìn)行收縮，則與(vi,vj)邊相關(guān)聯(lián)的三角形集合Planes(i,j)構(gòu)成了原模型上的一個區(qū)域，設(shè)邊收縮后生成的新位置v為x,y,z,1，定義這次邊收縮帶來的新誤差( V)為V到三角形集合Planes(i,j)中每個三角形所在面的距離的平方和，表示三角形集合Planes(i,j)中的每個三角形所在面的平面方

4、程ax+by+cz+d=O ，a2b2c2 = 1。在根據(jù)點(diǎn)到平面ax+by+cz+d=0的距離公式為9ax_by_cz 二 d a2 b2 c2以及等式運(yùn)算-工(pTv)2,就有 ( v )= P Planes(i,j)其中：Tp=(a,b,c,d)該式可變換如下:(v)=(x, y,z,1T)=、VT(ppT)Vp Planes(i, j)vT(- Kp)vp Planes(i, j)Kp其中：L為4*4的對稱矩陣，稱為三角形的誤差矩陣，它的定義如下ad bd cdad bd dQ稱為該次收縮的誤差矩陣，定義如下 1.3本小組關(guān)于Garland算法的一種實(shí)現(xiàn)。為了簡化算法實(shí)現(xiàn)的效率問題，使

5、用本組關(guān)于Gala nd算法的一種實(shí)現(xiàn)：1、 取邊收縮的誤差矩陣Q為邊的倆頂點(diǎn)收縮的誤差矩陣Qi和Qj之和，即(Q=Qi+Qj)。2、 取新頂點(diǎn)位置為收縮邊(i,j)中的一個，誤差由公式 v Qv計算得到，具體的選擇由i收縮 到j(luò)的所產(chǎn)生的誤差和由j收縮到i所產(chǎn)生的誤差值做比較得到的較小值決定。3、 實(shí)際邊收縮帶來的結(jié)果是刪除一個點(diǎn)，刪除一條邊，刪除倆個與邊關(guān)聯(lián)的三角形，增加 新邊、三角形。具體算法步驟如下：步驟1根據(jù)給定的模型數(shù)據(jù)，計算出所有頂點(diǎn)的頂點(diǎn)誤差矩陣Qi :為各平面對應(yīng)的a、c關(guān)聯(lián)矩Kp陣的和：計算過程涉及求面的c(注意滿足2 2 2 =a b C I),即為面的單位法向量，單位法

6、向量的求法可根據(jù)平面?zhèn)z點(diǎn)的叉乘 在單位化即可。步驟2設(shè)計一關(guān)于結(jié)構(gòu)體的優(yōu)先隊(duì)列來簡化堆的操作，存放i，j，及其收縮帶來的誤差，代表從i折疊到j(luò)的誤差，并設(shè)計一哈希表用于判定是否新邊。步驟3計算邊折疊誤差：根據(jù)步驟2，取邊折疊從i到j(luò)和從j到i的教小者作為該邊的誤差入隊(duì)并進(jìn)入哈希散列。步驟4選擇隊(duì)列中的隊(duì)頭元素q出隊(duì)（即代表從q.i折疊到q.j）。步驟5判斷i，j同時相關(guān)的三角形的個數(shù)：如果個數(shù)大于1，那么刪除與i，j同時關(guān)聯(lián)的三角形，刪除點(diǎn)i,進(jìn)行邊收縮（將剩余三角形中與i相關(guān)的三角形全部轉(zhuǎn)移到與 j相關(guān)）, 并往隊(duì)列中增加由于折疊帶來的新邊 （做與步驟3相同的操作），否則轉(zhuǎn)步驟4。步驟6如果

7、邊收縮達(dá)到給定的收縮哦邊的個數(shù)，則結(jié)束收縮，否則轉(zhuǎn)步驟4。2、實(shí)驗(yàn)分析2.1.1原始牛模型：5804個三角片2.1.2簡化后，三角片 2804 簡化時間2578ms角片1404簡化時間3235ms,，三角片704簡化時間3500ms22.1原始兔子模型19859個三角片三角片3859簡化時間40375ms2.2.2進(jìn)一步簡化 三角片1859 簡化時間41359ms2.2.3更進(jìn)一步簡化 三角片1159 簡化時間41219ms3、結(jié)束語Gala nd算法同樣,本次簡化，在簡化達(dá)到一定程度后，并不能確保保持具體信息，與 存在著簡化后的模型局部極大或極小的情況參考文獻(xiàn)Garland M， Heckbert P S.Surface sim