王 淳,于長(zhǎng)華,唐 昊,李海峰

(中國(guó)工程物理研究院計(jì)算機(jī)應(yīng)用研究所，四川 綿陽(yáng) 621999)

1 引言

數(shù)字城市是指以計(jì)算機(jī)技術(shù)、多媒體技術(shù)和大規(guī)模存儲(chǔ)技術(shù)為基礎(chǔ)，以寬帶網(wǎng)絡(luò)為紐帶，運(yùn)用遙感、GPS、GIS、遙測(cè)、仿真-虛擬等技術(shù)，對(duì)城市進(jìn)行多分辨率、多尺度、多時(shí)空和多種類的三維描述[1]。隨著智慧城市建設(shè)的開展，數(shù)字城市模型在城市規(guī)劃與管理、環(huán)境模擬、應(yīng)急響應(yīng)、導(dǎo)航、虛擬旅游以及其他科學(xué)和大眾應(yīng)用方面的需求越來越高[2]，是提升城市競(jìng)爭(zhēng)力、解決城市發(fā)展問題的重要支撐。

作為貫穿整個(gè)智慧城市建設(shè)的重要技術(shù)，數(shù)字城市建模是計(jì)算機(jī)視覺、計(jì)算機(jī)圖形學(xué)、遙感測(cè)量等領(lǐng)域的熱點(diǎn)問題，獲得國(guó)內(nèi)外研究者的大量關(guān)注[3]。從數(shù)據(jù)源來說，使用的數(shù)據(jù)包括從地面、航空和航天平臺(tái)獲取的影像和激光點(diǎn)云數(shù)據(jù)、眾源地理數(shù)據(jù)、數(shù)字高程等。從建模方法來說，目前主流方法有多視圖三維重建、基于激光點(diǎn)云的三維重建、基于矢量數(shù)據(jù)建模和多源數(shù)據(jù)融合建模等。從發(fā)展趨勢(shì)來看，大規(guī)模數(shù)字城市建模正在朝自動(dòng)化、精細(xì)化、語義化、集成化、標(biāo)準(zhǔn)化和開放共享等方向發(fā)展，在建模成本不斷降低的同時(shí)增強(qiáng)建模效率和模型可重用性[4]。

本文關(guān)注的是數(shù)字城市可計(jì)算模型，即可用于進(jìn)行數(shù)值模擬計(jì)算的數(shù)字城市模型。城市可計(jì)算模型擴(kuò)展了數(shù)字城市的應(yīng)用領(lǐng)域，使城市模型可用于自然災(zāi)害、戰(zhàn)爭(zhēng)破壞效應(yīng)研究和環(huán)境模擬研究[5 - 7]，在解決重大領(lǐng)域問題、提高管理和決策的科學(xué)性和高效性等方面發(fā)揮著重大作用。

Figure 1 Diagram of city modeling using OpenStreetMap data圖1 基于OpenStreetMap矢量數(shù)據(jù)的城市建模流程

為了給數(shù)值模擬軟件提供大規(guī)模城市的可計(jì)算模型，不僅需要具有面向大空間尺度、海量數(shù)據(jù)、頻繁更新的城市的快速建模能力，還需要使模型滿足特定的可計(jì)算條件，如不允許存在實(shí)體相交、懸邊、懸面、非閉合體、二次曲面等，且對(duì)不影響計(jì)算結(jié)果的細(xì)小特征進(jìn)行化簡(jiǎn)。但是，由于數(shù)據(jù)采集過程中存在的誤差，以及模型處理所做的必要的簡(jiǎn)化操作，導(dǎo)致直接生成的數(shù)字城市模型中存在大量非閉合、相接、相交、懸空等CAD模型缺陷[8,9]，使得城市模型不可用于數(shù)值模擬。由于城市模型的數(shù)據(jù)量巨大，不可能通過人工方式修復(fù)有缺陷的幾何體。即使使用商用CAD軟件的修復(fù)功能，圖形的布爾運(yùn)算仍需要耗費(fèi)大量時(shí)間，無法滿足快速構(gòu)建大規(guī)模城市可計(jì)算模型的需要。

本文以矢量數(shù)據(jù)建模技術(shù)為基礎(chǔ)，提出一種包含建筑和地形的LoD1城市模型[10]的快速構(gòu)建方法，重點(diǎn)研究建模數(shù)據(jù)的可計(jì)算處理。通過分析LoD1城市模型中所包含的CAD模型缺陷，本文給出了幾何圖形需滿足的可計(jì)算條件以及處理方法。這種在幾何圖形上進(jìn)行可計(jì)算處理的方式避免了人工操作和CAD布爾運(yùn)算，使得本文方法在建模效率、模型規(guī)模和可計(jì)算性等方面均能滿足高性能計(jì)算的要求。

