Calculate the edge points of a surface defined by 2 bezier curves?

Question

Given the 6 points defining 2 quadratic bezier curves, how do I calculate the points at which the tangents for both curves are the same?

The distance between tangents gets smaller and eventually reaches 0, when they coincide. How do I calculate this without looping a hundred times and checking each part? Is there a mathematical solution to this?

Answer 1

Conveniently wikipedia even shows gradient for a quadratic Bezier curve defined by P_0, P_1, P_2 so we don't even need to calculate it.

So, if we have 2 curves defined by B_1(t) and B_2(t), and we want to know the location in curve B_2(t) that has the same tangent as, for example, B_1(0.5). We need only to find t such that B_1'(0.5) = B_2'(t). Since the gradient is a linear equation it should be trivial to solve this equality.

edit: this is such a cool question I had to write some code :)

Consider this figure:

B = @(t,p0,p1,p2)((1-t)*((1-t)*p0 + t*p1) + t*((1-t)*p1 + t*p2)) 
C = @(t,p0,p1,p2)(2*(1-t)*(p1-p0) + 2*t*(p2-p1));

p0 = [1;2];
p1 = [3;5];
p2 = [6;-1];
X = [];
for t=0:0.05:1
    X = [X B(t,p0,p1,p2)];
end

q0 = [2;0];
q1 = [4;7];
q2 = [5;0];
Y = [];
for t=0:0.05:1
    Y = [Y B(t,q0,q1,q2)];
end

figure(1)
clf;
hold on;
plot([p0(1) p1(1) p2(1)], [p0(2) p1(2) p2(2)], 'ro:')
plot(X(1,:), X(2,:), 'g-');

plot([q0(1) q1(1) q2(1)], [q0(2) q1(2) q2(2)], 'bo:')
plot(Y(1,:), Y(2,:), 'm-');

% Consider: t = 0.2
% Note: B(0.2,p0,p1,p2) = [1.84; 2.84]
%       C(0.2,p0,p1,p2) = [4.4; 2.4]
%
% 2*(1-t)*([4;7] - [2;0]) + 2*t*([5;0]-[4;7]) = [4-2*t; 14-28*t]
% (4-2*t)/(14-28*t) = 4.4/2.4
% 9.6 - 4.8t = 61.6 - 123.2t
% 118.4t - 52 = 0
% t = 0.439
%
% B(0.439,q0,q1,q2) = [3.56; 3.45]

plot([1.84, 3.56], [2.84, 3.45], 'ks--')

This is matlab code, I hope it's somewhat clear, if you don't use matlab just note that column vectors are denoted as [a;b;c;d;...]. So I define 2 curves with points p0,p1,p2 and q0,q1,q2, then create a function to compute the Bezier (B) and the gradient (C). I then plot the curves and consider the tangent at t=0.2, I hope the remaining math is clear, but just ask a question if not.

Also, note that we do not solve for the gradients to be equal as I originally said! Instead we need to solve for the gradient that has the same ratio of x/y. And if there is no solution then there is no place where the tangents are equal.

Answer 2

Quadratic Bezier curves P and Q

P(t)=P0*(1-t)^2 + 2*P1*(1-t)*t + P2*t^2 = t^2*(P0-2*P1+P2)+2*t*(P1-P0)+P0

Q(t)=Q0*(1-u)^2 + 2*Q1*(1-u)*u + Q2*u^2= u^2*(Q0-2*Q1+Q2)+2*t*(Q1-Q0)+Q0

Derivative of Bezier curve of nth order is curve of (n-1)th order with control points Di=n(P(i+1)-Pi)

D0=2(P1-P0) D1=2(P2-P1)

D=D0*(1-t)+D1*t=2*t*(P2-2*P1+P0)+2*(P1-P0) – now we have tangent at the point with parameter t

Scalar form:

Dx=2*t*(P2x-2P1x+P0x)+2(P1x-P0x)

Dy=2*t*(P2y-2P1y+P0y)+2(P1y-P0y)

For second curve

Ex=2*u*(Q2x-QP1x+Q0x)+2(Q1x-Q0x)

Ey=2*u*(Q2y-QP1y+Q0y)+2(Q1y-Q0y)

The condition that the vectors are parallel:

DxEy-DyEx=0

The condition that the derivative vector for P curve touching corresponding point at Q curve

Vector product (Q(u) - P(t)) x D(t) = 0

Now we have two equations for two unknowns - t and u.

Let PAx = P2x-2P1x+P0x, PBx = P1x-P0x, same notation for PAy, PBy, QAx, QAy, QBx,QBy

Now equation system is:

(tPAx+PBx)(uQAy+QBy)-(tPAy+PBy)(uQAx+QBx)=0

(u^2*QAx+2*u*QBx+Q0x-t^2*PAx-2*tPBx-P0x) (t*PAy+PBy)-(u^2*QAy+2*u*QBy+Q0y-t^2*Pay-2*tPBy-P0y)(t*PAx+PBx)=0

Maple solves this system with such a result:

t = RootOf((PAx^2*PByQAy+PBxPAy^2*QAx-PAxPByPAyQAx-PBxPAyPAxQAy)*_Z^3+

(-2*PAxQByPAyQBx+PBxPAyPByQAx+PAxPByPBxQAy+Q0xPAyPAxQAy-PAx*PBy^2*QAx-PBx^2*PAyQAy+P0xPAy^2*QAx-P0yPAxPAyQAx-Q0yPAx^2*QAy+P0y*PAx^2*QAy+PAy^2*QBx^2-P0xPAyPAxQAy+Q0yPAxPAyQAx+PAx^2*QBy^2-Q0x*PAy^2*QAx)*_Z^2+

(Q0yPBxPAyQAx+Q0xPByPAxQAy+Q0yPAxPBy*QAx+2*PAx*QBy^2*PBx+2*PAy*QBx^2*PBy-2*PAxQByPBy*QBx-2*PBxQByPAyQBx-P0yPAxPByQAx-P0yPBxPAy*QAx-2*Q0xPAyPBy*QAx+2*P0yPAxPBxQAy-P0xPAyPBxQAy+2*P0xPAyPByQAx-P0xPByPAxQAy-2*Q0yPAxPBxQAy+Q0xPAyPBxQAy)*_Z-

P0yPBxPByQAx-Q0xPBy^2*QAx-Q0y*PBx^2*QAy+P0y*PBx^2*QAy+P0x*PBy^2*QAx-2*PBxQByPBy*QBx+PBx^2*QBy^2+PBy^2*QBx^2+Q0yPBxPByQAx+Q0xPByPBxQAy-P0xPByPBx*QAy)

This formula denotes that t is a root of cubic equation with these weird coefficients. Cubic is solvable. If there is real value of t in range [0..1], then we can calc u and check the same range. Of course, this is rather complex method and my calculations may contain errors and typos

Addition: case of 3 real roots of cubic (and 3 tangents) is possible: