楊必勝,姜少波

1.武漢大學測繪遙感信息工程國家重點實驗室,湖北武漢430079;2.武漢大學時空數(shù)據(jù)智能獲取技術與應用教育部工程研究中心,湖北武漢430079

基于切割環(huán)分解的三維建筑物細節(jié)層次模型構造

楊必勝1,2,姜少波1,2

1.武漢大學測繪遙感信息工程國家重點實驗室,湖北武漢430079;2.武漢大學時空數(shù)據(jù)智能獲取技術與應用教育部工程研究中心,湖北武漢430079

提出一種基于切割環(huán)分解的建筑物LOD(細節(jié)層次)模型的自動生成方法,該方法首先通過二面角操作算子識別建筑模型中的切割環(huán),然后通過切割環(huán)將建筑物模型迭代分割成建筑主體和一系列細部特征,并將分割的結果存儲在一棵構造實體幾何樹(CSG tree)中,最后對特征部件按重要性進行等級劃分,同時進行簡化處理。試驗結果表明該方法具有較高的計算效率,能有效減少模型表面的細節(jié)和較好保持模型的結構特征。

3D建筑物模型;模型分解;切割環(huán);CSG樹;特征識別

1 引 言

三維城市模型(3D city models,3DCM)作為城市的三維逼真描述,在城市建設和規(guī)劃等相關領域得到廣泛應用。由于不同的應用對三維城市模型具有不同細節(jié)層次需求,因此需要對三維城市模型進行細節(jié)層次(levels of detail,LOD)表達,從而滿足海量三維城市模型數(shù)據(jù)的交互式實時可視化、網(wǎng)絡漸進傳輸?shù)确矫娴男枨骩1-4]。建筑物LOD模型自動生成的關鍵是通過模型簡化或綜合等操作算子生成一系列從精細到粗糙的建筑物模型。計算機圖形學領域已經(jīng)開發(fā)許多比較成熟的三維模型簡化算法[5],這些算法一個共同特點是通過幾何元素刪除法或基于小波變換的方法實現(xiàn)三維模型從細到粗的LOD表達。這些方法對三維自由平滑曲面模型十分有效,尤其在地形LOD模型的自動生成方面具有很好的效果[6-8]。建筑物模型在整體幾何結構上主要是由平面構成,面和面之間具有明確的幾何約束關系,如共面、平行、垂直相交和對稱等[9],而且不存在高冗余度的幾何細節(jié)(圖1(a));其次,建筑物模型中存在大量的具有內在幾何關系約束的語義部件,如:門、窗、陽臺、煙囪和屋頂?shù)?目前針對三維自由曲面的簡化算法如文獻[10]中的Qslim,均難以保持建筑物模型自身固有的特征和約束,如圖1(b)。

近年來,三維建筑物的簡化引起許多學者的關注。文獻[11—12]提出一種平面分割方法,建筑物首先被分割成一些特征部件,然后對其進行分析綜合,該方法需要應用很多分割平面,算法比較復雜;文獻[9,13—14]采用一種半空間剖分的方法,該方法對于在不同層具有不同幾何結構的建筑物難以奏效;文獻[15]基于尺度空間理論利用開運算和閉運算移除小的部件和填補小的空洞,該算法僅適合于正交平行結構的建筑物;文獻[16]提出一種感知驅動的簡化方法,但需要將三維模型轉化成二維影像提取感知信息,計算代價比較大;文獻[17]提出一種人造對象間斷式的簡化方法,對比較簡單的人造模型能夠取得較好的效果,但對于稍微復雜的特征部件難以識別;文獻[18]對各種3D建筑物的簡化和綜合方法進行了比較分析。

圖1 Qslim簡化建筑物模型的效果Fig.1 Simplification effect of a building model with Qslim

綜上所述,現(xiàn)有簡化算法難以有效處理建筑物模型的LOD生成,因此提出一種基于切割環(huán)分解的建筑物模型簡化方法。首先通過二面角操作算子識別建筑模型中的切割環(huán),然后通過切割環(huán)將建筑物模型迭代分割成建筑主體和一系列部件,同時將分割的結果存儲在一棵構造實體幾何樹中,最后對相應的部件進行簡化,從而生成三維建筑物的LOD模型。

