基于漸近網格的三維建筑模型簡化方法應用

孔垂柳

(吉林建筑工程學院 計算機科學與工程學院，長春 130118)

基于漸近網格的三維建筑模型簡化方法應用

孔垂柳

(吉林建筑工程學院 計算機科學與工程學院，長春 130118)

在城市空間三維表現中，針對復雜自然景觀的地形地貌大多采用不規則三角網TIN模型表現。為節約存儲空間，在參照JPEG壓縮技術中的用戶興趣域編碼思想(ROI)結合邊收縮算法的基礎上，實現用戶興趣域以外的其它區域進行簡化，只對用戶興趣域保持較高分辨率。本算法在簡化過程中同時生成過程文件，保證了模型連續多分辨率的重建。

三維模型;網格簡化;漸進網格;用戶興趣域

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

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

1 邊收縮算法與漸進網格

1.1 邊收縮算法

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

邊收縮算法一種基于迭代點對收縮的網格簡化方法［3］.迭代點對收縮方法的原理是:每次迭代地從網格中選定一對頂點，然后將二者合并成為一個新的頂點，當要求選定的頂點是一條邊的2個端點時，就稱為“邊收縮”。

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

圖1 邊收縮算法原理

邊收縮算法主要步驟為:

(1)依照預定規則為每條邊的邊賦權值W(e);

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

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

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

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

1.2 漸進網格

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

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

2 ROI編碼思想

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

用戶興趣域建立ROI掩模移植入三維網格中，將三維模型的頂點集和邊集劃分為用戶興趣域頂點集、邊集和非用戶興趣域頂點集、邊集，從而實現非興趣域的三維模型簡化。

3 模型的簡化過程實施

在邊收縮算法的基礎上，根據用戶興趣點，將三維網格劃分為用戶興趣域和非用戶興趣域.在簡化過程中，盡量避免用戶興趣域的邊收縮，從而對用戶興趣域保持較高的分辨率.

算法步驟如下:

(1)對原始網格M進行預處理，建立頂點集合Vertexes(M)，三角形集合Triangles(M)和邊集合Edges(M);

(2)根據用戶輸入興趣點Vf，為三維網格M建立用戶興趣域。

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

我們為了減少計算量，將定義V與Vf間的標準化距離為mahatton距離:

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

(3)對網格的每條邊e分配邊權V(e)

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

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

(5)重復執行步驟(4)，直至達到用戶要求時結束，我們在實驗中設置了被刪除的頂點數與原總頂點的比例β小于預定值為結束要求。

4 結語

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

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

［2］宋正陽，胡玉清，謝傳節.關于多屬性三維網絡壓縮與傳輸問題的研究［J］.計算機技術與發展，2009(2):196－198.

［3］薛冰，王莉莉，沈哲.基于網格分割的帶紋理模型細節保持化簡方法［J］.計算機輔助設計與圖形學學報，2010(12):55－58.

［4］萬定生，倪海濤.基于代價函數三角網格模型動態簡化算法研究［J］.計算機工程與應用，2009(7):209－210.

［5］官倩寧，田卉，覃團發.基于ROI多特征和相關反饋的圖像檢索算法［J］.計算機科學，2008(5):261－263.

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

責任編輯:吳旭云

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

吉林建筑工程學院青年科技發展基金項目(J20091053)

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