薛 峰， 宋 為， 崔國影

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

三維場景建模是計算機輔助設計與虛擬現(xiàn)實領域的一大研究熱點，并產(chǎn)生了大量的成功應用系統(tǒng)。例如IBM基于三維建模技術(shù)研發(fā)的“虛擬紫禁城”[1]，用戶可以在互聯(lián)網(wǎng)上實時瀏覽。Google公司研發(fā)的“谷歌街景”虛擬漫游服務，能夠提供城市街道的三維場景漫游。網(wǎng)游公司推出的各種大型網(wǎng)絡游戲，以及越來越多的2.5維或者更高維的電子城市地圖系統(tǒng)等等。這些虛擬系統(tǒng)有一個共同點：建筑場景宏大。傳統(tǒng)的、依靠3D建模軟件人工建模方法，因其周期長、成本高而難以適用。因此，隨著各種虛擬現(xiàn)實系統(tǒng)的蓬勃發(fā)展，三維場景的快速、自動建模技術(shù)得到了越來越多的國內(nèi)外研究者的重視，并取得了大量研究成果，這些研究成果大致可分為以下三類：

1） 基于圖像輸入的建模方法。該項技術(shù)以傳統(tǒng)的 IBM(Image Based Modeling)建模技術(shù)最為成熟[2]。它是通過輸入圖像等，重建城市場景。但該方法依賴于現(xiàn)實場景的航拍圖，無法生成虛擬場景。后來Byong MokOh對該方法進行改進[3]，加入了用戶的交互操作，可得到變化更為豐富的建筑模型。但該類方法需要耗費大量時間進行模型制作和修正。

2） 基于規(guī)則的自動建模方法。這類方法包括基于 L系統(tǒng)[4-9]和形狀語法的建模方法，主要用于城市建筑群的自動生成，其基本思路是使用有限的參數(shù)約束，實現(xiàn)城市三維建模的自動化。Parish等基于擴展L系統(tǒng)提出一種城市街道自動生成方法，該方法被廣泛地用于游戲、虛擬現(xiàn)實應用中街道的自動生成。隨后 Parish和Müller又在基于形狀語法的城市自動建模研究上取得了進一步的成果[7]。

3） 基于參數(shù)化、模塊化的建模方法。模塊化建模由Birch等提出[9-10]。這種方法可針對不同特色建筑建模，但這些模塊的參數(shù)需要通過交互得到。Ullrich等[11]采用語義描述的方式，通過構(gòu)建模型數(shù)據(jù)庫進行輔助建模。在國內(nèi)，浙江大學的劉勇等以模塊化、參數(shù)化建模思想為基礎，并融入了遞歸形狀語法思想，實現(xiàn)中國江南民居的快速建模，取得了很好的效果[12]。隨后，劉勇等又提出一種更加智能的基于本體語義建模方法(Semantic Modeling)[13]，簡化了建模的操作。

圖1 建筑模塊形式化拓撲圖

上述研究雖然取得很多卓有成效的成果，但是大多數(shù)只適用于“盒狀(Box-Like)”城市建筑，即使基于模塊化的建模方法可用于某些特色建筑的建模，但是對于特色鮮明，風格迥異的地方特色建筑體（群）還顯得無能為力。筆者所在的研究小組在 2009年基于模塊化思想，提出了一種基于圖的廣度遍歷算法[14]，實現(xiàn)了徽派建筑體（群）的自動化建模；隨后又提出了基于MSSR的建模方法[15]。然而上述論文中提到的方法都是通過圖的廣度遍歷算法生成渲染文件，在處理大規(guī)模拓撲圖的時候存在效率不高的問題；與此同時前期的研究成果也在建筑多樣性的問題上做的有所限制，本文參照模塊化的建模思想，提出了基于子圖拓撲擴展和模塊組合的徽派建筑體（群）快速建模方法。

1 算法基本思想和流程

