CODEWITHSUNDEEP
mathcubic-spline
Sirisian
Sirisian

Reputation: 447

Calculate time t along a 2D cubic bezier equal to a given tangent vector

I have a cubic bezier defined by four points. I need to find the time t along the cubic bezier where the tangent is equal to a given vector. This problem is not as straightforward as it may seem on first glance. I'll explain the basic math first for how I approached it so you can find flaws and possibly a better solution.

A 2D cubic bezier and its tangent can be defined by these equations. Specifically the tangent:

T(t) = -3(1-t)^2 * P0 + 3(1-t)^2 * P1 - 6t(1-t) * P1 - 3t^2 * P2 + 6t(1-t) * P2 + 3t^2 * P3

And expanded for a 2D vector:

T_x(t) = -3(1-t)^2 * x0 + 3(1-t)^2 * x1 - 6t(1-t) * x1 - 3t^2 * x2 + 6t(1-t) * x2 + 3t^2 * x3
T_y(t) = -3(1-t)^2 * y0 + 3(1-t)^2 * y1 - 6t(1-t) * y1 - 3t^2 * y2 + 6t(1-t) * y2 + 3t^2 * y3

Then we also have a vector (x, y) representing the tangent we want to find the time t for.

These are simple quadratic equations so we just need an equation to solve. We can take the cross product (vx0 * vy1 - vy0 * vx1) between the two and solve for 0. This would find when the tangent of the cubic bezier is equal to our given tangent vector and we'd solve for t. (I don't care if the vector is opposite the tangent so if our vector is (1, 0) then it would also look for (-1, 0)). In Mathematica solving for t with this cross product approach would look like this:

Solve[(-3(1-t)^2*x0+3(1-t)^2*x1-6t(1-t)*x1-3t^2*x2+6t(1-t)*x2+3t^2*x3)*y-(-3(1-t)^2*y0+3(1-t)^2*y1-6t(1-t)*y1-3t^2*y2+6t(1-t)*y2+3t^2*y3)*x==0,t,Reals]

Mathematica would then output:

{{t->ConditionalExpression[(x0 y-2 x1 y+x2 y-x y0+2 x y1-x y2)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)-\[Sqrt]((x1^2 y^2-x0 x2 y^2-x1 x2 y^2+x2^2 y^2+x0 x3 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x0 y y2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2-x x0 y y3+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)^2),(x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&y2<y3)||(x<(x2 y-x3 y)/(y2-y3)&&y<0&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&y2<y3&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&x>(x2 y-x3 y)/(y2-y3)&&y2>y3)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&y>0)||(y<0&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3))]},

{t->ConditionalExpression[(x0 y-2 x1 y+x2 y-x y0+2 x y1-x y2)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)+\[Sqrt]((x1^2 y^2-x0 x2 y^2-x1 x2 y^2+x2^2 y^2+x0 x3 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x0 y y2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2-x x0 y y3+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)^2),(x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&y2<y3)||(x<(x2 y-x3 y)/(y2-y3)&&y<0&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&y2<y3&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&x>(x2 y-x3 y)/(y2-y3)&&y2>y3)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&y>0)||(y<0&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3))]}}

Here's an image that's easier to see. That said most of those cases have duplicate variables so it's much simpler than it looks. (Both condition cases are identical and the solutions are a positive or negative case in the equation since it solved a quadratic equation). In code form this is easy to see:

