前言
在上篇中，我们使用Cpp在UE编辑器环境下基于自定义输入的样条生成了道路和交汇路口，本文在此基础上更进一步完成街区生成。在IPCC（Interactive Procedural City Generator）中，街区生成需要选择包围的道路，然后使用ScriptableTool触发创建，需要人为逐步点击。本篇中希望以前文中生成的道路、交汇路口形成的空间自动分割生成街区，完成动态城市基础底板生成的最后一块任务。
本文对应的[项目GitHub](https://github.com/jiadevr/PCGDemo)使用5.6.1源码编译版本创建，需要C++编译环境。
道路生成完善
在生成街区前，我想首先对上文中提到的和街区生成强相关的一些不足的地方进行完善。
交汇路口错位问题
在上文中我们提到交汇路口和道路的错位问题，如下图所示：
这中现象是因为交汇路口末端以直线方式进行了延申，但延申部分没有采样样条，无法和样条结尾部分进行衔接。这个问题同时涉及到Segment长度设置、样条生成终点调节、甚至可能需要改用户输入的曲线，大量的修改会导致整体生成和用户的设计不符。在苦于解决方案时，我又翻出了我们的好样板IPCC，这才发现我在截取参考图时给相邻分段（图中右侧无高亮边缘）也点了预览，而实际的路口仅有一小部分（橘色高亮边缘）。
有了正确的参考，我们可以获知那么问题就很好解决了，既然我们是因为延申区域直线和Spline不符，那么我们可以缩短（删除）交汇路口延伸的距离，然后调整汇入路口末端的位置和朝向实现道路衔接，从而改善这一问题。这涉及到下面几方面更改：
缩短(删除)延申直线。
在UIntersectionMeshGenerator::CreateExtrudeShape()中我们定义了延申背离Intersection交点的SegmentEndpoint的部位为Start，经过测试这部分完全可以不延申，直接使用SegmentEndpoint作为Start依然可以获得比较好的衔接效果。因此我们直接使用RightMid/LeftMid作为新的Start。
在获取交汇路口连接点的时候同时传入衔接点的位置和旋转。
在FIntersectionSegment结构体中添加一个FRotation数据段，用于记录在相交点位的Spline旋转值。
URoadGeneratorSubsystem::TearIntersectionToSegments()构造OutSegments数组时读取样条的Rotation和Location一同写入OutSegments数组对应元素。OutSegments的值会通过UIntersectionMeshGenerator::SetIntersectionSegmentsData()传入UIntersectionMeshGenerator。
在UIntersectionMeshGenerator::CreateExtrudeShape()中构造RoadInterfaceSegments的部分把世界空间旋转值写入ConnectionLocations数组，在调用UIntersectionMeshGenerator::GetRoadConnectionPoint()时传递给Subsystem，再由Subsystem处理后传递给RoadMeshGenerator。
在生成道路时读取衔接点的位置和朝向组成开头/末尾Segment。
在URoadGeneratorSubsystem::GenerateRoads()中读取IntersectionSegment中的旋转值并设置为ConnectionTransform元素的Rotation值
对于有衔接问题的CornerCase，可以设置道路采样延申。这类似IPCC中的Shrink的反向操作，通过修改UIntersectionMeshGenerator对外接口修改交汇点实现部分穿插。或者在生成最终静态模型之后使用UE内的模型调整工具进行细节调整。
因为如果需要可以在计算交点的时候将衔接点向内缩20cm，由于我们生成交汇路口和传给Road生成的数据相互分离，可以在互不影响的情况下完成穿插生成。
道路衔接点完善效果如下：
环形道路首尾衔接问题
在前文的构建流程中，对于环形道路（USplineComponent::IsClosedLoop=true）的首尾连接部分是作为两条路分别构建的。这种方式虽然不会产生接口问题，但它会导致我们的路网描述模型出现漏洞，即“两条不同的道路通过交汇路口相接”出现特例。在实际场景中表现如下：
为了让后续街区建模过程能够统一，我们需要将两条道路合并为一段，也就是将两段道路的连续Segments信息拼在一起。确定了目标，下一步就是确定在哪里插入代码。道路构建所使用的连续Segments信息生成过程中主要依赖：
URoadGeneratorSubsystem::GetContinuousIndexSeries()函数通过传入的交汇路口Segments将所有道路Segments切成连续数组。
URoadGeneratorSubsystem::FindInsertIndexInExistedContinuousSegments()判断衔接点分段应该插入到连续数组的哪个分段组位置。
URoadMeshGenerator::SetRoadInfo()接收衔接点分段和连续分段信息，用于实际构建道路。
在上一篇文章中我们讨论了为什么单独设立函数再次遍历交汇路口的连续数组，另存衔接点信息。到了这里我们在前文的基础上还需要考虑这种分段的合并是否会对衔接点分段的定位造成影响。
在衔接点信息构建的过程中，或者说在我们道路构建的过程中，我们许多算法能高效完成任务存在一个前提，即传入分段数据组内的有序性（类似线段树思想）。在数据有序的前提下，我们只需要比较首尾就可以完成整段信息的比较，避免了逐元素遍历。具体到衔接点信息插入位置中，我们算法的假设是数组元素连续递增，这样我们只需要将插入点和分段首尾比较即可。如果我们在衔接点插入位置确定前就将连续分段数组合并，势必会导致首段内容不符合这一假设，算法就需要重新判断每段的情况，造成算法性能下降。
考虑到一条样条线上交汇路口分段总数比道路分段数总数要小，我们保持这种算法显然能减少遍历的元素数量，获得更大收益。那么可选的方式显然是在衔接点信息构建完成后、在信息传入URoadMeshGenerator前进行处理。在这里我们还有一个特性可以利用，如果头尾能够相接，那么首尾相接处一定不存在交汇口，也就是说连续数组的中首个子数组的首个元素前端和最后一个子数组的尾元素末端一定不存在衔接点信息，在修改衔接点数组时我们可以利用这一特性减少数组变动。代码片段如下：
完成数据调整之后，再次构建道路，就可以发现封闭样条的首尾段已经被我们合并为一条了。
交汇路口排序问题
另外在构建有向图的时候需要交汇路口（作为图节点）连接道路（作为图边）有序，我们在构造路口时候已经进行了排序，但当时文章说时“逆时针”排布。在本文Debug的时候发现实际是顺时针排序，对应专栏内容已经提交了修改，请大家注意。我们这里配合代码和图示再看一下：
FMath::Atan2返回的是弧度制，范围在(-pi,pi]，上部不连续。代码中为其负轴部分+2pi使其变为整个值域连续的[0,2pi]范围，随后根据各点和交点构成的边与X轴正方向夹角顺时针排序。图中左侧代表上文中提到的三种基本道路模型衔接点可视化，均为X轴正方向朝视口下部，Y轴正方向朝向视口左侧，其中点排序为从低位到高位颜色逐渐变鲜艳（黑色R=0->红色R=255）。请务必注意这个顺序，在后面有向图构建时会多次用到。
街区图中的环/面提取
在这里我们首先定义如何划分街区：在我们的常识和IPCC街区构建的步骤中我们都可以看出：街区是由道路、交汇路口围成的面（环），街区不能跨过道路。因此我们可以有如下推断，当街区由超过一条路组成时：
两条不同的道路通过交汇路口相接。
构成街区的道路两端均连接到交汇路口。
构成街区的交汇路口都至少连接两条道路。
根据以上推断，我们需要在其中找到道路、交汇路口构成的环。具体来说，这个问题更接近平面嵌入问题，我们可以从Github找到相关项目
[Lorenzovagliano/GraphFacesFinder-Cpp实现](https://github.com/Lorenzovagliano/GraphFacesFinder);[ammanvedi/planar-face-discovery-TS实现](https://github.com/ammanvedi/planar-face-discovery);[abol-karimi/polygons: Calculating interior faces of a planar graph-JS实现](https://github.com/abol-karimi/polygons)。总体来说是使用经典的双连接边找面思想，即“从一条边出发，到达节点时选择作为入边相邻左侧的边作为下一条边，直到回到起点，遍历路径即为一个面”，在具体查找中使用类似DFS+备忘录的方法。结合我们的实际情况，需要完成下面的步骤：
对交汇路口、道路建立编号映射，创建图容器和边结构。
将交汇路口的每个路口衔接点以顺时针\逆时针排序。
根据排序创建有向图。
使用上面的遍历思想查找面。
查找面算法测试。
对找到的面集合进行进一步处理。
下面对这些的步骤进行详细分析。
建立图结构
图结构文件名为RoadGraphForBlock，声明URoadGeneratorSubsystem和测试类RoadGraphTest为其友元。
首先对于路网这种稀疏图，我们使用邻接表存储可以节省存储空间、便于遍历。邻接表的一维表示有向图中边的出发节点序号，二维有序地存储边结构。边结构需要包括道路序号和有向图中边到达节点序号。邻接表我们直接使用二维数组表示为TArray<TArray<FRoadEdge>>。
确定储存形式后，我们对UIntersectionMeshGenerator和URoadMeshGenerator添加静态变量GlobalIndex，在对象构造的时候对成员变量赋值并++。这里有两个注意点：
在编辑器启动构造CDO对象的时候构造函数会第一次运行，也就是说如果我们初始值设置为0，那么第一个实例化的交汇路口、道路对象GlobalIndex为1。
uint32不能直接用于索引数组，TArray默认需要搭配int32作为数组索引。
基于上面两点考虑，我们在UIntersectionMeshGenerator和URoadMeshGenerator的GlobalIndex声明时使用int32类型，分别使用-1作为初始值，在公共接口中添加GetGlobalIndex接口用于返回。
除了图结构常规的增删查改接口之外，我们这里有两个特定的需求：
边在加入邻接表的时候需要符合特定顺序，即在第二维度指定序号插入。对应函数AddEdgeInGivenSlot()。
能够根据这个顺序，传入当前进入的边返回相邻的下一条出边。对应函数FindNextEdge()。
有对应的接口需求之后，我们颠倒一下顺序，先看创建有向图的部分，这样方便确定我们应该把值传到哪里，上面两个核心接口的实现也会一同给出。
创建有向图
上小节中我们已经确定了需要的API，我们准备从已经构建的Intersection中提取道路排序，因此不需要在图中额外传入节点和边的位置，使得我们的图结构可以更精炼。图结构代码段如下：
我们需要以固定的顺序在邻接表中放置边，因此我们在设置API的时候取消了无向图同时创建双边的接口。又考虑到后续为了便于测试，保留了添加单向有向边的接口。在插入边时的依赖条件是边序号、边出发节点序号、边进入节点序号。所以我们需要一个位置可以拿到连接的两个Intersection的编号。
这时我们很自然的可以想到在衔接点的位置。在为道路分配衔接点时，正好在处理到交汇路口的头尾信息SegmentGroupToConnectionToHead，因为数据同样需要传出处理部分，我们可以在RoadWithConnectInfo相邻的位置创建两个长度为2的数组，在提取头部和尾部时分别获取两个交汇路口的GlobalIndex和衔接ID。在SegmentGroupToConnectionToHead的Value结构FConnectionInsertInfo结构体中额外加入连接道路的ID和具体衔接点的ID，代码片段如下：
然后在路生成第3部分创建URoadMeshGenerator之后调用AddEdgeInGivenSlot()添加边。
已经有了插入模式，下一步就是考虑怎么把数据嵌入到SegmentGroupToConnectionToHead的Value值中。
交汇路口的排序
交汇路口的排序是后续面查找算法的基础，也是本文的核心内容。
在本文第二节中我们提到了道路排序问题，当时的排序主要是为了应对交汇路口的点生成，同样使用了遍历衔接点元素和它相邻的衔接点进行交点计算获得平滑过渡（上篇-交汇路口轮廓生成）。因此我们在先前的代码中已经完成了衔接点的顺时针排序。为了我们的代码后期更易于维护，这里选择直接提取、不重复计算的方式实现。
首先我们需要整理一下信息的传递过程：
从图中我们可以看出，由URoadGeneratorSubsystem生成的IntersectionBuildData是数据的源头，该数据符合顺序要求。但在UIntersectionMeshGenerator创建挤出图形的过程中保存到了MultiMap中，Map容器无法保证顺序，可能会导致数据被打乱。随后URoadGeneratorSubsystem调用GetRoadConnectionPoint传出数据时，可能无法通过数组序号获得正确的顺序。
那么在UIntersectionMeshGenerator一侧，我们需要为FIntersectionSegment添加两个成员变量来记录自己的GlobalIndex(OwnerGlobalIndex)和衔接口ID(EntryLocalIndex)，避免TMultiMap在数据变更过程中的失序，代码片段如下：
URoadGeneratorSubsystem在GeneratorRoads()中获取ConnectionLocations后直接附加到RoadIntersectionConnectionInfo数组中，随后在判断衔接点Segment时遍历RoadIntersectionConnectionInfo，又使用数组内元素构造了FConnectionInsertInfo类型的InsertInfo。
在上面添加IntersectionGlobalIndex和EntryLocalIndex字段后，在这里提取RoadIntersectionConnectionInfo的遍历元素中对应值进行填充。
最后是信息最终提取部分，在衔接信息RoadWithConnectInfo生成部分对SegmentGroupToConnectionToHead遍历，过程中把数据写入ConnectedIntersections和EntryIndexOfIntersections中。此时我们已经获得了对应的数据，可以在创建完URoadGeneratorComp调用图的AddEdgeInGivenSlot()有序添加边。
由此我们提取出了边排序，查找面的基础已经具备，下面进行面的查找。
查找面
遍历图的过程中，我们需要一个数组bVisited用于记录已经已经遍历过的有向边。在我们道路的生成中，双向道路只指定了一个ID道路编号，因此我们需要一种方式将双向边进行区分，以对应不同的bVisited序号。
这里有两种区分方法：记录总的边数目，用最大值进行偏移，即假设总边数为N，那么Index为x的道路两条边的数组序号为x和x+N；或者将两条边相邻排列，即编号为Index为x的道路数组序号为2x和2x+1。
本文选用第二种方式，仿照交汇路口建立时的标记方式，利用交汇路口序号递增的特性，设置当边起点交汇路口序号小于终点交汇路口信号时数组序号为2x，反之为2x+1，在Graph中添加如下函数：
其次我们还需要一个返回类型，按顺序包含遍历时经过的边和顶点。这里定义了结构体包含两个数组成员变量，在遍历时依次记录边和节点。
至此，我们已经有了排序好的图、双向边索引、返回结构，下面可以正式开始遍历图查找其中的面了。根据“从一条边出发，到达节点时选择作为入边相邻左侧的边作为下一条边，直到回到起点，遍历路径即为一个面”的思想，我们可以编写如下代码：
至此我们完成了街区生成中最难的部分，下面我们可以创建测试用例对上面的算法进行测试。
查找面测试
在上一篇文章的结尾我们提到了使用UE的自动化测试可以帮助我们测试需要视觉渲染的复杂逻辑，创建了FRoadGeneratorSubsystemTest类对连续Segment划分和衔接点Segment插入算法进行了测试。这里我们可以继续以这种方式对我们的面查找算法进行测试。
这里我选取了以下两个测试用例，其中橙色代表节点，紫色代表边：
由于我们的图结构中不带有几何信息，我们通过直接输入测试用例顺序的方式调用AddEdge，生成结果使用打印Log方式人工判断，测试类代码及输出如下：
从上面的输出中我们可以看到，除了我们需要的内部面，还会有一个环绕整个图外轮廓的外部面。这个面并不是我们所需要的，需要将其剔除。
额外处理-剔除
筛选有序点组成的多边形最直接的方法是使用面积法，即计算所有面的面积然后通过面积挑选出不需要的多边形。对于不确定形状但顶点有序的多边形我们可以由Shoelace计算其面积，根据计算结果移除其中面积最大的，实现去除外轮廓的目的。
由于图本身没有带有几何信息，这部分需要我们在Subsystem中完成。对应的，需要我们有交汇路口ID到对象的Map以便于索引（同时也创建RoadID和对象的索引）。在交汇路口生成处为Map添加元素后，我们可以编写下面的函数完成剔除：
执行函数后外轮廓被剔除，我们也获得了所有街区的循环信息。至此，我们创建的有向图就完成了它的使命。
街区创建
街区的创建方式和交汇路口相同，需要找到街区的二维轮廓后使用挤出生成几何体。从上面的面查询中我们可以获得围成街区的边和交汇路口ID，通过Map我们可以找到对应的Generator。再次本着复用的原则，我们希望直接从Generator中提取街区生成信息。根据环的信息，我们可以将道路轮廓、交会口过渡段细分点有序串联在一起形成整个街区的轮廓，下面我们分别来看如何把这些信息提取出来。
道路轮廓提取
我们在创建道路时使用的是沿着道路中线进行均匀扫描，每条道路的宽度一定，也就是说我们可以在URoadMeshGenerator通过偏移点获得道路边沿的有序点。因为我们每次都左转，当我们面向道路边方向时，我们需要获取的边沿总在我们左侧。这里再放一次排序的的图，可以看到衔接点随序号变大红色逐渐变鲜艳，我们的邻接表同样基于该序号确定顺序，每次取+1序号。
随后我们需要考虑道路提供的有序点路径是否和环边走向一致，当方向一致时道路扫描点就是我们需要的顺序，当方向相反时我们需要反转道路扫描点。为了实现这一目的，我们可以在URoadMeshGenerator和FRoadSegmentsGroup中创建两个成员变量，用于记录道路构建的起始交汇路口ID和终止交汇路口ID，通过URoadMeshGenerator::SetRoadInfo传入FRoadSegmentsGroup类型参数时进行初始化，提供对外接口GetConnectionOrderOfIntersection()用于比较道路走向。
这部分代码片段如下：
有了道路我们还需要在连续道路之间插入交汇路口的过渡段细分点，我们下面解决这一部分问题。
交汇口过渡段提取
上面我们通过URoadMeshGenerator提取了道路左边线，那么对应的我们也需要对应的交汇路口过渡段边线和其对应。
在附加交汇口过渡段时我们有两种选择，两种优势劣势相反
先加入道路出向交汇路口过渡段再加入道路。
先加入道路再加入道路入向交汇路口过渡段。
方法1的优势在于和邻接表的顺序相同，邻接表本身记录的就是从交汇口A经过道路B达到交汇口C的方式，但在对于起始节点的过渡段获取需要采用相反的算法，一致性比较差。而方法2的困难则是邻接表没有直接标注出进入目标节点时的衔接点序号。
为了获得较好的一致性，这里选择了方法2，并利用“交汇口A出发去交汇口B的衔接点ID和衔接点B到达衔接点A时进入的ID相同”的原理，在图结构中设置如下接口获得道路进入交汇路口时的EntryIndex。
获取EntryIndex下一步就是根据Index获取Entry的左侧过渡段细分点。按照我们之前的设想，我们已经进行了细分点排序，细分点同样采用顺时针排序。为了便于可视化，我们可以设置一个编辑器函数查看对应关系，代码片段如下所示：
运行效果：
看上去很匹配我们的需求，那么是不是所有位置都符合这一规律呢？显然事情不会这么顺利：
那么我们还是需要从根源下手，从上面来看发生单侧汇入的交汇路口特点是和X轴走向相近，这一特性使得在排序时X轴走向的边会天然优先。我们可以用对应衔接点的顺序作为数组顺序，避免排序造成的顺序紊乱。
恰巧在我们的Visited数组中的编号已经帮我们完成了序号的排序工作，其第二层key值就对应了EntryIndex，所以通过下面的代码就可以完成我们的需求：
这里的UIntersectionMeshGenerator::GetTransitionalPoints()提供了对给定衔接点到下一衔接点参数的获取，同时考虑到两个端点和道路给定的衔接点重合，提供了布尔参数在输出时进行过滤。
街区网格体生成
最后我们在URoadGeneratorSubsystem中将所有逻辑连贯起来，按照之前组建交汇路口的原理生成几何体。
生成效果如下：
总结
经过之前的种种努力，我们实现了在UE编辑器中运用四叉树、有向图等数据结构实现了自动道路交点判定、街区面提取等功能，最终创建了城市的道路、交汇路口和街区模型，为后续复刻高级内容提供了基础。在后面的文章中，我会将按照之前所说，结合PCG内容进行城市中建筑、配景、交通网络等内容的生成，一步步完成我们的复刻目标。
以上就是本次分享的全部内容，希望对大家有所帮助！