一種用于三維城市建筑物的可視域分析算法

靳海亮，李留磊，袁松鶴，耿文軒

(河南理工大學測繪與國土信息工程學院，河南 焦作 454000)

可視性分析包括通視分析和可視域分析，作為三維GIS的一種重要的空間分析方法，在城市規(guī)劃[1]、選址[2]、軍事[3]和考古等方面有著廣泛的應(yīng)用。通常情況下可視性分析是基于數(shù)字高程模型的，產(chǎn)生了很多基于規(guī)格格網(wǎng)地形數(shù)據(jù)和不規(guī)則格網(wǎng)地形數(shù)據(jù)的通視分析算法[4-6]，并基于此進行地形的可視域分析?；诔鞘薪ǔ蓞^(qū)數(shù)據(jù)的可視性分析從20世紀70年代開始，Benedikt-[7-8]等借助于計算機圖形學技術(shù)進行城市建成區(qū)的可視性分析研究，但也只是在二維方面適用，并沒有擴展到三維空間。

隨著三維城市GIS的發(fā)展，基于地形數(shù)據(jù)和城市建筑三維模型數(shù)據(jù)的通視分析和可視域算法也得到了廣泛的研究。尹長林[9]等采用平行投影、點和多邊形關(guān)系的計算方法確定視線和建筑物的通視情況，然后基于通視分析進行可視域分析，可視域分析的精度受到采樣視線多少的影響。王明孝[3]等則利用數(shù)字高程模型數(shù)據(jù)疊加建筑物高度信息生成城市建筑物模型，然后基于此進行可視性分析，可視域計算方法需要根據(jù)通視分析進行。Yang[10]等提出可視球的概念，實質(zhì)上是在視點所在平面上以一定間隔生成采樣視線，再在其垂直方向上按照同樣采樣間隔旋轉(zhuǎn)得到更多采樣視線，以進行可視性分析。韓俊[11]綜合考慮地形數(shù)據(jù)和建筑物模型數(shù)據(jù)，采用了基于圖形處理器(graphics processing unit，GPU)加速的深度緩存可視分析算法，算法的實現(xiàn)效率較高但需要依賴于硬件且實現(xiàn)過程較復雜。Suleiman[12]等基于視點構(gòu)造單位球體，計算地形及建筑物模型的多邊形面片在單位球體上的投影，取各個方向上投影中距離視點最近的多邊形面片區(qū)域作為可視區(qū)域。Pyysalo[13]等采用體素的方法來表達城市建筑物并疊加在地形數(shù)據(jù)上進行通視分析和可視域分析，將地形和建筑物數(shù)據(jù)作為一個整體，無法只針對建筑物進行可視域分析，進行可視域分析時也必須基于通視分析進行，可視域分析的精度依賴于采樣視線的數(shù)量。Suleiman[14]等假設(shè)地形和建筑物模型由一系列的三角面片構(gòu)成，建筑物和地形用不同的ID進行標識，建筑物模型可以被單獨列出但是在進行可視域分析時還需要根據(jù)通視分析進行實現(xiàn)，同樣也無法根據(jù)建筑物的特點進行可視域的分析。周永望[15]等通過擴展二維空間句法，對三維城市的通視性進行計算，并不能進行某一點的可視域的計算。

上述研究多是將地形數(shù)據(jù)和建筑模型數(shù)據(jù)作為整體考慮進行可視性分析，并沒有根據(jù)建筑物模型數(shù)據(jù)和地形數(shù)據(jù)的差別分別討論各自的可視性分析方法，而且即使單獨考慮建筑物的可視性分析，其通視性分析的方法也是基于地形數(shù)據(jù)的通視性分析的計算方法，忽略了建筑物模型數(shù)據(jù)的特點，計算出來的可視域精度也就需要依賴采樣視線的數(shù)量。

在城市環(huán)境中，地形一般起伏不大，因此本文不考慮城市地形數(shù)據(jù)對可視域分析的影響，針對城市建筑物模型進行可視域分析算法的研究。

1 城市建筑物模型的創(chuàng)建

本文只考慮城市建筑物對視點的可視域影響，因此只需對城市建筑物進行模型的創(chuàng)建，保證得到的建筑物模型相互之間是獨立的，每個建筑物模型由一系列的三角面片構(gòu)成。

2 基于通視分析的城市建筑物可視域算法原理

假設(shè)建筑物模型是由一系列的三角形面片構(gòu)成的，而且每個建筑物模型可通過其ID進行識別。下面對基于通視分析的城市建筑物可視域算法的實現(xiàn)原理進行解釋：

(1) 取建筑物模型集合中n個建筑物模型中的一個，得到所有構(gòu)成該模型的三角形面片，設(shè)三角形面片總數(shù)為k。

(2) 設(shè)置視點，取該模型的一個三角面片的中點作為目標點和視點構(gòu)成一線段，計算該線段所在的直線。

(3) 計算直線和建筑物集合中每個模型的三角面片所在面的交點，判斷該交點是否同時在該線段上和三角形內(nèi)，若在則說明相交，否則不相交。取距離視點最近的交點，若該交點不是目標點則說明不可視，否則可視。重復以上步驟，即可得到該視點的可視域。

根據(jù)以上原理可知其時間復雜度為O(n×k×n×k)，其中n為建筑物模型的數(shù)量，k為構(gòu)成建筑物模型的三角形面片平均數(shù)，一般情況下k要遠大于n。

3 算法的設(shè)計與實現(xiàn)

3.1 算法實現(xiàn)所需的具體數(shù)據(jù)結(jié)構(gòu)

Struct ColladaCoponent

{

String ccID;∥模型的名稱

List triangleMesh;∥模型的三角網(wǎng)

Vector3 midVector;∥模型的中心點

List floorCorners;∥模型最小矩形包圍盒的底部輪廓角點

List ceilingCorners;∥模型最小矩形包圍盒的頂部輪廓角點

List visibleCorners;∥某視點下的錐體底面角點

List visibleWallCorners;∥模型底部輪廓可視角點

Bool isOrthoModel;∥標記該模型是否為單面可視模型

Float disTovPerm;∥記錄模型中心點到視點的距離}

3.2 算法的主要步驟

(1) 根據(jù)構(gòu)成建筑物模型的三角面片的每個點坐標計算模型的最小矩形包圍盒、包圍盒的底部輪廓點(逆時針排序)、包圍盒的中心點坐標和建筑物高度。

(2) 設(shè)置視點及視點的視距，計算視點和每個建筑物模型的最小矩形包圍盒中心點的距離，判斷該距離和視距的大小關(guān)系確定在視距范圍內(nèi)的建筑物模型。

(3) 根據(jù)每個模型的包圍盒角點和視點，計算矩形包圍盒的可視角點，連接視點和可視角點生成錐體，錐體的棱代表視線的方向，錐體的棱的交點為視點。如圖1(a)所示。

(4) 為了簡化計算過程，同時保證得到的可視面一定可視，當視點高度大于建筑物模型高度時，認為該建筑物模型的頂部可視。

(5) 步驟(4)中已經(jīng)討論頂面可視的判斷條件，因此只需考慮側(cè)面的可視性。從圖1(a)可知建筑物模型的可視面有一面或多面，生成的錐體的底面多邊形將會比較復雜，為了簡化計算過程，需減少錐體棱的數(shù)量。根據(jù)模型包圍盒的底部輪廓點，選擇和視點在水平面上的投影成最大夾角的兩點作為錐體底面上的點。若此兩點構(gòu)成的邊為建筑物模型底部輪廓邊，則標記該模型為單面可視模型，作為錐體底面點，否則標記該模型為多面可視模型，同樣作為錐體底面點，并將在兩點之間的底部輪廓角點加載至模型底部輪廓可視角點集合。根據(jù)以上得到的兩點，取其在垂直方向上的包圍盒角點作為錐體底面上的另外兩點，四點逆時針排列構(gòu)成錐體的底面，如圖1(b)所示。根據(jù)以上過程，生成每個模型的錐體底面。

圖1 模型錐體示意圖

(6) 取視距范圍內(nèi)的一模型作為當前模型，根據(jù)步驟(2)中模型距離視點的距離，得到小于當前模型距離視點距離的模型作為待投影模型，計算視點和當前模型中點構(gòu)成的射線和待投影模型的中點和視點構(gòu)成的射線之間的夾角，若小于90°則計算待投影錐體底面在當前模型錐體底面所在平面上的投影區(qū)，計算投影區(qū)和當前模型錐體底面多邊形的差集，計算結(jié)果按逆時針排序。遍歷建筑物集合中的模型，重復以上過程，若差集不為空則說明當前模型的錐體多邊形存在可視域，若為空則說明當前模型的錐體底面多邊形不存在可視區(qū)域，計算效果如圖2(a)，該效果圖中的模型均為單面可視模型，可直接根據(jù)差集坐標集合進行可視化。

圖2 不同投影情況下的可視域?qū)崿F(xiàn)效果

(7) 根據(jù)步驟(6)，取錐體底面存在可視區(qū)域即差集不為空的模型，若該模型為多面可視模型，將差集中的點投影到水平面上得到投影線段和視點構(gòu)成三角形，計算該三角形的非投影邊和模型底部輪廓可視角點集合中的點依次構(gòu)成的線段的交點，剔除不在兩交點之間的模型底部輪廓可視角點，將交點和兩交點之間的底部輪廓可視角點逆時針排列。差集中的點構(gòu)成的多邊形是不規(guī)則的，每個點的Z值也不一樣，為簡化計算取差集中點坐標的最小最大Z值，作為可視區(qū)域在垂直方向上的邊界。根據(jù)差集中的點坐標的XY值和最小最大Z值，按照逆時針方向從模型底部到模型頂部生成可視墻面對應(yīng)的區(qū)域邊界點坐標，可視域計算效果如圖2(b)所示圖中點v為視點，線段a為視線，abcd圍成的區(qū)域為可視區(qū)域。遍歷建筑物集合，重復以上計算過程，得到所有模型的可視墻面區(qū)域邊界點坐標，最后進行可視化。

