復(fù)雜地形條件下虛擬城市街道生成方法

薛 峰， 邢東順， 曹詩蔚

(合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽合肥 230009)

虛擬城鎮(zhèn)的快速、自動建模方法是國內(nèi)外虛擬現(xiàn)實領(lǐng)域的研究熱門課題之一。文獻[1，2]提出了基于分裂語法的建筑模型智能生成方法，并將其利用到毀于史前的古羅馬城市——“龐培”的建模;文獻[3]提出了一種基于語義的建模方法，使得用戶的操作更簡單;文獻[4]在文獻[3]的基礎(chǔ)上提出了基于本體的古建筑智能建模方法，使得基于語義的建模更加合理。

目前，虛擬城市中的道路、街道生成算法主要有2種，其中一種是基于航拍遙感圖像重建已有的道路、街道，在GPS導(dǎo)航系統(tǒng)中使用的地圖大都是由航測圖片、遙感圖片或紙質(zhì)地圖等經(jīng)過掃描后再矢量化而成。文獻[5]提出了一種生成多邊形道路網(wǎng)絡(luò)拓撲結(jié)構(gòu)的有效算法，基本思想是先對多邊形道路網(wǎng)絡(luò)進行三角剖分，然后生成其中軸線，提高了道路準確度。為進一步提高道路精確度，文獻[6]提出一種道路拓撲生成算法，利用約束Delaunay三角化、骨架化的方法從電子地圖中提取道路。另一種是基于規(guī)則的街道自動生成方法，此類方法被廣泛地應(yīng)用于虛擬城市建模、大型游戲場景中的道路自動生成[7]。文獻[8，9]提出了一種基于擴展L系統(tǒng)(Ex tended L-system)的城市街道自動生成方法。

但是，上述文獻對于虛擬街道、道路的研究大部分都是基于簡單、平坦的地形條件下，缺少在復(fù)雜地形(高程起伏、河流等)約束條件下的道路創(chuàng)建規(guī)則，導(dǎo)致最終生成的城市場景不夠豐富、缺少變化。為此，筆者在徽派建筑體自動建模研究的基礎(chǔ)上[10]，提出一種復(fù)雜地形(高程起伏、河流約束等)約束條件下的街道生成算法，并在生成的街道模型中“填入”建筑物模型，實現(xiàn)復(fù)雜地形的虛擬城鎮(zhèn)場景的自動建模。

1 基于L系統(tǒng)的平面地形街道生成

1.1 本文方法流程

復(fù)雜地形下的街道自動生成方法基本步驟如下:①定義相應(yīng)的公理和重寫規(guī)則，采用L系統(tǒng)的重寫規(guī)則實現(xiàn)平面地形的街道生成;②通過高程映射的方法將平面地形的街道映射到起伏地形的三角網(wǎng)格中，生成起伏地面的街道;③加入對河流的識別，并對L系統(tǒng)的幾何解釋規(guī)則進行修正，使得創(chuàng)建的道路能夠與河流合理搭配。此外，本文還向生成的街道中“填充”具有皖南特色的徽派建筑模型，實現(xiàn)了大規(guī)模徽派建筑場景的建模，以說明本文街道生成方法的有效性。

1.2 L系統(tǒng)簡介

L系統(tǒng)本質(zhì)上是一個并行重寫系統(tǒng)，其核心概念是重寫(rew riting)。重寫的基本思想是根據(jù)預(yù)先定義的規(guī)則集(產(chǎn)生規(guī)則)不斷替換初始參數(shù)以形成更為復(fù)雜的、有規(guī)律的表示。L系統(tǒng)在形式化時一般采用字符串表示:令V表示字母，V*表示V上的所有單詞的集合，一個L系統(tǒng)是一個有序的三元組，即

其中，W是一個非空單詞，也是起始符號元，稱為公理;P是產(chǎn)生式規(guī)則即重寫規(guī)則。L系統(tǒng)的重寫過程如下:由一個初始公理字符串W開始，用一個重寫規(guī)則P逐次置換W的各個字符，不斷遞歸生成新的字符串。如假設(shè)L系統(tǒng)由變量〈F〉、常量〈+、-〉、重寫規(guī)則集〈F→F+F-F-F+F〉和起始字符串符組成。其中，F(xiàn)表示先前走;常量+、-分別表示向右轉(zhuǎn)90°、向左轉(zhuǎn)90°。

第1次重寫:G1=F+F-F-F+F;

第2次重寫:G2=F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F;

第3次重寫:G3=F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-FF+F+F+F-F-F+F+F+F-F-F+F+F+F-F-F+F。