2 基于切割環(huán)的建筑物LOD模型生成

2.1 三維建筑物模型的描述

由于三維場景中,建筑物整體結構大多規(guī)則簡單,而表面結構特征比較復雜,因此在研究中,只針對由三角網(wǎng)平面片構成的二維流形拓撲模型,暫時不考慮具有自由曲面的實體模型,對于由很多不連通的部件組成的三維建筑模型,在簡化的過程中不會改變其拓撲關系。建筑物模型的最小表達單元是三角形。因此,對于建筑物模型M可以表達為

式中,V是三維空間內的點,具有確定幾何坐標。

顯然,建筑物模型的最小表達單元中三角形的任意2個頂點〈Vi,Vj〉構成一條邊 ek=〈Vi, Vj〉。為描述方便,定義四個概念:①凸邊,從模型的外部進行觀察,該邊相鄰的兩個三角形的二面角大于180°,如圖2(a);②凹邊,從模型的外部進行觀察,該邊相鄰的兩個三角形的二面角小于180°,如圖2(b);③平面邊,該邊相鄰的兩個三角形共面;④切割環(huán),如果某個封閉環(huán)能將建筑物模型分割為兩個面殼,而且每個面殼的體積不為0,則該封閉環(huán)被定義為切割環(huán),切割環(huán)上的邊稱為切邊,面殼填洞后對應的實體稱為分割體。

圖3(a)中的環(huán)l1分割模型后得到兩個面殼,其中有一個面殼 FS1為平面片,體積為0,因此環(huán)l1不是切割環(huán)。根據(jù)切邊的凹凸性,選擇三類切割環(huán)進行分割:①凹切割環(huán),切割環(huán)中的所有切邊都是凹邊;②凸切割環(huán),切割環(huán)中的所有切邊都是凸邊;③混合凹切割環(huán),切割環(huán)中的切邊由凹邊和平面邊組成,且該環(huán)的所有切邊在一個平面內。圖3(b)中l(wèi)2為凹切割環(huán),圖3(c)中 l3為凸切割環(huán),圖3(d)中 l4為混合凹切割環(huán),它由黑色表示的凹邊和灰色表示的平面邊組成。

圖2 凸邊和凹邊Fig.2 Convex edge and concave edge

圖3 切割環(huán)舉例Fig.3 Illustration of cutting loops

文獻[19]認為三維模型中的特征是一些能夠從原始模型中有效分離出來的連接區(qū)域。對于建筑物模型而言,其表面結構特征主要表現(xiàn)為突出和凹陷的部件,如窗戶、門、陽臺、煙囪等,這些部件可以看成原始模型的一個子集,其可以任意復雜,但能從原始模型中有效分離,如圖4。由于切割環(huán)是分離建筑主體和特征部件的分界線,因此,識別建筑物模型中存在的切割環(huán)是實現(xiàn)建筑物LOD模型自動生成的關鍵步驟。

圖4 建筑物模型的結構特征Fig.4 Structural feature of a building model

2.2 切割環(huán)的識別

根據(jù)切割環(huán)的特性,提出基于切割環(huán)分解的三維建筑物LOD模型的生成方法,該方法的主要步驟如圖5。

圖5 算法流程圖Fig.5 The workflow of algorithm

為實現(xiàn)建筑物模型中切割環(huán)的自動識別,提出一種基于邊的深度優(yōu)先搜索(DFS)方法,為提高搜索效率,采用一種帶方向的半邊數(shù)據(jù)結構[20],切割環(huán)的識別過程是一種遞歸的半邊遍歷過程,主要包括凸凹切割環(huán)和混合凹切割環(huán)的識別。

凸凹切割環(huán)識別:①標記凸凹邊集合中的所有邊為未遍歷;②選取邊集合中的一條未遍歷邊為種子邊,設為e1,標記e1為遍歷標志;③遞歸遍歷e1的未被遍歷的鄰接邊 en,en與e1具有相同的凸凹性,標記 en為遍歷標志;④重復步驟③,記錄找到的封閉環(huán);⑤如果找到的環(huán)滿足切割環(huán)的定義,則該環(huán)為凸凹切割環(huán);⑥轉跳到步驟②,直到所有的凸凹邊均被遍歷。

混合凹切割環(huán)由凹邊和平面邊組成,其識別過程主要分為兩步:找到一條不封閉的凹邊集合;檢測平面邊集合,將不封閉的凹邊集合封閉起來,構成一個切割環(huán)。其中第一步與凸凹切割環(huán)的識別類似,在此不再贅述。在第二步中,如果平面邊集合屬于模型上的邊,則根據(jù)混合凹切割環(huán)的定義很容易判斷,如圖3(d)中的灰色邊;如果平面邊集合不屬于模型上的邊,則需要沿著凹邊集合的延伸方向生成平面邊集合,如圖6。文獻[21]針對CAD模型提出一種基于自然擴展生成平面邊的方法,該方法比較復雜。針對建筑物的結構特征,改進平面邊的生成方法。

設不封閉凹環(huán)集合 l={e1,e2,…,en},若 n> 1,則以l所在的平面作為分割平面對模型進行分割,產(chǎn)生的交線即為平面邊集合。若n=1,設e的兩個鄰面分別為 f1和 f2,如圖6,首先以 f1為分割平面對模型進行分割,設分割體中特征部件的最小外包體積為V1;同理以 f2為分割平面得到特征部件的最小外包體積為V2。如果V1

圖6 平面邊的生成Fig.6 Generation of planar edges

通過以上切割環(huán)的檢測可以識別出三維建筑物模型中的三類切割環(huán),由于不同類型的切割環(huán)可能存在相交的情況,這樣會導致同一個結構模型的多種分割方式,如圖7所示。因此對于相交的切割環(huán),必須舍棄那些導致分割質量不好的切割環(huán),僅保留一個分割質量最好的切割環(huán)。文獻[11]采用分割面上的新面積與舊面積的比值評價分割質量,對于有些模型,如其特征部件的新面積較大而體積很小,這種標準可能不太適合,因此,采用分割體的最小外包體積比值作為分割質量標準進行切割環(huán)的取舍。

式中,VF為特征部件的最小外包體積,VB為主體的最小外包體積。Q的值越小,則分割質量越好,相應的切割環(huán)被認為是越好的切割環(huán),保留最小Q值所對應的切割環(huán)。圖7說明具有相交關系的混合凹切割環(huán)l1和凸切割環(huán) l2所導致的兩種分割方式,其中加性分割用布爾并操作∪表示,減性分割用差操作∩表示,設l1和l2對應的分割質量分別為Q1和Q2,由于Q1>Q2,因此切割環(huán)l1被舍棄,保留切割環(huán)l2。通過切割環(huán)的取舍可以得到用于模型層次分割的切割環(huán)集合L。

圖7 一種結構模型的兩種分割方式Fig.7 Two different partitions of a model

2.3 基于切割環(huán)的建筑物模型層次分割

從建筑物模型中識別出的切割環(huán)即是建筑物主體與部件的分割線。給定建筑物模型M和一條切割環(huán)l,沿著l進行裁剪可以將建筑物模型分割成兩個面殼M1、M2。

根據(jù)切割環(huán)集合L,建筑物模型M能被分割成主體和一系列部件特征,因此,可以用一顆具有二叉結構的CSG樹予以表達。為了使得構建的二叉樹盡量平衡,必須建立切割環(huán)集合L={l1, l2,lopt,…}中各切割環(huán)之間的層次關系,采用分割準則ΔV確定切割環(huán)的層次。假設切割環(huán)集合L中的某條切割環(huán)l將建筑物模型M分割成兩個部分M1、M2,相應的最小外包體積為V1和V2,若ΔV=|V1-V2|=min,則該環(huán)被確定為分割模型M的最優(yōu)切割環(huán),設為lopt,將相應的兩個分割體M1、M2存儲于CSG樹的左右節(jié)點上,同理,對節(jié)點M1、M2進行分割,根據(jù)分割準則可以確定M1、M2的最優(yōu)切割環(huán),設為 l1、l2,由于 M和M1、M2具有層次關系,因此對應的最優(yōu)切割環(huán) lopt和 l1、l2也具有相應的層次關系,依此類推,直到確定所有切割環(huán)的層次關系為止,從而構造出一顆平衡CSG樹。顯然,如下層次分割是一種遞歸的過程。

