王 飛，李成名

(中國(guó)測(cè)繪科學(xué)研究院，北京 100830)

利用多邊形骨架線生成房屋模型算法研究

王 飛，李成名

(中國(guó)測(cè)繪科學(xué)研究院，北京 100830)

城市作為人類生活的重要聚集地，是三維GIS應(yīng)用的主要領(lǐng)域。本文結(jié)合房屋的二維輪廓數(shù)據(jù)與屋頂?shù)幕拘畔?傾斜角度、屋頂高度、紋理屬性)，以“骨架線提取—房屋模型構(gòu)建”為框架，提出了一種基于多邊形骨架線自動(dòng)生成簡(jiǎn)單房屋模型的算法，詳細(xì)描述了該方法的基本思想，并在試驗(yàn)結(jié)果的基礎(chǔ)上證實(shí)了該算法的有效性。

多邊形；骨架線；屋頂模型；可視化

城市作為人們生存和活動(dòng)的重要場(chǎng)所，在人類的社會(huì)、經(jīng)濟(jì)、政治生活中起著至關(guān)重要的作用[1]。近年來，大范圍地形及城市三維建模是可視化領(lǐng)域的一個(gè)研究熱點(diǎn)，方法較多，所生成的模型細(xì)節(jié)層次也不盡相同，大致有如下幾種[2]：根據(jù)DEM重建逼真的地形表面形態(tài)，通過疊加正射影像數(shù)據(jù)生成具有很強(qiáng)真實(shí)感的虛擬場(chǎng)景；使用CAD、3ds Max等建模軟件逼真設(shè)計(jì)模型的精細(xì)結(jié)構(gòu)和材質(zhì)特征，不僅可以表現(xiàn)外觀，還能充分表現(xiàn)實(shí)體的內(nèi)部形態(tài)，可用來進(jìn)行真三維實(shí)體的建模；利用攝影測(cè)量、激光掃描或其他地面測(cè)量手段采集三維數(shù)據(jù)和實(shí)際影像紋理，從而恢復(fù)實(shí)體的三維狀態(tài)；根據(jù)建筑物底部輪廓線(如DLG)和相應(yīng)的高度屬性進(jìn)行三維重建，用于表現(xiàn)較低細(xì)節(jié)水平的城市景觀。然而三維數(shù)據(jù)的生成，不僅消耗大量的人力物力財(cái)力，而且效率不高。三維房屋模型構(gòu)建的難點(diǎn)和關(guān)鍵是三維屋頂模型的構(gòu)建。目前，人工建模仍然是構(gòu)建三維建筑模型的主要技術(shù)，但其構(gòu)建的效率水平很低。針對(duì)這一問題，本文提出一種新的快速構(gòu)建簡(jiǎn)單三維房屋模型的方法。根據(jù)現(xiàn)有的二維矢量房屋數(shù)據(jù)(建筑物底部輪廓線)，結(jié)合建筑物的高度信息、屋頂傾角及屋頂限高信息，運(yùn)用多邊形骨架線生成算法，快速完成簡(jiǎn)單三維房屋模型的構(gòu)建。

1 房屋的骨架線提取

簡(jiǎn)單的建筑屋頂一般分為人字型屋頂和階躍型屋頂兩種[3]。人字形屋頂即坡屋頂，在建筑中應(yīng)用較廣泛，主要分為單坡式、雙坡式、四坡式、折腰式等。本文所涉及的坡屋頂是由建筑的多邊形基底面，按一定傾角向上延伸的斜屋面所構(gòu)成，由于斜屋面在空間上進(jìn)行相交，會(huì)形成多條屋脊線，這些屋脊線互相連接，將各個(gè)斜屋面圍成一個(gè)封閉的多邊形。生成坡屋頂?shù)娜S模型的關(guān)鍵是正確找到屋脊線，即可以描述房屋基底面的骨架線[4-5]。

