0HAL编号：tel-011479170https://theses.hal.science/tel-01147917v202017年5月22日提交0HAL是一个跨学科开放存取存储库，用于存储和传播科学研究文件，无论其是否已发布。这些文件可能来自法国或国外的教学和研究机构，也可能来自公共或私人研究中心。0跨学科开放存取存储库HAL旨在存储和传播法国或国外教育和研究机构、公共或私人实验室发布或未发布的研究文档。0交互式虚拟世界设计：将程序建模与直观用户控制相结合0Arnaud Emilien0引用此版本：0Arnaud Emilien. 交互式虚拟世界设计：将程序建模与直观用户控制相结合。图形学[cs.GR].格勒诺布尔大学，2014年。英文。NNT: 2014GRENM067. tel-01147917v20论文0获得学位0格勒诺布尔大学博士学位，由格勒诺布尔大学和蒙特利尔大学共同培养，专业：数学-计算机0部长令：2006年8月7日0ArnaudEmilien提交0由Marie-Paule Cani指导，PierrePoulin共同指导0在Jean Kuntzmann实验室和EDMSTII博士学院准备0蒙特利尔大学计算机和运筹学系0交互式创建虚拟世界：结合程序化建模和直观用户控制02014年12月10日公开支持的论文，评审委员会成员：0Bedˇrich Beneš，普渡大学副教授，评审 StéphaneMérillou，利摩日大学教授，评审 JoëlleThollot，格勒诺布尔国立理工学院教授，考官 VictorOstromoukhov，里昂第一大学教授，考官 EricGalin，里昂第二大学教授，考官 Marie-PauleCani，格勒诺布尔国立理工学院教授，导师 PierrePoulin，蒙特利尔大学教授，共同导师iii0简历0虚拟世界的复杂性不断增加，传统的建模技术难以满足生产这种场景所需的数量约束。程序化生成技术利用算法自动创建复杂的虚拟世界，但通常不直观，因此通常只适用于经验丰富的艺术家。事实上，这些方法为用户提供了很少的控制，并且很少是交互式的。此外，用户通常需要通过一系列试验和错误来找到其众多参数的值，直到获得满意的结果，这通常是耗时且繁琐的。本论文的目标是将程序化生成的创造力与直观用户控制相结合，以提供新的交互式虚拟世界建模方法。首先，我们提出了一种在崎岖地形上程序化生成村庄的方法，其中元素受到环境的严格约束。然后，我们提出了一种基于精细用户控制和自动生成一致内容的瀑布交互建模方法，以满足水文和地形的要求。接下来，我们提出了一种通过草图编辑地形的方法，其中地形的特征元素如山脊线被分析和变形以匹配用户绘制的复杂轮廓。最后，我们提出了一种绘画隐喻，用于创建和交互式编辑虚拟世界，其中使用矢量元素合成技术自动化场景的变形和编辑，同时保持其一致性。v0摘要0虚拟世界所需的复杂性正在不断增加。传统的建模技术难以满足生产这样场景所需的约束和效率。程序生成技术使用算法自动创建虚拟世界，但通常对有经验的程序员保留，因为这些方法对用户提供的控制较少，很少是交互式的。此外，用户通常需要找到几个参数的值。用户只能通过一系列的试验和错误来间接控制，这使得建模任务变得漫长和乏味。本论文的目标是将程序建模技术的强大功能与直观的用户控制相结合，实现设计虚拟世界的交互式方法。首先，我们提出了一种在任意地形上进行村庄程序建模的技术，其中元素受到严格的环境约束。其次，我们提出了一种瀑布景观程序建模的交互式技术，将直观的用户控制与根据水文和地形约束自动生成一致内容相结合。然后，我们描述了一种基于草图的交互式技术，用于编辑地形，其中地形特征被提取和变形以适应用户的草图。最后，我们提出了一种虚拟世界创建和编辑的绘画隐喻，其中利用基于示例的合成矢量元素的方法来自动变形和编辑场景，同时保持其一致性。vii0致谢0首先，我要感谢我的导师Marie-Paule Cani和PierrePoulin，感谢他们在整个博士期间给予我的热情、耐心、建议和科学上的帮助。我还要感谢他们花在审阅这篇论文上的时间。0我还要感谢许多与我合作过的人，Flora Ponjou Tasse，Derek Nowrouzezahrai，AdrienPeytavie和Eric Galin。我特别要感谢我的办公室室友AdrienBernhardt，在我博士第一年给予我的所有讨论和帮助。非常感谢UlysseVimont，在我博士最后一年成为我的办公室室友和合作者，在我最后的研究工作中提供了非常宝贵的帮助，并在日常生活中给予了我支持。还要感谢Élie Michel，我很高兴在他的实习期间指导他。0我还要感谢格勒诺布尔IMAGINE团队的所有成员，感谢他们的接待和对团队氛围的贡献。感谢我在LIGUM度过了美好一年的加拿大朋友，我在那里度过了一个美妙的一年，也通过所有的季节发现了这个国家。感谢Benjamin，Cédric，Rémi，Aude，Gilles-Philippe，Jonathan，Eric等人在这段时间内对我的支持，和我度过了美好的时光。0最后，我要向我的家人表示衷心的感谢，感谢他们始终如一的支持，没有他们，这一切都不可能实现。最后，特别感谢Aurélie，她一直在我身边，并在这三年的博士期间给予我无尽的阳光。2.1.3Plants and Ecosystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.1.4Urban Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.1.5Conclusion on Procedural Modeling. . . . . . . . . . . . . . . . . . . . .132.2Example-based Modeling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142.2.1Texture Synthesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142.2.2Point Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152.2.3Arrangement Synthesis. . . . . . . . . . . . . . . . . . . . . . . . . . . .152.2.4Inverse Procedural Modeling. . . . . . . . . . . . . . . . . . . . . . . . .162.2.5Conclusion on Example-based Modeling . . . . . . . . . . . . . . . . . . .172.3Interactive Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172.3.1Sketch-based Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.3.2Interactive Procedural Modeling. . . . . . . . . . . . . . . . . . . . . . .212.3.3Deformation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222.3.4Conclusion on Interactive Modeling. . . . . . . . . . . . . . . . . . . . .232.4Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .233Procedural Generation of Villages on Arbitrary Terrains253.1Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .283.2Growth of a Village Skeleton. . . . . . . . . . . . . . . . . . . . . . . . . . . . .293.2.1Growth Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293.2.2Dynamic Interest Maps. . . . . . . . . . . . . . . . . . . . . . . . . . . .303.2.3Aggregation-based Building Seeding . . . . . . . . . . . . . . . . . . . . .333.2.4Connection to the Road Network . . . . . . . . . . . . . . . . . . . . . . .343.3Land Parcel Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .353.3.1Road Conquest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .363.3.2Corner Conquest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .363.3.3Anisotropic Land Conquest . . . . . . . . . . . . . . . . . . . . . . . . . .363.3.4Parcel Simplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37ix0目录0目录 ix01 简介 102 虚拟世界建模：现状 502.1 虚拟世界的程序建模 . . . . . . . . . . . . . . . . . . . . . . . . . 702.1.1 地形 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702.1.2 水体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.3.5Building Footprint Computation . . . . . . . . . . . . . . . . . . . . . . .383.4Geometry Generation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .383.4.1Open Shape Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . .383.4.2Geometry Generation Algorithm . . . . . . . . . . . . . . . . . . . . . . .393.5Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .403.6Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .464Interactive Procedural Modeling of Coherent Waterfall Scenes474.1Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .504.1.1Two-level Classification for Running Water. . . . . . . . . . . . . . . . .504.1.2Processing Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .524.2From User Input to a Coherent Hydraulic Graph . . . . . . . . . . . . . . . . . .544.2.1Controller Network Creation. . . . . . . . . . . . . . . . . . . . . . . . .544.2.2Hydraulic Graph Generation. . . . . . . . . . . . . . . . . . . . . . . . .554.3Waterfall Network Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .574.3.1Subdivision and Adaptation to Terrain . . . . . . . . . . . . . . . . . . . .574.3.2Waterfall Network Construction. . . . . . . . . . . . . . . . . . . . . . .584.4Terrains Adapting to Waterfalls . . . . . . . . . . . . . . . . . . . . . . . . . . . .594.4.1Integration Mesh Generation. . . . . . . . . . . . . . . . . . . . . . . . .604.4.2Constraint-based Terrain Deformation . . . . . . . . . . . . . . . . . . . .604.4.3Procedural Decoration . . . . . . . . . . . . . . . . . . . . . . . . . . . . .624.5Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .634.6Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .685Sketch-based Terrain Editing695.1Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .725.2Sketch Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .735.3Feature-based Terrain Deformation . . . . . . . . . . . . . . . . . . . . . . . . . .755.3.1Feature Detection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .755.3.2Stroke-Feature Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . .765.3.3Terrain Deformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .785.4Lowering Protruding Silhouettes. . . . . . . . . . . . . . . . . . . . . . . . . . .795.5Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .805.6Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .826Worldbrush: Painting and Deforming Virtual Worlds using Example-basedSynthesis856.1Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .886.2Statistical Point Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .906.2.1Analysis of Point Distributions . . . . . . . . . . . . . . . . . . . . . . . .916.2.2Probability Density Function . . . . . . . . . . . . . . . . . . . . . . . . .946.2.3Synthesis using Monte Carlo Markov Chain . . . . . . . . . . . . . . . . .946.3Statistical Graph Synthesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .956.3.1Arc Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .956.3.2Arc Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .956.4Synthesis-based Deformation. . . . . . . . . . . . . . . . . . . . . . . . . . . . .966.4.1Copy-paste. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .966.4.2Move. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .986.4.3Seamcarving-based Scaling. . . . . . . . . . . . . . . . . . . . . . . . . .98x06.4.4 颜色插值和渐变 . . . . . . . . . . . . . . . . . . . . . . . 9906.5 基于合成的绘画 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.5.1 画笔 . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 10206.5.2 模糊... 10306.6 初步结果和讨论... 10306.7 结论... 10607 结论 1070用户研究 1110A.1 选择最佳变形... 111 A.2 填补空洞... 117 A.3 剪辑场景... 119 A.4 变形场景... 1200参考文献 1210xi10第1章0介绍0虚拟世界建模是计算机图形学中的一个重要主题，因为相关的技术和结果被广泛应用于视频游戏、电影和模拟器中。由于不断增长的需求，虚拟世界的制作成本越来越高，因为它们的大小和细节数量正在增加。事实上，传统的建模软件中所有的任务都是由艺术家“手工”完成的。例如，如果一个艺术家想创建几平方公里大小的城市，那么由于必须制作的细节数量，这个过程将是漫长而乏味的。这对于景观也是如此，它们理想地应该将任意地形与河流、森林、植物、岩石、草等结合起来，并且适应城市和非城市的定居点，包括道路、房屋、围栏、植物等。0程序建模依赖于使用算法自动生成内容。毫不奇怪，近年来它一直是研究的重点。这些方法在虚拟世界建模领域越来越多地被使用，例如生成地形、植被、河流网络甚至城市。然而，它们通常不直观，因为它们很少是交互式的，并且提供的控制很少。此外，它们是由艺术家设置的参数间接控制的，通常通过一系列令人沮丧的试错过程来调整，直到获得期望的结果。0为了克服间接控制的问题，这是采用这种方法的一个主要障碍，交互式程序建模领域在过去十年中受到越来越多的关注。它涵盖了从提供一些软控制程序的方法，例如通过在地图上绘制感兴趣的区域，到高度交互式的方法，其中交互类似于传统建模工具的交互，例如用户在留给软件生成树的树枝和叶子的同时勾画树的形状。0逆向程序建模的概念已被引入，用于对自动生成给定类型结果的正确设置进行自动确定。这个原则类似于图像和纹理合成的工作，并旨在减少甚至消除寻找良好设置的繁琐的试错过程，甚至算法规则。然而，随着结果在相互连接的组件中变得越来越复杂，目前还没有提出逆向程序建模虚拟世界的通用方法，甚至可以质疑为艺术家提供什么样的界面来满足所有愿望。20虚拟世界建模中的开放问题0设计用于建模虚拟世界的交互式方法面临许多挑战：0• 方法应该处理虚拟世界的复杂性和相关的环境约束，同时对非专家来说易于使用；0•方法应该提供智能用户控制，使用户能够专注于粗糙或精细的编辑愿望，而方法自动接管冗长而繁琐的任务；0• 方法还应该是实时的，并提供尽可能接近最终结果的结果，以便在交互建模会话中使用；0• 方法应该在其自动算法中自动找到要使用的设置。0贡献0在整个论文中，我们试图回答以下问题：0“我们如何改进虚拟世界的交互设计，以更好地满足用户需求和计算机能力？”0我们通过四个系统研究这个问题，结合了不同级别的直观用户控制和各种程序生成策略。这项工作的贡献如下：0•首先，我们将研究未被充分研究的程序化村庄建模问题。这项工作的主要贡献是将村庄适应多种环境约束，同时易于用户配置。我们的方法能够在任意地形上生成各种类型的村庄，从山间小村到渔村，尽管设置的数量有时会令人不知所措。然而，用户控制仍然是间接的，保持在程序化建模系统中的标准控制附近。0•其次，我们提出了一种用于交互式程序化建模瀑布风景的方法。这项工作允许用户在现有地形上交互式创建粗糙的瀑布网络，而算法会自动生成详细的风景，并处理环境约束和流体力学有效性。这个过程导致地形自动适应瀑布，瀑布适应地形。0•第三，我们介绍了一种交互式的第一人称基于草图的地形编辑方法。使用户能够从第一人称视角绘制山脉轮廓，我们的算法分析并变形现有地形以匹配所绘制的曲线。这个过程尽可能保留原始地形的细节和合理性，但将其变形以满足所绘制轮廓的约束。0•最后，我们提出了一种更通用的用于建模虚拟世界的交互式绘画系统，它依赖于基于示例的合成。用户使用类似现代绘画系统的交互来创建和编辑复杂的矢量场景。同时，算法通过分析当前场景中的示例的不同属性，并无缝生成满足相似性约束的结果，自动保持场景的一致性，并加速许多其他繁琐的任务。• Chapter 3: This chapter is an extended and updated version of an article presented atthe Computer Graphics International ’12 conference and published as a special issue ofjournal The Visual Computer [EBP∗12].• Chapter 4: This chapter is an extended version of a paper first presented at the nationalconference AFIG ’13 [EPCV13] and then selected for an improved version in French in theassociated journal REFIG [EPCV14a]. A further improved version has been published inthe journal Computer Graphics Forum [EPCV14b].• Chapter 5: This chapter details a collaboration with Flora Ponjou Tasse, Ph.D. studentat Cambridge University, during her visit to Inria Grenoble. This work was presented atthe conference Graphics Interface [TEC∗14a]. It was selected and an extended versionwas published in the journal Computer & Graphics [TEC∗14b].• Chapter 6: This chapter presents our most recent results, and we expect to submit anassociated paper soon. As such, the reader should be aware of less-polished results, andshould look forward to the publication.30文件结构0本文分为五个主要部分。首先，在第 2章中，我们介绍了用于虚拟世界设计的程序化和交互式建模技术的调查。我们涵盖了自然风景的自动程序化建模、交互式程序化建模、基于草图的建模、基于示例的合成和逆向程序化建模。在第 3章中，我们详细介绍了我们在任意地形上进行程序生成村庄的方法。在第 4章中，我们介绍了我们用于交互式建模连贯瀑布风景的方法。在第 5章中，我们描述了我们用于基于草图编辑地形的方法。在第 6章中，我们介绍了我们用于交互式绘制虚拟世界的方法。最后，我们总结了这项工作，并讨论了未来工作的一些途径，根据我们对所描述的所有系统的各种经验进行了扩展。0相关出版物0本论文的三章内容先前已作为出版物发表。它们已经略作修改，以更好地融入这一统一的文档中。它们是：Chapter 2Modeling Virtual Worlds:State of the artContents2.1Procedural Modeling of Virtual Worlds . . . . . . . . . . . . . . . . . . . . . .72.1.1Terrains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.1.2Water Bodies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.1.3Plants and Ecosystems . . . . . . . . . . . . . . . . . . . . . . . . . . .112.1.4Urban Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.1.5Conclusion on Procedural Modeling . . . . . . . . . . . . . . . . . . . .132.2Example-based Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.1Texture Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142.2.2Point Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152.2.3Arrangement Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . .152.2.4Inverse Procedural Modeling . . . . . . . . . . . . . . . . . . . . . . . .162.2.5Conclusion on Example-based Modeling . . . . . . . . . . . . . . . . .172.3Interactive Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.1Sketch-based Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . .182.3.2Interactive Procedural Modeling. . . . . . . . . . . . . . . . . . . . .212.3.4Conclusion on Interactive Modeling . . . . . . . . . . . . . . . . . . . .23502.3.3 变形 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2202.4 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23670本章介绍了虚拟世界建模的最新技术。虽然建模本身是一个庞大的研究领域，虚拟世界可以包括几乎任何东西，但我们不能假装涵盖所有与建模相关的工作。然而，我们尝试讨论与虚拟世界及其常见内容的特定工作大部分相关的内容。我们首先介绍了虚拟世界的程序生成技术的综述。我们丰富了这一综述，介绍了基于示例的合成的主要概念，并介绍了逆向程序建模的文献。我们通过介绍各种交互建模方法来总结这一最新技术，包括交互式程序建模、基于草图的建模，以及非程序化背景下形状变形方法的简要综述。02.1虚拟世界的程序化建模0程序化建模涉及使用算法自动创建内容。这种方法已经成功地应用于许多领域，如创建纹理、几何、动画，甚至声音。在本文中，我们重点关注为虚拟世界生成设计的程序化方法。已经为特定类型的虚拟世界对象开发了许多类型的程序化方法，包括地形[GGG�13]、植物[LRBP12]、城市[CEW�08]、道路网络[GPGB11]、建筑[LWW08]等。在本节中，我们进行了简要调查，以说明最常见的方法家族。有关更多详细信息，请参阅专门讨论该主题的更完整的现有技术[STBB14]。请注意，在本节中，我们仅详细介绍了用于虚拟世界建模的自动化方法。逆向程序化建模技术和交互式程序化建模技术分别在第2.2.4节和第2.3节中详细介绍。02.1.1 地形0在本节中，我们回顾了地形的主要数据结构和实时渲染技术，因为它们在支持和约束虚拟世界的交互建模中起着关键作用。然后我们回顾了如何进行程序化生成。02.1.1.1 数据结构0地形的实时渲染对于几乎所有交互式应用程序都是一个关键问题，因为地形构成了景观的主要元素。我们在本节简要回顾了用于实时表示和渲染地形的主要方法。0高度场。地形主要以高度场的形式表示，即每个单元格在给定的2D位置存储高程。这种表示的简单性和效率使得它在交互式软件中很受欢迎。此外，它非常适合GPU，即使对于非常大的地形（例如，[LH04，BN08，DIP14]）。高度场的主要局限性在于它们无法表示在同一2D位置具有多个高度值的复杂形状，例如洞穴、拱门和悬崖。0体素。体素表示在3D网格中存储体积密度值。它们可以用来模拟具有任意拓扑结构的复杂地形[Gei07]，但是存储成本高，表面提取过程昂贵。此外，地形主要是平坦的，大部分存储的数据是不相关的。为了减少这个问题，引入了结合高度场和体素的混合模型[Cry09]，但需要繁琐的手动设置。
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