var temp1 = (tx2 - tx3) / (y2 - y3);
var temp2 = (tx1 * tx1 + tx2 * tx2 + tx2 * (ty0 + ty1 - 2 * ty2) + tx1 * (-tx2 - tx3 - 2 * ty1 + ty2 + ty3) + tx3 * (ty1 - ty0) + ty1 * ty1 - ty0 * ty2 + ty2 * ty2 + ty0 * ty3 - ty1 * (ty2 + ty3)) / (tangent.y * (tx2 - tx3 - ty2 + ty3));
console.log ('Temp1: ', temp1, ' Temp2: ', temp2);
if
(
    tangent.x < temp1 &&
    (
        tangent.y < 0 && 
        (
            x0 < temp2 && y2 < y3 ||
            x0 > temp2 && y2 > y3
        ) ||
        tangent.y > 0 &&
        (
            x0 < temp2 && y2 > y3 ||
            x0 > temp2 && y2 < y3
        )
    ) ||
    tangent.x > temp1 &&
    (
        tangent.y < 0 &&
        (
            x0 < temp2 && y2 > y3 ||
            x0 > temp2 && y2 < y3
        ) ||
        tangent.y > 0 &&
        (
            x0 < temp2 && y2 < y3 ||
            x0 > temp2 && y2 > y3
        )
    )
)
{
    var tx0ty0 = tx0 - ty0;
    var ty1tx1 = ty1 - tx1;
    var tx2ty2 = tx2 - ty2;

    var temp6 = 2 * (tx0ty0 + tx2ty2) + 4 * ty1tx1;
    var temp5 = tx0ty0 + 3 * (tx2ty2 + ty1tx1) + ty3 - tx3;
    var temp7 = temp6 * temp6 - 4 * (tx0ty0 + ty1tx1) * temp5;
    var temp3 = Math.sqrt(temp7);
    var temp4 = 2 * temp5;
    var t1 = (temp6 - temp3) / temp4;
    var t2 = (temp6 + temp3) / temp4;
}

So what we have is two possible times as we'd expect since the problem is quadratic. Here's an interactive example in JS. That example uses a hardcoded tangent vector of (0.707, 0.707). (So a vector pointing down and to the right in that coordinate system).

There are problems though with the above code. Even correcting for floating point errors in the inequalities and square root calculations there are cases that aren't well defined. Like when y2 - y3 is 0 resulting in a division by zero case. There are subtleties to this also like in certain cases temp4 will have valid results that are very close to zero either producing the correct result or due to floating point issues generating a value for t1 and t2 much larger than expected. I've noticed this specifically in the cases where t1 or t2 are 0.5. Was thinking that flipping it across the the diagonal and solving again might solve some edge cases, but I'm just not confident on that approach.

What I'd like is a tried and tested approach, possibly with a code example, or another way to tackle this without weird edge cases.

Upvotes: 2

Views: 248

Answers (1)

6502
6502

Reputation: 114461

The problem can have several special cases... for example a Bezier arc can form a cusp or can even be a straight line or single point (just consider all control points identical). Having a single direct formula without special cases is not going to be possible.

Posing the problem as tx*y'(t) - ty*x'(t) = 0 where x'(t) is defined as a_x*t^2 + b_x*t + c_x (and similar for y) and solving with Maxima I got

enter image description here

and

enter image description here

as the two solutions for the general case.

They are valid only if the denominator is not zero of course, and in this case the solution to the equation simplifies to:

enter image description here

A Javascript implementation of this computation is:

tvals = []; // Array of solutions
var den = 2*ax*ty - 2*ay*tx;
if (Math.abs(den) < 1E-10) {
    var num = ax*cy - ay*cx;
    var den = ax*by - ay*bx;
    if (den != 0) {
        var t = -num / den;
        if (t >= 0 && t <= 1) tvals.push(t);
    }
} else {
    var delta = (bx*bx - 4*ax*cx)*ty*ty + (-2*bx*by + 4*ay*cx + 4*ax*cy)*tx*ty + (by*by - 4*ay*cy)*tx*tx;
    var k = bx*ty - by*tx;
    tvals = [];
    if (delta >= 0 && den != 0) {
        var d = Math.sqrt(delta);
        var t0 = -(k + d) / den;
        var t1 = (-k + d) / den;
        if (t0 >= 0 && t0 < 1) tvals.push(t0);
        if (t1 >= 0 && t1 < 1) tvals.push(t1);
    }
}

You can check a working interactive example in http://raksy.dyndns.org/beztan.html or as a video in https://youtu.be/5PKQUtytrlQ

Upvotes: 3

Related Questions