徽派建筑具有鮮明的地域和文化特色，是中國古代建筑中最典型的代表之一?；张山ㄖ嬖谙鄬Ψ€(wěn)定的模塊結(jié)構(gòu)、清晰的組合關系。一般地，一個單體徽派建筑可按圖1中的方式進行結(jié)構(gòu)分解，將分解得到的每個模塊對應成一個拓撲圖(Graph)節(jié)點(Node)，則一棟典型的徽派建筑體可轉(zhuǎn)化為一個平面拓撲圖。

按照上述方式，我們對皖南民居進行實地考察和圖片分析，得出徽派建筑的基本模塊和基本結(jié)構(gòu)，如表1所示。

由圖1可見，徽派建筑的模塊具有可分解特性[14]，假定事先獲得一個徽派建筑的二維拓撲圖，然后采用圖的廣度遍歷方法遍歷每個拓撲節(jié)點，實現(xiàn)模塊節(jié)點的順序渲染，最終輸出一個徽派建筑體。該算法能夠?qū)崿F(xiàn)徽派建筑的快速建模，但是依賴于事先定義好的二維拓撲草圖，自動化程度受限。本文提出一種基于子圖拓撲擴展的徽派建筑快速建模方法，能夠基于有限的初始節(jié)點信息，自動擴展成典型的徽派建筑平面布局二維拓撲圖，然后采用模塊組合和參數(shù)化的思想，實現(xiàn)快速建模。具體流程如圖2所示。

表1 徽派建筑的基本模塊與結(jié)構(gòu)

圖2 算法流程圖

1） 對徽派建筑的模塊組合特征、建筑之間的布局特點進行深入分析、總結(jié)，構(gòu)建“建筑體組合規(guī)則庫”、“建筑群組合規(guī)則庫”；

2） 基于少量的初始節(jié)點信息（如用戶手工輸入初始節(jié)點，后續(xù)初始節(jié)點由相鄰建筑模型過渡的公共節(jié)點代替），結(jié)合建筑體組合規(guī)則庫、建筑群組合規(guī)則庫，采用子圖擴展算法生成徽派建筑的二維平面拓撲圖；

3） 采用相關遍歷方法對生成的二維平面拓撲圖進行遍歷，在遍歷到每個節(jié)點時參照相鄰模塊之間的約束，自動給模塊賦予相應的幾何屬性、紋理屬性、風格屬性；

4） 直至整個拓撲圖遍歷完畢，輸出三維建筑模型。

2 徽派建筑拓撲圖自動生成

圖2所示的建模流程中，需要構(gòu)建兩個數(shù)據(jù)庫：徽派建筑組合規(guī)則數(shù)據(jù)庫、徽派建筑模塊數(shù)據(jù)庫。

2.1 徽派建筑組合規(guī)則庫的構(gòu)建

徽派建筑的組合規(guī)則庫包括：建筑體內(nèi)模塊組合規(guī)則庫和單體建筑之間組合規(guī)則庫。這兩個規(guī)則庫需要從徽派建筑體（群）的實際布局結(jié)構(gòu)中總結(jié)抽象而來?；张山ㄖw在本文指的是一個單獨的房屋或者庭院，其布局結(jié)構(gòu)呈多樣化、復雜化。如表2所示，大致可分為：“凹”字型、“回”字型、“H” 字型、“日”字型布局[15]。

表2 徽派建筑常見的平面布局結(jié)構(gòu)

在使用子圖擴展算法對輸入拓撲圖進行擴展時，通過建筑組合規(guī)則對其擴展節(jié)點進行約束和檢測，從而保證擴展節(jié)點的準確性和建模的正確性。建筑體內(nèi)組合規(guī)則按典型布局結(jié)構(gòu)可以總結(jié)為以下四類[16]，見表3。

表3 徽派建筑組合規(guī)則表

