增量幾何壓縮

《增量幾何壓縮》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、1139-1282/2000/11(09)1167-09?2000JournalofSoftware軟件學(xué)報(bào)Vol.11,No.9+增量幾何壓縮劉新國(guó)鮑虎軍彭群生浙江大學(xué)CAD&CG國(guó)家重點(diǎn)實(shí)驗(yàn)室，310027，杭州摘要本文提出了一個(gè)幾何壓縮算法節(jié)省三角網(wǎng)格模型存儲(chǔ)和傳輸時(shí)間。它首先遞歸地以區(qū)域擴(kuò)張方式將模型分解為一系列的層結(jié)構(gòu)，利用層間的連貫性，以及對(duì)層結(jié)構(gòu)的有效編碼，實(shí)現(xiàn)了高效的拓?fù)鋲嚎s。同時(shí)，還設(shè)計(jì)了一個(gè)有效的非線性預(yù)測(cè)器來實(shí)現(xiàn)幾何位置的壓縮。與以前的算法相比，它具有線性復(fù)雜度，壓縮比高，執(zhí)行速度

2、快。實(shí)驗(yàn)結(jié)果表明，存儲(chǔ)一個(gè)三角形的拓?fù)湫畔⑵骄恍?.42比特。關(guān)鍵詞幾何壓縮二維流形定向曲面三角形網(wǎng)格模型一、引言盡管自由曲面廣泛應(yīng)用于CAD和計(jì)算機(jī)動(dòng)畫系統(tǒng)中，但多邊形模型，尤其三角形網(wǎng)格由于其簡(jiǎn)單性和靈活性，也被大量的圖形硬、軟件普遍支持。近年來，稠密的三角形網(wǎng)格模型逐漸在許多應(yīng)用領(lǐng)域，如數(shù)字地形、可視化、虛擬現(xiàn)實(shí)及基于三維掃描的自動(dòng)造型中得到了越來越廣泛地應(yīng)用。這使得對(duì)高度復(fù)雜、精細(xì)三角形網(wǎng)格的實(shí)時(shí)編輯、繪制和傳送成為一個(gè)極具挑戰(zhàn)性的課題。最初人們?yōu)榱藴p少繪制時(shí)間，加快繪制速度研究幾何壓縮算法[

3、1,2,3,4,5]。幾何壓縮不同于傳統(tǒng)的圖象壓縮機(jī)制。一個(gè)幾何網(wǎng)格模型通常由其拓?fù)浜蛶缀涡畔⒍糠纸M成，其中拓?fù)湫畔⑹侵妇W(wǎng)格頂點(diǎn)之間的相互連接關(guān)系，而幾何信息則指網(wǎng)格頂點(diǎn)的位置信息及附著在各頂點(diǎn)的有關(guān)繪制信息，如顏色、法向和紋理坐標(biāo)等。幾何壓縮的目標(biāo)是減少?gòu)?fù)雜三角形網(wǎng)格在其拓?fù)浜蛶缀挝恢眯畔⒈磉_(dá)方面的冗余度。二、相關(guān)工作類似于VRML中的IndexFaceSet，一個(gè)簡(jiǎn)單的三角形網(wǎng)格模型可表示為一個(gè)頂點(diǎn)數(shù)組和一個(gè)三角形數(shù)組，分別存放頂點(diǎn)的幾何位置和三角形頂點(diǎn)下標(biāo)。對(duì)于N個(gè)頂點(diǎn)和M個(gè)面的三角形網(wǎng)格模型，

4、若用三個(gè)4個(gè)字節(jié)的浮點(diǎn)數(shù)來存貯每個(gè)頂點(diǎn)的空間坐標(biāo)，4個(gè)字節(jié)的整數(shù)表示頂點(diǎn)的下標(biāo)，其存儲(chǔ)量為12N+12M字節(jié)。通常三角形個(gè)數(shù)是頂點(diǎn)個(gè)數(shù)的兩倍左右，所以平均每個(gè)三角形的存儲(chǔ)量是18字節(jié)。注意到這種表示方法中仍存在許多冗余信息，一種基于帶狀三角形結(jié)構(gòu)（trianglestrip）的三角形網(wǎng)格表示方法得到了圖形學(xué)界的高度重視。通過重用前兩個(gè)被訪問過頂點(diǎn)和加入一個(gè)新頂點(diǎn)的方式來定義新的三角形，這種帶狀三角形結(jié)構(gòu)減少了對(duì)頂點(diǎn)的索引次數(shù)，從而大大減少數(shù)據(jù)存儲(chǔ)。在這種表示法中，平均而言，每一頂點(diǎn)被索引二次左右，存儲(chǔ)一