圖1所示從左至右分別為上述3次重寫得到的字符串經(jīng)過幾何解釋后得到的圖形。從中可以看出，通過核實的幾何解釋由L系統(tǒng)重寫規(guī)則得到的字符串，可以得到一系列有規(guī)律性的幾何圖形，這些幾何圖形可以模擬植物軀干、枝葉[11]和街道的生成[7]等。

圖1 3次重寫過程中直線變化結(jié)果

1.3 基于L系統(tǒng)的平面地形街道生成

城市街道建模是由普通道路、十字路口及丁字路口組成。普通道路建?？筛鶕?jù)道路的相關(guān)參數(shù)，生成一個條帶狀矩形平面。其中參數(shù)主要包括:道路起始點、道路長寬和與水平軸夾角等。十字路的建模相對比較復(fù)雜，概括來說是由普通道路、十字路口和拐角區(qū)域組成。

本文介紹基于L系統(tǒng)的街道、道路實現(xiàn)方法。假設(shè)生成平面地形街道的L系統(tǒng)的變量有F、S、Q、Z和T。其中，“F”代表普通道路;“S”代表十字路口(十字路口對面節(jié)點為下次創(chuàng)建道路的起點);“T”代表產(chǎn)生十字路;“Q”代表與水平軸夾角為+90°的道路;“Z”代表與水平軸夾角為-90°的道路。常量有W、R、+、-、4和0。其中，“W”代表記錄或恢復(fù)道路的起點;“R”代表十字路口(十字口中左、右兩邊道路其中一條道路的終點為下次創(chuàng)建道路的起點);“+”代表與水平軸的夾角為+90°或者是選擇十字路左邊道路為下次道路的起點;“-”代表與水平軸的夾角為-90°或者是選擇十字路右邊道路為下次創(chuàng)建道路的起點。此外，為了避免道路過于規(guī)整、呆板，本文引入另外2個常量字符“4”和“0”，其中，“4”代表e與水平軸的夾角為+45°;“0”表示取消下一個字符的意義。

起始字符為:

F+FFF4FFFQZT4FFF4FSTST。

重寫規(guī)則:T=+W+R+F+F+S-W+W-R-F-F-S-S-F-S-W+WSTTTTT;

Q=+W+F+F+F+F+F+F+F+F+FF-W;

Z=+W-F-F-F-F-F-F-F-FFF-W。

道路的聯(lián)通性通過道路的終點傳遞給下條路的起點。十字路口的終點傳遞問題比較復(fù)雜，因為每個十字路口都有3個分支，通過在函數(shù)中添加一個參數(shù)，用來決定哪個分支的終點為下條路的起始點。筆者在L系統(tǒng)中分別用S、+R和-R表示十字路口對面分支、左分支和右分支，從而解決道路連接問題。此外，通過分別創(chuàng)建十字路的幾個分支來解決道路的重疊問題，如重寫規(guī)則中的T=+W+R+F+F+S-W+W-RF-F-S-S-F-S-W+WSTTTTT。其中，+W+R+F+F+S-W是創(chuàng)建的十字路口左分支道路;+W是記錄分支的起始位置，以便在該位置創(chuàng)建另一條分支;+W-R-F-F-SS-F-S-W是創(chuàng)建的十字路口右分支道路，實驗結(jié)果如圖2所示。

圖2 基于L系統(tǒng)的平面地形道路生成效果圖

2 復(fù)雜地形的街道生成方法

復(fù)雜地形的街道生成是指在普通平面地形的基礎(chǔ)上，考慮高程起伏、河流等約束條件下的街道自動生成。方法基本思想:首先通過L系統(tǒng)實現(xiàn)平面地形上的道路創(chuàng)建;然后把模型中的點，映射到復(fù)雜地形之上，使一個四邊形在復(fù)雜地形約束條件下剖分為多個三角形;最后依次連接，從而完成在復(fù)雜地形上街道的生成。

2.1 起伏地形道路生成

大部分的城鎮(zhèn)都坐落在高程數(shù)據(jù)有起伏的地形之上，本文采用三角形網(wǎng)格表示起伏地面，以道路的一段(一個矩形塊)為對象，研究如何實現(xiàn)從平面地形到起伏地形的道路映射轉(zhuǎn)換，具體步驟如下:

(1)采用上述方法生成平面地形下的道路，如圖3所示中四邊形A、B、C和D表示平面地形上的一截道路。

圖3 起伏地形道路網(wǎng)格映射示意圖

(2)圖3中的三角網(wǎng)格表示平面地形對應(yīng)的起伏地面，A、B、C和D在起伏地面對應(yīng)的映射點集為A′、B′、C′和D′。

