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

王 飛，李成名

(中國測繪科學研究院，北京 100830)

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

王 飛，李成名

(中國測繪科學研究院，北京 100830)

城市作為人類生活的重要聚集地，是三維GIS應用的主要領域。本文結合房屋的二維輪廓數據與屋頂的基本信息(傾斜角度、屋頂高度、紋理屬性)，以“骨架線提取—房屋模型構建”為框架，提出了一種基于多邊形骨架線自動生成簡單房屋模型的算法，詳細描述了該方法的基本思想，并在試驗結果的基礎上證實了該算法的有效性。

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

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

1 房屋的骨架線提取

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

1.1 多邊形數據的分析

經過多年的發展，二維房屋數據已比較完善，一般以矢量面數據的方式進行存儲。房屋數據大致可以分為兩類：

1.1.1 凸多邊形

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

圖1 凸多邊形

1.1.2 凹多邊形

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

圖2 凹多邊形

1.2 提取多邊形的骨架線

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

圖3 骨架線生成事件

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

凸多邊形，只會觸發邊事件，骨架線算法通過以下幾個步驟生成：

輸入：凸多邊形P的頂點V1，V2，…，Vn(逆時針方向排列)的坐標；

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

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

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

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

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

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

輸入：凸多邊形P的頂點V1，V2，…，Vn(逆時針方向排列)的坐標；

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

(1) 初始化：①循環遍歷多邊形P的頂點，計算多邊形的外凸頂點的角平分線；②計算相鄰凸頂點的角平分線的交點和內凹頂點與相應對邊的交點，并標記交點事件(邊和分割事件)，根據交點到對應的頂點Vi-1和Vi之間的邊Ei的垂直距離LEi的大小，得到距離最近的交點li，并將交點根據距離LEi的大小進行排序存儲到隊列中(如圖5(a)所示)。

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

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

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

骨架線是用與原形狀連通性和拓撲結構相一致的直線段作為理想表達的一種對象表示，多邊形骨架線的本質是對多邊形的抽象描述，即可以描述多邊形輪廓的最切實際的線段連線。根據多邊形骨架線，結合屋頂的傾斜角度、高度和墻高度信息參數，將骨架線進行立體化和三角剖分，生成三維屋頂模型(平屋頂或尖屋頂)，最后進行紋理貼合，生成完整屋頂模型。

2.1 骨架線進行立體化

立體化就是根據房屋輪廓線生成的骨架線，結合屋頂的傾斜角度和限高信息參數，生成屋頂的三維骨架輪廓。此過程可以通過以下步驟：輸入：房屋輪廓線的二維骨架面；輸出：房屋輪廓線的三維骨架面。

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

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

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

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

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

圖6 屋頂高度信息的計算

2.2 骨架線三角剖分

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

借助開源的三角化庫Triangle對骨架面進行三角化，如圖7所示。

圖7 屋頂三角化

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

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

圖8 屋頂紋理貼圖

3 算法實現及評價

3.1 算法實現

本文基于多邊形骨架線的房屋模型生成的基本思想，采用目前主流的C++編程語言和開源OSG圖形渲染引擎，開發了基于房屋模型自動建模系統。該系統通過LOD技術對房屋數據進行可視化，當處于視線范圍之內時，才可以顯示房屋數據。可以將矢量數據存儲在服務器端，并發成服務，在客戶端可以通過該算法，根據矢量數據實時的生成三維模型并將其顯示出來。圖9為根據真實的平面矢量數據生成的三維房屋模型的可視化效果。

圖9 試驗成果示意圖

3.2 算法評價

經過試驗驗證，對該算法進行討論分析，主要有以下幾點：

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

(2) 自動化三維管網建模更加精細化。由于自動化的三維管網全部由計算機計算并生成模型，精度和準確度更高，能夠很好地避免人工建模過程中可能出現的誤差和錯誤。

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

4 結束語

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

[1] 王繼周，李成名，林宗堅. 城市三維數據獲取技術發展探討[J]. 測繪科學，2004，29(4): 71-73.

[2] 朱慶，李德仁，龔健雅，等. 數碼城市GIS的設計與實現[J]. 武漢大學學報(信息科學版)，2001，26(1): 8-11.

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

[4] 陳宇軍. 多邊形坡屋頂屋脊線的遞歸算法[J]. 建筑科學，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] 黃利民，張躍鵬. 利用三角網方法實現面域骨架線的自動生成[J]. 測繪學院學報，2002，19(4): 262-264.

[7] 胡鵬，王海軍，邵春麗，等. 論多邊形中軸問題和算法[J]. 武漢大學學報(信息科學版)，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]. 計算機輔助設計與制造，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].測繪通報，2017(1)：69-73.

10.13474/j.cnki.11-2246.2017.0015.

2016-03-08

測繪地理信息公益性行業科研專項(201412003)；國家科技支撐計劃(2015BAJ06B00)；中國測繪科學研究院基本科研業務費(7771520)

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