基于子图拓扑扩展的徽派建筑快速建模方法

薛 峰， 宋 为， 崔国影

（合肥工业大学计算机与信息学院，安徽 合肥 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.