波函数坍缩算法在数字城市仿真中的应用研究

廖浩宏，韦宇炜，罗立宏

(广东工业大学，广东 广州 510090)

1 引言

所谓的数字城市[1-3]，又称虚拟城市。是旨在借助计算机技术、多媒体三维技术和大数据存储等技术的基础上，综合应用3S技术(GPS全球定位系统、GIS地理信息系统和RS遥感)，将城市的自然资源、社会资源、公共基础设施等相关城市资源整合到系统平台中，并使其可视化的过程[4]。在“十五”期间，国家配合地方与企业共投入45亿人民币，在全国建立了125个数字城市并投入使用，其余145个数字城市建设正在稳步推进。数字城市在城市规划建设、资源管理、公共服务、人口资源调配等诸多领域起到了不可或缺的作用。

20世纪90年代以后，随着计算机的运行速度、算力、存储等方面的大幅提升，数字城市、虚拟漫游、大场景的数据处理和快速绘制优化等技术进入了快速发展阶段。Peter. Lindstrom、Hugues Hoppe等人提出了通过LOD(Level Of Detail)技术[5]构建不同细节层次的模型来减轻计算机对高精度模型数据的存储能力和渲染压力；Yazdizadeh A等人提出使用Texture Mipmap(纹理映射)技术对场景中的纹理数据进行处理[6]，在不影响用户漫游体验的前提下极大程度地压缩纹理贴图的分辨率，进而减轻计算机的渲染负荷；在国内刘波[7]等人通过分层来构造单体建筑的几何模型和纹理，并将分页式场景剔除技术引入到城市场景的图形渲染管线中，提高了计算机运行帧速率；在后续研究发展中，一些学者还通过改进LOD技术、结合二级四叉树索引降低网格搜索时间、利用GPU顶点着色并结合CUDA编码技术对DEM[8-10](digital elevation model)进行数据抽取来降低CUP的占用率，以此优化场景渲染效果。

随着5G技术、物联网等技术的问世，虚拟现实技术、数字化城市被再次推入人们视野之中。数据交换的速度和量化程度也正往高速、海量化的方向发展，虚拟现实所必备的硬件正逐步实现轻量化；而无人驾驶技术也在数字化城市、地理信息系统等技术加持下的取得阶段性成果。目前人们已经可以依托大量的智能软件和数据采集硬件如无人机航测等对现有的现实内容进行数字化、虚拟化快速生成。但是，软件却无法代替人脑进行创作。而现阶段，大量的虚拟仿真项目和市场需求仍集中在虚构的城市场景内容上，海量虚拟数字城市场景的建模和搭建在开发时间成本上仍是一个较为麻烦的问题。因此，上述项目流程仍存在设计流程上的不足。例如在城市道路规划的设计过程中仍需要城市规划师等专业人员进行设计，若能将该算法应用到实现动态生成区域的场景规划，这将使得建设成本和效率将进一步得到改善。

据《艾瑞2018年L4级自动驾驶技术及应用场景行业研究报告》中提到，由于深度学习只有通过大量的数据训练才可以实现对相思目标和道路情况的识别和判断，而由于城市道路交通情况过于复杂，在模拟器上训练的场景有限，当前L4级自动驾驶系统还难以应付城市开放道路上的载客运输作业，最终只能应用于封闭园区如港口集装箱运输、工业区运输作业等[11]。

本文主要研究约束求解驱动图像生成算法WFC(Wave Function Collapse， 波函数坍缩)，并将其应用到数字城市的场景设计和程序生成之中，以此解决上述中城市规划与机器深度学习的虚拟环境设计提供一个新的设计制作思路。

2 波函数坍缩法则

在整个程序的运行中，波函数坍缩算法主要执行了四个关键性任务[12-14]：从输入图像中提取局部模式；将这些模式处理成一个索引，以加速约束检查；通过增加局部熵值来增量地生成输出图像；最后，将整个生成的图像进行输出(以图1作为案例样本)。

通过上述样本案例进行解析，并且给出以下伪代码：

defn Run()：

PatternsFromSample()；

BuildPropagator()； ∥构建传播算子

Loop until finished：

Observe()； ∥观察

Propagate()； ∥传播

OutputObservations()； ∥输出观测

