在多个点处拆分三次贝塞尔曲线

Question

我正在编写一种算法，将三次贝塞尔曲线拆分为多条曲线（最多 4 条）。我从一开始就有了要分割的每个点的 t 值。我也已经有了一个用于一次分割曲线的算法：

SubdivPoints subdivideBezier(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3, float t)
{
    Vector2 p11 = (p1 - p0) * t + p0;
    Vector2 p21 = (p2 - p1) * t + p1;
    Vector2 p31 = (p3 - p2) * t + p2;

    Vector2 p12 = (p21 - p11) * t + p11;
    Vector2 p22 = (p31 - p21) * t + p21;

    Vector2 p13 = (p22 - p12) * t + p12;

    return SubdivPoints(p11, p12, p22, p31, p13);
}

我的问题是，有没有一种简单的方法可以将其展开多次拆分？我想在每次分割后我想重新计算 t 值；我想知道的一件事是简单的算术在这里是否可行。例如。假设我的 t 值为 0.2 和 0.6。我在 t = 0.2 处分割曲线，得到两条曲线。第二条曲线涵盖原始值 0.2 < t < 1 的 t 值。如果我通过除法重新计算第二个 t 值 0.6：(0.6 - 0.2) / (1 - 0.2) = 0.5，然后将第二条曲线除以 t = 0.75，这行得通吗？或者我需要用其他方式重新计算吗？

Answer 1

即使您当前的方法有效也很难说，因为我们看不到背后的原因 SubdivPoints。我可以想到两种方法：

代数

如果您将问题视为多项式的参数 t 缩放，那么它会变得更加清晰。例如，您想要部件 t=<0.25,0.5> 的控制点。这意味着我们需要形成新的控制点来表示具有参数 u=<0.0,1.0> 的相同曲线。怎么做？
1. 将 BEZIER 写成多项式
每个轴都可以以相同的方式单独完成让我们只关注 x 轴。我们有 4 个 X 坐标为 (x0,x1,x2,x3) 的 BEZIER 控制点。如果我们应用伯恩斯坦多项式来形成三次多项式，我们得到：
```
x(t)=      (                           (    x0))
    +    t*(                  (3.0*x1)-(3.0*x0))
    +  t*t*(         (3.0*x2)-(6.0*x1)+(3.0*x0))
    +t*t*t*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))
```
1. 通过替换重新缩放参数
为此使用线性插值：
```
t0=0.25 -> u0=0.0
t1=0.50 -> u1=1.0
t=t0+(t1-t0)*(u-u0)/(u1-u0)
t=0.25+0.5*u
```
现在使用 u 而不是 t
重写多项式
```
x(t)=             (                           (    x0))
    +(0.25+u/2)  *(                  (3.0*x1)-(3.0*x0))
    +(0.25+u/2)^2*(         (3.0*x2)-(6.0*x1)+(3.0*x0))
    +(0.25+u/2)^3*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))
```
1. 更改多项式形式以再次匹配 BEZIER 方程
现在您需要分离 u^0,u^1,u^2,u^3 的多项式项，并修改每一项以匹配 BEZIER 样式（来自 #1）。从中提取新的控制点。

比如词条u^3就是这样。获得 u^3 的唯一可能性来自
```
(1/4+u/2)^3= (1/8)*u^3 + (3/16)*u^2 + (3/32)*u + (1/64)
```
所以分隔 u^3 项将是：
```
u*u*u*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))/8
```
其他的会有点复杂，因为你需要把所有的线组合在一起……简化后你需要分离新的坐标。如您所见，这有点疯狂，但那里有代数求解器，例如 Derive for Windows ...

抱歉，我没有 time/mood/stomach 来完整举例说明所有的术语，但你会发现这将是一个多项式的疯狂...
曲线拟合

这是基于您正在查找控制点的坐标并检查它与所需曲线的距离。因此，测试“"all possible" 点并记住目标范围内原始曲线与新曲线之间的接近匹配。这将无法解决，因为可能存在无限数量的控制点，因此我们需要通过利用一些东西将它们减少到可管理的大小. 例如我们现在的控制点不会离原来的控制点太远所以我们可以用它来限制每个点的面积。你可以使用 approximation search 或任何其他最小化技术。

如果你使用插值三次，你也可以获得更好的起点。参见 BEZIER vs Interpolation cubics。所以：
1. 从您的 BEZIER 曲线计算 4 个新的插值三次控制点
  
  所以如果我们有和以前一样的范围那么
```
X0 = BEZIER(t0-(t1-t0))
X1 = BEZIER(t0)
X2 = BEZIER(t1)
X3 = BEZIER(t1+(t1-t0))
```
  这些是插值立方体控制点而不是 BEZIER。它们应该均匀分散。 X1,X2 是曲线端点，X0,X3 是它们之前和之后，以尽可能保持参数的局部形状和线性度
2. 从(X0,X1,X2,X3)转回BEZIER控制点(x0,x1,x2,x3)
  
  你可以使用上面 link 中的我的公式：
```
// input: X0,Y0,..X3,Y3  ... interpolation control points
// output: x0,y0,..x3,y3 ... Bezier control points
    double x0,y0,x1,y1,x2,y2,x3,y3,m=1.0/9.0;
    x0=X1;             y0=Y1;
    x1=X1+((X1-X0)*m); y1=Y1+((Y1-Y0)*m);
    x2=X2+((X2-X3)*m); y2=Y2+((Y2-Y3)*m);
    x3=X2;             y3=Y2;
```
  如您所见，每个轴的计算方式相同...
3. 对 BEZIER 控制点应用近似搜索
  
  新的 (x0,x1,x2,x3) 还不精确，因为通过盲目改变控制点，我们可能会略微错过曲线扭曲形状的一些局部极值。所以我们需要寻找真实的。幸运的是，新的控制点 (x0',x1',x2',x3') 将非常接近这些点，所以现在我们必须只在其对应部分附近搜索每个点，周围有一些合理的半径（比如边界框 size/8 或其他任何东西......你将看到结果并可以调整...

[备注]

如果您需要精确的结果，那么只能使用 #1 方法。方法 #2 总会有一些错误。如果形状不需要精确，有时在没有最终拟合的情况下将插值三次转换为 BEZIER 就足够了（如果形状不太复杂 in/near 切割区域）。

我之前写的不知道你用的是什么原理SubdivPoints无法回答重复使用它的结果会是什么...

此外，您没有指定解决方案的约束，例如结果的准确性、speed/runtime 限制……如果范围是固定的（恒定的）或在运行时可能会发生变化（这将使 #1 方法极其复杂因为你需要将范围作为变量处理直到结束）

Answer 2

由于您的 subdivideBezier() 函数确实遵循 De Casteljau 算法，我假设它可以在参数 t 处细分三次贝塞尔曲线。所以，是的，要在不同的参数（比如 t2）上继续细分，您需要做的就是找出 t2 落在哪条细分曲线上，根据该曲线计算新的 t2* 并细分。在您要在 t=0.2 和 0.6 处细分的示例中，0.6 的新参数应为 (0.6-0.2)/(1-0.2) = 0.5。因此，您可以简单地将第二条曲线细分为 t=0.5.

在多个点处拆分三次贝塞尔曲线

Split a cubic bezier curve at multiple points

math

curve

bezier