[实验][PCG]使用Shapely计算路口边缘
目标与效果根据Landscape Spline曲线，计算并自动放置预制好的Spline Mesh Blueprint Actor。并且配置正确参数。
Shapely计算路口边缘
https://www.zhihu.com/video/1497542024220315648
生成前
生成后
可同时处理多个交叉口，以及多条路的交口
使用Matplotlib进行初步的Debug
关于Python和Shapely
目前，在Unreal里直接使用Houdini Engine会面临着配置参数繁琐，计算时间长，自动化程度低等等问题。而Unreal蓝图又缺乏比较方便的计算几何库。
UE4.27后已经开始支持Python3。Unreal Python可以调用所有暴露给蓝图的方法，同时拥有庞大的第三方库。因此我想尝试使用Python来处理部分PCG生成的工作。
Shapely是Python的第三方计算几何库，虽然面向的是GIS等地理的计算方法，但他的功能强大且丰富的点线面计算方法都是通用方法，依然可以应用在通用几何计算中。
Shapely目前还只能处理2维模型，但可以保留Z轴。但很多方法中Z轴参数并不参与计算。而本例中也无需考虑立交桥等立体交通形式，因此该限制反而有利于减少我处理曲线坐标的难度。如果你需要考虑Z轴（高度），那请谨慎采纳本篇文章的方法与观点。令人欣喜的是，在Shapely2.0（还未发布）中，会考虑三维空间的计算。
需要用到的库
[*]shapely ：主要的计算几何库，提供基础功能
[*]numpy ： 用于坐标系间的计算的数学库
[*]matplotlib：用于图形化数据的debug库，正式应用时，可以去除。
[*]itertools ：用于数据分类的库
[*]unreal：与Unreal内部数据进行交互
处理思路与对象
UE4中Spline Mesh需要至少两个顶点位置以及他们的切线方向才能获得弧形效果。如下图：
边缘由一个Spline Mesh来构成，起始点和终点的位置以及他们的切线控制了形态。
计算过程
整个计算过程比较简单：
第一步——将所有道路的交点找到
第二步——曲线有两个以上交点时，需要从两个相邻交点的中间进行分割曲线
第三步——将交点以及通过该交点的曲线进行打组并单独处理
第四步——在上一步所得的每个组中，对曲线的边线进行求交，并从交点处向外延找到位置 https://www.zhihu.com/equation?tex=l_1 和 https://www.zhihu.com/equation?tex=l_2 。然后计算切线 https://www.zhihu.com/equation?tex=t_1 和 https://www.zhihu.com/equation?tex=t_2 。以上四个值是我们最终想要的结果。
不难看出上面第四步会重复第一到第三步中的大部分操作。因此关于求交点等方法可以作为全局方法。
我创建了三个类来分别代表不同层级的对象：
RoadLine ：用于保存道路曲线以及附带的属性。作为我们最基础的数据结构。
EdgeSpline： 作为最小的生成单元。一个交叉路口至少包含2个EdgeSpline实例。每个实例代表两条相交马路的一边。
CrossArea ：作为计算过程第三步中的交点与过该交点曲线的一个集合。
代码分析
整体过程
主要步骤直接写在了主函数main中:
def main():
""" gen road edge script """
''' 加载Json文件，保存了引擎中Spline的点信息 '''
filters = {'Width': 500.0, 'SplineType': 1}
points_json = load_spline_json('roadmap_segment.json', **filters)# read the roadmap json file
'''生成原始曲线，合并相邻曲线。'''
lines = linemerge(shape(points_json))
'''查找交叉点，并合并属于同一个交叉口的交叉点'''
cross_result = merge_intersections(get_intersections(lines), 700.0)
'''创建我们自定义的类RoadLine实例，并保存经过本线段上的交点'''
road_lines = []
for i, line in enumerate(lines.geoms):
roadline = RoadLine.get_properties_from_json(line, points_json, i)
roadline.update_intersections_attribute(cross_result, 700.0)
if len(roadline.intersections) > 0:
# 如果一条曲线有交点，便保存近数组进行进一步处理
road_lines.append(roadline)
'''绘制原始曲线和交点'''
for line in lines.geoms:
plt.plot(line.xy, line.xy)
for pt in cross_result:
plt.scatter(pt.x, pt.y)
'''创建交叉口类CrossArea，初始化时将会计算我们想要的结果'''
cross_area_list = []
for cp in cross_result:
cross_area = CrossArea(cp, road_lines, filters)
cross_area_list.append(cross_area)
'''获得最后结果'''
property_content = []
for ca in cross_area_list:
property_content += ca.get_spline_properties()
ca.draw() # 画中心原始线段和交点
ca.draw_edge_only() # 绘制边缘线，以及控制点
'''打印结果用于检查'''
# for prop in property_content:
# print(prop)
'''输出所绘制的曲线'''
plt.axis("equal")
plt.show()
'''将结果写入Json'''
content = {}
with open('output_cross_splines.json', 'w') as pf:
content['spline'] = property_content
json.dump(content, pf)从代码注释中可以看到整个计算的脉络。但是在测试过程中，会出现很多细节上的问题，下面会一一进行探讨：
细节处理
shapely判断点是否在线段上时会因为数据精度偏差而失败
我发现，在得到两条曲线的交点后，再判断该交点是否在曲线上（touch方法）时，有时会给出否的结果。我想应该和数据精度相关，因此我采用了自己的判断方法：
def get_touch_lines(point, lines, tolerance=1.0):
_touch_lines = []
if isinstance(lines, MultiLineString):
for line in lines.geoms:
dist = point.distance(line)
if dist < tolerance:
_touch_lines.append(line)
else:
for road in lines:
dist = point.distance(road.line)
if dist < tolerance:
_touch_lines.append(road)
return _touch_lines通过判断点到线段的距离来判断点是否在曲线上。
当多条曲线相交于一个交叉路口时，其实会产生多个交点
由于人工摆放的曲线，无法精确到多个曲线从一点通过，因此必然会出现多个交点的问题。该问题只能进行一次交点的距离判断，当两个交点低于道路宽度的一半时，就应该进行merge操作。
def merge_intersections(point_list, tolerance=700.0):
result = []
for i in range(len(point_list) - 1):
current = point_list.pop()
rest = MultiPoint(point_list)
p0, p1 = nearest_points(current, rest)
if p0.distance(p1) > tolerance:
result.append(current)
result += point_list
return result同时，我也会在CrossArea类中重新更新交点的位置，使其处在所有交点的质心位置：
class CrossArea:
···
def cross_road(self, line_list, filters):
···
if len(result) > 2:
inters = get_intersections()
if len(inters) > 1:
points = MultiPoint(inters)
centroid_coords = # 将所有交点的质点返回
self.__cross = Point(centroid_coords)
return result如何正确的切割曲线
像上图中，所有曲线都会在交点间进行切断，这样做的好处有很多，避免了求边缘交点时与两外的交叉口进行错误的相交计算。切割曲线的方法如下：
在两个交点的中间位置进行切割曲线
假设曲线上有三个交点，那么两端的交点处理方式一致，而中间的交点需要求两个cut点：
def cut_mid(line, start, end):
if start > end:
start, end = end, start
coords = list(line.coords)
line_pts = []
start_pt = line.interpolate(start)
end_pt = line.interpolate(end)
line_pts.append(start_pt)
for i, p in enumerate(coords):
pd = line.project(Point(p))
if start <= pd <= end:
line_pts.append(Point(p))
line_pts.append(end_pt)
return LineString(line_pts)
class CrossArea:
···
def cross_road(self, line_list, filters):
roads = get_touch_lines(self.__cross, line_list, filters[&#39;Width&#39;])
result = []
for road in roads:
dist = road.line.project(self.__cross)
intersections = road.intersections
if len(intersections) > 1:
# when the road has more than one intersection
sorted_inters = sorted(intersections, key=lambda x: road.line.project(x))
total = len(sorted_inters)
i = sorted_inters.index(self.__cross)
if 0 < i < total-1: # 中间的点
start = (road.line.project(sorted_inters) + dist) * 0.5
end = (road.line.project(sorted_inters) + dist) * 0.5
result.append(RoadLine(cut_mid(road.line, start, end), road))
elif i == 0: # 最左边的点
start = 0
end = (road.line.project(sorted_inters) + dist) * 0.5
result.append(RoadLine(cut_mid(road.line, start, end), road))
elif i == total-1: # 最右边的点
start = (road.line.project(sorted_inters) + dist) * 0.5
end = road.line.length
result.append(RoadLine(cut_mid(road.line, start, end), road))
else:
# when the road has only one intersection
result.append(road)
···
return result多条曲线相交时，如何获得外围交点
所有交点
如上图所示，当超过两条曲线交汇时，代表道路的边缘曲线会有过多的交点，而只有部分交点是我们需要的：
最终想要的结果
通过上图我们可以发现，其实我们需要的是最外围的交点。可以采用凸包和位置判断来获得最外围交点：
利用凸包和位置判断最后的交点
class CrossArea:
···
def get_edge_inters(self):
inters = get_intersections()
multi_points = MultiPoint(inters)
convex = multi_points.convex_hull # 获得所有点的凸包
result = filter(convex.touches, inters) # 通过点在凸包位置进行过滤
return
···Spline Mesh的切线方向问题
由于Unreal的Spline切线参数是有方向的，如果方向不对，会使一端的面片方向反转。同时Spline Mesh有左右之分，只能让Spline Mesh向左弯折才能和道路边缘匹配。因此我们需要知道曲线的方向。
方法是从交点切割边缘线段（下图绿线），然后与主线（下图红线）求交，若相交就删除。
通过中心道路曲线与边缘曲线是否有交点，就可以过滤出保留的边缘曲线
def cut(line, distance):
# Cuts a line in two at a distance from its starting point
if distance <= 0.0 or distance >= line.length:
return
coords = list(line.coords)
for i, p in enumerate(coords):
pd = line.project(Point(p))
if pd == distance:
return [
LineString(coords[:i + 1]),
LineString(coords)]
if pd > distance:
cp = line.interpolate(distance)
if cp.has_z:
return [
LineString(coords[:i] + [(cp.x, cp.y, cp.z)]),
LineString([(cp.x, cp.y, cp.z)] + coords)]
else:
return [
LineString(coords[:i] + [(cp.x, cp.y)]),
LineString([(cp.x, cp.y)] + coords)]
class EdgeSpline:
···
def get_straight_roads(self):
straight_lines = []
for edge in self.edges:
dis = edge.line.project(self.inter)
result = cut(edge.line, dis)
if len(result) != 2:
return None
line1, line2 = result, result
# 如果当前的曲线和中心线有交点，就排除该曲线
multiroads = MultiLineString()
if line1.intersects(multiroads):
if line2.intersects(multiroads):
# 当道路为环形时，可能会有两次相交，此处处理此种特殊情况（之前在两个交点之间切断曲线已经避免了此类情况的产生）
sub_inter1 = line1.intersection(multiroads)
if self.inter.buffer(self.roads.width * 2.0).contains(sub_inter1):
straight_lines.append(RoadLine(line2, edge))
else:
straight_lines.append(RoadLine(line1, edge))
else:
straight_lines.append(RoadLine(line2, edge))
else:
straight_lines.append(RoadLine(line1, edge))
return straight_lines当将外围的曲线保留之后，通过在两条曲线上各取一点，然后根据顺时针对点进行排序处理：
计算起点和终点的位置和切线方向
class EdgeSpline:
···
def calc_properties(self):
points = []
if self.straights is None:
return None
for road in self.straights:
line, width = road.line, road.width
dist = line.project(self.inter)
if dist < 1.0:
end = line.interpolate(width)
else:
end = line.interpolate(dist - width)
points.append(end)
if len(points) == 2:
# be sure they are counter-clockwise order
points.insert(1, self.inter)
if LinearRing(points).is_ccw:
points.reverse()
start_loc = np.array(points.xy)
end_loc = np.array(points.xy)
start_tan = (np.array(self.inter.coords.xy) - start_loc) * 2.0
end_tan = (end_loc - np.array(self.inter.coords.xy)) * 2.0
self.set_properties(start_loc, start_tan, end_loc, end_tan)
return points
···蓝图参数设置
如果输出的参数在蓝图的构造函数中直接赋值给Spline Mesh Component，会导致蓝图的Spline无法在视窗交互调整。因此我们需要创建一个Custom Event来帮我们赋值：
左边没有链接的节点是废除的
总结
本文主要是实验仅使用Python的情况下能否完成道路的交叉口计算和摆放。由于只是一次简单的尝试，因此代码中缺乏很多报错处理，主要精力都放到了具体业务上。然而通过测试，发现该工具在处理小角度相融合的两条路时，会计算错误。同时没有考虑高度的完全比配，所以必须配合VT使用。
另外使用Python处理模型存在Debug困难的问题。但是计算速度以及便捷性要远胜于Houdini Engine。
Shapely库处理曲线和点云尚可，现无法处理三维模型（未来shapely2.0肯能会提供相应的功能）。scikit-geometry库将是一个不错的选择，它是基于著名的CGAL库的python封装，但由于还只是早期的公开库，因此还需等待一段时间才会功能完善。
另外由于我本人参与的项目引擎是4.25，Unreal的python还是2.7版本，因此无法安装shapely库。所以只能将python3封装成exe，然后在python2.7中调用，这看起来就很不靠谱，但依然能够跑通。即使在这样的环境下，计算速度依然好过Houdini Engine。
这是我第一次使用python来处理曲线的相关问题，很难保证该方法的普遍性，如果你有什么疑问，我可能无法给你满意的答复。
不建议直接使用在项目中，功能尚待完善。本例中也不会考虑处理交叉口中心区域。
若文章有错误或不妥之处，望指正，感激！另外，如果你对Python在PCG中的应用很感兴趣或已有经验，非常欢迎与你建立联系和交流。
交叉口中心地带并没有处理
文件下载
python 3.9
需要安装shapely，numpy ，itertools ，matplotlib库。
python file:
https://github.com/Liuzkai/PythonScript/blob/master/GeometryPy/gen_road_cross_edge.py
测试json：
https://github.com/Liuzkai/PythonScript/blob/master/GeometryPy/roadmap_segment.json
生成json是项目中已开发的功能，不在本文中讨论。你可根据模板Json生成相应的Json点云信息即可。
参考
[*]^The Shapely User Manualhttps://shapely.readthedocs.io/en/stable/manual.html#efficient-rectangle-clipping
页:
[1]