而徽派建筑群是由若干單體建筑按照一定的規(guī)則組建而成，因此徽派建筑群的組合規(guī)則即可認為是建筑體之間的組合規(guī)則。建筑群的組合規(guī)則比較簡單，可分為：平行排列和垂直排列兩種。其中要注意的是平行組合的庭院大門是同向的，如圖3(a)所示；而垂直組合的庭院大門均朝外，如圖3(b)所示。

圖3 建筑體之間組合方式

2.2 徽派建筑屬性庫的構(gòu)建

徽派建筑模塊屬性庫是建模中遍歷渲染的數(shù)據(jù)庫基礎。模塊屬性包括：角色屬性、幾何屬性、空間位置屬性以及紋理屬性等，還包括建筑體所在地理環(huán)境和用途的風格屬性。模塊自身各種屬性對模塊本身形成一定約束，同時模塊間的屬性也相互約束，因此屬性約束可作為建筑拓撲遍歷渲染的推理基礎。將這些規(guī)則形式化定義如下：定義A'為當前已知模塊，A為后續(xù)未知模塊；R(A)為A的角色約束，即A是什么模塊；G(A)為模塊的幾何約束；P(A)為模塊的空間位置約束；S(A)為模塊風格約束，風格約束是通過當前拓撲結(jié)構(gòu)和幾何屬性得到；T(A)為模塊的紋理屬性。模塊的屬性約束規(guī)則定義如下[14]：

上述的4個形式表達式按照從上到下的順序進行推理。當?shù)玫揭粋€拓撲結(jié)構(gòu)時，從當前節(jié)點按照角色推理得到后續(xù)的節(jié)點集合；然后執(zhí)行步驟2），通過幾何屬性約束規(guī)則可以發(fā)現(xiàn)部分模塊的約束條件不足而不能被渲染，則從候選集中刪除該節(jié)點，集合縮??；3）通過2）集合中剩余節(jié)點均具備完整的幾何屬性，將集合中的所有節(jié)點執(zhí)行3）、4）步驟進行最后的渲染。最后以其中的一個節(jié)點為初始節(jié)點重復上述步驟，直到拓撲遍歷渲染結(jié)束。

2.3 基于子圖擴展的徽派建筑拓撲自動生成

基于子圖擴展的徽派建筑拓撲自動生成包括兩方面推理：建筑體拓撲的推理、建筑群拓撲的擴展。建筑體拓撲可以作為建筑群擴展的基礎：得到一個建筑體拓撲后可由建筑群組合規(guī)則擴展得到下一個建筑體。

建筑體（群）拓撲圖擴展具體過程，如圖4所示。

圖4 建筑體拓撲圖擴展流程圖

1） 對輸入的拓撲圖進行擴展，擴展的過程用建筑體組合規(guī)則庫進行檢測，如果當前新的擴展節(jié)點不符合規(guī)則，則回溯到剛才的步驟，重新執(zhí)行直到獲得正確的擴展節(jié)點；

2） 當前的拓撲不是完整建筑體，則利用當前新的拓撲圖作為輸入拓撲圖，執(zhí)行步驟1）；

3） 當前的拓撲圖是一個完整的建筑體拓撲結(jié)構(gòu)，則將其輸出，并以該拓撲圖中的lsw或rsw節(jié)點為初始節(jié)點，結(jié)合建筑群組合規(guī)則得到新的建筑體的拓撲圖輸入，繼續(xù)執(zhí)行步驟1）。

以一個簡單拓撲圖輸入為例，其擴展結(jié)果如圖5所示。

