分类号

分类号： TP311.5 单位代码： 10335 密 级： 学 号： 20806061 硕士学位论文 中文论文题目中文论文题目 ：交互式三维城市构建与建筑布局的算法研究交互式三维城市构建与建筑布局的算法研究 英文论文题目：英文论文题目：Interactive Technique For Three-dimensional City Modeling and Building Layout 申请人姓名： 平 施 指导教师： 刘利刚 副教授 合作导师： 专业学位类别： 应用数学 专业学位领域： 计算机图形学 所在学院： 理学院 论文提交日期论文提交日期 2010 年年 5 月月 交互式三维城市构建与建筑布局的算法研究交互式三维城市构建与建筑布局的算法研究 论文作者签名论文作者签名: 指导教师签名指导教师签名: 论文评阅人 1： 评阅人 2： 评阅人 3： 评阅人 4： 评阅人 5： 答辩委员会主席： 委员 1： 委员 2： 委员 3： 委员 4： 委员 5： 答辩日期： 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得 浙江大学浙江大学 或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 签字日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解 浙江大学浙江大学 有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 浙江大学浙江大学 可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 (保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师签名： 签字日期： 年 月 日 签字日期： 年 月 日 浙江大学硕士学位论文 摘要 摘要 摘要 快捷的三维城市构建是城市规划、数字娱乐、电子学习等虚拟现实应用的基 础前提。构造虚拟城市模型因而有着深刻的应用背景，但采用交互式建模工具及 商业造型软件来构建是费时、繁琐的手工任务。近年来，程序化技术的运用以其 成本低、构建速度相对较快得到越来越多研究者的关注。 我们把虚拟城市构建划分为道路网络、功能分区、模型构建和建筑布局。已 有的技术在路网和建筑模型的构建上做了不错的尝试，但常常需要用户去输入特 定格式的约束条件，这给用户增加了额外的负担，对于当前大多数的城市设计系 统而言，一般用户交互是比较繁杂不方便的，有些甚至不是专门人士是无法完成 交互工作的。本文的一个出发点是提供给用户贯穿始终的简捷直观的交互手段， 无论是约束输入，还是对结果的修改，都以“可见即可得”的方式呈现出来，这 归功于流场和样条曲线的运用。另外目前针对建筑布局的算法较少，本文提出了 一种由粗至精的建筑排布策略，先对城市区域划分实现大尺度的建筑群排布，再 把镶嵌技术运用在区域内单个建筑的排布上，大小尺度的控制使得建筑排布更加 简易且贴近实际。 本文的主要研究内容如下：首先是基础路网的构建，主要依赖张量场设计、 流场可视化以及路网生成策略；然后是城市特征元素的引入和对路网的调整，如 河流、湖泊、公园等，主要依赖计算机辅助几何设计方法，并根据用户指定来实 现城市区域群的功能划分；最后是建筑布局方案，主要依赖原本用于图像加工的 镶嵌技术，将具体的建筑物引导到合适的位置，并与周围建筑和道路保持协调。 本文在Visual Studio 2005平台上开发了基于MFC和OpenGL相结合的三维虚 拟城市生成系统，通过MFC开发来实现图形控件和交互面板，用OpenGL来完成 模型变换和渲染，快速实现了张量场设计、流场可视化、路网生成和建筑选择及 安置等系列功能。 关键词：关键词： 三维城市，程序化构建，直观交互，路网，城市规划，建筑布局 I 浙江大学硕士学位论文 Abstract Abstract Since convenient 3D city modeling is fundamental to the application of virtual city planning, digital entertainment, and E-learning,etc. Construction of virtual city model has profound application background, however, the use of interactive modeling tools and commercial modeling software could be very inefficient. Nowadays, procedural techniques becomes a more popular way due to its low cost and fast modeling. Four components of virtual city modeling are road network, function division, buildings modeling, and buildings layout. Though there are several existing technologies have some nice moves on road network and buildings modeling, certain types of constraints are inevitably required to be put in by users, which results extra work. For most of existing city planning system, user interaction is very inconvenient and some even requires professionals. One important aim of this article is to exhibit a simple and intuitive way, for either input of constrains or modification of result. Moreover, buildings layout which is one crucial part of city planning, is seldom referred in current algorithms. We are introducing a strategy of buildings layout by refining, which means first arranging the blue prints by blocks then working on the details using mosaic technique on every single block, to make it more reasonable. Following aspects will be discussed in the paper. First construct the basic road network,mainly depends on tensor field designing, flow visualization and the strategy of roads construction; Second introduce the characteristic elements of a city, such as river,lake,park,etc, mainly depends on CAGD; In the end, we will discuss the strategy of buildings layout, mainly depends on mosaic technique. This paper develops a 3D virtual city generating system,based on MFC and Open- GL,using Visual Studio 2005.We implement graph control and interaction panel by MFC,and accomplish model transformation and rendering by OpenGL,implementing several functions such as tensor field designing,flow visualization,etc rapidly. Key Words：3D City, Procedural Modeling, Intuitionistic Interaction, Road Network, City Planning , Buildings Layout II 浙江大学硕士学位论文 目录 目录 目录 摘要I AbstractII 第 1 章 绪论1 1.1 三维城市构建(3D city modeling)概述 1 1.2 程序化技术(Procedural Techniques)的应用. 2 1.2.1 栅格规划技术(Grid Layout) 2 1.2.2 L 系统(Lindenmayer Systems). 3 1.2.3 模板技术(Template Based) 3 1.2.4 离散语法技术(Split Grammars) 4 1.2.5 其他技术 5 1.3 本文的方法 5 1.3.1 直观的用户交互 5 1.3.2 合理的建筑排布 5 1.4 文章结构 6 第 2 章 路网的构建7 2.1 张量场构建 7 2.1.1 张量场简介 8 2.1.2 张量场构建方案 8 2.2 路网的构建方案.11 2.2.1 交错式遍历方案.11 2.2.2 单线寻迹方案 12 2.2.3 种子点方案 13 2.3 小结 14 第 3 章 城市特征设计15 3.1 预备知识 15 3.2 特征设计 17 3.2.1 河流设计 17 3.2.2 湖泊和公园设计 18 3.2.3 特征设计对路网的影响 18 3.3 区域抽取和功能划分 18 3.3.1 区域多边形抽取 19 3.3.2 区域功能划分 19 3.4 小结 19 第 4 章 建筑布局设计21 4.1 建筑模型及选取 21 4.2 建筑布局策略 23 III 浙江大学硕士学位论文 目录 4.2.1 建筑群规划 23 4.2.2 改进的 CVD 算法 25 4.3 结果及结论 28 第 5 章 总结与展望32 5.1 全文总结 32 5.2 研究展望 33 参考文献34 致谢36 IV 浙江大学硕士学位论文 绪论 第1章 绪论 第1章 绪论 随着地球空间信息学的发展， “数字地球” 概念逐渐为人们所熟悉。 严格地讲， 数字地球是以计算机技术为基础，运用海量地球信息对地球进行多分辨率、多尺 度、多时空和多种类的三维描述，并利用它作为工具来支持和改善人类活动和生 活质量。整个“数字地球”是一个浩大的工程，而“数字城市”则是其中一个重 要组成部分，它首先基于城市的三维构建。 1.11.1 三维城市构建三维城市构建(3D city modeling)概述 概述 城市的三维构建是在计算机中对城市地物在三维空间中进行表达，以反映城 市景观为主要特征，并包含从各个方向观察城市景观时的所有必要信息。 图 1.1 三维城市模型的例子 城市是一个复杂的系统，涉及到地理学、建筑学、生态学、规划学等多门科 学，体现了经济、科技、社会的时空演变。城市信息化已成为未来城市发展的趋 势，很多政府部门及商业部门需要城市模型辅助制定发展规划。在很多新兴领域 如虚拟现实和数字娱乐业需要城市模型作为仿真的背景。网上 3D 城市地图让我 们足不出户就可以快速地游览一个远在千里之外的城市。这一切，都因为城市建 模技术的发展而得到应用，同时也因为这些需求让城市建模技术得到了更好的发 展，如图 1.1 所示。 构造虚拟城市模型有着深刻的应用背景，虚拟城市构建可以划分为功能分 区、道路网络和建筑布局、模型的几何建模。这类面向自然景物及大规模场景的 1 浙江大学硕士学位论文 绪论 建模技术需要表现对象的特质和丰富的细节。随着技术革新和计算机性能的提 升，对虚拟城市场景真实感、多细节、多尺度的用户需求不断上升，传统方法依 赖增加艺术性的劳动量已经不能跟上节奏，而且往往带来难以承受的人力成本。 如采用交互式建模工具及商业造型软件建模(3dsMax、Maya 等)，是费时、繁琐的 手工任务。 1.21.2 程序化技术程序化技术(Procedural Techniques)的应用 的应用 快捷的 3D 城市建模是城市规划、数字娱乐、电子学习等虚拟现实应用的基 础前提。一个潜在的解决方案就是程序化技术的运用。很多技术已经在计算机图 形学领域活跃了 20 余年，有着广泛运用，如增加纹理噪音技术，创建出类似大 理石，木头等建筑材质的 3D 纹理，各种树木、植被的逼真可视化技术，山脉、 湖泊、灌木丛等自然特征的程序化生成技术，完善的粒子系统模拟水流、喷泉、 火焰等特效，还有基于文法的建模技术生成错落有致的建筑群等。包含多类模型 的复杂场景曾经是需要耗时数月的人工构建过程，得益于这些技术，如今对场景 分解后的同类片段场景运用对应的程序化生成包，可以在几分钟之内生成富含细 节和变化的模型。 但一个成熟的历经发展的城市，视觉和功能上都趋于完备，创建一个如此巨 大、复杂、逼真的城市系统，无论对研究人员还是开发人员，仍是一个令人敬畏 的挑战。由于大规模场景中细节要素多、规模大，通常是选取主要特征来简化系 统，采用自动或半自动的执行算法，才能减少规模的限制。目前已有的工作大都 遵循这个思路。 1.2.11.2.1 栅格规划技术栅格规划技术(Grid Layout) 文献1提出了一种实时程序化生成城市的解决方案， 应用程序基于简单的栅 格勾画来创建一个路网，并利用简单的图元组合产生建筑，这些建筑被安置在路 网栅格的中心。在其功能扩展了的系统中，建筑得以覆盖到多个栅格，路网兼具 杂乱性，使得结果更具现实感，如图 1.2 所示。 基于简单栅格产生的路网过于规则和相似，不够反应现实中城市多样的道路 2 浙江大学硕士学位论文 绪论 布局风格，同时由简单图元组合而成的建筑缺乏细节和真实感。 图 1.2 栅格规划技术实时生成的城市1 1.2.21.2.2 L 系统 L 系统(Lindenmayer Systems) L 系统主要应用在自然植物的造型技术中，文献2利用道路规划与植物生长 的类似性，应用 extended-L 系统生成虚拟城市的道路网和建筑的几何模型，完成 了城市模型的建造，这个方法可以产生较高的路网精度。需要输入的是高度图、 植被图、水流图，还需要额外的如人口密度图、街道类型和最大建筑高度等信息， 如图 1.3 所示的路网生成应用程序将按照给定的输入条件和面板上的参数设置来 自动完成道路设计的工作2。 但基于真实的数据输入作为约束，使得系统的承受力难以评估，还有缺乏交 互的整合使得传统编辑手段难以运用在结果的修正上，用户为了得到满意的结 果，有时候不得不调整约束再重新来过。 图 1.3 城市引擎用户界面：执行100步后的曼哈顿路网效果 2 1.2.31.2.3 模板技术模板技术(Template Based) 文献3主要解决道路网的生成问题， 归纳了4种风格的道路网生成模板： 基于 3 浙江大学硕士学位论文 绪论 人口模板、辐射模板、栅格模板和混合模板，如图 1.4所示。其表示方式分别采 用Voronoi图模型和简化的规则产生式，将模板作为约束嵌在城市地图中，再利用 这些约束条件得出变形后的全局路网，方法结合了地形信息，并详细地处理了道 路的3D模型，即交点处理方法。该文的规则比L系统产生式要简单。 模板的运用集中体现了城市中的经典道路布局类型，但模板风格有限，混合 型模板试图减少单一模板的简单性，可结果还达不到真实的道路布局所需的复杂 性和尺度。 图 1.4 结果自左向右：基于人口模板、辐射模板、栅格模板和混合模板3 1.2.41.2.4 离散语法技术(Split Grammars) 离散语法技术(Split Grammars) 文献4基于离散语法的建模技术是一种过程式建模技术， 它基于形状概念产 生一些离散的语法，这些语法可用来生成有正面现实感的单个建筑。其是把建筑 造型的过程转化为一个规则迭代过程和结果的解释过程，提高了造型的效率，过 程可用图 1.5 形象描述。但是其难点在于从领域知识抽取便于操作的规则产生式 集合，对造型对象进行形式化的描述。由于预先设定的规则有限性，造型缺少实 际的灵活性。 图 1.5 左图：离散的语法及对应模型；右图：完整的语法及对应模型4 4 浙江大学硕士学位论文 绪论 1.2.51.2.5 其他技术 其他技术 另外还有文献5采用专家系统的方法设计虚拟城市的功能分区、 道路元素及 建筑物等要素分布，定义知识库和规则进行推理，但是并没有提供实现。文献6 等把代理技术(Agent)引入城市建模，用于解决分区和道路网建模任务，避免了显 式定义规则的复杂性，不同道路类型的过渡上处理的不错，但是也没有处理建筑 布局的任务，而且算法耗时，一个村庄尺度的场景生成需耗时 15 分钟，还不包 括建筑布局的任务。 1.31.3 本文的方法 本文的方法 1.3.11.3.1 直观的用户交互 直观的用户交互 纵观现有的技术，无论是路网的生成还是建筑的几何建模，都需要用户(或者 开发人员)输入一些条件， 比如 extended-L 系统需要预先指定道路类型、 人口密度、 自然边界等，在这些条件的约束下再启用程序化技术完成主要的工作。但约束条 件往往受限制于开发者指定的格式输入，如道路类型由几类固定模板决定，人口 密度是一副灰度图等等。另外城市设计系统不仅要有自动生成的能力，还要有方 便的交互能力，因为还没有算法能模拟城市的复杂度，所以无论当前哪个技术， 缺少用户编辑都是做不出一个逼真城市的，所以留给用户后期交互编辑的空间还 很大，但对于当前大多数的城市设计系统而言，其交互过程都比较繁杂不方便， 有些甚至不是专门人士是无法完成交互工作的。基于文献12的启发，本文的一 个出发点就是提供给用户贯穿始终的简捷直观的交互手段，无论是约束输入，还 是对结果的修改，都以“可见即可得”的方式呈现出来。 1.3.21.3.2 合理的建筑排布 合理的建筑排布 目前的主流算法要么针对路网的构建，要么针对建筑模型的构建，很少专门 提及建筑的排布策略。考虑到建筑的排布是城市设计不可绕过的环节，为得到最 终效果，Grid Layout、L-systems等设计系统在构建路网后，将路网交叉出的小区 域作为建筑的安放位置，这样的策略明显缺乏多尺度的控制，用户不可能对这么 5 浙江大学硕士学位论文 绪论 多的小区域上去指定建筑类型，取而代之的只能是一种或者几种建筑在全局的随 机重复使用，除非引入更复杂的交互。本文提出的建筑排布策略就是为了更好的 在路网和建筑之间铺设一个桥梁，考虑到城市的功能分区，我们将街道的构建分 为两个层次：主要街道网和街区内部街道网。主要街道网的构建完毕后，是一个 大尺度的结果，可由此对城市的街区划分功能区。针对不同的功能区，用户有能 力指定相应的建筑类型， 如居民区可安放哪些建筑， 商业区可安放哪些建筑等等， 而不像以往那样缺乏控制。除了大尺度的划分区域功能和合理选择建筑类型，在 小尺度的每个建筑的定位问题上，本文运用了 2D镶嵌(Mosaics)技术7，并针对建 筑群的运用做了改进，使得功能区内的建筑排布更加贴近实际。 1.41.4 文章结构 文章结构 文章接下来的几个部分是：第二章是基础路网的构建，主要依赖张量场原理、 流场可视化以及路网生成策略；第三章是城市特征元素的引入和对路网的调整， 如河流、湖泊、公园等；第四章是建筑布局的详细讨论和结果展示；第五章是总 结与展望，总结了本文算法和系统的优缺点，指出今后的工作方向。 6 浙江大学硕士学位论文 路网的构建 第2章 路网的构建 第2章 路网的构建 城市的道理网络承担着城市的主要交通任务，道理网络的设计对整个城市的 构建有着较为广泛的影响。本文的路网构建首先基于一个直观的张量场构建。 2.12.1 张量场构建 张量场构建 在这一节中，将描述如何构建按用户定制的张量场。方法是通过设计张量元 作为约束来影响张量场，约束主要分为自然边界约束和手工约束。这里将从前人 工作中借用一些向量和张量设计技术，如基本张量场的使用等8-10。张量场的构 建基于两个约束条件：用户约束和拓扑图信息。用户约束指的是用户想要的张量 类型，如在城市的一般区域内，用户想指定一个类似栅格状的张量，如图 2.1 所 示。而在某个中心区域，用户想创建一个类似辐射状的张量，如图 2.2 所示。拓 扑图信息指的是河流湖泊、公园、高地等地理约束，比如在河流沿岸，设计的路 网总是沿河岸走向的，如图 2.3 所示，用户定制的张量场要能体现这一要求。 图 2.1 栅格类型张量及对应的路网：左用户指定；中对应张量；右对应路网 图 2.2 辐射类型张量及对应的路网：左用户指定；中对应张量；右对应路网 7 浙江大学硕士学位论文 路网的构建 图 2.3 自然约束及对应的路网：左河流；右园林 2.1.12.1.1 张量场简介 张量场简介 二阶张量 可以看做是一个t22矩阵，这个矩阵满足如下形式： 2cos2sin 2sin2cos R，这里，0R)2 , 0 该对称且迹为零的特殊矩阵有着两个特殊的特征值：1和1； 对应的特征向量为： 0 sin cos 和 () () + + 0 2/sin 2/cos 为方便起见，将1和对应的特征向量分别称为二阶张量t的主向量和辅向量。 1 一个张量场 T 是一个连续函数，指对应域内每一点，有一个张 量。当为零时，称为退化点，否则就是非退化的。 2 ),(Ryxp= )(pT)(pTp 另一个和张量场相关并且重要的概念是超流线(hyperstreamline)，在一个张量 场 T 中， 超流线上每一点处的切向恰好是此处张量的某一特征方向(始终是主向量 或者辅向量)；为方便起见，将主向量和辅向量对应的超流线分别称为张量场 T 的主超流线和辅超流线。超流线在张量场可视化和路网构建中将起重要的桥梁作 用。 2.1.22.1.2 张量场构建方案 张量场构建方案 我们的设计框架允许用户在某一位置指定想要的路网类型(如前述的栅格型 或辐射型等)，每一指定约束都将转换为一个定义在全局域内的张量元。这些张量 元最终作为约束条件来影响整个张量场，使得在指定位置依旧能保持用户的类型 要求。另一方面为了匹配自然边界约束，如河流和湖泊，我们的设计框架允许自 8 浙江大学硕士学位论文 路网的构建 动产生合适类型的张量元，这些张量元族和用户手工约束产生的张量元将组合在 一起，构成张量场的张量元(约束条件)集合。下面描述怎样根据手工输入和自然 约束转为张量元。 ? 基本张量元构建 栅格型栅格型：城市街区的一重要类型就是栅格状的类型，栅格由正交的两条平行 路网构成，某点处的一个栅格类型等效于定义在这点的一个非退化张量，该张量 满足主方向和栅格的朝向一致。如图 2.1 所示，用户指定点以及该处的主方向 0 p () yx uu ,，我们就能计算出对应张量的长度和角度参数： 22 yx uul+=， () xy uuarctan=。从而得到等效的张量元： = 2cos2sin 2sin2cos )(lpT 辐射型辐射型：城市街区的另一重要类型就是辐射状的类型，辐射由一个中心点、 若干同心圆路网和若干发散路网构成，某点处的一个辐射类型也等效于定义在这 点的一个非退化张量，该张量满足主方向和辐射的同心圆超流线一致，辅方向和 辐射的发散超流线一致。如图2.2所示，用户指定点),( 000 yxp=，我们就能直接 计算出等效的张量元： = )(2 2 )( 22 22 xyxy xyxy pT，这里 0 xxx p =， 0 yyy p = 边界约束边界约束：一般城市道路总是受自然边界约束的影响，典型的如杭州的环西 湖道路(北山路，南山路等)，沿钱塘江道路(之江路，闻涛路等)。为了使张量场能 顺应自然边界曲线的要求，我们先离散边界曲线为折线多边形L，然后做如下处 理：对于线段LAB，我们在A点处按照栅格型指定一个非退化张量，其方向为 AB。如图2.4所示。L的每一线段都对应一个非退化张量，然后所用的张量组合 在一起作为该自然边界的张量元族。上述过程自动进行，使得用户能更集中交互 未受边界影响或者影响很小的区域处的张量。 9 浙江大学硕士学位论文 路网的构建 A B 折线L 图 2.4 自然边界离散处理 ? 全局张量场构建 系统允许用户通过设计张量元集合来创建和修改张量场，张量元和用户在某 点处指定的张量类型(栅格型或辐射型)一一对应。我们构建全局张量场的方法借 鉴文献9张量场设计系统，每一个用户指定和边界约束都转为全局张量场的基， 这些基通过径向基函数求和，使得拟合出的全局张量场能满足用户的指定条件， 如图2.5所示。公式为： = i i ppd pTepT i )()( 2 这里是衰减因子，p是张量场定义域内的任意一点， 对应第i个张量元，是 第 个张量元的位置。对于已经创建好的张量场，系统允许用户再次修改已有张 量元的位置，朝向和影响范围等，甚至删除不满意的张量元。这为用户逐步交互 出满意的张量场提供了方便。通过约束条件创建张量场的方法还有很多，我们采 用张量元组合的策略是因为其简单和直观。 d i T i p i 图 2.5 左：用户交互的张量元约束；右：全局张量场效果图 10 浙江大学硕士学位论文 路网的构建 2.22.2 路网的构建方案 路网的构建方案 在这个章节中，将描述如何构建一个按照用户定制的路网。方法是通过当前 区域已经定制好的张量场。“道路”这个城市化的概念将等同与流场中的“超流线”。 我们的超流线定制方案以文献11的工作为出发点，用以产生均匀布置的超流线 族。对于一个给定的流场，可以产生一族超流线，而对于一个给定的张量场，可 以产生两族超流线，分别对应于张量场的主方向流场和辅方向流场。 但是文献11的工作有两个不足之处， 一是独立的产生主方向超流线和辅方向 超流线使得结果不够联通，如图2.6(a)，尤其发生在辅方向超流线不和任何主方 向超流线相交时。二是在狭小区域内的一些重要点因为没有超流线的延伸，使得 结果有缺失，如发生在河(海)岸凸起的地方等。因此我们又借鉴了文献12的设计 思路。主要是采用交错式的方案减少不联通性，如图2.6(b)。同时提供种子点选 取，使得狭小区域内同样能有路网。 (a) (b) 图 2.6 (a)超流线独立生成11 ； (b)超流线交错生成12 2.2.12.2.1 交错式遍历方案 交错式遍历方案 为处理不联通的情况，我们按照算法2.1(交错式寻迹过程)生成主方向和辅方 向的超流线。 算法算法 2.1： 步骤1：从一个种子点出发，我们沿着主方向及其反方向延伸，具体延伸算 法在单线寻迹方案中描述， 当延伸停止后， 一条对应主方向的超流线就产生好了， 如图2.7(a)，黄点为种子点，黄线为对应超流线。 11 浙江大学硕士学位论文 路网的构建 步骤2：在得到的超流线上计算两个新的种子点，它们满足条件：(i)在当前超 流线上；(ii)和当前超流线的种子点都相距一个间隔参数，如图2.7的(b)中两 个红点。 sep d 步骤3：从新种子点各自出发，我们沿着辅方向及其反方向延伸，当延伸停 止后，两条对应辅方向的超流线就产生好了。类似的我们在这条辅超流线上计算 新的种子点满足(i)、(ii)要求。回到第一步继续。当没有有效种子点时，迭代过程 终止，关于种子点的有效性在2.2.3中描述。 图2.7是这个过程的简单示意，结果是两个交错联通的超流线族，用以表示 一个简单的路网。 (a) (b) (c) (d) (e) 图 2.7 交错式的遍历方案生成路网示意图 2.2.22.2.2 单线寻迹方案 单线寻迹方案 交错式遍历描述的是整个路网的构建方案，具体到一条道路(超流线)的构建， 用的是算法2.2(单线寻迹过程)，这里以一条主方向超流线M为例： 算法算法 2.2： 步骤1：给定超流线M末端位置，计算张量，然后计算其主方向。 考虑到特征向量的符号不确定性， 我们假定前一位置处的主方向为， 选择使 得，令前后保持一致。如果是在起点(即没有前继点)，则随意选择。 p)(pT v E pre V v E 0* prev VE v E 步骤2： 根据和， 用经典Runge-Kutta数值算法18来计算下一插值点。 公式如下： p v E next p 12 浙江大学硕士学位论文 路网的构建 其中为步长，hdxdyyxf/),(=。 得到后，M末端延伸至，回到第一步继续。当满足以下条件之一时， 迭代过程终止： next p next p (1)、M末端穿过整个区域的边界或者河流、湖泊、公园等自然约束边界时； (2)、M末端接近辐射类型的中心时； (3)、M末端回到了起点，构成回路时； (4)、M超出用户指定的最大长度时； (5)、M和一条已经存在的超流线过分接近时，这里参照间隔参数。 sep d 2.2.32.2.3 种子点方案 种子点方案 用于寻迹过程的初始点称为种子点，种子点除了按照交错寻迹方案中提出的 计算方法外，还需要辅助以用户指定，尤其是第一条超流线的起点。种子点一般 不只一个，用户可根据实际情况指定多个。所有的种子点将放置在一个优先队列 中， 每个种子点的权重按照公式来计算， 其中是该种子点位 置，是到最近河流边界的距离，是到最近辐射类型中心点的距离。如此 设置权重是使得靠近河流边界和辐射点的种子点能获得较大的权重，排在优先队 列的靠前位置，从而优先寻迹。另外，也可以在一些重要的位置处显式设置较大 的权重，强制其优先寻迹。每次寻迹都是按照队列的顶端种子出发，寻迹完毕生 成一条超流线后，顶端种子弹出，按照交错寻迹方案计算的新种子点压入到队列 中，并根据计算的权重自动插入到合适的位置。对于已有的种子点，还需要判别 其是否有效，无效的种子点不会用于生成超流线。当满足以下两个条件之一时， rb dd p ee += p b dp r dp )22( 6 43211 kkkkyy kk += + ),( 1kk yxfk = h ) 2 , 2 1 ( 12 k h yhxfk kk += ) 2 , 2 1 ( 23 k h yhxfk kk += ),( 34 hkyhxfk kk =+ 13 浙江大学硕士学位论文 路网的构建 种子点无效： o (1)、超出区域； o (2)、和某条超流线过分接近。 o 2.32.3 小结 小结 本章主要描述了城市道路网络的构建方案，路网构建首先基于一个直观的张 量场构建，张量场的构建又基于张量元约束的集合，其中包括手工编辑的张量元 和自然边界产生的张量元，这些约束条件通过径向基函数插值出全局张量场，使 结果能很好的满足局部条件，同时用户以“所见即所得”的方式进行交互，简单 直观。在张量场构建完毕后，联合算法2.1和2.2来生成路网，不仅使得道路的 延伸符合超流线的轨迹，而且整个路网保持较好的联通性，同时种子点选取方案 的提出，更好的解决了局部区域缺失的情况，使得结果更加完整，如图2.8所示。 (a) (b) (c) (d) (e) (f) 图 2.8 张量场和路网：(a) 栅格约束下的张量场；(b) 栅格和辐射约束下的张量场；(c) 栅格、 辐射及河流约束下的张量场；绿点为种子点；(d) (e) (f)为对应(a) (b) (c)的路网示意图 14 浙江大学硕士学位论文 城市特征设计 第3章 城市特征设计 第3章 城市特征设计 城市是一个自然和社会交融的产物，除了道路和建筑，亘古遗留的自然遗迹 也是城市的重要组成部分，如河流、山脉、湖泊、湿地等。此外，宜居的城市也 需要建造公园、草地、植物园、动物园等，满足人们的生活休闲情趣。一个城市， 如果缺少了这些特征元素，那就像是一个器械工厂，没有人文和韵致。在我们的 系统中，给出了河流，湖泊和公园这几个常见元素的设计。 对于河流，湖泊和公园的设计，我们主要针对其边界设计来做，在以往的工 作中侧重使用边界提取方法(如利用Canny边缘检测)，对已有的一副图像提取其 边界，这给用户造成了额外的负担：一、寻找一副合适的图(基于边界提取往往要 求仅包含所需要的对象，如图像中仅一条河流)；二、转为算法支持的格式。本文 设计的系统就是要避免增加这些的负担，最简单的方式是让用户直接绘制折线段 来近似边界，这样容易修改，但不够光顺。就光顺而言让用户直接手绘边界曲线 是一个不错的选择，但是这提升了美工方面的要求。综合考虑，我们采用三次B 样条插值曲线来做 13，它的好处是用户交互简单，只需要指定几个关键点，结果 则是一条光顺的曲线(连续)，如果对结果不满意，可通过拖拉关键点来修正。 下面给出详细的描述。 2 C 3.13.1 预备知识 预备知识 问题1：给定数据点列，要求做一条三次B样条曲线 3 0 RQ n ii = ， + = j jj ptNtp 24, )()( n ttt 0 (1) 插值这些数据点， 且使得是定义在节点向量上的B样条基， 除端点外，曲线为连续。 )( 4, tN j , 10n ttt 2 C 假定型值点对应的参数为， 由B样条基的局部支柱性可知， 在区间 上仅有 这样四个基非零，根据de Boor-Cox公式易知 i Q i t) 1,+iit t iiiij, 1, 2, 3=)( 4, tN j 15 浙江大学硕士学位论文 城市特征设计 0)()/()()( 1, 11, = +ikiikiikiiki tNtttttN，2 , 3 , 4=k 因而在节点上其实只有三个基函数非零。利用这一性质可使反求控制顶点的 方程组系数矩阵呈三对角型，使计算简捷。在确定参数数值时候，首先取 ， i tt= i t 012 ttt= 21+ = nnn ttt；可使插值曲线通过控制多边形首末端点并切于端 边。其次，为使曲线光顺性较好，可用型值点间的累加弦长法决定内节点值，即 ， 0 0 =t iiii QQtt 11 += ， ni,.,2 , 1= 考察问题1，按照插值条件，在节点处可建立对曲线(1)反求控制顶点的方 程 i t i i ij jiji QptNtp= = + 1 3 24, )()( ， ni,.,2 , 1= (2) 这是有n+3个未知量，n+1个方程的方程组，添加两个端点条件有唯一解，写为 矩阵式即，这里：，。 QNP = T nn pppp),.,( 10, 1+ =P T nn QQQQ),.,( 10, 1+ =Q = 1234 4, 14, 24, 3 14, 214, 314, 4 14, 014, 114, 2 04, 104, 204, 3 4321 )()()( )()()( . )()()( )()()( gggg tNtNtN tNtNtN tNtNtN tNtNtN ffff nnnnnn nnnnnn N 这里，由端点条件决定，我们选择自由端条件： , k f k g)4 , 3 , 2 , 1( =k 11,+n QQ 0)( 0 =tp0)( = n tp 此时 211 hhf+=， )2( 212 hhf+=， 13 hf =，0 4 =f，； 0 1 = Q nn hhg+= 11 ， )2( 12 += nn hhg， n hf = 3 ，0 4 =g，； 0 1 = +n Q 这里 1 = iii tth 系数矩阵的其余基函数取值可由de Boor-Cox公式算出： N 16 浙江大学硕士学位论文 城市特征设计 = + = = + + + + + + ),)()()( , )( )( )( )( )( ),)()()( 1112 2 14, 1 1112 12 1121 12 4, 2 1121 2 14, 3 iiiiiiii iiii iiii iiii iiii ii iiiiiiii tttttttN tttt tttt tttt tttt tN tttttttN 1,.,2 , 1=ni 从而可以唯一求出一个三次样条函数或一条三次样条曲线。如图3.1所示。 图 3.1 黑框点为数据点列，红框点为反求的控制点列，黑色实线为插值的三次样条曲线 3.23.2 特征设计 特征设计 3.2.13.2.1 河流设计 河流设计 河流蜿蜒的河岸线左右着城市的道路和布局。为了更细致的刻画河流边界， 我们将河岸线看做是不相交的两条B样条曲线，分别予以设计，如图3.2所示。 (a) (b) (c) 图 3.2 (a) 河流边界两族点列和对应的两条河岸线；(b)用户方便的交互修改：拖拉数据点； (c)简单交互后的河岸线 17 浙江大学硕士学位论文 城市特征设计 3.2.23.2.2 湖泊和公园设计 湖泊和公园设计 湖泊的边界简单些， 只需要一条B样条曲线来模拟， 但是注意一般是封闭的， 即数据点列是封闭多边形， n ii Q 0 =n QQ = 0 ，首尾相接，如图3.3所示。公园的边 界设计和湖泊如出一辙。 (a) (b) 图 3.3 (a) 湖泊边界点列和对应的湖岸线；(b) 交互后的湖岸线 3.2.33.2.3 特征设计对路网的影响 特征设计对路网的影响 当城市中河流、湖泊和公园的边界定制好后，将按照第二章中的“基本张量元 构建”之“边界约束”中的处理方法，将连续边界转为离散张量元，这些约束条件被 逐个添加到约束集合中，进而影响整个张量场的构建。最后根据此张量场得到的 超流线能够顺应边界走向， 使得路网能很好的包络起河流， 湖泊和公园， 如图3.5(a) 所示。 3.33.3 区域抽取和功能划分 区域抽取和功能划分 当两族超流线都生成完毕后，得到一个路网。城市有了道路后，还要有建筑， 建筑不是放在道路上，而是放在路和路之间的区域内，这就要求从路网中抽取出 城市的区域分块。为了更好的区分城市的区域性质，在分块群内可进一步划分出 区域功能。 18 浙江大学硕士学位论文 城市特征设计 3.3.13.3.1 区域多边形抽取 区域多边形抽取 在已有的路网拓扑图上抽取出内置的多边形区域分两个步骤进行： 算法算法 3.1： 步骤1：通过相交计算，计算任一主方向超流线和任一辅方向超流线的交点， 并假定V是交点集合，E是同一条超流线上相邻两点间的超流线片段的集合，则 得到图； ),(EVG = 步骤2： 从超流线族的一个交点出发， 沿着当前超流线M前行至下一交点， 假定是M和N的交点， 在M中的前继点是， 在N中的后续点是， 判断、三点是否构成逆时针，是则跳到超流线N上，不是则继续沿 着M。无论M还是N，都继续前行至下一交点。再按照上述逆时针判别法做出 选择。 p pp pre pp next p pre pp next p 形象的讲，就是在已经构建好的路网上，从一个路口出发，当遇到路口时能 向左拐就向左拐，不能左拐则继续前行，直至回到起点，那么一块区域就抽取出 来。当遍历完所有路口后，即可抽取整个城市的封闭区域多边形集合。如图3.4 所示。 3.3.23.3.2 区域功能划分 区域功能划分 当抽取出城市的各个多边形区域后，先从宏观上俯瞰下我们城市的功能，这 样会给人一目了然的感觉，我们对城市区域主要划分为住宅区、商贸区、文娱区、 厂房区、地标高楼区和混合区等几个常见区域类型。系统提供了对城市区域群的 功能划分过程，用户可以鼠标选定一个或者几个，甚至一片的多边形们为某一类 型的城市区域，如市中心的几个区域指定为商贸区或者地标高楼区等，靠近河流 沿岸的、湖边的区域适宜人居住，可指定