Finding the proper parametric value for a bezier curve given a coordinate

Question

I am working on a project involving bezier curves and I am having trouble finding a value t which is in the range [0, 1] that corresponds to a particular position on a bezier curve. I set up a test where I put incremental values of t (specifically at increments of 0.001 to 1) and subbed them in the x and y parametric equations of a bezier curve, I then subtract that value with the true value and if it is within a small threshold for both x and y I found an appropriate t. Unfortunately, there does not seem to be a single value for t that corresponds to the required coordinates. This means the loop actually finishes without ever succeeding the conditional in the for loop.

The coordinate that should be on the curve is (75, -2.26384401). I put my code below that shows the coordinates of the control points and the true x and y coordinates. Any help would be greatly appreciated. Thanks!

int _tmain(int argc, _TCHAR* argv[])
{
float P0[2] = { 55, -11.105 };
float P1[2] = { 72.569, -11.105 };
float P2[2] = { 50.217, 1.396 };
float P3[2] = { 100, 1.396 };

float t = 1.0F;
float int_t = t / 1000; // intervals
float x;
float y;
float tx = 75.0000000F; // where it should be in x
float ty = -2.26384401F; // where it should be in y
float epsilon = 0.01;
float final_t;

for (float i = 0; i < t; i += int_t)
{
    final_t = i;
    x = powf(1.0F - i, 3.0F)*P0[0] + 3.0F*powf(1.0F - i, 2.0F)*i*P1[0] + 
        3.0F*(1.0F - i)*powf(i, 2.0F)*P2[0] + powf(i, 3.0F)*P3[0]; // x(t)

    y = powf(1.0F - i, 3.0F)*P0[1] + 3.0F*powf(1.0F - i, 2.0F)*i*P1[1] + 
        3.0F*(1.0F - i)*powf(i, 2.0F)*P2[1] + powf(i, 3.0F)*P3[1]; // y(t)

    // for my testing
    cout << "---------------------------------" << endl;
    cout << "i = " << i << endl;
    cout << "x = " << x << endl;
    cout << "y = " << y << endl;
    cout << "---------------------------------" << endl;

    if ((fabsf(x - tx) <= epsilon) && (fabsf(y - ty) <= epsilon))
        break;
}
cout << endl;
cout << "x = " << x << endl;
cout << "y = " << y << endl;
cout << "t = " << final_t << endl;

return 0;
}

Answer 1

Your problem is that the input point Pt(tx,ty) does not lie on the BEZIER (P0,P1,P2,P3) curve at all. So the distance to the curve is always much bigger then your small epsilon no matter how close match of t you find ....

Here how it looks like:

The BEZIER curve is in gray. Green X is the input (tx,ty) point and Red + is found closest point on curve t=0.753

Here C++/VCL code I did this with:

//---------------------------------------------------------------------------
#include <math.h>
#include "approx.h"
double P0[2] = { 55, -11.105 };
double P1[2] = { 72.569, -11.105 };
double P2[2] = { 50.217, 1.396 };
double P3[2] = { 100, 1.396 };

double Pt[2] = { 75.0000000,-2.26384401 };
//---------------------------------------------------------------------------
void BEZIER_getxy(double *p0,double *p1,double *p2,double *p3,double &x,double &y,double  t) // return x,y of point on BEZIER curve for t
    {
    double a0,a1,a2,a3,tt,ttt;
    tt=t*t; ttt=tt*t;
    a0=                                    (    p0[0]);
    a1=                        (3.0*p1[0])-(3.0*p0[0]);
    a2=            (3.0*p2[0])-(6.0*p1[0])+(3.0*p0[0]);
    a3=(    p3[0])-(3.0*p2[0])+(3.0*p1[0])-(    p0[0]);
    x=a0+(a1*t)+(a2*tt)+(a3*ttt);
    a0=                                    (    p0[1]);
    a1=                        (3.0*p1[1])-(3.0*p0[1]);
    a2=            (3.0*p2[1])-(6.0*p1[1])+(3.0*p0[1]);
    a3=(    p3[1])-(3.0*p2[1])+(3.0*p1[1])-(    p0[1]);
    y=a0+(a1*t)+(a2*tt)+(a3*ttt);
    }