(3)分別計算平面ADD′A′、平面BCC′B′和起伏地形網(wǎng)格三角形相應(yīng)邊的交點。如平面ADD′A′和△XYZ的邊XY、XZ的交點P、Q。其中，平面ADD′A′用Ax+By+Cz+D=0表示，三角形三邊用直線的參數(shù)方程表示，交點計算公式為:

(4)順序連接所有交點，即可得到起伏地面的道路邊界。

采用圖3所示的方法，可得到圖4所示的實驗結(jié)果。

圖4 起伏地形的道路建模效果圖

2.2 河流約束條件下道路生成

很多建筑都是依水而建，在具有河流、湖泊等水系元素的復(fù)雜地形上自動生成街道是增強虛擬城鎮(zhèn)建模真實感的重要手段。因此，本文在起伏地形的基礎(chǔ)上增加河流、湖泊的約束，研究復(fù)雜地形約束條件下基于L系統(tǒng)的街道自動生成方法。河流約束條件下的道路生成一般有2個特征:道路一般沿河岸伸展，形成河堤;橫向道路在遇到河堤時自動終止。本文采用修訂L系統(tǒng)中的幾何解釋規(guī)則實現(xiàn)以上2個特征，從而完成河流約束地形的道路自動生成。

3 實驗結(jié)果

本文采用Visual C++6.0開發(fā)工具和VRM L作為實驗環(huán)境對所提方法進行驗證，圖5a為采用本文方法全自動生成的具有高程起伏、河流、湖泊地形的街道的俯視圖，從中可以看出沿河岸有一條河堤(比一般道路較寬)，所有縱向的路都終止于河堤;圖5b為從一定角度觀察的效果圖，從中可以看出道路在起伏地形下的逼真效果。

為了進一步說明本文的街道自動生成方法的適用性，采用文獻[10]中徽派建筑群的自動建模方法，在圖5所示的街道中“填充”徽派建筑，得到如圖6所示的大場景徽派建筑效果[11]。

圖5 本文街道自動生成方法效果圖

圖6 填充后效果圖

4 結(jié)束語

本文通過擴展L系統(tǒng)理論，提出一種基于復(fù)雜地形的約束條件下城市道路、街道的自動生成方法，實現(xiàn)了在復(fù)雜地形上的道路生成方法，豐富了虛擬城市建模中街道、道路的自動生成理論與方法。但是，本文方法所創(chuàng)建道路還略顯死板，如何進一步修訂L系統(tǒng)的重寫規(guī)則，使得創(chuàng)建道路更具有多樣性、隨機性，是下一步需要研究的問題。

[1] M ueller P，Wonka P，Haegler S，et al.Proceduralmodeling of buildings[C]//Computer Graphics Proceedings，Annual Con feren ce Series，ACM SIGGRAPH.Boston，2006:614-623.

[2] Mu ller P，Zeng G，W onka P，et al.Image-based procedural m odeling of facades[C]//Computer G raphics Proceedings，Annual Conference Series，ACM SIGGRAPH.San Diego，2007:85-94.

[3] Liu Yong，Xu Congfu，Pan Zhigeng，et al.Sem an tic modeling project:building vernacular house of sou theast China[C]//Proceedings of ACM SIGGRAPH In ternational Conference on V irtual Reality Con tinuum and its Applications in Industry.Singapore，2004:412-418.

[4] Liu Yong，Xu Congfu，Zhang Qiong，et al.The smart architect:scalable ontology-based m odeling of ancient Chinese architectu res[J].IEEE Intelligent Systems，2008，23(1):49-56.

[5] 李 杰，張文棟，張 樨.一種多邊形道路網(wǎng)絡(luò)拓撲生成算法的設(shè)計與實現(xiàn)[J].電子學(xué)報，2006，34(8):1396-1400.[6] 宋維佳，張麗芬，王曉華.一種基于骨架化的道路拓撲生成算法[J].交通與計算機，2004，22(3):37-40

[7] 王麗英，華煒鮑，虎 軍.規(guī)則驅(qū)動的虛擬城市道路網(wǎng)絡(luò)和建筑布局建模[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2006，18(11):1704-1709.

[8] Parrish H，Muller P.Procedu ral modeling of cities[C]//SIGGRAPH.Los Angeles，2001:301-308.

[9] Hu J，You S，Neum ann U.Approaches to large-scale u rban m odeling[J].IEEE Compu ter G raphics and Applications，2003，23(6):62-69.

[10] 薛 峰，張 鍵，路華峰，等.一種徽派建筑快速建模方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2009，21(11):1595-1600.

[11] Prusinkiewicz P，Hammely M，M jolsnessz E，et al.Animation of plan tdevelopm ent[J].Com puter Graphics，1993，27(3):351-360.