1.1 多邊形數(shù)據(jù)的分析

經(jīng)過多年的發(fā)展，二維房屋數(shù)據(jù)已比較完善，一般以矢量面數(shù)據(jù)的方式進(jìn)行存儲(chǔ)。房屋數(shù)據(jù)大致可以分為兩類：

1.1.1 凸多邊形

如果把一個(gè)多邊形的所有邊中，任意一條邊向兩方無限延長(zhǎng)成為一直線時(shí)，其他各邊都在此直線的同旁，那么這個(gè)多邊形就叫做凸多邊形，其內(nèi)角應(yīng)該全不是優(yōu)角(如圖1所示)。凸多邊形根據(jù)是否包含多變形(洞)，又可以分為無洞凸多邊形、有洞凸多邊形。

圖1 凸多邊形

1.1.2 凹多邊形

如果把一個(gè)多邊形的所有邊中，有一條邊向兩方無限延長(zhǎng)成為一直線時(shí)，其他各邊不都在此直線的同旁，那么這個(gè)多邊形就叫做凹多邊形，其內(nèi)角中至少有一個(gè)優(yōu)角(如圖2所示)。凹多邊形根據(jù)是否包含多變形(洞)，又可以分為無洞凹多邊形、有洞凹多邊形。

圖2 凹多邊形

1.2 提取多邊形的骨架線

在幾何學(xué)中，骨架線是對(duì)多邊形形狀的抽象描述[6]。骨架線在某些方面與中軸線具有相似的特性[7]，但不同的是：骨架線是由直線段構(gòu)成，而中軸可以由曲線構(gòu)成。Aichholzer等[8]于1995年提出了一種新的簡(jiǎn)單多邊形的內(nèi)部結(jié)構(gòu)的骨架線，是由多邊形的角平分線構(gòu)成的角平分線網(wǎng)絡(luò)。骨架線的形成，可以采用具有固定角度的斜坡的構(gòu)建原理，通過模擬平行切割屋頂獲取屋頂?shù)墓羌芫€。在二維視圖中，骨架線表現(xiàn)在多邊形的邊內(nèi)縮；即多邊形的邊以恒定速度縮小，頂點(diǎn)沿著角平分線以恒定速度內(nèi)移[9-10]。Aichholzer[11]將這種現(xiàn)象描述為兩種事件：①邊事件：不相鄰邊E0和E2進(jìn)行相交，E1邊消失，長(zhǎng)度收縮為零，如圖3(a)所示；②分割事件：相鄰邊E0和E1同時(shí)與對(duì)邊E3相交，將對(duì)邊E3一分為二，即分割整個(gè)多邊形，如圖3(b)所示。分兩步詳述骨架線的生成算法：

圖3 骨架線生成事件

1.2.1 凸多邊形骨架線生成算法

凸多邊形，只會(huì)觸發(fā)邊事件，骨架線算法通過以下幾個(gè)步驟生成：

輸入：凸多邊形P的頂點(diǎn)V1，V2，…，Vn(逆時(shí)針方向排列)的坐標(biāo)；

輸出：凸多邊形P的骨架線。

(1) 初始化：①循環(huán)遍歷多邊形P的頂點(diǎn)，計(jì)算多邊形的每條邊Ei=ViVi+1和每個(gè)頂點(diǎn)Vi應(yīng)的角平分線Bi；②循環(huán)遍歷所有頂點(diǎn)角平分線Bi，判斷其與相鄰的角平分線Bi-1和Bi+1是否相交。如果相交，根據(jù)交點(diǎn)到對(duì)應(yīng)的頂點(diǎn)Vi-1和Vi之間的邊Ei的垂直距離LEi的大小，得到距離最近的交點(diǎn)Ii，并將交點(diǎn)根據(jù)距離LEi的大小進(jìn)行排序存儲(chǔ)到隊(duì)列中(如圖4(a)所示)。

