复杂地形条件下虚拟城市街道生成方法

薛 峰， 邢东顺， 曹诗蔚

(合肥工业大学计算机与信息学院，安徽合肥 230009)

虚拟城镇的快速、自动建模方法是国内外虚拟现实领域的研究热门课题之一。文献[1，2]提出了基于分裂语法的建筑模型智能生成方法，并将其利用到毁于史前的古罗马城市——“庞培”的建模;文献[3]提出了一种基于语义的建模方法，使得用户的操作更简单;文献[4]在文献[3]的基础上提出了基于本体的古建筑智能建模方法，使得基于语义的建模更加合理。

目前，虚拟城市中的道路、街道生成算法主要有2种，其中一种是基于航拍遥感图像重建已有的道路、街道，在GPS导航系统中使用的地图大都是由航测图片、遥感图片或纸质地图等经过扫描后再矢量化而成。文献[5]提出了一种生成多边形道路网络拓扑结构的有效算法，基本思想是先对多边形道路网络进行三角剖分，然后生成其中轴线，提高了道路准确度。为进一步提高道路精确度，文献[6]提出一种道路拓扑生成算法，利用约束Delaunay三角化、骨架化的方法从电子地图中提取道路。另一种是基于规则的街道自动生成方法，此类方法被广泛地应用于虚拟城市建模、大型游戏场景中的道路自动生成[7]。文献[8，9]提出了一种基于扩展L系统(Ex tended L-system)的城市街道自动生成方法。

但是，上述文献对于虚拟街道、道路的研究大部分都是基于简单、平坦的地形条件下，缺少在复杂地形(高程起伏、河流等)约束条件下的道路创建规则，导致最终生成的城市场景不够丰富、缺少变化。为此，笔者在徽派建筑体自动建模研究的基础上[10]，提出一种复杂地形(高程起伏、河流约束等)约束条件下的街道生成算法，并在生成的街道模型中“填入”建筑物模型，实现复杂地形的虚拟城镇场景的自动建模。

1 基于L系统的平面地形街道生成

1.1 本文方法流程

复杂地形下的街道自动生成方法基本步骤如下:①定义相应的公理和重写规则，采用L系统的重写规则实现平面地形的街道生成;②通过高程映射的方法将平面地形的街道映射到起伏地形的三角网格中，生成起伏地面的街道;③加入对河流的识别，并对L系统的几何解释规则进行修正，使得创建的道路能够与河流合理搭配。此外，本文还向生成的街道中“填充”具有皖南特色的徽派建筑模型，实现了大规模徽派建筑场景的建模，以说明本文街道生成方法的有效性。

1.2 L系统简介

L系统本质上是一个并行重写系统，其核心概念是重写(rew riting)。重写的基本思想是根据预先定义的规则集(产生规则)不断替换初始参数以形成更为复杂的、有规律的表示。L系统在形式化时一般采用字符串表示:令V表示字母，V*表示V上的所有单词的集合，一个L系统是一个有序的三元组，即

其中，W是一个非空单词，也是起始符号元，称为公理;P是产生式规则即重写规则。L系统的重写过程如下:由一个初始公理字符串W开始，用一个重写规则P逐次置换W的各个字符，不断递归生成新的字符串。如假设L系统由变量〈F〉、常量〈+、-〉、重写规则集〈F→F+F-F-F+F〉和起始字符串符组成。其中，F表示先前走;常量+、-分别表示向右转90°、向左转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次重写得到的字符串经过几何解释后得到的图形。从中可以看出，通过核实的几何解释由L系统重写规则得到的字符串，可以得到一系列有规律性的几何图形，这些几何图形可以模拟植物躯干、枝叶[11]和街道的生成[7]等。

图1 3次重写过程中直线变化结果

1.3 基于L系统的平面地形街道生成

城市街道建模是由普通道路、十字路口及丁字路口组成。普通道路建模可根据道路的相关参数，生成一个条带状矩形平面。其中参数主要包括:道路起始点、道路长宽和与水平轴夹角等。十字路的建模相对比较复杂，概括来说是由普通道路、十字路口和拐角区域组成。

本文介绍基于L系统的街道、道路实现方法。假设生成平面地形街道的L系统的变量有F、S、Q、Z和T。其中，“F”代表普通道路;“S”代表十字路口(十字路口对面节点为下次创建道路的起点);“T”代表产生十字路;“Q”代表与水平轴夹角为+90°的道路;“Z”代表与水平轴夹角为-90°的道路。常量有W、R、+、-、4和0。其中，“W”代表记录或恢复道路的起点;“R”代表十字路口(十字口中左、右两边道路其中一条道路的终点为下次创建道路的起点);“+”代表与水平轴的夹角为+90°或者是选择十字路左边道路为下次道路的起点;“-”代表与水平轴的夹角为-90°或者是选择十字路右边道路为下次创建道路的起点。此外，为了避免道路过于规整、呆板，本文引入另外2个常量字符“4”和“0”，其中，“4”代表e与水平轴的夹角为+45°;“0”表示取消下一个字符的意义。

