Curveball

# Curveball 来源：https://mightyburger.net/projects/curveball/ Curveball 是我为 Neverball（https://neverball.org/）开发的曲线生成工具。 curveball 标志 你可以在网页上使用 Curveball（https://curveball.mightyburger.net/）！源代码托管在 Github（https://github.com/MightyBurger/curveball）。你可以在那里找到更多截图。如果你更想以桌面应用的方式运行 Curveball，可以从 Github 下载发布版本，或自行编译。别担心——编译 Curveball 很简单，尤其如果你已经有 Rust 环境。哦对了，这东西是用 Rust 🦀 写的。这意味着它肯定很棒，对吧？ ## 曲线的疯狂 为什么需要 Curveball？我正在为一个名为 Neverball（https://neverball.org/）的开源游戏制作关卡集，需要一些精巧的形状。Neverball 已经有一个名为 `curve.c` 的曲线生成工具（https://github.com/Neverball/neverball/blob/master/contrib/curve.c）。它足以满足现有所有 Neverball 关卡集的需求（除了 Nevermania——fwp（https://github.com/fwp）一定自己写过几个脚本）。但 `curve.c` 只能生成一种曲线：圆弧。诚然，它提供了很多可调节的参数。但我需要 `curve.c` 无法生成的曲线，所以自己写了一些脚本来填补空白。后来我想到把这些零散的脚本整合成一个工具，并为其添加可视化功能，就像 curve.js（https://play.neverball.org/curve.js/）那样。我动手开始开发，结果有点一发不可收拾。最终成果就是 Curveball！ ## 它是如何工作的？ 我早期的脚本非常基础，但我逐渐找到了一些精巧的抽象方法，让它变得更好、更简洁。 ## 从整个宇宙开始 Neverball 的关卡由许多“笔刷”组成。每个笔刷都是一小块几何体。笔刷的定义方式很奇特：每个笔刷是**半空间的交集**。如果你之前没听说过，这可能听起来有点吓人，让我来解释一下。想象你像这样构建一个笔刷：首先，让笔刷占据整个宇宙。然后，一遍又一遍地切割宇宙，直到剩下一个小块。这听起来很古怪，但采用这种方式有其技术原因，例如简化碰撞检测代码。 现在我们需要在文本文件中描述这些形状。Neverball 解析 Quake 地图格式（https://quakewiki.org/wiki/Quake_Map_Format），其中每个“切割”由平面上的三个点定义。这些点必须按特定顺序排列；如果弄错了，可能会意外地切掉宇宙的错误半边！如果好奇，这里是一个立方体的数据示例： `` { "classname" "worldspawn" // brush 0 { ( 0 0 64 ) ( 0 64 64 ) ( 64 0 64 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0 ( 0 0 0 ) ( 0 0 64 ) ( 64 0 64 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0 ( 0 0 64 ) ( 0 0 0 ) ( 0 64 64 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0 ( 64 0 64 ) ( 64 64 64 ) ( 64 64 0 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0 ( 64 64 0 ) ( 64 64 64 ) ( 0 64 64 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0 ( 0 0 0 ) ( 64 0 0 ) ( 64 64 0 ) mtrl/invisible 0 0 0 0.5 0.5 0 0 0 } } `` 括号里的是点。之后的每一部分都与纹理相关。 ## 凸性 不幸的是，笔刷的工作方式决定了每个笔刷都必须是**凸的**（https://en.wikipedia.org/wiki/Convex_polytope）。然而，大多数曲线都不是凸的。因此，曲线通常需要由许多较小的笔刷组成。 ## 更简单的方法 `curve.c` 和我早期的脚本只是手动仔细选择点。这非常容易出错，而且有点麻烦。结果发现，我们的问题正是**凸包算法**（https://en.wikipedia.org/wiki/Convex_hull_algorithms）可以解决的。我找到了 `chull` crate（https://crates.io/crates/chull），它用 Rust 实现了凸包算法。现在我可以给 `chull` 一堆点，让它自己弄清楚如何用这些点构成形状。太酷了！这让我可以轻松快速地拼凑出新的曲线生成器。不过，这也使得给每个面分配纹理变得麻烦。Trenchbroom（https://trenchbroom.github.io/）可以快速给大量面涂抹纹理，所以我选择不担心这个问题。 使用 `chull` 只需定义顶点就能轻松生成这些曲线。但仍有改进空间。 ## 关键思路：拉伸 我发现了一个非常巧妙的抽象方法来生成这些曲线。它的灵感来自像 Solidworks（https://www.solidworks.com/）这样的机械 CAD 软件。思路是：**定义一个 2D 轮廓**，然后**将其拉伸到 3D 空间中**。在 Curveball 中，2D 轮廓会沿着路径被复制多次。然后 Curveball 取两个相邻面的所有顶点，通过 `chull` 生成一个笔刷。重复此过程直到路径终点，曲线就制作完成了。这种生成形状的方式非常自然，并且开启了许多可能性。每一种**轮廓**和**路径**的组合都能产生新的曲线。有些组合可能很奇怪且用处不大，但你也能制作出很多有趣且实用的曲线。如果我编写 $m$ 种不同的轮廓和 $n$ 种不同的路径，那么我就可以产生 $m \cdot n$ 种不同的曲线！手动编写每一种排列将花费大量时间。 ## 朝向 一个有趣的问题是沿着路径旋转轮廓。这对于**旋转**路径来说尤其自然，但对其他路径也可能很有用。我在编程实现时遇到了麻烦。最初的尝试失败了，因为它们都犯了一个错误。事实证明，仅知道路径上的**点**和前进的**方向**并不足以确定应该如何旋转！我遗漏了一个自由度：扭转。我最终偶然发现了**弗朗内标架**（https://en.wikipedia.org/wiki/Frenet%E2%80%93Serret_formulas）。如果我能定义沿曲线上任意点的 $\mathbf{T}$、$\mathbf{N}$ 和 $\mathbf{B}$ 向量，那么只需将矩阵 $\left[ \mathbf{T}, \mathbf{N}, \mathbf{B} \right]$ 乘以该点，就能旋转该点。你可以使用有趣的技术，比如积分**弗朗内-塞雷公式**（https://en.wikipedia.org/wiki/Frenet%E2%80%93Serret_formulas）或寻找**最小旋转标架**（https://medium.com/intuition/lockdown-geometry-rotation-minimizing-frames-ff373d2f355b）来找到这些向量，但 Curveball 中的路径都非常简单，直接定义这三个向量很容易，所以我选择了后者。沿着路径旋转轮廓并不总是期望的行为，因此我在 Curveball 中将其设为可选。 这是函数签名： `` pub fn extrude( n: u32, profile: &PRF, path: &PTH, profile_orientation: ProfileOrientation, ) -> CurveResult> where PRF: Profile, PTH: Path, `` 还不错！`Profile` 是一个可以生成平面内点向量的东西，可能沿路径变化。`Path` 是一个可以生成点以及弗朗内标架以形成路径的东西。 ## 规则的例外 除了**拉伸**之外，Curveball 还可以生成另外三种曲线，我称之为**经典曲线**、**斜坡曲线**和**Rayto**。 **经典曲线**实际上也可以作为拉伸生成。这是因为 `extrude()` 可以接受沿路径变化的 2D 轮廓。我选择单独实现它，以使接口与 `curve.c` 类似。 **Rayto** 也可以作为拉伸生成。但你必须非常巧妙地使用我上面描述的功能。这会很麻烦，所以我直接实现了它。 **斜坡曲线**是唯一无法通过 `extrude()` 生成的曲线。原因是它以不同的方式生成笔刷。当你在 Curveball 中制作这条曲线时，你会注意到笔刷看起来像三角形的小块。 ## 接下来是什么？ 是时候使用这个工具了！我有一些关卡因为需要特定的曲线形状而搁置了。现在我可以继续前进，制作一些有趣的关卡了。我很期待看到 Neverball 社区会利用这个工具创造出什么。 *注：我对本文进行了细微的编辑以修正技术细节。*