2.1 构建传播算子

引入一种“传播算子”(或称为模式)的概念，这个传播算子是一种特殊的、配置唯一的平铺板块。在简单的平铺算法中，传播算子被认为是线性的约束关系；在重叠的算法中，传播算子可以通过观察被原图像所推断出来，并通过设置一组从图像中构建出来的子图像放置到N*N的模式索引数组中，并且还应考虑其对称性和旋转不变性。

图2 通过样本生成3*4结构图

如图2所示，当N=2时，可以从样本图像中构建出12个唯一模式，由于红色和白色像素在原图像中没有相邻的情况，所以没有该类组合模式。采样的图像是周期性的平铺，这是可选的。在模式设计中，BuildPropagator()创建了一个索引数据结构，用来描述那些可以放置在彼此附近的方式。对于重叠的版本，索引包含提前计算好的答案，这个答案回答了当一个放置在另一个特性的x，y偏移量时，两个模式之间是否匹配的问题。(当N=3时，有(2(N-1)+1)2=36 个偏移量需要考虑。)对于平铺的版本，这个索引可以直接从设计器被指定的平铺关系中创建出来。在任何一种情况下，它在模式之间创建了一种稀疏的关系。

在核心增量生成的过程中，决策变量(网格位置)被重复选择然后进行被分配。在约束求解过程中，除了当前部分分配之外，求解器通常持续追踪未分配变量的剩余域，它是一个被存储在一个名为wave的表中，松散地引用了量子波函数。而表的条目，称之为系数，是一个记录算法是否仍然可以将给定的模式分配给给定的位置的布尔值。波函数中所有的系数被初始化成一个真值，这相当于说每一个决策变量都有一个未还原的初始域。分配和传播都有助于缩小变量的域。

2.2 最小熵原理驱动解析

Observe()的目的是用最低的非零熵来识别网格上的位置。这里的熵所对应于波的解释，这意味着在每个网格位置上找到模式的概率分布。熵最低的细胞是传播后最紧或最小域的变量。在约束求解中，在约束求解中，选择最约束变量或等效最小剩余值变量(MRV)的启发式方法是最好的。在此设置模式的的生成概率为，则通过以下方法计算模式板块的熵值

(0≤λ≤4∩λ≤N*)

选择具有最低的非零熵(或最小的剩余值)的位置的策略期初是任意的。如果想在不回溯的情况下最大限度地优化发现整个任务，应该让做的每一个选择都最大限度地增加总任务的数量，这与目前的选择时一致的。这就避免了排除(可能极为罕见的)合法的全部分配，假设这些转让是在其它全部转让之间分配的。如果剩余的总任务的数目近似为未分配的变量的域的大小的乘积(换句话说，假设其余的选择时独立的)，然后用最小域分配位置(最低熵/最小剩余价值)，在分配之后让产品价值最大化。为了建立另一个松散的物理联系(这一次与统计力学)，熵启发式是最大熵原理的实现之一。

由于在所选的位置有多个有效模式——或者在上一个循环中已经将其设置为零熵——需要在这些模式中选择其中一种。其中一个模式是选择一个随机样本，加权方式是模式在输入的图像中出现的频率，这实现了模式的出现在输出中的分布与输入中的分布相似。

2.3 变量坍缩约束

一旦观察到一个位置(一个变量已经被分配)，它将被标记为需要在波中更新的位置(作为一个通过约束传播开始更新变量域的地方)。像AC3，WFC传播过程确保了如果在相关的变量域中存在一个有效值，这个变量只出现在变量域中，这就可以满足这些变量上的约束可以被满足。更新一个变量的域意味着需要潜在地更新所有相邻变量。因此，传播是通过一种算法进行的，从图形的角度可以是作为flood填充方式。

每个观测的最终结果至少确定了位置和尽可能地降低了周围区域的熵。

图3 观测坍缩范围逐渐扩大

一旦系统中没有更多的熵(所有变量只有一个单例域)，可以输出最终生成的图像。此外，可以利用一个优势，就是每一个单元都有一个潜在的状态数组，并且在每个观察和传播周期之后输出如图3所示的一个局部完成的图像，那么以此就能生成一张指定的完美的视觉标记图。

2.4 LCV输出观测

defn OutputObservations(coefficient＿matrix)：

Foreach cell：

Set observed value to the average of the color value of this cell in the pattern for the remaining valid patterns；

Return the observed values as an output image；

上述伪代码中可以看出，可以将WFC视为一种约束求解算法。它使用最小的剩余值(MRV)启发式地选择要决定的下一个变量，对于决策上，它使用了根据原始图像中的分布选择模式的启发式方式。另一种可供选择的启发式就是众所周知的最小约束值(LCV)选择启发式(LCV也可以由最大熵原理驱动)。然而，它很难预测这种启发式选择对内容生成的影响。

3 算法的改进系统架构设计

本文通过改进波函数坍缩算法，将其引入的虚拟城市场景的构架中。延续了Maxim Gumin算法中的思想，在Unity程序中将整个场景划分成若干个 width * length * height的大小的盒子，称之为“Slot”，用于将生成的道路板块模型插入到该Slot中，进而拼接成完整的场景地图[15]。

在第一步构建传播算子环节中，通过解析构建的道路模型网格拓扑结构，生成模块与模块之间的指纹，用于对相邻两个道路模型之间是否可以匹配的依据，使其在后续的场景生成过程中可以生成符合逻辑的平铺模式，并且将其提取成合法的模式相邻的索引(即Gumin所说的传播)以及填充算法的网络拓扑结构。

1 { assign(X，Y，P)：pattern(P) } 1 ：-cell(X，Y)．

：-adj(X1，Y1，X2，Y2，DX，DY)，

assign(X1，Y1，P1)，

not 1 { assign(X2，Y2，P2)：legal(DX，DY，P1，P2) }．

接下来，在观察和传播两个阶段中，通过设置板块生成的概率、通过的方向、封边等要素结合解析出其个体熵值，再计算每一个Slot可能插入的模块群中解析出综合熵值，以此分配影响最低的Slot；系统一旦观察到该分配的位置，它将被标记为中心点对周围的Slot进行衍生分配，向外进行坍缩生成。一旦系统中没有更多的熵，即可生成最终的场景地图。

4 数据存储和调度优化

受到计算机硬件设备的性能限制，对于大型场景的虚拟漫游仍然无法一次性渲染出来，即使渲染出来运行帧速率也是非常低，这就必须对程序中的海量模型数据进行分块管理以及根据玩家的位置进行动态调度加载。程序对模块数据的管理方式以及动态调度方法对场景的浏览效果非常重要，合理的模块数据管理方式和动态调度方法不仅可以使得程序更好地查找和加载场景，而且可以在运行中保持优质的画面效果。本文针对Unity引擎对建筑道路进行模块化设计制作，并且将道路、高架桥拼接模型信息进行有机存储，并根据玩家所处的视点位置对模型进行动态加载。

4.1 场景数据的分块组织管理

合理的场景数据管理形式和高效的数据检索方式[16]，能够有效地在进行场景漫游的时候快速有效地生成区域模块。

从场景体素化的角度出发对地图的剪裁进行考虑，共制作了147个道路组件，包括街道路口，高架桥等模型，旨在搭建一个无限边界且具有两层高架桥的数字虚拟城市。每个组件与组件之间用相同的键值(即配对指纹)进行标记，在场景生成时即可生成符合逻辑的模块。

世界场景的区域块chunk及其子级和每个组件模块module之间的关系如图4所示。每个模块有属于它们的相关属性和每个面对应的配对指纹信息；而世界地图从依据chunk进行剪裁，往下到Room、Slot等小模块进行细分。将整个世界场景划分为若干个Slot，接着将所有的module模块元素往作为中进行穿插，最后即可生成一个符合现实逻辑的虚拟城市。

图4 数字城市场景地图生成流

● Chunk是场景中最大的数据模块，主要负责管理Slot插槽矩阵、通道、房间和模型渲染网格等信息；

● Slot插槽。将整个虚拟场景划分为三维网格矩阵，每个单元称之为Slot，在进行坍缩的时候将每个模型的信息坍缩确认之后则放入Slot之中；

● Module主要负责存储模块的预设信息(如：截面信息、配对指纹等)和邻接模块预设等；

● FaceDetails 模块面的详细信息；

4.2 场景数据的动态调度

当实现对整个地图的自动化生成之后，开始着手对系统化的运行进行动态加载，以防止城市模型数据过多而导致的运行卡顿，提高虚拟漫游的浏览效果。在这里采用基于视点的动态加载策略方案[16]。

如图5所示，将正式大数字城市的场景数据划分成三个部分，视点关注区、预可见缓冲区和数据局缓冲区。其中视点关注区是3*3个由100为单位的形成的模块矩阵，经过一些建筑物的遮挡关系原理玩家在虚拟漫游场景中的视线点几乎在该区域之内；而外围的16个预可见缓冲区则是对玩家进行下一步移动的时候的预处理区域：划分场景的最中心100为移动界限，通过unity的Update事件函数来更新玩家在世界坐标的位置，程序通过开启一个新的线程，每50毫秒对玩家的位置信息和中心边界的位置关系进行判断，当玩家超过当前的边界时则会开始发生三者数据区域的数据交换和更新。

图5 数据动态调度变化

建立预可见缓冲区数据的最大的优点就是为了保证关注区周围的场景数据都已经被绘制出来，解决玩家视点方向随机性所带来的的可能会出现视野穿帮的问题，同时也优化了场景中可能因为单个模块的加载时间太长而出现了卡顿的浏览问题，保证平滑过渡的漫游体验。

5 实验数据测试

本研究测试输出的硬件环境如下：

图6 在算法生成的数字场景中漫游

● 硬件环境

笔记本：华硕飞行堡垒7

处理器：Intel(R) Core(TM)i5-9300H 2.4GHz

内存： DDR4 2666MHz 8GB

显卡：NVIDIA GeForce GTX 1650 独立显卡4GB

硬盘空间：512GB

本文基于Unity物理引擎平台作为内容开发工具，结合波函数坍缩算法进行研究，并设计实现了汽车驾驶的第三人称城市漫游系统[17]。通过实践与数据测试，主要解决大型场景搭建耗费成本高，且在虚拟漫游平台加载缓慢，帧率不稳定等问题。这里主要从以下两方面来进行数据测试，验证其算法的可行性与优越性。

5.1 不同方式制作大场景所需时间对比

上述表中在相同的模型贴图制作流程的情况下，进行了算法生成的方式和传统手动搭建的两种方式中相关流程开发时间的比对，发现对于大型虚拟场景的制作开发尤其是无边界数字城市场景而言，通过波函数坍缩算法生成的场景在开发时间成本上有着其本身优越的特性，并且这个优势随着场景的增大而不断凸显。

表1 传统搭建流程与算法生成成本数据对比

5.2 不同量级场景下运行性能优化数据对比

在Unity的Profiler性能测试工具中对实现的系统进行数据性能测试[18]，并最终汇集成数据表格和统计图。

表2 性能优化效果对比

图7 不同量级场景下运行帧速率对比

上述表中通过使用相同的模型，用不同的方式去搭建虚拟场景，通过在运行过程中对帧速率、DrawCall、以及模型面片数等性能指标进行数据比对，发现在传统的搭建方式中，虚拟漫游的运行性能与场景的大小成反比，当场景达到1500m*1500m的大小时，漫游的运行速率掉到了10帧以下，并出现了卡顿等现象；而通过算法生成的场景在越大的场景中甚至是无边界场景中展现出了算法的优越性，稳定保持在30FPS左右。

6 结语

本文主要针对Unity物理引擎，使用波函数坍缩算法，对目前城市规划设计领域传统设计模式开发时间长、耗费精力大、成本投入高等问题以及针对于深度学习的无人驾驶所依托的海量的训练场景面临的场景搭建的等问题进行研究和实现。经过实验和分析对比，得出以下结论：

1)通过研究波函数坍缩算法求解生成制作虚拟漫游系统，通过与普通人工搭建场景进行数据对比可以得出：该算法在对大型场景尤其是无边界场景的制作时有着巨大的优势；

2)结合动态调度算法，可实现对大规模分块数据进行动态管理研究，可优化系统的运行性能。通过不同量级场景下未做优化处理的数字场景进行数据对比证明了该算法对大型场景搭建的便捷性和漫游的优越性的提高。