起始字符为:

F+FFF4FFFQZT4FFF4FSTST。

重写规则: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。

道路的联通性通过道路的终点传递给下条路的起点。十字路口的终点传递问题比较复杂，因为每个十字路口都有3个分支，通过在函数中添加一个参数，用来决定哪个分支的终点为下条路的起始点。笔者在L系统中分别用S、+R和-R表示十字路口对面分支、左分支和右分支，从而解决道路连接问题。此外，通过分别创建十字路的几个分支来解决道路的重叠问题，如重写规则中的T=+W+R+F+F+S-W+W-RF-F-S-S-F-S-W+WSTTTTT。其中，+W+R+F+F+S-W是创建的十字路口左分支道路;+W是记录分支的起始位置，以便在该位置创建另一条分支;+W-R-F-F-SS-F-S-W是创建的十字路口右分支道路，实验结果如图2所示。

图2 基于L系统的平面地形道路生成效果图

2 复杂地形的街道生成方法

复杂地形的街道生成是指在普通平面地形的基础上，考虑高程起伏、河流等约束条件下的街道自动生成。方法基本思想:首先通过L系统实现平面地形上的道路创建;然后把模型中的点，映射到复杂地形之上，使一个四边形在复杂地形约束条件下剖分为多个三角形;最后依次连接，从而完成在复杂地形上街道的生成。

2.1 起伏地形道路生成

大部分的城镇都坐落在高程数据有起伏的地形之上，本文采用三角形网格表示起伏地面，以道路的一段(一个矩形块)为对象，研究如何实现从平面地形到起伏地形的道路映射转换，具体步骤如下:

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

图3 起伏地形道路网格映射示意图

(2)图3中的三角网格表示平面地形对应的起伏地面，A、B、C和D在起伏地面对应的映射点集为A′、B′、C′和D′。

(3)分别计算平面ADD′A′、平面BCC′B′和起伏地形网格三角形相应边的交点。如平面ADD′A′和△XYZ的边XY、XZ的交点P、Q。其中，平面ADD′A′用Ax+By+Cz+D=0表示，三角形三边用直线的参数方程表示，交点计算公式为:

(4)顺序连接所有交点，即可得到起伏地面的道路边界。

采用图3所示的方法，可得到图4所示的实验结果。

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

2.2 河流约束条件下道路生成

很多建筑都是依水而建，在具有河流、湖泊等水系元素的复杂地形上自动生成街道是增强虚拟城镇建模真实感的重要手段。因此，本文在起伏地形的基础上增加河流、湖泊的约束，研究复杂地形约束条件下基于L系统的街道自动生成方法。河流约束条件下的道路生成一般有2个特征:道路一般沿河岸伸展，形成河堤;横向道路在遇到河堤时自动终止。本文采用修订L系统中的几何解释规则实现以上2个特征，从而完成河流约束地形的道路自动生成。

3 实验结果

本文采用Visual C++6.0开发工具和VRM L作为实验环境对所提方法进行验证，图5a为采用本文方法全自动生成的具有高程起伏、河流、湖泊地形的街道的俯视图，从中可以看出沿河岸有一条河堤(比一般道路较宽)，所有纵向的路都终止于河堤;图5b为从一定角度观察的效果图，从中可以看出道路在起伏地形下的逼真效果。

为了进一步说明本文的街道自动生成方法的适用性，采用文献[10]中徽派建筑群的自动建模方法，在图5所示的街道中“填充”徽派建筑，得到如图6所示的大场景徽派建筑效果[11]。

图5 本文街道自动生成方法效果图

图6 填充后效果图

4 结束语

本文通过扩展L系统理论，提出一种基于复杂地形的约束条件下城市道路、街道的自动生成方法，实现了在复杂地形上的道路生成方法，丰富了虚拟城市建模中街道、道路的自动生成理论与方法。但是，本文方法所创建道路还略显死板，如何进一步修订L系统的重写规则，使得创建道路更具有多样性、随机性，是下一步需要研究的问题。

[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] 李 杰，张文栋，张 樨.一种多边形道路网络拓扑生成算法的设计与实现[J].电子学报，2006，34(8):1396-1400.[6] 宋维佳，张丽芬，王晓华.一种基于骨架化的道路拓扑生成算法[J].交通与计算机，2004，22(3):37-40

[7] 王丽英，华炜鲍，虎 军.规则驱动的虚拟城市道路网络和建筑布局建模[J].计算机辅助设计与图形学学报，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].计算机辅助设计与图形学学报，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.