//---------------------------------------------------------------------------
void BEZIER_gett (double *p0,double *p1,double *p2,double *p3,double  x,double  y,double &t) // return t which is closest to (x,y)
    {
    double e,xx,yy;
    approx at;
    for (at.init(0.0,1.0,0.1,3,&e);!at.done;at.step())  // search t
        {
        BEZIER_getxy(p0,p1,p2,p3,xx,yy,at.a);
        xx-=x; xx*=xx;
        yy-=y; yy*=yy;
        e=xx+yy; // error is distance between points ^ 2
        }
    t=at.aa;
    }
//---------------------------------------------------------------------------
void BEZIER_draw (double *p0,double *p1,double *p2,double *p3,TCanvas *can,double x0,double y0,double zoom) // just render curve with VCL/GDI
    {
    int e;
    double x,y,t;
    BEZIER_getxy(p0,p1,p2,p3,x,y,0.0);
    x=x0+(x*zoom);
    y=y0-(y*zoom);
    can->MoveTo(x,y);
    for (e=1,t=0.0;e;t+=0.02)
        {
        if (t>=1.0) { e=0; t=1.0; }
        BEZIER_getxy(p0,p1,p2,p3,x,y,t);
        x=x0+(x*zoom);
        y=y0-(y*zoom);
        can->LineTo(x,y);
        }
    }
//---------------------------------------------------------------------------
void TMain::draw() // this is just my window redraw routine
    {
    if (!_redraw) return;

    // clear buffer
    bmp->Canvas->Brush->Color=clBlack;
    bmp->Canvas->FillRect(TRect(0,0,xs,ys));
    double x0=-40.0,y0=170.0,zoom=3.0;  // view
    double x,y,w=10,t;

    // whole BEZIER curve (Gray curve)
    bmp->Canvas->Pen->Color=clDkGray;
    BEZIER_draw(P0,P1,P2,P3,bmp->Canvas,x0,y0,zoom);

    // input point Pt (Green X)
    bmp->Canvas->Pen->Color=0x0000FF00;
    x=x0+(Pt[0]*zoom);
    y=y0-(Pt[1]*zoom);
    bmp->Canvas->MoveTo(x-w,y-w);
    bmp->Canvas->LineTo(x+w,y+w);
    bmp->Canvas->MoveTo(x+w,y-w);
    bmp->Canvas->LineTo(x-w,y+w);

    // closest point (Red +)
    bmp->Canvas->Pen->Color=clRed;
    BEZIER_gett (P0,P1,P2,P3,Pt[0],Pt[1],t);
    BEZIER_getxy(P0,P1,P2,P3,x,y,t);
    x=x0+(x*zoom);
    y=y0-(y*zoom);
    bmp->Canvas->MoveTo(x-w,y);
    bmp->Canvas->LineTo(x+w,y);
    bmp->Canvas->MoveTo(x,y-w);
    bmp->Canvas->LineTo(x,y+w);

    Caption=t;

    // render backbuffer
    Main->Canvas->Draw(0,0,bmp);
    _redraw=false;
    }
//---------------------------------------------------------------------------

As I am too lazy to debug your code I used for the BEZIER cubic solver my approx class from this related QA:

• How approximation search works

in the search itself I set search parameters for t=<0.0,1.0> with step 0.1 and 3 recursions leading to 0.1/10^(3-1) final precision of t which is 0.001 as your int_t step but the solution is found in 30 steps instead of yours 1000

To remedy your code just remember x,y,t wih smallest distance to tx,ty instead of just the one where distance<=epsilon

Answer 2

On easy way is with a cubic solver.

Now solve for x and solve for y. If the point is truly on the curve, you will get identical t values. Likely it's a bit off, so substitute the ts back, and take the closest one.

The coefficients are

  DX = m_P0.x;
  CX = 3.0f * ( m_P1.x - m_P0.x );
  BX = ( 3.0f * m_P2.x ) - ( 6.0f * m_P1.x ) + ( 3.0f * m_P0.x );
  AX = m_P3.x - ( 3.0f * m_P2.x ) + ( 3.0f * m_P1.x ) - m_P0.x; 

Do the same for y.

Now solve the cubic AXt^3 + BXt^2 + CXt + DX - px = 0 and find the three roots for t. Do the same for y, and find the three roots for t.

Now we've got 6 roots. Some might be complex, so ignore. So might be outside the interval 0 - epsilon, 1 + epsilon (allow a little slop) so ignore. If the point px, py is exactly on the curve, two of the t values will be on 0-1 and identical, and that's your answer. In reality the point will be a bit off. So Substitute all (up to 6) t values back into the bezier and get x, y. At least one x,y pair should be very close to px, py, except maybe for a point very close to cusp.

You can further refine your answer if you have two close points and px py is on the interval between them.