孔垂柳

(吉林建筑工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，長春 130118)

基于漸近網(wǎng)格的三維建筑模型簡化方法應(yīng)用

孔垂柳

(吉林建筑工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，長春 130118)

在城市空間三維表現(xiàn)中，針對(duì)復(fù)雜自然景觀的地形地貌大多采用不規(guī)則三角網(wǎng)TIN模型表現(xiàn)。為節(jié)約存儲(chǔ)空間，在參照J(rèn)PEG壓縮技術(shù)中的用戶興趣域編碼思想(ROI)結(jié)合邊收縮算法的基礎(chǔ)上，實(shí)現(xiàn)用戶興趣域以外的其它區(qū)域進(jìn)行簡化，只對(duì)用戶興趣域保持較高分辨率。本算法在簡化過程中同時(shí)生成過程文件，保證了模型連續(xù)多分辨率的重建。

三維模型;網(wǎng)格簡化;漸進(jìn)網(wǎng)格;用戶興趣域

在數(shù)字城市可視化技術(shù)研究中，三維數(shù)據(jù)建模始終擔(dān)當(dāng)著城市物態(tài)文化的數(shù)字表現(xiàn)技術(shù)核心。自然景觀中地形地貌的呈現(xiàn)不規(guī)則的自由曲面大多采用三角形網(wǎng)格模型表示，為了表現(xiàn)追求質(zhì)感真實(shí)，隨之而來的就是構(gòu)建的模型數(shù)據(jù)量巨大，給計(jì)算機(jī)繪制帶來了壓力。為了解決海量數(shù)據(jù)與有限的計(jì)算能力之間的矛盾，于是需要對(duì)三角形網(wǎng)格模型的模型進(jìn)行簡化。

近年來，國內(nèi)外對(duì)網(wǎng)格模型簡化方法的研究已取得了階段性成果，有基于小波分解理論的網(wǎng)格簡化方法和基于頂點(diǎn)聚類的網(wǎng)格簡化方法［1］;還有Schroeder提出的基于頂點(diǎn)刪除的網(wǎng)格簡化方法［2］;Hoppe等提出了基于邊收縮的網(wǎng)格簡化方法因其高效性成為常用的選擇。在實(shí)際應(yīng)用中，用戶通?？赡苤粚?duì)網(wǎng)格的部分區(qū)域感興趣，并希望該區(qū)域保有較高的分辨率，而其它區(qū)域只要達(dá)到基本的視覺要求即可。常見的網(wǎng)格簡化算法并未區(qū)分對(duì)用戶興趣域和非用戶興趣域，而將全體區(qū)域是同等對(duì)待的，所以網(wǎng)格還有進(jìn)一步簡化的可能和必要。用戶興趣域(ROI，region of interest)編碼技術(shù)已經(jīng)成熟的引用在圖像和視頻編碼領(lǐng)域。三維模型簡化領(lǐng)域中，引入ROI編碼思想，作為三維模型進(jìn)一步簡化新方法應(yīng)用，保證用戶興趣域的高分辨率，能在滿足用戶可視化要求的前提下更有效地節(jié)約存儲(chǔ)空間。

1 邊收縮算法與漸進(jìn)網(wǎng)格

1.1 邊收縮算法

在圖形學(xué)中，三角形網(wǎng)格為表示大量立體形狀和自由曲面的常用方法.所謂三角形網(wǎng)格就是一組三角形構(gòu)建片面的集合，大小不同的三角形共同構(gòu)成了一個(gè)物體的表面，模型的分辨率越高則采用的三角形數(shù)量就越多。

邊收縮算法一種基于迭代點(diǎn)對(duì)收縮的網(wǎng)格簡化方法［3］.迭代點(diǎn)對(duì)收縮方法的原理是:每次迭代地從網(wǎng)格中選定一對(duì)頂點(diǎn)，然后將二者合并成為一個(gè)新的頂點(diǎn)，當(dāng)要求選定的頂點(diǎn)是一條邊的2個(gè)端點(diǎn)時(shí)，就稱為“邊收縮”。

如圖1所示，網(wǎng)格中刪除的邊為e1=＜v1，v2＞，則它的2個(gè)頂點(diǎn)v1，v2被合并為新頂點(diǎn)V0，與這條邊相鄰的2個(gè)三角形也同時(shí)被刪除，如果e1在邊界上，則對(duì)應(yīng)只刪除1個(gè)三角形。隨著邊收縮操作的進(jìn)行，網(wǎng)格模型中三角形逐漸減少，網(wǎng)格分辨率也就隨之降低。一般通過設(shè)定邊的權(quán)值來選擇刪除。