圖4 凸多邊形骨架線生成步驟

(2) 判斷優(yōu)先隊(duì)列是否為空，若不為空進(jìn)行以下步驟(如圖4所示)：①取出隊(duì)列中的第一個(gè)交點(diǎn)I，頂點(diǎn)Vc和Vd的角平分線相交而成；②判斷頂點(diǎn)Vc和Vd是否已處理，如果已處理，則跳過以下步驟，直接繼續(xù)循環(huán)步驟(2)；③判斷頂點(diǎn)Vc的上個(gè)頂點(diǎn)Va的上個(gè)頂點(diǎn)是否與Vd相同，若相同則說明這3個(gè)點(diǎn)形成一個(gè)交點(diǎn)I，輸出3個(gè)骨架線VcI、VdI、VaI，并對(duì)3個(gè)頂點(diǎn)進(jìn)行標(biāo)記處理，跳過以下步驟，直接繼續(xù)循環(huán)步驟(2)；④輸出兩個(gè)骨架線VcI、VdI骨架線，并對(duì)兩個(gè)頂點(diǎn)進(jìn)行標(biāo)記處理；⑤根據(jù)交點(diǎn)I生成新的頂點(diǎn)V，并調(diào)整頂點(diǎn)和邊的前后鏈接關(guān)系。重復(fù)步驟(1)中的②方法。循環(huán)繼續(xù)。

1.2.2 凹多邊形骨架線生成算法

凹多邊形，觸發(fā)邊和分割事件，骨架線算法通過以下幾個(gè)步驟生成：

輸入：凸多邊形P的頂點(diǎn)V1，V2，…，Vn(逆時(shí)針方向排列)的坐標(biāo)；

輸出：凸多邊形P的骨架線。

(1) 初始化：①循環(huán)遍歷多邊形P的頂點(diǎn)，計(jì)算多邊形的外凸頂點(diǎn)的角平分線；②計(jì)算相鄰?fù)鬼旤c(diǎn)的角平分線的交點(diǎn)和內(nèi)凹頂點(diǎn)與相應(yīng)對(duì)邊的交點(diǎn)，并標(biāo)記交點(diǎn)事件(邊和分割事件)，根據(jù)交點(diǎn)到對(duì)應(yīng)的頂點(diǎn)Vi-1和Vi之間的邊Ei的垂直距離LEi的大小，得到距離最近的交點(diǎn)li，并將交點(diǎn)根據(jù)距離LEi的大小進(jìn)行排序存儲(chǔ)到隊(duì)列中(如圖5(a)所示)。

圖5 凹多邊形骨架線生成步驟

(2) 判斷優(yōu)先隊(duì)列是否為空，若不為空進(jìn)行以下步驟(如圖5所示)：①取出隊(duì)列中的第一個(gè)交點(diǎn)I，判斷該交點(diǎn)的事件類型，如果交點(diǎn)I的事件類型為邊事件，執(zhí)行凸多邊形的步驟(2)；否則執(zhí)行以下步驟；②判斷頂點(diǎn)是否已處理，如果已處理則跳過以下步驟，直接繼續(xù)循環(huán)步驟(2)；③輸出骨架線VcI，并且對(duì)該頂點(diǎn)進(jìn)行標(biāo)記處理；④根據(jù)交點(diǎn)I生成新的頂點(diǎn)V，并將隊(duì)列一分為二，調(diào)整頂點(diǎn)和邊的前后鏈接關(guān)系。重復(fù)步驟(1)中的②方法。循環(huán)繼續(xù)。

2 基于骨架線生成屋頂模型

骨架線是用與原形狀連通性和拓?fù)浣Y(jié)構(gòu)相一致的直線段作為理想表達(dá)的一種對(duì)象表示，多邊形骨架線的本質(zhì)是對(duì)多邊形的抽象描述，即可以描述多邊形輪廓的最切實(shí)際的線段連線。根據(jù)多邊形骨架線，結(jié)合屋頂?shù)膬A斜角度、高度和墻高度信息參數(shù)，將骨架線進(jìn)行立體化和三角剖分，生成三維屋頂模型(平屋頂或尖屋頂)，最后進(jìn)行紋理貼合，生成完整屋頂模型。