2 城市可計(jì)算建模流程

本文采用OpenStreetMap[11]矢量數(shù)據(jù)作為構(gòu)建數(shù)字城市模型的數(shù)據(jù)源。OpenStreetMap是一個(gè)開源地理信息項(xiàng)目，通過標(biāo)簽和屬性值提供結(jié)構(gòu)化的地圖描述，在路徑規(guī)劃、地圖導(dǎo)航、智能交通等領(lǐng)域都得到廣泛應(yīng)用。目前，已有若干基于OpenStreetMap構(gòu)建或?yàn)g覽三維模型的軟件，如blender-osm[12]、OSM2World[13]和OSMBuildings[14]等。

基于OpenStreetMap建立三維模型的一般流程參見文獻(xiàn)[15]。本文的目標(biāo)是可計(jì)算建模，需要處理原始數(shù)據(jù)中的非閉合、相接、相交、懸空等CAD模型缺陷，因此在一般流程的基礎(chǔ)上還要加入“可計(jì)算處理”步驟。因此，本文采用的基于OpenStreetMap矢量數(shù)據(jù)構(gòu)建城市模型的流程包含4個(gè)步驟(如圖1所示)：數(shù)據(jù)讀取、數(shù)據(jù)解析、可計(jì)算處理和模型輸出。每個(gè)步驟的具體內(nèi)容如下所示：

(1)數(shù)據(jù)讀取。讀取原始數(shù)據(jù)，即從OpenStreetMap數(shù)據(jù)中讀取基本元素，從高程數(shù)據(jù)中讀取頂點(diǎn)坐標(biāo)。

(2)數(shù)據(jù)解析。將原始數(shù)據(jù)轉(zhuǎn)化為可用于建模的城市單元體數(shù)據(jù)，包括解析建筑數(shù)據(jù)(含輪廓、高度、組合方式及其它屬性)和地形三角網(wǎng)。

(3)可計(jì)算處理。消除城市單元體中的CAD模型缺陷，使其能夠用于生成可計(jì)算城市模型。即消除建筑與建筑、建筑與地形之間的重疊、縫隙、曲率突變等幾何錯(cuò)誤和細(xì)小特征，滿足數(shù)值模擬的要求。

(4)模型輸出。將各類城市單元體合并，形成城市模型，并通過圖形引擎輸出。

在上述各個(gè)步驟中，數(shù)據(jù)讀取、數(shù)據(jù)解析和模型輸出與一般的建模軟件相同。因此，本文重點(diǎn)研究的內(nèi)容是可計(jì)算處理。

3 城市模型CAD模型缺陷分析

本文構(gòu)建的是LoD1城市模型(如圖2a所示)[10]，包含從OpenStreetMap數(shù)據(jù)中提取的建筑模型和從高程數(shù)據(jù)中提取的地形模型。建筑模型只包含地面輪廓和高度，高程地形由三角面片組成。LoD1城市模型是對(duì)真實(shí)城市的高度簡(jiǎn)化和抽象，既具有結(jié)構(gòu)簡(jiǎn)單的優(yōu)點(diǎn)，又能反映真實(shí)城市的幾何特性，適合于大多數(shù)在大規(guī)模數(shù)字城市上計(jì)算的數(shù)值模擬程序。

Figure 2 Model structure圖2 模型結(jié)構(gòu)

由于數(shù)據(jù)采集過程中存在的誤差，以及模型處理所做的必要的簡(jiǎn)化操作，生成的數(shù)字城市模型很可能存在CAD模型缺陷[8]。直接修復(fù)CAD模型缺陷的過程非常復(fù)雜和耗時(shí)，但考慮到LoD1城市模型(如圖2a所示)的結(jié)構(gòu)遠(yuǎn)比CAD模型(如圖2b所示)的幾何結(jié)構(gòu)簡(jiǎn)單，如果在LoD1城市模型上進(jìn)行可計(jì)算處理，將極大簡(jiǎn)化處理過程。這是由于:(1)LoD1城市模型只涉及一部分CAD模型缺陷；(2)對(duì)LoD1城市模型的可計(jì)算處理可轉(zhuǎn)化為對(duì)二維圖形的處理，將大大降低處理難度?；谝陨纤枷?，本文首先在LoD1城市模型所對(duì)應(yīng)的二維圖形上進(jìn)行可計(jì)算處理，然后將其轉(zhuǎn)化成CAD模型，就可保證大規(guī)模城市模型的可計(jì)算性和建模效率。

