道路曲线的设计选择

如果我需要在游戏中绘制弯曲的道路我该怎么办? 我会使用贝塞尔曲线和样条曲线。 它们是曲线的标准解决方案。 数学很简单。 他们相当灵活。 但它们也有一些缺点,你还应该将圆弧视为基元。 这是一个比较:

为什么是圆弧?

当使用贝塞尔曲线和样条线进行道路绘制时,通常必须将样条线变成一系列短线段。 这在实践中很好,但也不能令人满意,并且可能会导致某些游戏中出现视觉伪影。 还有一些附带问题,例如表示地块和细分地块,贝塞尔曲线在这些问题上表现不佳。 我想知道是否有其他东西可以代替。

在尝试了一些东西之后,我向我的朋友多米尼克提到了这个问题,他建议我看看圆弧; Steffen Itterhelm 的博客文章也建议使用弧线; StackExchange 上的这个讨论也建议使用弧线。 我玩弧线的次数越多,它们对我来说就越好。

2、特性的考虑

考虑一段路,在游戏中绘制和使用道路需要什么?

1、偏移量

给定偏移量和道路中心,我们需要能够以距道路给定的偏移量绘制一条路径。 为什么?

  • 道路的左右边缘是偏移的。
  • 多车道道路中的车道标记是偏移的。
  • 道路和与道路相邻的区域之间的边界存在偏移。 SimCity 和 Cities XL 等游戏将这些区域划分为“地块”,放置房屋、工厂、商店等。
  • 道路之间的交叉点是通过偏移量计算的。

2、距离

给定路段上的位置,我们需要计算出它沿路有多远。 给定沿路的距离,我们需要找出位置。 为什么?

  • 将位置转换为距离可以让我们计算路段的长度,用于寻路和移动。
  • 为了使车辆沿着道路行驶,我们需要将距离转换为位置。
  • 将鼠标点击转换为距离也可能很有用。

3、构建块:线段

让我们从两点之间的简单路段开始。 最简单的连接是线段。

1、偏移量

要偏移直线,请计算法线 N =rotateLeft(normalize(P2 - P1)),乘以偏移量,然后将该向量添加到端点。

请注意,偏移量可以为负值以朝另一个方向移动。 偏移量使我们能够绘制道路边缘和条纹。 对于弯曲路径,我们需要使用路径上每个点的法线进行偏移。

2、距离

要将距离转换为位置(插值),请计算正切  T = normalize(P2 - P1),乘以距离,然后将该向量添加到第一个端点。

这使我们能够沿着道路移动车辆。 对于弯曲的路径,情况会更加复杂。

要将位置转换为距离(测量值),我们按照相反的步骤操作:减去第一个端点,然后与切线 T 进行点积。

我们可以通过将第二个端点转换为距离来获得道路的总长度, length=  (P2 - P1) ⋅ T。请注意,这简化为  ||P2 - P1||,因为 T = normalize(P2 - P1) = ( P2 - P1) / ‖P2 - P1‖,且  (P2 - P1) ⋅ (P2 - P1) = ‖P2 - P1‖²

4、构建块:贝塞尔曲线

当我想画一条弯曲的道路时,我首先想到的就是贝塞尔曲线。 除了曲线的两个端点之外,贝塞尔曲线还有额外的“控制点”来控制形状。 最常见的两种形式是二次型(有一个控制点)和三次型(有两个控制点)。

这是一条沿着二次贝塞尔曲线绘制的道路:


1、偏移量

事实证明,贝塞尔曲线的偏移本身并不是贝塞尔曲线。 如果你偏移终点和控制点,最终会得到一条宽度不恒定的道路; 它看起来不对。 或者,如果你尝试保持恒定的宽度,并且道路的左/右侧不是贝塞尔曲线或任何容易描述的曲线。 解决方法是将曲线转换为一系列短线段,然后计算每个线段的偏移量。 该图在不使用解决方法的情况下移动控制点,你可以看到它的宽度并不完全恒定:

2、距离

事实证明,贝塞尔曲线的长度无法精确计算。 解决方法是使用近似值,或将曲线变成一系列短线段。

事实证明,插值法并不完全可计算。 同样的解决方法,将曲线变成短线段,也可以用于插值。 还有其他方法,但它们并不那么简单。

5、解决方法:一系列线段

尽管贝塞尔曲线很常见,受到许多图形库的支持并且易于使用,但它们对于道路绘制没有很好的属性。 对于偏移、距离和插值,你可以使用一系列线段来近似曲线,并获得贝塞尔曲线无法精确计算的属性。

你需要多少条线段? 这里有一个权衡。 使用更少但更长的线段可以使近似值对玩家可见,但相邻区域的多边形会更简单,这将使交集和其他计算更快。 Cities XL 和 SimCity 5 支持道路附近的区域(用于农场和建筑物),并且这两款游戏都使用较长的线段。 以下是《城市 XL》的屏幕截图:

如果你告诉玩家他们可以建造“弯曲的道路”,那么一系列短直的道路可能不是他们期望得到的。 如果你把这个部分做得足够短,大多数玩家就不会在意。

我还没有《模拟城市 5》的屏幕截图,但从预览来看,他们的道路比《城市 XL》中的道路要平坦一些。 路段越短,道路看起来就越弯曲。 但是,如果你需要对区域和交叉点执行计算,这些计算可能会更慢。 《海岛大亨 3》和《海岛大亨 4》的道路看起来比《城市特大》或《模拟城市 5》中的道路更加弯曲。以下是《海岛大亨 4》的屏幕截图:

《运动中的城市 2》拥有美丽的道路。 我还不确定他们是否使用贝塞尔曲线或圆弧。 如果他们使用贝塞尔曲线,他们必须创建大量线段,这样玩家就无法分辨。 无论他们在做什么,看起来都非常好。

6、构建块:圆弧

二次贝塞尔曲线的替代方法是圆弧。 两者都不是另一个的超集——贝塞尔曲线不能产生圆弧,圆弧也不能产生贝塞尔曲线。

请注意,圆弧的对称性增加了其令人愉悦的形状,但它也限制了控制点。 考虑圆弧的主要原因是它们不需要贝塞尔曲线的“一系列线段”解决方法。 请注意,你仍然需要将它们转换为多边形才能在 GPU 上渲染它们,但你可以原生的数学形式对其进行推理。

1、偏移量

为了形成一条偏移曲线,我们在每个点加上偏移量乘以法线 N。对于圆弧,法线是半径向量,因此偏移曲线是半径的变化,从而产生另一个圆弧。

我们需要处理的一件棘手的事情是非常大的半径。 直线是半径无穷大的圆弧; 零半径是你永远不想要的。 但是我们想要执行诸如半径加减之类的操作,并且对于大半径,我们可能会遇到数值精度问题。 一种想法是使用曲率(1/半径)或有符号曲率而不是半径。 直线可以表示为曲率为零的圆弧; 无限曲率是你永远不想要的。 另一种选择是检测大半径并切换到线段。

2、距离


圆弧的长度是由圆的长度推导出来的。 它是半径乘以跨度的角度(以弧度为单位)。

要沿圆弧插值,我们将位置转换为角度(除以半径),插值角度,然后转换回位置(乘以半径)

这里我们也可能遇到无限半径的问题,因为我们先除以半径,然后乘以半径。 是否有更好的表示方法可以避免这些问题? 我不知道。

7、Biarcs:两条弧粘在一起

弧线的缺点是它们不如贝塞尔曲线灵活,尤其是三次贝塞尔曲线。 增加弧灵活性的一种方法是将其中两个连接在一起形成双弧。 构建双弧需要两个端点及其切线,但它还有一个额外的自由度。

双弧的一个关键问题是在哪里连接两个弧。 我们想要两个圆弧的切线相匹配的点。 它们匹配的地方都在一个圆上。 在此图中,移动端点和切线,然后将控制点移动到彩色圆圈上的某个位置:

请注意,控制点不在彩色圆圈上会导致两条弧线连接不顺畅。 另请注意圆圈上的颜色:它们显示了生成的双弧的长度。 双弧越短通常越好,但你还需要考虑曲率以及与相邻道路的连通性。

上面的 biarc UI 演示了 biarc 的工作原理,但对于玩家修建道路来说,它并不是一个很好的 UI。 更好的 UI 会将控制点限制在圆上,或者根据一些启发式自动选择控制点。 在 biarc 文献中,没有一种所有人都同意的最佳启发式,因此你可能需要尝试几种,看看哪一种最适合你的游戏。 另外,我的猜测是你甚至不想让玩家控制切线。 你可以轻松选择产生巨大圆弧的切线。 在游戏中,你可能会将道路连接到现有道路,因此切线已经确定。

8、结束语

弯曲路径的默认选择是贝塞尔曲线/样条线。 这是一个合理的选择。 他们易于理解且易于合作。 但是,你需要将它们转换为分段线性曲线才能使用它们。 Cities XL、Tropico 4 和 SimCity 5 都使用贝塞尔曲线。

但对于道路和铁轨,我认为圆弧是一个有趣的选择。 它们在表示和模拟方面具有一些很好的特性,但可能存在半径非常大的问题。 《铁路大亨 3》和《席德梅尔的铁路》都使用它们。 赛车游戏使用它们。 我认为《火车狂热》使用了它们。 还有其他使用圆弧的建筑游戏吗?

这不仅仅是游戏。 Apple 地图和 Google 地图使用线段,而 Transit 应用程序使用圆弧。

使用哪个真的很重要吗? 大多数玩家可能不会在意。 但有些人会。 当我玩《Cities XL》时,我对道路不弯曲以及建筑物不适合形状怪异的道路留下的空间感到非常恼火。 我确实认为弧线值得考虑。


原文链接:Curved Paths

BimAnt翻译整理,转载请标明出处