當輸入拓撲圖的前墻節(jié)點(gw)，擴展生成一個后墻節(jié)點(bw)，經(jīng)過建筑體組合規(guī)則檢測，不符合規(guī)則，則重復此步驟，再次利用初始輸入進行擴展（默認從gw開始）；當前墻(gw)節(jié)點的擴展節(jié)點為廊房(lc)模塊時，經(jīng)檢測符合規(guī)則，則繼續(xù)以當前的拓撲圖（新生成節(jié)點lc為初始）進行擴展，直到獲得一個完整的建筑體模型。建筑體之間的推理，利用上述的完整模型的側(cè)墻作為原始節(jié)點輸入，進行擴展，根據(jù)建筑群組合規(guī)則可知：如果擴展的節(jié)點是后墻，則是兩個垂直的建筑體，如果擴展的仍然是側(cè)墻，則是兩個并列的建筑體，在確定兩建筑體之間的關系后繼續(xù)擴展，生成新的建筑體。

圖5 子圖擴展結(jié)果檢測示意圖

2.4 徽派建筑拓撲的遍歷渲染

徽派建筑建模的最后一步是對已經(jīng)生成的拓撲結(jié)構(gòu)圖遍歷、渲染生成最后的場景模型。根據(jù)2.2節(jié)的描述，遍歷渲染主要依賴于模塊本身的屬性約束和模塊間的屬性約束。其流程如圖6所示。

圖6 拓撲遍歷渲染

圖7 四種典型布局結(jié)構(gòu)的徽派建筑模型

在整個遍歷渲染過程中，本文以建筑體后墻模塊對應的節(jié)點bw為當前節(jié)點。在遍歷過程中，當前節(jié)點通過模塊間的約束規(guī)則推理時，會產(chǎn)生多個后續(xù)節(jié)點，那么下一步渲染我們選擇能得到完整幾何屬性描述文件的節(jié)點；如后續(xù)節(jié)點仍有多個，那么這些節(jié)點可以不分先后順序的渲染，并將其放在List表中，當遍歷完List中所有的節(jié)點以后，以最后渲染的節(jié)點為當前節(jié)點繼續(xù)向后遍歷。現(xiàn)在我們以“凹”字型建筑體遍歷渲染為例，從后墻節(jié)點開始遍歷；其后續(xù)節(jié)點共有3個：lsw，rsw和rf，而rf橫截面的寬度屬性不能由當前節(jié)點推理得到，所以選擇遍歷lsw和rsw節(jié)點；這兩個節(jié)點的遍歷不分先后，將其放在List中，無論先遍歷哪個節(jié)點均可；然后再以List尾部節(jié)點為當前節(jié)點繼續(xù)遍歷。若先渲染lsw節(jié)點，則后渲染的rsw視為新的當前節(jié)點繼續(xù)遍歷。按照此規(guī)則，得到整個“凹”字型建筑體的遍歷順序：bw，lsw，rsw，rf，gw，lc，rc，yw。

3 實驗結(jié)果與討論

我們基于VC+VRML，對本文算法進行了實驗驗證。圖7展示了本文算法建模得到的四種典型布局結(jié)構(gòu)的徽派建筑體。在實際建模中我們可能得到比之更復雜的建筑體，例如在自動生成拓撲的時候可能會生成比“日”字型復雜的“目”字型或者其他布局結(jié)構(gòu)的建筑體。

圖8展示了兩種不同建筑體組合形式的建模效果，這四幅結(jié)果圖清楚的展示了不同布局結(jié)構(gòu)之間的不同組合方式，這些組合方式也是生成建筑群的一個基本組合方式。

圖8 由典型布局結(jié)構(gòu)組合的徽派建筑模型

為了驗證本文方法能夠快速構(gòu)建較大場景的模型，我們根據(jù)建筑體之間組合規(guī)則庫，對建筑體的個數(shù)加以控制，實現(xiàn)了多棟徽派建筑的快速建模，如圖9所示。對于大規(guī)模的徽派建筑，本文采用了將街區(qū)簡單的組合的方式來實現(xiàn)。圖7中，所有模型均在幾秒鐘以內(nèi)完成構(gòu)建。

圖9 本文方法得到的大場景模型

4 結(jié) 束 語

