y coordinate for a given x cubic bezier

Question

This question is very similar to: Quadratic bezier curve: Y coordinate for a given X?. But this one is cubic...

I'm using the getBezier function to calculate the Y coordinates of a bezier curve. The bezier curve starts always at (0,0) and ends always at (1,1).

I know the X value, so I tried to insert it as percent (I'm a moron). But that didn't work, obviously. Could you provide a solution? It's necessary it's an idiot proof function. Like:

function yFromX (c2x,c2y,c3x,c3y) { //c1 = (0,0) and c4 = (1,1), domainc2 and domainc3 = [0,1]
    //your magic
    return y;
}

Leastways

You need to understand that the curves are a function from 'percent' to (X, Y). You also might benefit from knowing that there may be two points on a cubic Bezier curve (X, Y1), (X, Y2) with Y1 != Y2. – Soldiery

I forgot to tell you the domains of c2x, c2y, c3x and c3y are [0,1]. So this is impossible. – Leastways

@bpjesvla: As far as the math goes it isn't impossible. – Deciliter

That was @elisbben. And no, this isn't homework, I'm trying to get transitions working in IE in one htc file. This is the only problem I had so far. I'm not a math student... – Leastways

@Leastways Gotcha. That means that the function is monotonic, which makes this pretty easy... – Soldiery

Answer 1

Since the problem is so limited (function x(t) is monotonic), we can probably get away with using a pretty cheap method of solution-- binary search.

var bezier = function(x0, y0, x1, y1, x2, y2, x3, y3, t) {
    /* whatever you're using to calculate points on the curve */
    return undefined; //I'll assume this returns array [x, y].
};

//we actually need a target x value to go with the middle control
//points, don't we? ;)
var yFromX = function(xTarget, x1, y1, x2, y2) {
  var xTolerance = 0.0001; //adjust as you please
  var myBezier = function(t) {
    return bezier(0, 0, x1, y1, x2, y2, 1, 1, t);
  };

  //we could do something less stupid, but since the x is monotonic
  //increasing given the problem constraints, we'll do a binary search.

  //establish bounds
  var lower = 0;
  var upper = 1;
  var percent = (upper + lower) / 2;

  //get initial x
  var x = myBezier(percent)[0];

  //loop until completion
  while(Math.abs(xTarget - x) > xTolerance) {
    if(xTarget > x) 
      lower = percent;
    else 
      upper = percent;

    percent = (upper + lower) / 2;
    x = myBezier(percent)[0];
  }
  //we're within tolerance of the desired x value.
  //return the y value.
  return myBezier(percent)[1];
};

This should certainly break on some inputs outside of your constraints.

Soldiery

Even with my limited knowledge I should have found this... Thanks! – Leastways

Given your intuition about y(x) being single-valued given the constraints on the middle two control points, your knowledge may be limited but you're pretty quick on your feet. Feel free to upvote or even accept my answer ;) – Soldiery

Should you want to use a straightforward solution this module is doing a great job with both performance and precision: github.com/gre/bezier-easing (not the author btw) – Christabelle

Answer 2

I used the algorithm from this page and wrote it down in JavaScript. It works for all the cases I have tested so far. (And doesn't use a while loop.)

Call the solveCubicBezier function. Pass in the x values of all the control points and the x value you want to get the y coordinate from. For example:

var results = solveCubicBezier(p0.x, p1.x, p2.x, p3.x, myX);

results is an array containing the 't' values originally passed into the Bezier function. The array can contain 0 to 3 elements, because not all x values have a corresponding y value, and some even have multiple.

function solveQuadraticEquation(a, b, c) {

    var discriminant = b * b - 4 * a * c;

    if (discriminant < 0) {
        return [];

    } else {
        return [
            (-b + Math.sqrt(discriminant)) / (2 * a),
            (-b - Math.sqrt(discriminant)) / (2 * a)
        ];
    }

}

function solveCubicEquation(a, b, c, d) {

    if (!a) return solveQuadraticEquation(b, c, d);

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

    var p = (3 * c - b * b) / 3;
    var q = (2 * b * b * b - 9 * b * c + 27 * d) / 27;

    if (p === 0) {
        return [ Math.pow(-q, 1 / 3) ];

    } else if (q === 0) {
        return [Math.sqrt(-p), -Math.sqrt(-p)];

    } else {

        var discriminant = Math.pow(q / 2, 2) + Math.pow(p / 3, 3);

        if (discriminant === 0) {
            return [Math.pow(q / 2, 1 / 3) - b / 3];

        } else if (discriminant > 0) {
            return [Math.pow(-(q / 2) + Math.sqrt(discriminant), 1 / 3) - Math.pow((q / 2) + Math.sqrt(discriminant), 1 / 3) - b / 3];

        } else {

            var r = Math.sqrt( Math.pow(-(p/3), 3) );
            var phi = Math.acos(-(q / (2 * Math.sqrt(Math.pow(-(p / 3), 3)))));

            var s = 2 * Math.pow(r, 1/3);

            return [
                s * Math.cos(phi / 3) - b / 3,
                s * Math.cos((phi + 2 * Math.PI) / 3) - b / 3,
                s * Math.cos((phi + 4 * Math.PI) / 3) - b / 3
            ];

        }

    }
}

function roundToDecimal(num, dec) {
    return Math.round(num * Math.pow(10, dec)) / Math.pow(10, dec);
}

function solveCubicBezier(p0, p1, p2, p3, x) {

    p0 -= x;
    p1 -= x;
    p2 -= x;
    p3 -= x;

    var a = p3 - 3 * p2 + 3 * p1 - p0;
    var b = 3 * p2 - 6 * p1 + 3 * p0;
    var c = 3 * p1 - 3 * p0;
    var d = p0;

    var roots = solveCubicEquation(
        p3 - 3 * p2 + 3 * p1 - p0,
        3 * p2 - 6 * p1 + 3 * p0,
        3 * p1 - 3 * p0,
        p0
    );

    var result = [];
    var root;
    for (var i = 0; i < roots.length; i++) {
        root = roundToDecimal(roots[i], 15);
        if (root >= 0 && root <= 1) result.push(root);
    }

    return result;

}

Othilia

Hi. I am getting a error with the following values: solveCubicBezier(13.969161963240431, 74.2679238696713, 303.900002823836, 901.3362308681752, 300) The problem seems be to caused by the equation Math.pow((q / 2) + Math.sqrt(discriminant), 1 / 3) returning Nan. Its trying to evaluate raising a negative number to a power of 0.3 which cant be done. It's actually attempting to evaluate Math.Pow(-0.08, 0.3). Any ideas what could be done? – Konyn

The cube root function can be implemented as function crt(v) { if(v<0) return -Math.pow(-v,1/3); return Math.pow(v,1/3); }. This only gives the real root, as opposed to all three roots including imaginary roots, which is generally find as we can't really use complex numbers in JS anyway. I created an implementation with this cube root worked in over at jsbin.com/fewih/1/edit – Openhearth

Why take the trouble to define a, b, c, d and then not use these values in the call to solveCubicEquation? – Ammonium

Answer 3

I've implemented this solution in Java and works very fine. But the most important is that I understand it. Thanks!

public class CubicBezier {
    private BezierCubic bezier = new BezierCubic();
    public CubicBezier(float x1, float y1, float x2, float y2) {
        bezier.set(new Vector3(0,0,0), new Vector3(x1,y1,0), new Vector3(x2,y2,0), new Vector3(1,1,1));
    }
    public float get(float t) {
        float l=0, u=1, s=(u+l)*0.5f;
        float x = bezier.getValueX(s);
        while (Math.abs(t-x) > 0.0001f) {
            if (t > x)  { l = s; }
            else        { u = s; }
            s = (u+l)*0.5f;
            x = bezier.getValueX(s);
        }
        return bezier.getValueY(s);
    }
};

public class BezierCubic {
private float[][] cpoints = new float[4][3];
private float[][] polinom = new float[4][3];

public BezierCubic() {}

public void set(Vector3 c0, Vector3 c1, Vector3 c2, Vector3 c3) {
    setPoint(0, c0);
    setPoint(1, c1);
    setPoint(2, c2);
    setPoint(3, c3);
    generate();
}

public float getValueX(float u) {
    return getValue(0, u);
}

public float getValueY(float u) {
    return getValue(1, u);
}

public float getValueZ(float u) {
    return getValue(2, u);
}

private float getValue(int i, float u) {
    return ((polinom[0][i]*u + polinom[1][i])*u + polinom[2][i])*u + polinom[3][i];
}

private void generate() {
    for (int i=0; i<3; i++) {
        float c0 = cpoints[0][i], c1 = cpoints[1][i], c2 = cpoints[2][i], c3 = cpoints[3][i];
        polinom[0][i] = c0 + 3*(c1 - c2) + c3;
        polinom[1][i] = 3*(c0 - 2*c1 + c2);
        polinom[2][i] = 3*(-c0 + c1);
        polinom[3][i] = c0;
    }
}

private void setPoint(int i, Vector3 v) {
    cpoints[i][0] = v.x;
    cpoints[i][1] = v.y;
    cpoints[i][2] = v.z;
}

} }

Painstaking

Answer 4

The original answer already contains everything you need to know

There are numerical issues. The exact solution for cubics suffers from stability problems.

The smooth geometric nature of typical Bezier curves means that spacial search (recursive subdivision) converges nicely, it's usually "fast enough", and it extends easily to N dimensions. There's quite a readable implementation in the Qt source code.

Tanhya

Not idiot proof enough for me :) If it isn't too much of a deal, could you write it out? – Leastways