本節(jié)提出對(duì)LoD1城市模型進(jìn)行可計(jì)算處理的解決方案。首先，給出CAD模型缺陷的分類和分析(3.1節(jié))；然后，研究LoD1城市模型中存在的CAD模型缺陷及其應(yīng)對(duì)措施(3.2節(jié))；最后，給出使模型避免CAD模型缺陷、滿足可計(jì)算條件的技術(shù)路線(3.3節(jié))。

3.1 CAD模型缺陷分類

CAD模型的表達(dá)采用的是拓?fù)浜蛶缀畏蛛x的思想。幾何數(shù)據(jù)描述空間實(shí)體的位置，拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)描述空間實(shí)體間的連接關(guān)系。在這種分離的設(shè)計(jì)方式中，其幾何數(shù)據(jù)與拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)相對(duì)獨(dú)立實(shí)現(xiàn)，然后通過關(guān)聯(lián)操作建立它們之間的聯(lián)系。

根據(jù)CAD模型拓?fù)浜蛶缀蔚奶攸c(diǎn)，可以把CAD模型缺陷分為拓?fù)浔磉_(dá)缺陷和幾何表達(dá)缺陷，如圖3所示。其中拓?fù)浔磉_(dá)缺陷可以進(jìn)一步分為非正則拓?fù)淙毕荨⑼負(fù)洚悩?gòu)缺陷和拓?fù)渚热毕?，幾何表達(dá)缺陷可進(jìn)一步分為幾何異構(gòu)缺陷、幾何精度缺陷和幾何潛在錯(cuò)誤表達(dá)。詳細(xì)的CAD模型缺陷分類及處理方法參見文獻(xiàn)[8]。CAD模型缺陷嚴(yán)重破壞了幾何模型的完整性和精確性，會(huì)導(dǎo)致數(shù)值模擬計(jì)算失敗。

Figure 3 Categories of CAD model deficiencies圖3 CAD模型缺陷分類

3.2 LoD1城市模型CAD模型缺陷分析

由于LoD1城市模型的特殊結(jié)構(gòu)，它所對(duì)應(yīng)的CAD模型只會(huì)涉及CAD模型缺陷的部分類型。對(duì)各類CAD模型缺陷在LoD1城市模型中的表現(xiàn)分析如下：

(1)非正則拓?fù)淙毕?。CAD系統(tǒng)中模型可以是描述物理模型的正則形體，也可以是在現(xiàn)實(shí)世界不存在的非正則形體。當(dāng) CAD 系統(tǒng)是非正則形體時(shí)，一部分拓?fù)淙毕菀脖话谀Ｐ椭?。典型的非正則拓?fù)淙毕萦袘颐?、懸邊和孤立的點(diǎn)。在LoD1城市模型中，如果建筑地面輪廓不是簡(jiǎn)單閉合的多邊形，由其拉伸而成的建筑模型會(huì)產(chǎn)生非正則拓?fù)淙毕?。另一種情況是建筑輪廓相交，此時(shí)頂點(diǎn)或邊的拓?fù)溥B接關(guān)系會(huì)發(fā)生錯(cuò)誤。

(2)拓?fù)洚悩?gòu)缺陷。拓?fù)洚悩?gòu)是指CAD模型中的模型拓?fù)潢P(guān)系在計(jì)算機(jī)中的描述方法不同，因此在文件轉(zhuǎn)換時(shí)，會(huì)出現(xiàn)拓?fù)洳幌嗳莸葐栴}。本文的城市模型是基于圖形引擎直接生成的，不涉及多個(gè)CAD系統(tǒng)間的轉(zhuǎn)換，因此避免了拓?fù)洚悩?gòu)缺陷。

(3)拓?fù)渚热毕?。拓?fù)渚热毕菔怯上到y(tǒng)精度問題造成的拓?fù)浔磉_(dá)不一致，如曲面之間的裂縫或重疊、邊與邊的裂縫以及邊與頂點(diǎn)的裂縫。對(duì)LoD1城市模型來說，當(dāng)多個(gè)建筑模型相接，或當(dāng)建筑模型與地形模型之間存在重疊或裂縫時(shí)，會(huì)產(chǎn)生拓?fù)渚热毕荨?/p>

(4)幾何異構(gòu)缺陷。幾何異構(gòu)是指異構(gòu)CAD系統(tǒng)中描述模型實(shí)體的數(shù)學(xué)定義不同，主要發(fā)生在復(fù)雜曲線曲面(如NURBS曲線曲面)上?，F(xiàn)有的建筑模型和地形模型只包含平面，因此避免了二次曲面帶來的幾何異構(gòu)缺陷。

