曲率贝塞尔曲线——改良经典配方

# 曲率贝塞尔曲线 来源：https://acko.net/blog/curvature-beziers/ 曲率贝塞尔曲线：改进经典配方 封面图 - 雷诺4CV贝塞尔曲线是计算机辅助设计和计算机图形学的基石。像Bic笔一样，它的设计已有数十年历史，且无处不在。你常会在各种绘图和动画工具中发现它作为默认或唯一选择出现。 由保罗·德·卡斯特尔雅乌（https://en.wikipedia.org/wiki/Paul_de_Casteljau）于1959年构思，并在20世纪60年代由皮埃尔·贝塞尔（https://en.wikipedia.org/wiki/Pierre_B%C3%A9zier）在雷诺公司完善，贝塞尔曲线持久的魅力在于其简洁性。尽管已发明更复杂的曲线，且新的曲线（https://linebender.org/blog/hyperbezier/）不断被提出，但这些曲线仅限于特定领域，如高精度计算机辅助设计或道路设计。在通用领域，贝塞尔曲线尽管存在缺陷，却顽固地拒绝被取代。 因此，贝塞尔曲线似乎成了我们不得不沿用的遗留技术。作为软件工程师，我的问题是：我们能否在不否定基于和使用它们构建的所有技术的前提下，让贝塞尔曲线变得更好？ 答案是肯定的。 ## 线性插值过程 绘制贝塞尔曲线是一个出奇简单且线性的过程： *提示：本文中的所有图表都是完全交互式的。* 给定一系列控制点，我们用直线将它们连接起来。然后我们同时沿这些直线行进，以产生新的点，这些新点可以再次连接。这个过程重复进行，直到我们得到一个位于曲线上的单点。 这种构造方式使得贝塞尔曲线比其最初看起来要规则得多。 线性插值（又称*lerps*）可以总结为一个紧凑的公式，例如对于4个控制点 $ \left(A, B, C, D\right) $： 规则很简单：$\left(1 - t\right)$ 的降幂，$t$ 的升幂，系数取自帕斯卡三角形的第n行： 对于二维和三维曲线，该公式分别应用于X、Y或Z坐标。 虽然可以为任意数量的控制点构建贝塞尔曲线，但通常的做法是仅使用具有4个控制点的三次贝塞尔曲线。这是因为曲线仅保证通过第一个和最后一个控制点，这使得更高次的贝塞尔曲线更难塑形。 较大的曲线则通过连接多个三次贝塞尔线段来构建，通过对齐切线形成一段看似光滑的分段曲线： 这就是通常理解的三次贝塞尔*样条*。大多数绘图应用中的精确“钢笔工具”则由绘制和编辑控制点组成，而不是直接绘制曲线。 ## 一个普遍存在的谎言 钢笔工具通常有几种不同的控制点模式： 直观上，这些代表了各种程度的平滑性。对称切线被提供为最平滑的选项，当你放松约束时，一些平滑性特质会丧失。 在现实中，这**完全错误**，并且很容易证明。 贝塞尔曲线可以精确分割，通过从插值图中读出新的控制点： 左右两段与原始曲线100%相同，并且在接缝处始终完美衔接。然而，除了在靠近中间的某个分割点外，中间的切线将始终是不对称的。这可以使用*曲率梳*来确认，曲率梳表示每个点的曲率（倒数）半径： 曲率梳保持连续，没有跳跃。 这意味着相邻切线长度是否相等（即是否对称）完全无关紧要。试图以这种方式绘制平滑且直观的贝塞尔曲线是徒劳无功的。 一种简单的改进方法是将切线视为相对而非绝对的。例如，我们可以使它们与每个线段起点和终点之间的距离成比例： 这种样条更容易编辑，因为当你移动每个曲线点时，相邻线段会自然地弯曲以让开。这样产生的尖点要少得多。编辑切线的方式保持不变。 然而，如果我们再次绘制曲率，就能看出这并不是一个很好的解决方案： 按比例缩放切线并不能保证在编辑过程中曲率得以保持，也不能保证曲率在线段之间保持连续。 这也表明，向用户提供曲率梳可视化作为“有用的工具”其实相当*刻薄*：调整一端的曲率也会影响另一端，需要反复来回调整直到足够接近。 ## 小心操作 一个更有效的策略是直接处理曲率。 虽然这通常是个难题，但事实证明这里存在一些令人惊讶的关系，我们可以直接观察： 考虑线段 $A-B-C-D$ 起点处的曲率。这仅受 $A$、$B$ 和 $C$ 位置的影响。如果点 $D$ 与 $C$ 断开，则可以自由移动。 此外，由于切线 $A-B$ 是水平的，只有 $C$ 的垂直位置起作用。这是基础线性插值的结果，它们最终在公式中消去了许多项。 因此，$A$ 点的曲率仅受 $A-B$ 的长度以及 $C$ 到 $A-B$ 的垂直距离的影响。另一端的 $D$ 点情况同理，与 $C-D$ 和 $B$ 有关。 然而，这本身并没有太大用处。当我们移动一个曲线点（$A$ 或 $D$）时，通常也会移动相邻的控制点（$B$ 或 $C$）以保持切线。当我们旋转对称或不对称的切线时，下一段中的相邻切线也会旋转相同的角度，从而改变该侧的曲率。 尽管如此，这表明保持曲率本身并非一个疯狂的想法，并且可以通过适当地缩放切线来实现。规则很简单： - 当我们移动一个曲线点时，必须保持相邻线段起点和终点的曲率 - 当我们移动一条切线时，必须保持当前线段对端的曲率，以及相邻线段两侧的曲率 这应该能产生一种真正尊重用户意图的编辑体验。不过并非完全如此： 移动曲线点效果很好，但当旋转切线时，该切线的长度本身是用户意图的一个差劲表示。微小的变化可能导致曲率发生巨大偏移，这会使曲线在试图找到匹配解决方案时跳动并意外爆炸。 因此，最好直接使用曲率控制柄，其长度直接对应曲率： 与曲率梳不同，控制柄的长度是非倒数的曲率半径，这是更自然的选择。 这些控制柄非常稳定，可以在需要时即时转换为经典的贝塞尔控制点，而无需在两种表示之间来回转换。有帮助的是，这也避免了数值漂移。 ## 金发姑娘原则 为了真正实现这一点，我们需要在给定期望曲率 $k_0$ 和 $k_1$、起点/终点 $A$ 和 $D$ 以及起点/终点单位长度切线的情况下，求解切线长度 $l_0$ 和 $l_1$。 给定曲线 $\gamma\left(t\right)$，我们可以将单位切向量 $\mathbf{T}\left(t\right)$ 表示为归一化的导数： 这可以用于通过使用一阶和二阶导数的两个向量叉积来找到曲率向量 $\mathbf{K}\left(t\right)$： 叉积确保 $\mathbf{K}\left(t\right)$ 垂直于 $\mathbf{T}\left(t\right)$，即它们提取中间项的法向量分量。现在我们可以求解 $\mathbf{K}\left(0\right) = k_0$ 和 $\mathbf{K}\left(1\right) = k_1$。 经过数学推导，我们得到了关于 $l_0$ 和 $l_1$ 的二次方程组： 其中： 这反映了几个要点： - 曲率 $k_i$ 的符号定义了曲线是顺时针还是逆时针弯曲。移动曲线点时，曲线可能被迫翻转，因此 $±$ 是必要的，并且两个符号可以独立变化。 - $l_0$ 和 $l_1$ 之间的耦合仅受 $b$ 影响。如果 $b = 0$，则两个方程独立，问题很容易解决。这对应于两条切线平行的情况。 - 常数项 $c_i$ 仅受切线 $\mathbf{T_i}$ 到 $D-A$（或 $A-D$）的垂直距离影响。这与之前的发现一致，即只有垂直距离影响曲率。 因此，问题简化为寻找两条双抛物线（一条水平，一条垂直）的交点： 每条双抛物线的两侧代表顺时针或逆时针弯曲。我们需要求解四次，分别对应每种符号组合 $\left(+,+\right)$、$\left(+,-\right)$、$\left(-,+\right)$、$\left(-,-\right)$。 要解这个方程组，我们可以重写任一方程以分离 $l_1$ 或 $l_0$： 选择一个，平方后代入另一个原始方程作为 $l_1^2$ 或 $l_0^2$ 项。这产生一个关于另一个变量（分别为 $l_0$ 或 $l_1$）的四次方程，可以直接使用四次公式求解。 然后我们可以计算另一个 $l_i$，通过： 然而，并非四次方程的所有解都是方程组的真正解，因为进行了平方运算。因此在我们接受一个解 $(l_0, l_1)$ 之前，必须仔细检查原始方程是否成立。 我们还需要拒绝 $l_0 < 0$ 或 $l_1 < 0$ 的解，因为这代表切线被翻转了180度。 在大多数情况下，只会有一个有效解，并且效果相当好： 对于角点类型，一个或两个 $k_i$ 是无穷大。这很容易解决，因为相应的 $l_i$ 为零，另一个可以直接计算出来。 ## 分组与吸附 不幸的是，如果有多个解，它们各代表一条不同的曲线： 如果曲线在你编辑时跳来跳去，那将是非常糟糕的编辑体验，但没有明显的方法来选择正确的一个。 一种策略是在编辑时记住之前的 $l_0$ 和 $l_1$，并选择最接近前一条曲线的解。然而，这将引入编辑的路径依赖，你移动点的顺序和方向会影响最终得到的曲线。对于绘图工具来说，这相当令人沮丧且不受欢迎。 方程的不同解也可能突然出现和消失，因此这并不能完全消除跳变，只能减少。 理想情况下，结果曲率本身应该始终平滑变化。这可以通过为解设计一个合适的加权启发式方法并计算其加权平均值来实现。 1) 禁区： 当一个解接近 $l_0 < 0$ 或 $l_1 < 0$ 时，它即将消失，因此其权重应趋近于零。 2) 当两条反向弯曲的抛物线即将相切时，两个解会相互靠近，然后同时消失： 这些解不稳定，应避免使用。为检测这种情况，我计算每个方程的梯度向量。 它们之间的夹角可以通过点积除以各自长度来找到： 值接近 $-1$ 表示两条反向弯曲的抛物线，而值接近 $1$ 表示两条对齐的抛物线。后者不那么糟糕，因为这意味着存在许多几乎等效的解。 3) 当曲率半径相对于贝塞尔曲线本身非常大时，其中一个可能的解是曲线自交形成一个环。这应该被抑制： 我们可以除以 $\|\mathbf{l}\|$ 的长度，即 $\sqrt{l_0^2 + l_1^2}$，偏好那些具有较短切线的解。 将所有这些结合起来，我选择的加权启发式方法是： - 通过应用 $\arccos \left(-\cos \theta\right)$，我们将点积范围 $\left(-1..1\right)$ 重新映射到 $\left(0..\pi\right)$，这有效地消除了不稳定解 - 较大的 $\|\mathbf{l}\|$ 代表不期望的解，因此应受到严厉惩罚，仅在它们是唯一选项时才被选择 - 当整个启发式值接近 $0$ 时，其影响应平滑消失，因此进行了整体平方 使用这个作为权重，得到的贝塞尔曲线始终平滑变化，即使起点和终点被移动并相互穿过。 但是，当多个解被平均在一起时，得到的 $(l_0, l_1)$ 不一定满足原始方程组。这意味着即使附近存在精确解，结果曲率也不总是精确的。 为了缓解这个问题，我们可以添加一个额外的重采样步骤，根据到加权平均值的逆距离的四次方对解重新加权： 当可用时，这使得解能平滑地吸附到精确解上。 ## 可迁移曲线 这种方法特别好的一点是，它可以基本无缝地嵌入现有系统，几乎不需要修改。 调整和编辑贝塞尔控制柄的界面可以保留，包括4种点类型的概念。只是切线长度的含义发生了变化。将非对称点转换为对称点实际上会均衡左右两侧的曲率，这正是用户真正想要的。 内部表示可以大部分保持相同类型，即一系列点，只是这些点代表曲率切线，而非贝塞尔切线。不过，最好直接显式地存储单位长度切线和曲率，这在数值上更稳定。对于这里的演示，我制作了曲率控制柄 ↔ 点/切线/曲率 ↔ 贝塞尔控制柄之间的成对转换函数。 分割曲率贝塞尔曲线比分割经典贝塞尔曲线简单得多，因为起点和终点的控制柄完全不变，并且新创建的控制柄是对称的： 但仍有一个缺陷。当分割一条具有S形弯曲的曲线时，弯曲处附近的分割并不精确： 启发式方法在一侧或两侧选择了错误的曲线。这可以通过记住曲率的特定方向来解决，并且仅在必要时翻转曲率符号。虽然这确实引入了编辑中最小的路径依赖。 因此，实际上你需要在UI中为歧义控制点提供一个额外的方向切换。这也意味着内部表示必须以切线 + 带符号曲率的形式存储才能完全稳定，而不仅仅是曲率控制柄。 在S形弯曲附近，曲率半径——因此控制柄尺寸——实际上变为无穷大，因为 $\|k\|$ 变为 $0$。贝塞尔控制点位于一条直线上，因为到切线的垂直距离为零。 因此，即使精确处理，这仍然可能产生大到不切实际的曲率控制柄。也许需要的是第五种“拐点”点类型，用于 $\|k\|$ 恰好为零的点，尽管此类点往往非常不稳定，有时没有解存在： 要将经典贝塞尔曲线迁移到曲率贝塞尔曲线，你可以测量起点和终点的单位切线和曲率。在绝大多数情况下，这将得到完全相同的曲线。如果不同，则必须分割原始贝塞尔曲线以避免歧义。 对于贝塞尔曲线的复杂操作，例如布尔并集或交集，这些操作仍必须在贝塞尔形式下进行。这意味着需要在两种表示之间进行一定程度的来回转换，这将引入一些开销。