0

I have a Bezier curve: (0,0), (.25,.1), (.25,1), and (1,1).

This is graphically seen here: http://cubic-bezier.com/#.25,.1,.25,1

We see on the x axis is time.

This is my unknown. This is a unit cell. So I was wondering how can I get x when y is 0.5?

Thanks

I saw this topic: y coordinate for a given x cubic bezier

But it loops, I need to avoid something loops So I found this topic: Cubic bezier curves - get Y for given X

But I can't figure out how to solve a cubic polynomial in js :(

Community
  • 1
  • 1
Noitidart
  • 35,443
  • 37
  • 154
  • 323

3 Answers3

3

This is mathematically impossible unless you can guarantee that there will only be one y value per x value, which even on a unit rectangle you can't (for instance, {0,0},{1,0.6},{0,0.4},{1,1} will be rather interesting at the mid point!). The fastest is to simply build a LUT, like for instance:

var LUT_x = [], LUT_y = [], t, a, b, c, d;
for(let i=0; i<100; i++) {
  t = i/100;
  a = (1-t)*(1-t)*(1-t);
  b = (1-t)*(1-t)*t;
  c = (1-t)*t*t;
  d = t*t*t;
  LUT_x.push( a*x1 + 3*b*x2 + 3*c*x3 + d*x4 );
  LUT_y.push( a*y1 + 3*b*y2 + 3*c*y3 + d*y4 );
}

Done, now if you want to look up an x value for some y value, just run through LUT_y until you find your y value, or more realistically until you find two values at index i and i+1 such that your y value lies somewhere in between them, and you will immediately know the corresponding x value because it'll be at the same index in LUT_x.

For nonexact matches with 2 indices i and i+1 you simply do a linear interpolation (i.e. y is at distance ... between i and i+1, and this at the same distance between i and i+1 for the x coordinates)

Mike 'Pomax' Kamermans
  • 49,297
  • 16
  • 112
  • 153
  • Aw darn so we have to loop. Thanks so much for this. I really apprecaite all the help. I'm using this for a Firefox addon Profilist. I needed to keep things as fast as possible because one of the reasons: the calculations are done while the firefox menu panel fades in and out, doing heavy stuff slows stuff down on old computers. I would seriously love to show you how I'm using this so you know your effort was gone to waste do you use Firefox? – Noitidart Oct 15 '14 at 04:56
  • 1
    a one-time loop is fast. After that you can simply use a binary search which is O(log(n)). If your LUT is 100 places, that's only 7 checks. Even 1000 spots only needs 10 checks. – Mike 'Pomax' Kamermans Oct 15 '14 at 05:30
  • Holy moly no way, can you please show me how to do that in the function below I had no idea of this algorithm! – Noitidart Oct 15 '14 at 05:31
  • 1
    Build your LUT. That's a one time O(n). Then if you need, say, `y=a`, you set `low=0`, `high=last`, `mid=(low+high)/2`. Is `mid==a`? Done. If not, if `a < mid` we keep low, set `high=mid`, `mid=(low+high)/2` and check again. If `a > mid` we keep high, set `low=mid`, recompute mid, and then check. Keep doing that, and every step you reduce the search space by a factor 2. So worst case, 100 elements becomes 50, 25, 13, 8, 4, 2, "found", in at most 7 steps. Winner. – Mike 'Pomax' Kamermans Oct 15 '14 at 05:34
  • This is interesting, this guy here seems to have made a solver without using any looping: http://freewebs.com/brianjs/ultimateequationsolver.htm his code is here: http://www.freewebs.com/brianjs/js_files/quartic_cubic_quadratic.js i beutified the code here: https://gist.github.com/Noitidart/563a9f9587719a26ed27 – Noitidart Oct 15 '14 at 06:06
  • hey mike man. so i split the bezier curve at at a percent. so that percent should be `t` right? but t is either `.68` or `.69` how to get the interpolation actor for the `t`? using this function to split here: http://stackoverflow.com/a/23452618/1828637 – Noitidart Oct 15 '14 at 06:39
  • no, `t` and distance-along-the-curve are not linearly related. Splitting at `t=0.3` and wanting it at "30%" are very different things, and you cannot generally split at "a percentage" unless you first find out where that even is. See http://pomax.github.io/bezierinfo/#tracing – Mike 'Pomax' Kamermans Oct 15 '14 at 15:42