本文在徽派建筑模塊化分析和研究的基礎上[14-15]，利用子圖擴展的方法實現(xiàn)徽派建筑的拓撲結(jié)構(gòu)自動生成。首先以用戶簡單的拓撲輸入為初始信息，通過子圖擴展以及徽派建筑（群）約束規(guī)則，自動地生成建筑體（群）的拓撲結(jié)構(gòu)圖，然后基于建筑的模塊屬性約束對生成的拓撲進行遍歷渲染，從而得到徽派建筑體（群）的場景模型。然而現(xiàn)實中的徽派建筑風格突出、樣式豐富、造型細膩，因此如何完善徽派建筑的細節(jié)描述，使得徽派建筑虛擬場景更加逼真，是我們下一步需要研究的課題。

[1]李長山, 劉曉明, 朱麗萍, 李冰．虛擬現(xiàn)實技術(shù)及其應用[M]. 北京: 石油工業(yè)出版社, 2006: 1-3.

[2]Henrik T. Avocado: a distributed virtual reality framework [J]. IEEE Virtual Reality'99, 1999: 14-21.

[3]Mok B O, Chen M. Image-based modeling and photo editing, proceedings of SIGGRAPH 01 [C]//Los Angeles, CA, USA, 2001: 433-442.

[4]Hillier B. Space is the machine: a configurational theory of architecture [M]. Cambridge University Press, Cambridge, UK, 1997.

[5]Prusinkiewicz P, Lindenmayer A. The algorithmic beauty of plants [C]//New York: Spinger～Verlag,1990.

[6]Mech R, Prusinkiewicz P. Visual models of plants interacting with their environment [C]//Proceedings of ACM SIGGRAPH 96, ACM Press, H. Rushmeier, Ed.,1996: 397-410.

[7]Parish Y I H, Müller P. Procedural modeling of cities [C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH. Los Angeles,CA, USA, 2001.

[8]Wonka P, Wimmer M, Sillion F X, Ribarsky W. Instant architecture [J]. ACM Transactions on Graphics, 2003,22(4): 669-677.

[9]Birch P J, Jennings V J, Day A M, Amold D B.Procedural modeling of vernacular housing for virtual heritage environments[C]//ACM Special Interest Group on Computer Graphics and Interactive Techniques: Virtual Reality, Archeology, and Cultural Heritage. NY, USA: ACM, 2001: 187-196.

[10]Birch P J, Browne S P, Jennings V J, Day A M,Amold D B. Rapid procedural-modelling of architectural structures[C]// Proceedings of the 2001 conference on Virtual reality, archeology, and cultural heritage, Glyfada, 2001: 187-196,371.

[11]Ullrich T, Settgast V, Fellner D W. Semantic fitting and reconstruction [J]. Journal on Computing and Cultural Heritage, 2008, 1(2):560-574.

[12]Liu Yong, Xu Congfu, Pan Zhigeng, Pan Yunhe.Semantic modeling project: building vernacular house of southeast China[C]//ACM Siggraph International Conference on Virtual Reality Continuum and Its Applications in Industry, NY,USA: ACM, 2004.

[13]Liu Yong, Xu Congfu, Zhang Qiong, Pan Yunhe.Ontology based semantic modeling for Chinese ancient architectures [C]//The Twenty-first National Conference on Artificial Intelligence(AAAI). Boston,Massachusetts: AAAI, 2006: 16-20.

[14]薛 峰, 張 鍵, 陸華峰. 一種徽派建筑快速建模方法[J]. 計算機輔助設計與圖形學學報, 2009,21(11): 1596-1600.

[15]薛 峰, 曹詩蔚, 邢東順. 基于MSSR的徽派建筑快速建模方法[J]. 計算機應用研究, 2010, 27(8):3141-3143.

[16]Xue Feng, Wang Xiaotao, Liang Feng, Yang Pingping.Fast ASA modeling and texturing using subgraph isomorphism detection algorithm of relational model[C]//2012 International Multimedia Modeling Conference, 2013: 535-537.