為方便起見,構造CSG樹時將特征部件存儲為左節(jié)點,主體存儲為右節(jié)點,圖8描述了分割結果的實例。

圖8 模型分割結果的CSG樹Fig.8 Partitioning of a model into a CSG tree

2.4 建筑物LOD模型生成

原始建筑物模型經(jīng)過切割環(huán)的分割后變?yōu)橐活w具有二叉結構的CSG樹,通過對CSG樹的葉節(jié)點進行刪除或簡化,可以生成建筑物的LOD模型。如何選擇需要簡化的部件,即特征部件在給定尺度下如何進行重要性排序成為重要的問題,為此定義每個葉節(jié)點的代價函數(shù)為

式中,V為原始模型M的最小外包體積;Vi為特征部件Mi的最小外包體積。根據(jù)代價函數(shù)計算CSG樹中每個葉節(jié)點的代價,代價開銷最小的葉節(jié)點將優(yōu)先被簡化或刪除。建筑物LOD模型的生成步驟為:①節(jié)點刪除,選擇C值最小的的左孩子葉節(jié)點Mi,將該節(jié)點刪除并作刪除標記,同時對相應的右孩子節(jié)點進行填洞和共面處理,并將結果存儲在左孩子節(jié)點上;②節(jié)點收縮,如果一個節(jié)點的左孩子節(jié)點被標記為刪除,且右孩子節(jié)點為葉子節(jié)點,則這兩個孩子節(jié)點可以收縮成一個父節(jié)點,并將左孩子節(jié)點的內容存儲在父節(jié)點上。

經(jīng)過上面處理后,CSG樹中所有葉子節(jié)點的組合將形成一個有效的LOD,通過設置代價閾值T,可以生成不同層級的LOD模型。圖9說明了節(jié)點M1的簡化過程。

圖9 CSG樹中節(jié)點M1的簡化Fig.9 Simplification of nodeM1in CSG tree

其中,需要說明的兩個操作為:①填洞處理,如果一個面殼節(jié)點的切割環(huán)的所有切邊共面,直接對該環(huán)采用多邊形三角化方法即可,如果所有切邊不在一個平面內,作者采用切割環(huán)在面上的收縮方式來進行填洞[22],首先在面殼中尋找切割環(huán)的鄰接面,然后將這些鄰接面自然向外延伸并相交,即可將空洞填補;②共面處理,填洞處理后,模型中可能存在許多冗余的共面三角形,選擇文獻[10]的方法,指定一個接近于0的閾值 Tc進行處理,Tc通常取1.0×10-4。

3 試驗結果

在Windows XP3平臺下采用C++和Open-GL相結合實現(xiàn)了本文提出的算法,為檢驗該算法在LOD模型生成方面的效果,選取了四組不同的現(xiàn)代建筑物模型進行試驗,表1列出試驗數(shù)據(jù)與試驗條件的基本信息。

表1 試驗數(shù)據(jù)與試驗條件Tab.1 Experimental data and conditions

根據(jù)該算法,通過選取不同的閾值 T,分別對四組試驗數(shù)據(jù)生成了三層LOD模型,并和多分辨率生成算法Qslim在相同的簡化率下進行比較,見圖10～圖13,其中LOD0表示原始模型。圖10中,LOD1模型的三角形數(shù)量為52,LOD2模型的三角形數(shù)量為12;圖11中,LOD1模型的三角形數(shù)量為924,LOD2模型的三角形數(shù)量為404;圖12中,LOD1模型的三角形數(shù)量為1 749, LOD2模型的三角形數(shù)量為270;圖13中,LOD1模型的三角形數(shù)量為2 514,LOD2模型的三角形數(shù)量為540。本文方法所產(chǎn)生的LOD模型較好的保持建筑物模型的整體結構特征,而Qslim方法所產(chǎn)生的LOD1基本上保持建筑物的整體結構特征,但LOD2出現(xiàn)明顯的變形,破壞建筑物的平行、對稱性等特征。