(5)幾何精度缺陷。幾何精度缺陷是由系統(tǒng)精度問題造成的幾何表達(dá)不一致，主要是針對(duì)曲面和曲線而言。在LoD1城市模型中不存在這種情況。

(6)幾何潛在錯(cuò)誤。幾何潛在錯(cuò)誤主要由角度、尺寸、鄰近和曲率4類情況產(chǎn)生的。大部分的潛在錯(cuò)誤都是拓?fù)湔_，并能產(chǎn)生合法的實(shí)體模型，因此本文不對(duì)幾何潛在錯(cuò)誤進(jìn)行特別的處理。但是，為了減少數(shù)值模擬的計(jì)算量，需要消除模型中不影響計(jì)算結(jié)果的細(xì)小幾何特征，這也會(huì)消除絕大部分幾何潛在錯(cuò)誤。

3.3 可計(jì)算處理技術(shù)路線

根據(jù)2.2節(jié)對(duì)CAD模型缺陷的分類和分析，可歸納出LoD1城市模型需滿足的可計(jì)算條件：

(1)建筑底面輪廓為簡(jiǎn)單多邊形，即頂點(diǎn)數(shù)大于或等于3且不存在自相交。

(2)建筑輪廓之間不存在相交。

(3)建筑輪廓之間不存在幾何精度造成的相接。

(4)建筑模型底部與地形貼合，即既無裂縫也不重疊。

本文采用以下4類方法使城市模型滿足可計(jì)算條件(如表1所示)：

Table 1 Analysis on CAD model deficiencies in LoD1 city model

(1)輪廓簡(jiǎn)化。由于原始建筑輪廓含有大量冗余點(diǎn)，對(duì)輪廓進(jìn)行簡(jiǎn)化不僅可以減少冗余，還可以消除絕大部分幾何潛在錯(cuò)誤。

(2)輪廓收縮。建筑輪廓相交或相接是由數(shù)據(jù)采集誤差造成的，將相交建筑的輪廓收縮一小段距離，就可以避免絕大多數(shù)相交或相接。

(3)地形貼合。將建筑向地形三角網(wǎng)投影，計(jì)算海拔高度，保證建筑各頂點(diǎn)的海拔高度一致，可避免建筑與地形之間的重疊或裂縫。

(4)刪除。如果用以上方法仍不能滿足可計(jì)算條件，直接將建筑刪除，不對(duì)其建模。

基于以上分析，完整的城市模型可計(jì)算處理包括輪廓簡(jiǎn)化、自相交檢測(cè)、相交檢測(cè)、相接檢測(cè)、地形貼合、高度檢查、輪廓收縮等步驟?？捎?jì)算處理流程如圖4所示。

Figure 4 Computable processing pipeline in this paper圖4 本文采用的可計(jì)算處理流程

4 城市模型可計(jì)算處理

本節(jié)給出圖4所示的可計(jì)算處理流程中各個(gè)步驟的具體算法。

4.1 建筑輪廓自相交檢測(cè)

Figure 5 Counter-clockwise polygon with self-intersection圖5 逆時(shí)針走向多邊形自相交

假設(shè)多邊形頂點(diǎn)數(shù)是n，判斷自相交將計(jì)算n條直線方程和n次直線相交，然后計(jì)算n個(gè)交點(diǎn)是否在多邊形內(nèi)部。由于判斷點(diǎn)在多邊形內(nèi)部的算法復(fù)雜度是O(n)，該算法復(fù)雜度為O(n2)。

4.2 建筑輪廓簡(jiǎn)化

建筑輪廓簡(jiǎn)化是指對(duì)給定的建筑輪廓，在減少建筑輪廓頂點(diǎn)數(shù)量的情況下，使簡(jiǎn)化后的建筑輪廓與原建筑輪廓盡量保持形狀一致。因?yàn)榻ㄖ喞挥幸环N拓?fù)漕愋停员疚膹哪繕?biāo)邊2條鄰邊的位置關(guān)系(平行、非平行)來考慮建筑輪廓簡(jiǎn)化問題。2種位置關(guān)系的簡(jiǎn)化如圖6a和圖6b所示，設(shè)簡(jiǎn)化容差為Ts,當(dāng)Sn的長(zhǎng)度小于Ts時(shí)，將Sn設(shè)置為待處理邊。圖中加粗的邊為新增加的邊，虛線邊為待刪除的邊，文獻(xiàn)[17]詳細(xì)介紹了2種位置關(guān)系的簡(jiǎn)化方法。

Figure 6 Contour simplification method圖6 輪廓簡(jiǎn)化方法