5、個(gè)三角形大約需14字節(jié)。盡管帶狀三角形結(jié)構(gòu)可以減少對(duì)三角形網(wǎng)格模型的存儲(chǔ)，但是采用一系列帶狀三角形結(jié)構(gòu)完全覆蓋一個(gè)具復(fù)雜拓?fù)涞哪Ｐ筒⒎且譡6,7,8,9,10]事。進(jìn)一步研究發(fā)現(xiàn)，采用更復(fù)雜的編碼方法，還能夠大大地節(jié)省存儲(chǔ)量。[2,5]Deering給出了一個(gè)一般化的帶狀三角形表示方法，通過增加索引緩沖的長(zhǎng)度，在重[8]用已訪問頂點(diǎn)方面得到了更多的控制，從而減少數(shù)據(jù)存儲(chǔ)量。Taubin等在TopologySurgey算法中，通過構(gòu)造一棵頂點(diǎn)樹和一棵三角形樹對(duì)連接關(guān)系進(jìn)行編碼。借助于這兩棵樹，表示一個(gè)三角

6、形只需要1個(gè)比特。加上記錄頂點(diǎn)樹所需的額外數(shù)據(jù)，存儲(chǔ)一個(gè)三角形平均僅需[6]1.2至3.5比特(平均不超過2比特)。而Gumhold等則構(gòu)造和維護(hù)一些頂點(diǎn)序列組成的分割邊界，并引入七種不同的操作構(gòu)造下一個(gè)三角形，根據(jù)構(gòu)造三角形所使用的操作對(duì)這些分割邊界進(jìn)行動(dòng)態(tài)維護(hù)。由于這些操作的使用頻率各不相同，且相差很大，所以可采用Huffman編碼進(jìn)一步減少數(shù)據(jù)量，存儲(chǔ)一個(gè)三角形平均需要1.5至4.23比特。[11,12,13,14,15,16,17]多分辨表示和LoD簡(jiǎn)化算法也可以看作是一類幾何壓縮算法，只是它改

7、變了原來模型中頂點(diǎn)集合和拓?fù)湫畔?，而這在很多情況下是不被允許的。但是Hoppe的累進(jìn)網(wǎng)[11,13]格方法（簡(jiǎn)稱PM）不同，它所表示的LoD模型序列具有很強(qiáng)的連慣性，通過簡(jiǎn)單的頂點(diǎn)分裂操作可以逐步地完全恢復(fù)原來的拓?fù)湫畔?。再?duì)頂點(diǎn)分裂操作的有效編碼，就能實(shí)現(xiàn)+本文收國(guó)家自然科學(xué)杰出青年基金（批準(zhǔn)號(hào)：69925204），霍英東青年教師基金資助?！?168—JournalofSoftware軟件學(xué)報(bào)2000,11(9)幾何壓縮。一個(gè)分裂操作包含一個(gè)分裂頂點(diǎn)和兩條分裂邊，如果當(dāng)前層次模型的頂點(diǎn)數(shù)為N，存儲(chǔ)分裂

8、頂點(diǎn)需要Log(N)個(gè)比特；如果頂點(diǎn)平均入度為6，存儲(chǔ)兩條分裂邊平均需要大約5.3[14]比特。Taubin等擴(kuò)展了PM方法，通過對(duì)一組相關(guān)的頂點(diǎn)分裂，稱之為森林分裂(forestsplit)，進(jìn)行編碼，減少記錄分裂操作的數(shù)據(jù)，從而獲得更高的壓縮比。拓?fù)湫畔嚎s的關(guān)鍵在于充分地利用三角形頂點(diǎn)序列的連貫性。這需要我們以一種特殊地順序和方式遍歷網(wǎng)格中的三角形。通過以區(qū)域擴(kuò)張的方法將原網(wǎng)格模型分解為一系列的層結(jié)構(gòu)，在層與層之間保持極大的頂點(diǎn)連慣性