三次贝塞尔曲线 - 给定X值求Y值 - 控制点的X值递增是一个特殊情况。

Question

三次贝塞尔曲线 - 给定X值求Y值 - 控制点的X值递增是一个特殊情况。

mathbeziercubic-bezier

9

我已经阅读了关于在三次贝塞尔曲线中找到X处的Y的a few discussions，并且也阅读了这篇article。

我的情况比一般情况更加受限制，我想知道是否有比上述讨论中提到的一般解决方案更好的解决方案。

我的情况：

不同控制点的X值是递增的。即：X3 > X2 > X1 > X0。
此外，由于上述原因，X(t)也是严格单调递增的。

是否有考虑到这些约束条件的有效算法呢？

- Jake

2个回答

2

如果二分查找过于复杂，仍然有一种 O(1) 的方法，但其功能相对有限。我假设您正在使用一个由一些 t 参数化的 4 控制点 (p0(x0,y0), p1(x1,y1), p2(x2,y2), p3(x3,y3)) 的三次贝塞尔曲线，其中 t 在区间 [0.0, 1.0] 中：

t = 0.0 -> x(t) = x0, y(t) = y0;
t = 1.0 -> x(t) = x3, y(t) = y3;

首先，暂时不考虑贝塞尔曲线，使用Catmull-Rom曲线代替，这只是表示相同曲线的另一种方式。要在两个立方体之间进行转换，请使用以下方法：

// BEzier to Catmull-Rom
const double m=6.0;
X0 = x3+(x0-x1)*m; Y0 = y3+(y0-y1)*m;
X1 = x0;           Y1 = y0;
X2 = x3;           Y2 = y3;
X3 = x0+(x3-x2)*m; Y3 = y0+(y3-y2)*m;

// Catmull-Rom to Bezier
const double m=1.0/6.0;
x0 = X1;           y0 = Y1;
x1 = X1-(X0-X2)*m; y1 = Y1-(Y0-Y2)*m;
x2 = X2+(X1-X3)*m; y2 = Y2+(Y1-Y3)*m;
x3 = X2;           y3 = Y2;

其中(xi,yi)是贝塞尔控制点，(Xi,Yi)是Catmull-Rom点。如果所有控制点之间的X距离相同：

(X3-X2) == (X2-X1) == (X1-X0)

如果 X 坐标与 t 成线性关系，那么我们可以直接从 X 计算出 t:

t = (X-X1)/(X2-X1);

现在我们可以直接计算任何X的Y值。因此，如果您可以选择控制点，则选择满足X距离条件的控制点。

如果条件不满足，您可以尝试更改控制点以满足条件（通过二分搜索、将立方体分成更多块等），但要注意，如果不小心更改控制点可能会改变生成曲线的形状。

- Spektre

谢谢！我不能随意选择X值，因为它们取决于其他因素。但是Mike的答案似乎提供了一条路径。 - Jake

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mike 'Pomax' Kamermans · Accepted Answer

首先，这个答案只适用于你的控制点约束意味着我们总是处理一个正常函数的参数等价形式。在这种情况下，这显然是你想要的，但是任何在未来发现这个答案的人都应该知道，这个答案基于这样一个假设：对于任何给定的x值，只有一个y值...

这绝对不适用于一般的贝塞尔曲线

话虽如此，我们知道，尽管我们已经将这条曲线表示为二维参数曲线，但我们正在处理的曲线必须具有某种未知形式的函数y = f(x)。我们还知道，只要我们知道唯一属于特定x的“t”值（这仅在严格单调递增的系数属性的情况下才成立），我们就可以计算y作为y = By(t)，因此问题是：我们能否计算我们需要插入By(t)的t值，给定一些已知的x值？

答案是：是的，我们可以。

首先，我们开始的任何x值都有自己的x = Bx(t)，因此，鉴于我们知道x，我们应该能够解决该函数并找到导致该x的相应的t值。

让我们看一下x(t)的函数：

x(t) = a(1-t)³ + 3b(1-t)²t + 3c(1-t)t² + dt³

我们可以将其重写为简单的多项式形式：

x(t) = (-a + 3b- 3c + d)t³ + (3a - 6b + 3c)t² + (-3a + 3b)t + a

这是一个标准的三次多项式，只使用已知常数作为系数，我们可以轻松地将其重写为：

x = (-a + 3b- 3c + d)t³ + (3a - 6b + 3c)t² + (-3a + 3b)t + a
0 = (-a + 3b- 3c + d)t³ + (3a - 6b + 3c)t² + (-3a + 3b)t + (a-x)

现在我们只需要解决这个方程：我们知道除了t之外的每一个值，我们只需要一些数学见解来告诉我们如何做。

当然，"只是"不是正确的限定词，在找到三次函数的根方面没有什么"简单"的，但幸运的是，16世纪Gerolano Cardano利用复数奠定了确定根的基础。在任何人发明复数之前。相当了不起！但这是一篇编程答案，不是历史课，所以让我们开始实施：