基于以上方法可實(shí)現(xiàn)建筑輪廓簡(jiǎn)化，在保證建筑模型在外觀特征不失真的情況下，減少三維建筑物模型的細(xì)節(jié)特征和面片數(shù)，以適應(yīng)不同復(fù)雜度要求的數(shù)字城市可計(jì)算模型。

4.3 建筑輪廓相交檢測(cè)

如圖7所示，2個(gè)簡(jiǎn)單多邊形A和B的關(guān)系可分為6種情況：不相交、相接、疊加、包含、內(nèi)部和相等[18]。對(duì)于可計(jì)算模型的建筑輪廓來說，只允許圖7a和圖7d所示的2種情況：

Figure 7 Spatial relations between polygons圖7 多邊形空間關(guān)系示意

(1)2棟建筑的底面輪廓不相交。此時(shí)只需判斷A的所有邊都在B的外部。當(dāng)且僅當(dāng)A的所有頂點(diǎn)都在B的外部，且A的每條邊與B都不相交時(shí)，此情況成立。

(2)建筑底面輪廓包含空洞，即建筑的底面輪廓A包含空洞B。此時(shí)只需判斷B的所有邊都在A的內(nèi)部。當(dāng)且僅當(dāng)B的每個(gè)頂點(diǎn)都在A的內(nèi)部，且B的每條邊都與A不相交時(shí)，此情況成立。

判斷多邊形關(guān)系的算法復(fù)雜度是O(n2)。

4.4 建筑輪廓相接檢測(cè)

在CAD系統(tǒng)中，實(shí)體間的拓?fù)湎噜応P(guān)系經(jīng)常出現(xiàn)誤差精度導(dǎo)致的問題。CAD系統(tǒng)判斷一個(gè)點(diǎn)是否位于一條直線上并不是由計(jì)算的絕對(duì)結(jié)果來決定，而是通過判斷該點(diǎn)到直線的距離是否小于系統(tǒng)偏差。如果在系統(tǒng)允許的偏差范圍內(nèi)，則可以表示該點(diǎn)在曲線上，反之說明該點(diǎn)在曲線外。大多數(shù)商業(yè)CAD系統(tǒng)中使用的最小偏差大約為10-4甚至10-3。

Figure 8 Joint polygons caused by geometric precision圖8 幾何精度造成的相接

為了檢測(cè)相接的建筑輪廓，需要計(jì)算一個(gè)多邊形的所有頂點(diǎn)到另一個(gè)多邊形所有邊的最短距離。如果頂點(diǎn)不在邊上但最短距離小于偏差(如圖8所示)，為避免拓?fù)渚热毕菪枧卸橄嘟?。相接檢測(cè)的算法復(fù)雜度與相交檢測(cè)相同，都是O(n2)。

4.5 建筑輪廓收縮

為避免城市建筑與相鄰建筑碰撞，可將建筑輪廓收縮指定的距離(即安全緩沖距離)，即從建筑輪廓頂點(diǎn)沿角平分線方向向建筑輪廓內(nèi)部平移一定的距離。

如圖9所示，多邊形的相鄰2條邊L1和L2，v1和v2分別是L1和L2的單位向量，2條邊在交點(diǎn)Pi處作平行于L1和L2、平行線間距為L(zhǎng)且位于多邊形內(nèi)部的2條邊，交于Qi。Qi的計(jì)算公式如下所示：

其中,sinθ=v1×v2。對(duì)建筑輪廓的n個(gè)頂點(diǎn)進(jìn)行收縮，算法的復(fù)雜度為O(n)。

Figure 9 Computation of compressed vertex圖9 內(nèi)縮點(diǎn)計(jì)算

4.6 建筑與地形貼合

實(shí)現(xiàn)建筑與地形貼合的關(guān)鍵在于計(jì)算建筑所在的地表海拔高度，即從建筑頂點(diǎn)發(fā)出垂直射線向地形三角網(wǎng)投影，并計(jì)算投影點(diǎn)所在的三角面片。

通過射線與三角網(wǎng)求交計(jì)算建筑所在地表的海拔高度的方法如下所示。將射線R定義為一個(gè)基點(diǎn)P和一個(gè)方向d，其參數(shù)方程是：

R(t)=P+td

假設(shè)三角形Q的頂點(diǎn)序列為{V0,V1,V2}，對(duì)于三角形內(nèi)的任意一點(diǎn)，它的位置可通過三角形頂點(diǎn)定義，其參數(shù)方程如下：

Q(a,b,c)=aV0+bV1+cV2

其中，a+b+c=1。計(jì)算射線R與三角面片Q的交點(diǎn)只需將上述2個(gè)方程聯(lián)立，經(jīng)整理為：

