基于子圖拓撲擴展的徽派建筑快速建模方法

薛 峰， 宋 為， 崔國影

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

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

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

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

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

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

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

1 算法基本思想和流程

徽派建筑具有鮮明的地域和文化特色，是中國古代建筑中最典型的代表之一。徽派建筑存在相對穩定的模塊結構、清晰的組合關系。一般地，一個單體徽派建筑可按圖1中的方式進行結構分解，將分解得到的每個模塊對應成一個拓撲圖(Graph)節點(Node)，則一棟典型的徽派建筑體可轉化為一個平面拓撲圖。

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

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

表1 徽派建筑的基本模塊與結構

圖2 算法流程圖

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

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

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

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

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

圖2所示的建模流程中，需要構建兩個數據庫：徽派建筑組合規則數據庫、徽派建筑模塊數據庫。

2.1 徽派建筑組合規則庫的構建

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

表2 徽派建筑常見的平面布局結構

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

表3 徽派建筑組合規則表

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

圖3 建筑體之間組合方式

2.2 徽派建筑屬性庫的構建

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

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

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

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

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

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

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

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

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

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

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

圖5 子圖擴展結果檢測示意圖

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

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

圖6 拓撲遍歷渲染

圖7 四種典型布局結構的徽派建筑模型

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

3 實驗結果與討論

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

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

圖8 由典型布局結構組合的徽派建筑模型

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

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

4 結 束 語

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

[1]李長山, 劉曉明, 朱麗萍, 李冰．虛擬現實技術及其應用[M]. 北京: 石油工業出版社, 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.