给定一些已知的x值，和对于我们的坐标a、b、c和d的知识，我们可以按照以下方式实现我们的根查找：

// Find the roots for a cubic polynomial with bernstein coefficients
// {pa, pb, pc, pd}. The function will first convert those to the
// standard polynomial coefficients, and then run through Cardano's
// formula for finding the roots of a depressed cubic curve.
double[] findRoots(double x, double[] coordinates) {
  double
    pa = coordinates[0],
    pb = coordinates[1],
    pc = coordinates[2],
    pd = coordinates[3],
    pa3 = 3 * pa,
    pb3 = 3 * pb,
    pc3 = 3 * pc,
    a = -pa  +   pb3 - pc3 + pd,     
    b =  pa3 - 2*pb3 + pc3, 
    c = -pa3 +   pb3, 
    d =  pa  -     x;

  // Fun fact: any Bezier curve may (accidentally or on purpose)
  // perfectly model any lower order curve, so we want to test 
  // for that: lower order curves are much easier to root-find.
  if (approximately(a, 0)) {
    // this is not a cubic curve.
    if (approximately(b, 0)) {
      // in fact, this is not a quadratic curve either.
      if (approximately(c, 0)) {
        // in fact in fact, there are no solutions.
        return new double[]{};
      }
      // linear solution:
      return new double[]{-d / c};
    }
    // quadratic solution:
    double
      q = sqrt(c * c - 4 * b * d), 
      b2 = 2 * b;
    return new double[]{
      (q - c) / b2, 
      (-c - q) / b2
    };
  }

  // At this point, we know we need a cubic solution,
  // and the above a/b/c/d values were technically
  // a pre-optimized set because a might be zero and
  // that would cause the following divisions to error.

  b /= a;
  c /= a;
  d /= a;

  double
    b3 = b / 3,
    p = (3 * c - b*b) / 3, 
    p3 = p / 3, 
    q = (2 * b*b*b - 9 * b * c + 27 * d) / 27, 
    q2 = q / 2, 
    discriminant = q2*q2 + p3*p3*p3, 
    u1, v1;

  // case 1: three real roots, but finding them involves complex
  // maths. Since we don't have a complex data type, we use trig
  // instead, because complex numbers have nice geometric properties.
  if (discriminant < 0) {
    double
      mp3 = -p/3,
      r = sqrt(mp3*mp3*mp3), 
      t = -q / (2 * r), 
      cosphi = t < -1 ? -1 : t > 1 ? 1 : t, 
      phi = acos(cosphi), 
      crtr = crt(r), 
      t1 = 2 * crtr;
    return new double[]{
      t1 * cos(phi / 3) - b3,
      t1 * cos((phi + TAU) / 3) - b3,
      t1 * cos((phi + 2 * TAU) / 3) - b3
    };
  }

  // case 2: three real roots, but two form a "double root",
  // and so will have the same resultant value. We only need
  // to return two values in this case.
  else if (discriminant == 0) {
    u1 = q2 < 0 ? crt(-q2) : -crt(q2);
    return new double[]{
      2 * u1 - b3,
      -u1 - b3
    };
  }

  // case 3: one real root, 2 complex roots. We don't care about
  // complex results so we just ignore those and directly compute
  // that single real root.
  else {
    double sd = sqrt(discriminant);
    u1 = crt(-q2 + sd);
    v1 = crt(q2 + sd);
    return new double[]{u1 - v1 - b3};
  }
}

好的，这是一大块代码，有一些额外的内容：

crt() 是立方根函数。在本例中，我们实际上不关心复数，所以更容易的方式是使用类的定义、宏、三元运算符或你所选择语言的任何缩写：crt(x) = x < 0 ? -pow(-x, 1f/3f) : pow(x, 1f/3f);。
tau 就是2π。当你进行几何编程时，它很有用。
approximately 是一个将值与目标周围的非常小区间进行比较的函数，因为 IEEE 浮点数是混蛋。基本上，我们说 approximately(a,b) = return abs(a-b) < 0.000001 或者其他什么。

其余部分应该相当容易理解，如果有点 Java 式（我在使用Processing进行这些操作）。

通过这个实现，我们可以编写我们的实现来找到给定x的y。现在，数学可能会产生多个根，但是我们非常特定的初始条件意味着我们知道在用于Bezier曲线的[0,1]区间中只有一个根，因此我们可以简单地检查哪个值符合该标准，然后使用该根计算y(t)。

double xCoordinates = [...];
double yCoordinates = [...];

...

double x = some value we know!
double[] roots = findRoots(x, xCoordinates);

double t;
if (roots.length > 0) {
  for (double r: roots) {
    if (r < 0 || r > 1) continue;
    t = r;
    break; }}

double y = compute(t, yCoordinates);

就这样，我们完成了：现在我们有了“t”值，可以用它来获取相应的“y”值。