3

All the solutions that use a look up table can only give you an approximate result. If that is good enough for you, you are set. If you want a more accurate result, then you need to use some sort of numeric method.

For a general Bezier curve of degree N, you do need to loop. Meaning, you need to use bi-section method or Newton Raphson method or something similar to find the x value corresponding to a given y value and such methods (almost) always involve iterations starting with an initial guess. If there are mutiple solutions, then what x value you get will depend on your initial guess.

However, if you only care about cubic Bezier curves, then analytic solution is possible as roots of cubic polynomials can be found using the Cardano formula. In this link (y coordinate for a given x cubic bezier), which was referenced in the OP, there is an answer by Dave Bakker that shows how to solve cubic polynomial using Cardano formula. Source codes in Javascript is provided. I think this will be your good source to start your investigation on.

Community
  • 1
  • 1
fang
  • 3,473
  • 1
  • 13
  • 19
0

Thanks again to Mike's help we found the fastest way to do this. I put this function togather, takes 0.28msg on average:

function getValOnCubicBezier_givenXorY(options) {
  /*
  options = {
   cubicBezier: {xs:[x1, x2, x3, x4], ys:[y1, y2, y3, y4]};
   x: NUMBER //this is the known x, if provide this must not provide y, a number for x will be returned
   y: NUMBER //this is the known y, if provide this must not provide x, a number for y will be returned
  }
  */
  if ('x' in options && 'y' in options) {
    throw new Error('cannot provide known x and known y');
  }
  if (!('x' in options) && !('y' in options)) {
    throw new Error('must provide EITHER a known x OR a known y');
  }

  var x1 = options.cubicBezier.xs[0];
  var x2 = options.cubicBezier.xs[1];
  var x3 = options.cubicBezier.xs[2];
  var x4 = options.cubicBezier.xs[3];

  var y1 = options.cubicBezier.ys[0];
  var y2 = options.cubicBezier.ys[1];
  var y3 = options.cubicBezier.ys[2];
  var y4 = options.cubicBezier.ys[3];

  var LUT = {
    x: [],
    y: []
  }

  for(var i=0; i<100; i++) {
    var t = i/100;
    LUT.x.push( (1-t)*(1-t)*(1-t)*x1 + 3*(1-t)*(1-t)*t*x2 + 3*(1-t)*t*t*x3 + t*t*t*x4 );
    LUT.y.push( (1-t)*(1-t)*(1-t)*y1 + 3*(1-t)*(1-t)*t*y2 + 3*(1-t)*t*t*y3 + t*t*t*y4 );
  }

  if ('x' in options) {
    var knw = 'x'; //known
    var unk = 'y'; //unknown
  } else {
    var knw = 'y'; //known
    var unk = 'x'; //unknown
  }

  for (var i=1; i<100; i++) {
    if (options[knw] >= LUT[knw][i] && options[knw] <= LUT[knw][i+1]) {
      var linearInterpolationValue = options[knw] - LUT[knw][i];
      return LUT[unk][i] + linearInterpolationValue;
    }
  }

}

var ease = { //cubic-bezier(0.25, 0.1, 0.25, 1.0)
  xs: [0, .25, .25, 1],
  ys: [0, .1, 1, 1]
};

var linear = {
  xs: [0, 0, 1, 1],
  ys: [0, 0, 1, 1]
};

//console.time('calc');
var x = getValOnCubicBezier_givenXorY({y:.5, cubicBezier:linear});
//console.timeEnd('calc');
//console.log('x:', x);
Noitidart
  • 35,443
  • 37
  • 154
  • 323