這是一個(gè)由3個(gè)未知量組成的線性方程。求解t,b,c的值，如果0≤b≤1，0≤c≤1且b+c≤1，則交點(diǎn)位于三角形內(nèi)。通過以上算法完成所有三角網(wǎng)面片求交測(cè)試，得到射線與三角網(wǎng)的交點(diǎn)。

如果建筑通過了高度檢查，即建筑輪廓所有頂點(diǎn)的海拔高度一致且頂點(diǎn)在合法坐標(biāo)范圍內(nèi)，則將投影點(diǎn)所在的三角面片的高度作為建筑海拔高度。

5 大規(guī)模圖形快速檢索

對(duì)于大規(guī)模城市模型來說，可計(jì)算處理的計(jì)算復(fù)雜度成為影響算法性能的關(guān)鍵問題。假設(shè)建筑數(shù)量為M，建筑頂點(diǎn)數(shù)量為N，地形三角面片數(shù)量為D，則對(duì)所有建筑計(jì)算相接或相交關(guān)系的復(fù)雜度為O(M2N2)，為所有建筑計(jì)算海拔高度的復(fù)雜度為O(MND)。大規(guī)模城市中通常建筑和地形三角面片的數(shù)量大約在105～106量級(jí)，如此規(guī)模的計(jì)算量實(shí)際上是無法執(zhí)行的。為了解決建模效率的問題，本節(jié)提出大規(guī)模圖形快速檢索算法，以提高圖形檢索和處理的效率，降低可計(jì)算處理的復(fù)雜度。

5.1 鄰近建筑輪廓快速檢測(cè)

在對(duì)建筑模型的可計(jì)算處理中，建筑地面輪廓的相交和相接檢測(cè)占用了大量時(shí)間。為此本文提出基于最大包圍盒的鄰近建筑輪廓快速檢測(cè)算法。通過快速提取與每棟建筑鄰近的建筑，減少相交檢測(cè)次數(shù)。

如圖10所示，黑點(diǎn)代表城市區(qū)域內(nèi)建筑位置。首先計(jì)算所有建筑的包圍盒，記所有包圍盒的最大長(zhǎng)度和寬度為(lmax,wmax)。假設(shè)當(dāng)前計(jì)算的建筑(五角星所示)的包圍盒長(zhǎng)和寬為(l,w)，則x方向上只有與該建筑包圍盒中心距離小于(l+lmax)/2的建筑可能與其相交(垂直帶狀灰色區(qū)域所示)。同理，y方向上與該建筑包圍盒中心距離小于(w+wmax)/2的建筑可能與其相交(水平帶狀灰色區(qū)域所示)。因此，相交的建筑一定在x和y方向上同時(shí)滿足包圍盒中心距離要求，即落在灰色陰影區(qū)域。該區(qū)域內(nèi)的建筑數(shù)量與城市建筑總量無關(guān)，取決于城市建筑的最大密度和最大包圍盒范圍，可以認(rèn)為是一個(gè)常數(shù)。因此，一棟建筑只需要與常數(shù)個(gè)其它建筑作相交檢測(cè)，就可得到與其相交的所有建筑。這樣可將建筑相接和檢測(cè)算法的復(fù)雜度降至O(MN2)。

Figure 10 Fast detection of neighboring building contours圖10 鄰近建筑輪廓快速檢測(cè)

5.2 射線與三角網(wǎng)快速求交

由于城市模型中包含大量的建筑頂點(diǎn)和地形三角面片，而普通的求交涉及大量冗余的射線和三角面片，計(jì)算量過高，為此本文提出基于層次化包圍盒的快速求交算法。

本文將整個(gè)三角網(wǎng)區(qū)域進(jìn)行層次化分解，待計(jì)算出最小的包圍盒后，再對(duì)其內(nèi)部的三角網(wǎng)面片進(jìn)行求交測(cè)試。該算法剔除了包圍盒外部的面片，因此大大減少了求交測(cè)試的次數(shù)。具體算法步驟如下所示：

(1) 將三角網(wǎng)投影到xy平面上，構(gòu)建所有三角網(wǎng)的二維矩形包圍盒。

(2) 在矩形包圍盒的基礎(chǔ)上，按x和y2個(gè)方向?qū)⑵浞指畛?個(gè)子矩形。

(3) 若某一子區(qū)域的三角形數(shù)量大于給定的閾值m，則返回(2)，將該子矩形進(jìn)一步剖分成4個(gè)更小的矩形。直到每個(gè)矩形區(qū)域里的三角面片數(shù)都小于m(如圖11所示)。

Figure 11 Recursive splitting to quadtree圖11 四叉樹遞歸分割

(4) 對(duì)于劃分的每個(gè)子矩形，計(jì)算其包含的三角網(wǎng)的三維長(zhǎng)方體包圍盒，并組成包圍盒樹。