圖1 邊收縮算法原理

邊收縮算法主要步驟為:

(1)依照預(yù)定規(guī)則為每條邊的邊賦權(quán)值W(e);

(2)選擇權(quán)最小的邊(Vi，Vj)進(jìn)行邊收縮操作，刪除邊(Vi，Vj)及其相鄰三角形;

(3)更新待刪除邊的集合;

(4)如果滿足結(jié)束條件則退出，否則轉(zhuǎn)(1)，繼續(xù)下一次邊收縮操作。

邊收縮算法的結(jié)束條件一般為可設(shè)定為以下兩種情況:①邊收縮引入的誤差達(dá)到一定閾值δ;②被刪除的頂點(diǎn)數(shù)滿足一定要求(數(shù)目γ或比例β);結(jié)束條件中的各個(gè)參數(shù)需要依據(jù)先驗(yàn)知識(shí)設(shè)定。

1.2 漸進(jìn)網(wǎng)格

在邊收縮算法的基礎(chǔ)上，Hoppe提出了漸進(jìn)網(wǎng)格(Progressive Mesh)的構(gòu)造方法［4］。所謂的漸進(jìn)網(wǎng)格PM由1個(gè)粗糙的簡化網(wǎng)格Mr和1個(gè)頂點(diǎn)信息記錄列表組成的，列表內(nèi)容即{Mr，Vsplit0，Vsplit1，Vsplitn－1}。這個(gè)列表數(shù)據(jù)依次記錄刪除的點(diǎn)及次序，也就是原始網(wǎng)格M簡化成Mr的漸進(jìn)過程。漸進(jìn)網(wǎng)格算法包括網(wǎng)格簡化和網(wǎng)格重構(gòu)互逆過程組成。

首先，網(wǎng)格的簡化是通過邊收縮操作實(shí)現(xiàn)的.每次邊收縮運(yùn)算，使原始網(wǎng)格M中的1條邊及其相鄰三角形被刪除，網(wǎng)格的分辨率也降低，最后得到了簡化后的較粗糙網(wǎng)格Mr和一系列細(xì)節(jié)信息記錄。而網(wǎng)格的恢復(fù)是邊收縮操作的逆操作—點(diǎn)分裂操作完成的，點(diǎn)分裂的次序也是根據(jù){Vsplit0，Vsplit1，….Vsplitn－1}細(xì)節(jié)信息記錄，重新向網(wǎng)格中插入頂點(diǎn)和三角形，最后恢復(fù)出具有原始分辨率的網(wǎng)格。

2 ROI編碼思想

ROI(Region of Intersting)編碼技術(shù)是JPEG2000標(biāo)準(zhǔn)提出的一種新技術(shù)［5］，其基本思想是:對(duì)用戶興趣域進(jìn)行低壓縮比甚至是無損壓縮編碼以求獲得高質(zhì)量的重建圖像，而對(duì)其它區(qū)域采用較高壓縮率以求節(jié)省存儲(chǔ)空間。在圖像編碼中，ROI編碼技術(shù)通過對(duì)用戶興趣域產(chǎn)生ROI掩模，將原始圖像劃分為用戶興趣域和非用戶興趣域。

用戶興趣域建立ROI掩模移植入三維網(wǎng)格中，將三維模型的頂點(diǎn)集和邊集劃分為用戶興趣域頂點(diǎn)集、邊集和非用戶興趣域頂點(diǎn)集、邊集，從而實(shí)現(xiàn)非興趣域的三維模型簡化。

3 模型的簡化過程實(shí)施

在邊收縮算法的基礎(chǔ)上，根據(jù)用戶興趣點(diǎn)，將三維網(wǎng)格劃分為用戶興趣域和非用戶興趣域.在簡化過程中，盡量避免用戶興趣域的邊收縮，從而對(duì)用戶興趣域保持較高的分辨率.

算法步驟如下:

(1)對(duì)原始網(wǎng)格M進(jìn)行預(yù)處理，建立頂點(diǎn)集合Vertexes(M)，三角形集合Triangles(M)和邊集合Edges(M);

(2)根據(jù)用戶輸入興趣點(diǎn)Vf，為三維網(wǎng)格M建立用戶興趣域。