2.1 骨架線進(jìn)行立體化

立體化就是根據(jù)房屋輪廓線生成的骨架線，結(jié)合屋頂?shù)膬A斜角度和限高信息參數(shù)，生成屋頂?shù)娜S骨架輪廓。此過程可以通過以下步驟：輸入：房屋輪廓線的二維骨架面；輸出：房屋輪廓線的三維骨架面。

(1) 初始化：①循環(huán)遍歷所有骨架線，將骨架線與屋頂輪廓線組成的骨架面，依次存儲(chǔ)到隊(duì)列中。并將所有的骨架點(diǎn)(如圖6(a)Vi所示)標(biāo)記為未處理。以單個(gè)骨架面AV1V2V3E為例進(jìn)行計(jì)算。

(2) 取出骨架面AV1V2V3E中的骨架點(diǎn)Vi，判斷是否為空，若不為空則進(jìn)行以下步驟，否則退出(圖6(b)所示)：①取出骨架點(diǎn)V1，判斷該點(diǎn)是否已處理，若已處理，則直接跳過以下步驟，直接循環(huán)步驟(2)，否則進(jìn)行下一步驟(由于骨架點(diǎn)具有對(duì)稱性，因此可以只計(jì)算一次即可)；② 計(jì)算骨架點(diǎn)V1到屋頂輪廓線AE的垂直距離L1；③根據(jù)上步驟的垂直距離L1，結(jié)合屋頂傾角信息，計(jì)算骨架點(diǎn)V1到輪廓面的垂直距離H1，即骨架點(diǎn)V1的高度Z1值，并將該骨架點(diǎn)V1標(biāo)記為已處理。

(3) 取出骨架面AV1V2V3E中的骨架點(diǎn)V1，判斷是否為空，若不為空則進(jìn)行以下步驟，否則退出：①取出骨架面AV1V2V3E中的骨架線AV1，判斷屋頂限高Z值是否在骨架線高度值范圍內(nèi)。若不在范圍內(nèi)，說明該骨架線沒有削平點(diǎn)，直接循環(huán)步驟(3)；否則有削平點(diǎn)Xi，判斷是否第一次出現(xiàn)削平點(diǎn)。如果是第一次，則記下該削平點(diǎn)，否則生成閉合削平頂X1V1V2X2(如圖6(c)所示)。②判斷是否取出所有骨架面，如果沒有，則循環(huán)步驟①；否則，生成閉合的削平的骨架面AV1V2V3E(如圖6(c)所示)。

(4) 如果沒有削平點(diǎn)，生成的三維骨架面如圖6(a)所示；否則，生成的三維骨架面如圖6(d)所示。

(5) 最后根據(jù)屋頂輪廓線和墻的高度信息，進(jìn)行屋頂抬高處理(如圖6(e)、6(f)所示)。

圖6 屋頂高度信息的計(jì)算

2.2 骨架線三角剖分

由于采用了OpenGL圖形編程接口，因此必須從幾何圖元的點(diǎn)、線和多邊形開始構(gòu)造三維模型。構(gòu)造三維立體時(shí)，從共面性能考慮，特別推薦使用三角形。它具有建模、變換、光線處理、色彩處理、動(dòng)畫，以及其他更先進(jìn)的高級(jí)圖形處理能力，如紋理映射、物體運(yùn)動(dòng)模糊效果等，可以制作真實(shí)感強(qiáng)烈的三維立體圖形[12]。因此，筆者選擇三角形作為幾何圖元，即將多邊形進(jìn)行三角化。

借助開源的三角化庫Triangle對(duì)骨架面進(jìn)行三角化，如圖7所示。

圖7 屋頂三角化

2.3 屋頂模型生成與紋理貼圖

在三維圖形中，物體的外觀不僅僅包括形狀，不同物體的表面有著不同的顏色和圖案。紋理貼圖是一種能大幅度提高三維圖像真實(shí)性的三維圖像處理技術(shù)，使用這項(xiàng)技術(shù)可以減少紋理銜接錯(cuò)誤；實(shí)時(shí)生成剖析截面顯示圖；有更真實(shí)的霧、煙、火和動(dòng)畫效果；提高變換視角看物真實(shí)性；模擬移動(dòng)光源產(chǎn)生的自然光影效果。因此，一個(gè)簡(jiǎn)單有效的、提高物體的真實(shí)感的方法就是紋理貼圖，如圖8所示。

圖8 屋頂紋理貼圖

3 算法實(shí)現(xiàn)及評(píng)價(jià)

3.1 算法實(shí)現(xiàn)

本文基于多邊形骨架線的房屋模型生成的基本思想，采用目前主流的C++編程語言和開源OSG圖形渲染引擎，開發(fā)了基于房屋模型自動(dòng)建模系統(tǒng)。該系統(tǒng)通過LOD技術(shù)對(duì)房屋數(shù)據(jù)進(jìn)行可視化，當(dāng)處于視線范圍之內(nèi)時(shí)，才可以顯示房屋數(shù)據(jù)?？梢詫⑹噶繑?shù)據(jù)存儲(chǔ)在服務(wù)器端，并發(fā)成服務(wù)，在客戶端可以通過該算法，根據(jù)矢量數(shù)據(jù)實(shí)時(shí)的生成三維模型并將其顯示出來。圖9為根據(jù)真實(shí)的平面矢量數(shù)據(jù)生成的三維房屋模型的可視化效果。

圖9 試驗(yàn)成果示意圖

3.2 算法評(píng)價(jià)

經(jīng)過試驗(yàn)驗(yàn)證，對(duì)該算法進(jìn)行討論分析，主要有以下幾點(diǎn)：

(1) 算法占用了很少的計(jì)算機(jī)資源。在程序運(yùn)行過程中，程序只需要很短的運(yùn)行時(shí)間就可以進(jìn)行大規(guī)模房屋模型的生成。如試驗(yàn)中一張包含500多個(gè)房屋面的SHP數(shù)據(jù)，只需幾秒的時(shí)間就可以自動(dòng)生成三維房屋模型；而人工進(jìn)行建模，可能是幾天的工作量，因此節(jié)約了大量的時(shí)間和成本。

(2) 自動(dòng)化三維管網(wǎng)建模更加精細(xì)化。由于自動(dòng)化的三維管網(wǎng)全部由計(jì)算機(jī)計(jì)算并生成模型，精度和準(zhǔn)確度更高，能夠很好地避免人工建模過程中可能出現(xiàn)的誤差和錯(cuò)誤。

(3) 便于三維功能分析。在自動(dòng)化生成的房屋模型場(chǎng)景中能夠很容易地進(jìn)行三維功能分析，如通視分析、距離量測(cè)分析等。

4 結(jié)束語

本文通過試驗(yàn)，初步形成了以二維房屋多邊形數(shù)據(jù)為數(shù)據(jù)源，結(jié)合房屋的傾斜角度、限高等信息，自動(dòng)構(gòu)建三維房屋模型的可行性方案。該方案計(jì)算量小，速度快，三維模型生產(chǎn)效率高，能靈活地解決帶洞或不帶洞的凸凹多邊形房屋建模問題。但是從實(shí)用化角度方面，仍然需要進(jìn)一步改善，包括對(duì)二維矢量數(shù)據(jù)的房屋屬性字段標(biāo)準(zhǔn)的規(guī)范制定，以及圓形房屋的建模問題，最終才能建立更貼近真實(shí)效果、更實(shí)用的房屋簡(jiǎn)單三維模型構(gòu)建系統(tǒng)。

