Cubic bezier curves - get Y for given X - special

I've read a few discussions regarding finding Y at X for a cubic Bezier curve, and have also read this article regarding the matter.

My case is more constrained than the general one, and I wonder if there's a better solution than the general ones mentioned in the above discussions.

My case:

The X value of the different control points is increasing. Ie: X3 > X2 > X1 > X0.
Also, as a result of above, X(t) is strictly monotonically increasing as well.

Is there any efficient algorithm that takes such constraints into account?

回答1:

First off: this answer only works because your control point constraint means we're always dealing with a parametric equivalent of a normal function. Which is obviously what you want in this case, but anyone who finds this answer in the future should be aware that this answer is based on the assumption that there is only one y value for any given x value. Which is, of course, absolutely not true for Bezier curves in general.

With that said, we know that—even though we've expressed this curve as a parametric curve in two dimensions—we're dealing with a curve that for all intents and purposes must have some unknown function of the form y = f(x). We also know that as long as we know the "t" value that uniquely belongs to a specific x (which is only the case because of your strictly monotonically increasing coefficients property), we can compute y as y = By(t), so the question is: can we compute the t value that we need to plug into By(t), given some known x value?

To which the answer is: yes, we can.

First, any x value we start off with can be said to come from x = Bx(t), so given that we know x, we should be able to find the corresponding value(s) of t that leads to that x.

let's look at the function for x(t):

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

We can rewrite this to a plain polynomial form as:

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

This is a standard cubic polynomial, with only known constants as coefficients, and we can trivially rewrite this to:

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

You might be wondering "where did all the -x go for the other values a, b, c, and d?" and the answer there is that they all cancel out, so the only one we actually end up needing to subtract is the one all the way at the end. Handy!

So now we just... solve this equation: we know everything except t, we just need some mathematical insight to tell us how to do this.

...Of course "just" is not the right qualifier here, there is nothing "just" about finding the roots of a cubic function, but thankfully, Gerolano Cardano laid the ground works to determining the roots back in the 16^th century, using complex numbers. Before anyone had even invented complex numbers. Quite a feat! But this is a programming answer, not a history lesson, so let's get implementing:

Given some known value for x, and a knowledge of our coordinates a, b, c, and d, we can implement our root-finding as follows:

// 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 pa, double pb, double pc, double pd) {
  double
    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};
  }
}

Okay, that's quite the slab of code, with quite a few additionals:

crt() is the cuberoot function. We actually don't care about complex numbers in this case so the easier way to implement this is with a def, or macro, or ternary, or whatever shorthand your language of choice offers: crt(x) = x < 0 ? -pow(-x, 1f/3f) : pow(x, 1f/3f);.
tau is just 2π. It's useful to have around when you're doing geometry programming.
approximately is a function that compares a value to a very small interval around the target because IEEE floating point numerals are jerks. Basically we're talking about approximately(a,b) = return abs(a-b) < 0.000001 or something.

The rest should be fairly self-explanatory, if a little java-esque (I'm using Processing for these kind of things).

With this implementation, we can write our implementation to find y, given x. Which is a little more involved than just calling the function because cubic roots are complicated things. You can get up to three roots back. But only one of them will be applicable to our "t interval" [0,1]:

double x = some value we know!
double[] roots = getTforX(x);
double t;
if (roots.length > 0) {
  for (double _t: roots) {
    if (_t<0 || _t>1) continue;
    t = _t;
    break;
  }
}

And that's it, we're done: we now have the "t" value that we can use to get the associated "y" value.

回答2:

If a binary search is too complex, there is still an O(1) approach but its fairly limited. I assume you are using a 4 control point (p0(x0,y0),p1(x1,y1),p2(x2,y2),p3(x3,y3)) cubic Bezier parametrized by some t in the interval [0.0 , 1.0] so:

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

First lets forget about Beziers for a while and use a catmull-rom curve instead, which is just an alternative way to represent the same curve. To convert between the 2 cubics use these:

// 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;

where (xi,yi) are Bezier control points and (Xi,Yi) are Catmull-Rom points. Now if the X distance between all control points have the same distance:

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

then the X coordinate is linear with t. That means we can compute t directly from X:

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

Now we can compute the Y for any X directly. So if you can chose the control points then chose them so they meet the X distance condition.

If the condition is not met you can try to change control points so it is satisfied (by binary search, by subdividing the cubics into more patches etc...) but beware changing control points can change the shape of the resulting curve if not careful.