設(shè)MV(Vertex)，ME(Edge)分別表示網(wǎng)格M的頂點(diǎn)集掩模和邊集掩模，V f為用戶輸入興趣點(diǎn)，V和E分別表示M的任意頂點(diǎn)和任意邊，且V≠V f，E_index1和E_index2分別為邊E的兩個(gè)頂點(diǎn)，判斷V是否為用戶興趣域，我們則采用向量間距離是否小于給定的約束。

我們?yōu)榱藴p少計(jì)算量，將定義V與Vf間的標(biāo)準(zhǔn)化距離為mahatton距離:

頂點(diǎn)集掩模和邊集掩模作為三維網(wǎng)格頂點(diǎn)集和邊集用戶興趣域的映射用1和0表示，只要有一個(gè)頂點(diǎn)在興趣域中，我們就認(rèn)定此邊E屬于用戶興趣域，不在化簡范圍內(nèi)，于是原始網(wǎng)格被劃分為用戶興趣域和非用戶興趣域。

(3)對(duì)網(wǎng)格的每條邊e分配邊權(quán)V(e)

對(duì)三角網(wǎng)格的用戶興趣域和非用戶興趣域采用不同的邊權(quán)定義方案.對(duì)非用戶興趣域，采用最短邊策略定義邊權(quán)，用邊長作為權(quán)值［6］。為了突出用戶興趣域中邊的重要性，定義用戶興趣域中邊的權(quán)值為所有的非用戶興趣域邊長的最大值與自身的邊長之和。

(4)從邊集合中選取具有最小邊權(quán)的邊做邊收縮;

(5)重復(fù)執(zhí)行步驟(4)，直至達(dá)到用戶要求時(shí)結(jié)束，我們?cè)趯?shí)驗(yàn)中設(shè)置了被刪除的頂點(diǎn)數(shù)與原總頂點(diǎn)的比例β小于預(yù)定值為結(jié)束要求。

4 結(jié)語

隨著我國城市化工業(yè)化進(jìn)程發(fā)展，城市景觀圍繞城市人文主題呈現(xiàn)個(gè)性化衍變。復(fù)雜的不規(guī)則建筑幾何體的三維表現(xiàn)依舊是數(shù)字城市的基礎(chǔ)性研究工作。本文利用漸近網(wǎng)格的思想實(shí)現(xiàn)了一種將建筑實(shí)體分區(qū)域化簡作為降低數(shù)據(jù)量和追求真實(shí)感的一種折衷方案，較好的完成了吉林市東南部城鄉(xiāng)區(qū)域全景三維模擬展示。

［1］盧威，曾定浩，潘金貴.支持外觀屬性保持的三維網(wǎng)格模型簡化［J］.軟件學(xué)報(bào)，2009(3):243－245.

［2］宋正陽，胡玉清，謝傳節(jié).關(guān)于多屬性三維網(wǎng)絡(luò)壓縮與傳輸問題的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2009(2):196－198.

［3］薛冰，王莉莉，沈哲.基于網(wǎng)格分割的帶紋理模型細(xì)節(jié)保持化簡方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010(12):55－58.

［4］萬定生，倪海濤.基于代價(jià)函數(shù)三角網(wǎng)格模型動(dòng)態(tài)簡化算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，2009(7):209－210.

［5］官倩寧，田卉，覃團(tuán)發(fā).基于ROI多特征和相關(guān)反饋的圖像檢索算法［J］.計(jì)算機(jī)科學(xué)，2008(5):261－263.

［6］朱英浩，張劍清，張祖勛.基于攝像機(jī)及線劃圖的網(wǎng)上三維場景［J］.計(jì)算機(jī)仿真，2007(11):236－239.

責(zé)任編輯:吳旭云

Application of simplification of three-dimensional architecture model based on asymptotic grid

KONG Chui-liu
(1.College of Computer Science and Technology，Jilin Institute of Architecture and Civil Engineering，Changchun 130118，China)

While displaying city space in the three-dimensional way，it is common to present natural landscapes by using the triangulated irregular network(TIN)model.In order to save storage space，the problem is solved on the basis of border contraction algorithm combining with the conception of domain of user interest(ROI)in JPEG compression technique.We simplify the reign beyond the interest of users to maintain a high resolution.A document is generated while the algorithm is simplified，which ensures the reconstruction of the continuous multi-resolution model.

three-dimensional model;mesh simplification;asymptotic grid;domain of user interest

TP391

A

1009－3907(2011)06－0029－03

2011-03-30

吉林建筑工程學(xué)院青年科技發(fā)展基金項(xiàng)目(J20091053)

孔垂柳(1972-)，女，吉林長春人，副教授，碩士，主要從事軟計(jì)算方面的研究。