(5) 當(dāng)計(jì)算射線與三角網(wǎng)交點(diǎn)時(shí)，首先從上至下計(jì)算射線與包圍盒樹的每個(gè)節(jié)點(diǎn)的交點(diǎn)。如果射線與包圍盒不相交，則剔除包圍盒內(nèi)的所有三角面片，由此得到最小的包圍盒區(qū)域，再將射線與區(qū)域塊內(nèi)的三角面片求交。

這樣構(gòu)造的層次化包圍盒樹的層數(shù)為O(logD)。此時(shí)計(jì)算一條射線與三角網(wǎng)的交點(diǎn)需要從頂向下計(jì)算射線與包圍盒樹的相交次數(shù)是O(logD)，計(jì)算所有建筑頂點(diǎn)海拔高度的復(fù)雜度降為O(MNlogD)。

對(duì)絕大多數(shù)建筑來說，其所有頂點(diǎn)都位于相同的地形三角面片內(nèi)。因此，可采用啟發(fā)式算法進(jìn)一步降低復(fù)雜度。在獲取與第1個(gè)建筑頂點(diǎn)相交的三角面片后，其它建筑頂點(diǎn)首先直接與該三角面片求交，如果不相交再與地形包圍盒樹求交。這將使絕大多數(shù)建筑頂點(diǎn)求交的復(fù)雜度降為O(1)，理想情況下所有建筑頂點(diǎn)海拔高度的復(fù)雜度為O(MlogD)。

6 實(shí)驗(yàn)

本文在服務(wù)器單個(gè)結(jié)點(diǎn)上構(gòu)建可計(jì)算模型。每個(gè)結(jié)點(diǎn)包括144核，主頻為2.3 GHz。對(duì)可計(jì)算處理的關(guān)鍵步驟(如建筑輪廓求交、簡(jiǎn)化、地形貼合)采用OpenMP并行。

6.1 模型可計(jì)算性驗(yàn)證

為了驗(yàn)證模型的可計(jì)算性，本文選擇2 000 m×2 000 m范圍的某城市區(qū)域，在同一區(qū)域構(gòu)建了4個(gè)經(jīng)過可計(jì)算處理(選擇不同的簡(jiǎn)化邊長(zhǎng)度參數(shù)，Ts=0 m,4 m,8 m,12 m)的城市模型。本文設(shè)計(jì)了運(yùn)輸炸藥車輛在城市街道發(fā)生意外突然爆炸的計(jì)算場(chǎng)景，利用自主研制程序，模擬計(jì)算了2 000 kg炸藥在5 m高度爆炸后沖擊波傳輸過程及其對(duì)城市建筑物的毀傷效應(yīng)。在后處理中，選取同一時(shí)刻，利用超壓峰值探查計(jì)算處理結(jié)果，如圖12所示?？梢钥闯觯谙嗤挠?jì)算條件下，4個(gè)城市模型的計(jì)算結(jié)果差別非常小，說明在不同參數(shù)下的可計(jì)算處理基本不影響計(jì)算結(jié)果。經(jīng)過檢驗(yàn)，本文構(gòu)建的城市模型不存在CAD模型缺陷，模型可計(jì)算性滿足數(shù)值模擬的要求。

Figure 12 Comparison of computation results on different simplified models圖12 在不同簡(jiǎn)化模型上的計(jì)算結(jié)果比較

6.2 大規(guī)模場(chǎng)景建模

以構(gòu)建紐約城市模型為例，本文選取了710 km2的場(chǎng)景區(qū)域。該場(chǎng)景包含陸地、海面和山地，建筑數(shù)量約30萬棟。構(gòu)建的可計(jì)算模型含217萬面片，建模時(shí)間約25 min。該實(shí)驗(yàn)表明，經(jīng)過快速可計(jì)算處理，基于原始矢量數(shù)據(jù)構(gòu)建的城市模型在準(zhǔn)確性、效率、模型規(guī)模等方面均能滿足大規(guī)模城市場(chǎng)景數(shù)值模擬的需求。

本文構(gòu)建的模型不僅可以用于數(shù)值模擬計(jì)算，還可用于虛擬展示。圖13顯示了采用OpenSceneGraph圖形引擎對(duì)可計(jì)算處理之后的城市模型進(jìn)行構(gòu)建，并且在數(shù)字地球模塊OSGEarth中的渲染效果。

Figure 13 Displaying city model with OpenSceneGraph圖13 用OpenSceneGraph展示城市模型

6.3 輪廓簡(jiǎn)化對(duì)模型的影響

為了統(tǒng)計(jì)輪廓簡(jiǎn)化算法在建模中的作用，本文選擇了一組簡(jiǎn)化邊長(zhǎng)度參數(shù)Ts=1 m,2 m,4 m,6 m，其效果如圖14所示。

Figure 14 Effect of building contour simplification圖14 建筑輪廓簡(jiǎn)化效果

本文對(duì)紐約城市模型開展輪廓簡(jiǎn)化實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示。

Table 2 Statistics on the effect of contour simplification

隨著簡(jiǎn)化邊長(zhǎng)度參數(shù)Ts的增大，建筑頂點(diǎn)數(shù)最多降低33.5%。實(shí)驗(yàn)表明，輪廓簡(jiǎn)化消除了細(xì)小幾何特征，避免了絕大部分幾何潛在錯(cuò)誤，使城市模型更適合于數(shù)值模擬。

6.4 輪廓收縮對(duì)模型的影響

原始數(shù)據(jù)中存在大量建筑相交或相接，而簡(jiǎn)單地刪除這些建筑會(huì)造成模型失真。因此,本文對(duì)相交和相接的建筑采用輪廓收縮，在消除模型非正則缺陷的同時(shí)盡量減少刪除的建筑數(shù)量，以保持處理前后模型的一致性。

為了顯示輪廓簡(jiǎn)化算法在建模中的作用，本文選擇平行線間距L=0.2，從6個(gè)城市中選擇了不同尺寸的區(qū)域，統(tǒng)計(jì)輪廓收縮前后的建筑相交次數(shù)，結(jié)果如表3所示?？梢钥吹?，在OpenStreetMap原始數(shù)據(jù)中，相交建筑的數(shù)量占建筑總數(shù)的比例很大(最多占71%)，而采用輪廓收縮后相交次數(shù)大幅降低，最多下降95%。

Table 3 Effect of contour shrinkage

6.5 模型規(guī)模對(duì)建模時(shí)間的影響

為了統(tǒng)計(jì)模型規(guī)模對(duì)建模時(shí)間的影響，本文從6個(gè)城市中選擇了不同尺寸的區(qū)域進(jìn)行建模，對(duì)模型規(guī)模、建筑數(shù)量和建模時(shí)間進(jìn)行統(tǒng)計(jì)，如表4所示。由于建模分為數(shù)據(jù)讀取、數(shù)據(jù)解析、可計(jì)算處理和模型構(gòu)建4個(gè)階段，建模時(shí)間是這4個(gè)階段的總時(shí)間?？梢钥吹?，隨著模型面片數(shù)和建筑數(shù)量的增加，各個(gè)階段的執(zhí)行時(shí)間都基本滿足線性增長(zhǎng)，其中模型構(gòu)建時(shí)間增長(zhǎng)最快，而數(shù)據(jù)讀取、解析、可計(jì)算處理占用的時(shí)間相對(duì)較短。因此，本文的建模效率主要受限于圖形引擎的性能，不會(huì)隨著模型規(guī)模的增大而急劇增加。圖15顯示了隨著面片數(shù)和建筑數(shù)量的增加，建模時(shí)間增長(zhǎng)的速度。

Figure 15 Relation between modeling time and model scale圖15 建模時(shí)間與模型規(guī)模關(guān)系

7 結(jié)束語

本文提出了大規(guī)模城市可計(jì)算模型的快速構(gòu)建方法。通過分析LoD1城市模型中的CAD模型缺陷，本文確定了需要滿足的可計(jì)算條件。在可計(jì)算處理中，本文方法消除了建筑與建筑、建筑與地形之間的相交、相接和裂縫，避免了城市模型的CAD模型缺陷。本文還針對(duì)大規(guī)模場(chǎng)景提出了圖形快速檢索算法，避免了計(jì)算量的快速增長(zhǎng)。實(shí)驗(yàn)表明，構(gòu)建710 km2、30余萬棟建筑、217萬面片的可計(jì)算模型約需要25 min，模型滿足可計(jì)算條件。本文方法計(jì)算效率高、可靠性強(qiáng)，滿足了大規(guī)模城市數(shù)值模擬的要求。

Table 4 Statistics on modeling time

未來的城市可計(jì)算建模可在以下方向開展深入研究：(1)增加城市單體的類型，如對(duì)道路、水域、植被等建模，使城市內(nèi)容更加豐富；(2)提升模型復(fù)雜度，構(gòu)建LoD2或LoD3的城市可計(jì)算模型；(3)改進(jìn)模型的可計(jì)算性，如進(jìn)一步消除模型中的潛在幾何錯(cuò)誤，降低數(shù)值模擬計(jì)算的復(fù)雜度。