[1] 王繼周，李成名，林宗堅(jiān). 城市三維數(shù)據(jù)獲取技術(shù)發(fā)展探討[J]. 測(cè)繪科學(xué)，2004，29(4): 71-73.

[2] 朱慶，李德仁，龔健雅，等. 數(shù)碼城市GIS的設(shè)計(jì)與實(shí)現(xiàn)[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2001，26(1): 8-11.

[3] 程亮，李滿春，龔健雅，等. LiDAR數(shù)據(jù)與正射影像結(jié)合的三維屋頂模型重建方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2013，38(2): 208-211.

[4] 陳宇軍. 多邊形坡屋頂屋脊線的遞歸算法[J]. 建筑科學(xué)，2007(1): 86-89.

[5] LAYCOCK R G，DAY A M. Automatically Generating Roof Models from Building Footprints[C]∥The 11th International Conference in Central Europe on Computer Graphics，Visualization and Computer Vision.Plzen: UNION Agency-Science Press，2003: 81-84.

[6] 黃利民，張躍鵬. 利用三角網(wǎng)方法實(shí)現(xiàn)面域骨架線的自動(dòng)生成[J]. 測(cè)繪學(xué)院學(xué)報(bào)，2002，19(4): 262-264.

[7] 胡鵬，王海軍，邵春麗，等. 論多邊形中軸問題和算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2005，30(10): 853-857.

[8] AICHHOLZER O，ALBERTS D，AURENHAMMER F，et al. Straight Skeletons of Simple Polygons[C]∥Proceeding of 4th International Symposum of LIESMARS.Wuhan:[s.n.]，1995: 114-124.

[9] CACCIOLA F. A CGAL Implementation of the Straight Skeleton of a Simple 2D Polygon with Holes[C]∥2nd CGAL User Workshop.[S.l.]:CGAL，2004.

[10] AICHHOLZER O，AURENHAMMER F. Straight Skeletons for General Polygonal Figures in the Plane[C]∥Proceedings of the Second Annual International Conference on Computing and Combinatorics.[S.l.]：Springer-Verlag，1996: 117-126.

[11] AND P F，OBDRZALEK S. Straight Skeleton Implementation[C]∥ Proceedings of the Spring Conference on Computer Graphics.Budmerice：[s.n.]，2001:210-218.

[12] 陳緒兵，夏華，肖躍加，等. 三維原型的OpenGL真彩光照方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與制造，2002(3): 53-55.

ResearchonAlgorithmsforSolvingRoofModelbyUsingStraightSkeletonofPolygon

WANG Fei，LI Chengming

(Chinese Academy of Surveying and Mapping, Beijing 100830, China)

City, as an important place of human life, is the main field of 3D GIS application. A method to automatically generate the roof model based on straight skeleton of polygon is presented, with skeleton line extraction-housing model as the framework, based on 2D contour data of housing and the basic information of the roof (angle, roof height, texture attributes). At last the basic idea of the method is described and the effectiveness of the algorithm is verified by experimental results.

polygon; straight skeleton; roof model; visualization

P208

A

0494-0911(2017)01-0069-05

王飛，李成名.利用多邊形骨架線生成房屋模型算法研究[J].測(cè)繪通報(bào)，2017(1)：69-73.

10.13474/j.cnki.11-2246.2017.0015.

2016-03-08

測(cè)繪地理信息公益性行業(yè)科研專項(xiàng)(201412003)；國(guó)家科技支撐計(jì)劃(2015BAJ06B00)；中國(guó)測(cè)繪科學(xué)研究院基本科研業(yè)務(wù)費(fèi)(7771520)

王 飛(1987—)，男，碩士生，主要從事三維地理信息系統(tǒng)研究。E-mail: wangfei-921@163.com