圖10 本文算法和QSlim生成建筑物LOD的比較(data-1)Fig.10 Comparison of LOD models obtained with our algorithm and Qslim(data-1)

圖11 本文算法和QSlim生成建筑物LOD的比較(data-2)Fig.11 Comparison of LOD models obtained with our algorithm and Qslim(data-2)

圖12 本文算法和QSlim生成建筑物LOD的比較(data-3)Fig.12 Comparison of LOD models obtained with our algorithm and Qslim(data-3)

圖13 本文算法和QSlim生成建筑物LOD的比較(data-4)Fig.13 Comparison of LOD models obtained with our algorithm and Qslim(data-4)

由模型生成LOD模型的運行時間見表2,本文算法運行時間在1.0 s左右,具有較高的效率。

表2 本文算法效率評價Tab.2 Algorithm efficiency evaluation s

4 結 論

本文方法通過切割環(huán)識別建筑物模型表面的結構特征,從而實現(xiàn)建筑物模型的分割,進而在保留建筑物整體結構特征的前提下實現(xiàn)建筑物模型的簡化。試驗的結果和與現(xiàn)有的簡化方法的比較表明該方法能夠有效地實現(xiàn)切割環(huán)的識別并對建筑物模型進行分割,從而保證生成的建筑物LOD模型能夠保持其整體的結構特征。該方法只適合于三角網(wǎng)平面片組成的建筑模型,因此,本研究的下一步將重點解決具有自由曲面特征的建筑物模型,并對生成的LOD模型進行定量分析實現(xiàn)LOD模型間的相似性度量。

[1] GLANDER T,DOLLNER J.Abstract Representations for Interactive Visualization of Virtual 3D City Models[J]. Computers,Environment and Urban Systems,2009,33 (5):375-387.

[2] ZHU Qing,HU Mingyuan.Semantics-based LOD Models of 3D House Property[J].Acta Geodaetica et Cartographica Sinica,2008,37(4):514-520.(朱慶,胡明遠.基于語義的多細節(jié)層次3維房產(chǎn)模型[J].測繪學報,2008,37(4): 514-520.)

[3] PONCHIO F,HORMANN K.Interactive Rendering of Dynamic Geometry[J].IEEE Transactions on Visualization and Computer Graphics,2008,14(4):914-925.

[4] YAN G B S,LI Q Q,GONG J Y.A Robust and Rapid Algorithm for Generating and Transmitting Multiresolution Three Dimensional Models[J].Chinese Science Bulletin, 2006,51(8):987-993.

[5] LUEBKE D,REDDY M,COHEN J,et al.Level of Detail for 3D Graphics[M].San Francisco:Morgan Kaufmann, 2003:19-46.

[6] YANGB S,LI Q Q,SHI W Z.Constructing Multiresolution Triangulated Irregular Network Model for Visualization[J].Computers and Geosciences,2005,31(1):77-86.

[7] YANG B S,SHI W Z,LI Q Q.A Dynamic Method for Generating Multiresolution TIN Models[J].Photogrammetric Engineering and Remote Sensing,2005,71(8): 917-927.

[8] PAJAROLA R,GOBBETTI E.Survey of Semi-regular Multiresolution Models for Interactive Terrain Rendering [J].The Visual Computer,2007,23(8):583-605.

[9] KADA M.Scale-dependent Simplification of 3D Building ModelsBased on CellDecomposition and Primitive Instancing[C] ∥ Proceedings of the International Conference on Spatial Information Theory.Melbourne: Springer Verlag,2007:222-237.

[10] GARLAND M,HECKBERT P.Surface Simplification Using Quadric Error Metrics[C]∥SIGGRAPH Proceedings.Los Angeles:Addison Wesley,1997:209-216.