3.3 算法復雜度分析

首先假設(shè)建筑物模型集合中共有n個建筑物模型，每個建筑物模型包含3k個點。計算每個建筑物模型的最小矩形包圍盒，其時間復雜度為On×3k。計算n個建筑物模型的錐體的復雜度為rOn，r為每個建筑物模型的底部輪廓點的數(shù)量，r為常數(shù)4。計算錐體之間的投影，最壞情況為n個建筑物模型正好相互遮擋，時間復雜度為On×(n-1)/2，計算投影承載面上多邊形之間的差集。因此本算法的時間復雜度為On×3k，與基于通視分析的城市建筑物可視域計算方法的時間復雜度相比有了較大的提高。

3.4 試驗驗證

算法實現(xiàn)基于三維可視化平臺EV-Globe，其提供的EV-Globe SDK包含了可視化控件GlobeWindow和讀取DAE格式模型數(shù)據(jù)的類ColladaModel。本文通過SketchUp軟件生成DAE格式的建筑物模型。在型號HP g4、i3系列CPU、內(nèi)存2 GB的筆記本上，利用Visual Studio2010集成開發(fā)環(huán)境中，基于C#語言和EV-Globe SDK實現(xiàn)基于通視分析的城市建筑物可視域算法和本文算法，效果分別如圖3(a)和圖3(b)所示，圖中點v為視點，abcd圍成的建筑物表面區(qū)域為可視區(qū)域。二者耗時對比見表1。

表1 基于通視分析的可視域算法和本文算法耗時對比

圖3 可視域?qū)崿F(xiàn)效果

4 結(jié) 語

本文考慮建筑物模型相對規(guī)則的特點，計算得到每個建筑物的最小矩形包圍盒，基于視點和最小矩形包圍盒得到包圍盒的可視角點，再根據(jù)視點和可視角點得到錐體，計算模型錐體在另一模型錐體底面所在面上的投影區(qū)，計算投影區(qū)和錐體底面多邊形的差集，從而得到每個模型的可視面，使建筑物模型的可視域計算不再需要通過計算模型三角面片上的每個點的通視性得到，既簡化了計算過程，提高了計算效率，也保證了可視域計算效果的正確性。

[1] 李德仁，趙中元，趙萍.城市規(guī)劃三維決策支持系統(tǒng)設(shè)計與實現(xiàn)[J].武漢大學學報(信息科學版),2011,36(5)：505-509.

[2] 眭海剛，朱慶，龔健雅.基于DEM及GIS的最佳位置的自動確定[J].武漢測繪科技大學學報,1998,24(2)：138-141.

[3] 王明孝，王晶杰.基于城市建筑物的戰(zhàn)場環(huán)境可視分析[J].地理空間信息,2012,10(1)：57-60.

[4] 應(yīng)申，李霖，梅洋，等.增量法地形可視計算與分析[J].測繪學報,2007,36(2)：192-197.

[5] 王晨昊，湯曉安，馬伯寧，等.基于距離場映射的地形可視域分析方法[J].測繪學報,2011,40(5)：563-568.

[6] 張立朝，趙鵬，張合朝.地形分析中柵格中間層構(gòu)建的尺度適應(yīng)性[J].測繪通報,2017(1)：130-133.

[7] BENEDIKT M L. To Take Hold of Space: Isovists and Isovistfields[J].Environment and PlanningB: Planning and Design,1979,6: 47-65.

[8] TURNER A, DOXA M, O’SULLIVAN D, et al.From Iso-vists to Visibility Graphs: A Methodology for the Analysis of Architectural Space[J].Envrionment and PlanningB:Planning and Design,2001,28:103-121.

[9] 尹長林，許文強.基于3DGIS的城市規(guī)劃可視性分析模型研究[J].測繪科學,2011,36(4)：142-144.

[10] YANG P PJ, PUTRA S Y, LI W. Viewsphere: a GIS-Based3D Visibility Analysis for Urban Design Evaluation[J].Environment and PlanningB: Planning and Design,2007,34: 971-992.

[11] 韓俊.基于三維仿真的空間可視分析研究與實現(xiàn)[D].鄭州：信息工程大學,2011.

[12] SULEIMAN W, JOLIVEAU T, FAVIER E. A New Algorithm for 3D Isovists[C]∥Advances in Spatial Data Handling.[S.l.]：Springer Berlin Heidelberg, 2013:464-474.

[13] PYYSALO U, OKSANEN J, SARJAKOSKI T.Viewshed Analysis and Visualization of Landscape Voxel Models[C]∥Proceedings of the 24th International Cartographic Conference. Santiago Chile：[s.n.],2009.

[14] SULEIMAN W, JOLIVEAU T, FAVIER E. 3D Urban Visibility Analysis with Vector GIS Data[C]∥GISRUK，2011(1)：12.

[15] 周永望，田朝前，李敏.基于三維空間句法的城市空間通視性分析[J].計算機工程與應(yīng)用, 2014,50(1)：240-244.