基于子圖拓?fù)鋽U(kuò)展的徽派建筑快速建模方法

薛 峰， 宋 為， 崔國影

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

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

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

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

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

圖1 建筑模塊形式化拓?fù)鋱D

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

1 算法基本思想和流程

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

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

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

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

圖2 算法流程圖

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

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

3） 采用相關(guān)遍歷方法對(duì)生成的二維平面拓?fù)鋱D進(jìn)行遍歷，在遍歷到每個(gè)節(jié)點(diǎn)時(shí)參照相鄰模塊之間的約束，自動(dòng)給模塊賦予相應(yīng)的幾何屬性、紋理屬性、風(fēng)格屬性；

4） 直至整個(gè)拓?fù)鋱D遍歷完畢，輸出三維建筑模型。

2 徽派建筑拓?fù)鋱D自動(dòng)生成

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

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

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

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

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

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

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

圖3 建筑體之間組合方式

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

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

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

2.3 基于子圖擴(kuò)展的徽派建筑拓?fù)渥詣?dòng)生成

基于子圖擴(kuò)展的徽派建筑拓?fù)渥詣?dòng)生成包括兩方面推理：建筑體拓?fù)涞耐评怼⒔ㄖ和負(fù)涞臄U(kuò)展。建筑體拓?fù)淇梢宰鳛榻ㄖ簲U(kuò)展的基礎(chǔ)：得到一個(gè)建筑體拓?fù)浜罂捎山ㄖ航M合規(guī)則擴(kuò)展得到下一個(gè)建筑體。

建筑體（群）拓?fù)鋱D擴(kuò)展具體過程，如圖4所示。

圖4 建筑體拓?fù)鋱D擴(kuò)展流程圖

1） 對(duì)輸入的拓?fù)鋱D進(jìn)行擴(kuò)展，擴(kuò)展的過程用建筑體組合規(guī)則庫進(jìn)行檢測(cè)，如果當(dāng)前新的擴(kuò)展節(jié)點(diǎn)不符合規(guī)則，則回溯到剛才的步驟，重新執(zhí)行直到獲得正確的擴(kuò)展節(jié)點(diǎn)；

2） 當(dāng)前的拓?fù)洳皇峭暾ㄖw，則利用當(dāng)前新的拓?fù)鋱D作為輸入拓?fù)鋱D，執(zhí)行步驟1）；

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

以一個(gè)簡(jiǎn)單拓?fù)鋱D輸入為例，其擴(kuò)展結(jié)果如圖5所示。

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

圖5 子圖擴(kuò)展結(jié)果檢測(cè)示意圖

2.4 徽派建筑拓?fù)涞谋闅v渲染

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

圖6 拓?fù)浔闅v渲染

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

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

3 實(shí)驗(yàn)結(jié)果與討論

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

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

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

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

圖9 本文方法得到的大場(chǎng)景模型

4 結(jié) 束 語

本文在徽派建筑模塊化分析和研究的基礎(chǔ)上[14-15]，利用子圖擴(kuò)展的方法實(shí)現(xiàn)徽派建筑的拓?fù)浣Y(jié)構(gòu)自動(dòng)生成。首先以用戶簡(jiǎn)單的拓?fù)漭斎霝槌跏夹畔ⅲㄟ^子圖擴(kuò)展以及徽派建筑（群）約束規(guī)則，自動(dòng)地生成建筑體（群）的拓?fù)浣Y(jié)構(gòu)圖，然后基于建筑的模塊屬性約束對(duì)生成的拓?fù)溥M(jìn)行遍歷渲染，從而得到徽派建筑體（群）的場(chǎng)景模型。然而現(xiàn)實(shí)中的徽派建筑風(fēng)格突出、樣式豐富、造型細(xì)膩，因此如何完善徽派建筑的細(xì)節(jié)描述，使得徽派建筑虛擬場(chǎng)景更加逼真，是我們下一步需要研究的課題。

[1]李長(zhǎng)山, 劉曉明, 朱麗萍, 李冰．虛擬現(xiàn)實(shí)技術(shù)及其應(yīng)用[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]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2009,21(11): 1596-1600.

[15]薛 峰, 曹詩蔚, 邢東順. 基于MSSR的徽派建筑快速建模方法[J]. 計(jì)算機(jī)應(yīng)用研究, 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.