[11] THIEMANN F,SESTER M.Segmentation of Buildings for 3D Generalisation[C]∥Proceedings of ICA Workshop on Generalisation and Multiple Representation.Leicester: [s.n.],2004:1-7.

[12] THIEMANN F,SESTER M.3D-symbolization Using Adaptive Templates[C]∥Proceedings of ISPRS Technical Commission Symposium.Vienna:[s.n.],2006:109-113.

[13] KADA M.3D Building Generalization Based on HalfspaceModeling[C] ∥Proceedingsofthe ISPRS Workshop on Multiple Representation and Interoperability of Spatial Data.Hannover:[s.n.],2006:58-64.

[14] KADA M.Generalization of 3D Building Models for Map-like Presentations[C]∥The International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences:XXXVII.[S.l.]:ISPRS,2008: 399-404.

[15] FORBERG A.Generalization of 3D Building Data Based on a Scale-spaces Approach[J].ISPRS Journal of Photogrammetry and Remote Sensing,2007,62(2):104-111.

[16] DU Z Q,ZHU Q.ZHAO J Q.Perception-driven Simplification Methodology of 3D Complex Building Models[C]∥The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences:XXXVII.[S.l.]:ISPRS,2008:645-651.

[17] JANGJ,WONKA P,RIBARSKY W,et al.Punctuated Simplification ofMan-made Objects[J]. TheVisual Computer,2006,22(2):136-145.

[18] SESTER M.3D Visualization and Generalization[C]∥51st Photogrammetric Week.Stuttgart:[s.n.],2007: 285-295.

[19] RIBELLES J,HECKBERT P S,GARLAND M,et al. Finding and Removing Features from Polyhedra[C]∥Proceedings ASME Design Engineering Technical Conference.Pittsburgh:[s.n.],2001:1-10.

[20] BOTSCH M,PAUL Y M,ROSSL C,et al.Geometric Modeling Based on Triangle Meshes[C]∥Proceedings of ACM SIGGRAPH 2006 Courses.New York:ACM, 2006:26-27.

[21] LU Y,GADH R,TAUTGES T J.Feature Based Hex Meshing Methodology:Feature Recognition and Volume Decomposition[J].Computer-aided Design,2001,33(3): 221-232.

[22] MA L J,HUANG Z D,WU Q S.Extracting Common Design Patterns from a Set of Solid Models[J].Computer-Aided Design,2009,41(12):952-970.

Generating Levels of Detail of 3D Building Models Based on Cutting Loops Decomposition

Y ANGBisheng1,2,J IANG Shaobo1,2
1.State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430079, China;2.Engineering Research Center for Spatio-temporal Data Smart Acquisition and Application,Ministry of Education of China,Wuhan University,Wuhan 430079,China

A cutting loop decomposition approach for generating LOD of 3D building models was proposed.Firstly, the cutting loops of 3D building model were detected according to a dihedral angle operator.Secondly,the building model was decomposed into the main body and a series of feature parts through the cutting loops,which were stored as nodes in a CSG tree.Finally,the nodes in the CSG tree were selectively simplified according to the significance of each node.The experimental results show that the proposed approach is efficient and able to preserve the structural features of the building models.

3D building models;model decomposition;cutting loop;CSG tree;feature identification

Y ANG Bisheng(1974—),male,professor, PhD supervisor,majors in geoinformatics,lidar point clouds understanding and mapping,multi-scale modeling and progressive transmission of spatial data.

1001-1595(2011)05-0575-07

P208

A

教育部新世紀優(yōu)秀人才支持計劃(NCET-07-0643);教育部重點項目(108085);中央高?；究蒲袠I(yè)務費專項資金(3103005)

(責任編輯:宋啟凡)

2010-06-17

2010-10-14

楊必勝(1974—),男,教授,博士生導師,主要從事激光掃描點云解譯與三維重建、空間數(shù)據(jù)的多尺度建模與漸進傳輸方面的研究。

E-mail:bshyang@whu.edu.cn