координата у для данного кубического Безье

Question

Этот вопрос очень похож на: Квадратичная кривая Безье: координата Y для данного X? .Но этот кубический ...

Я использую функцию getBezier для вычисления Y-координат кривой Безье.Кривая Безье всегда начинается с (0,0) и заканчивается всегда (1,1).

Я знаю значение X, поэтому я попытался вставить его в процентах (я идиот).Но это не сработало, очевидно.Не могли бы вы предоставить решение?Это необходимо для защиты от идиота.Нравится:

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

Answer 1

Поскольку проблема настолько ограничена (функция x (t) является монотонной), мы, вероятно, можем избежать использования довольно дешевого метода решения - двоичного поиска.

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

Это, безусловно, должно сломатьна некоторые входы за пределами ваших ограничений.

Answer 2

Я использовал алгоритм из этой страницы и записал его в JavaScript.Это работает для всех случаев, которые я тестировал до сих пор.(И не использует цикл while.)

Вызовите функцию solveCubicBezier.Передайте значения x всех контрольных точек и значение x, из которого вы хотите получить координату y.Например:

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

results - это массив, содержащий значения 't', первоначально переданные в функцию Безье.Массив может содержать от 0 до 3 элементов, потому что не все значения x имеют соответствующее значение y, а некоторые даже имеют несколько.

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;

}

Answer 3

Я реализовал это решение на Java и работает очень хорошо.Но самое главное, что я это понимаю.Спасибо!

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

}}

Answer 4

Оригинальный ответ уже содержит все, что вам нужно знать

Есть числовые проблемы. Точное решение для кубики страдает от проблем устойчивости.

Гладкая геометрическая природа типичных кривых Безье означает, что пространственный поиск (рекурсивное подразделение) хорошо сходится, он обычно "достаточно быстр" и легко распространяется на N измерений. В исходном коде Qt есть вполне читаемая реализация.