y coordinate for a given x cubic bezier

问题:

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

回答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.

回答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;

}

回答3:

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.

回答4:

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

} }