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

There are some questions about closest point on Bezier curve at SO — MBo, Dec 18 '16 at 05:49
Thanks @MBo for commenting so quickly first off! Is there a particular one that you think would be most insightful? — InsigMath, Dec 18 '16 at 05:52
I personally used method solving quintic equation (zero derivative of distance function). It finds all possible solutions (if many exist), but might suffer from numerical errors. But subdivision methods for Bezier work well too: http://stackoverflow.com/questions/2742610/ — MBo, Dec 18 '16 at 06:06
@InsigMath added answer with details but your input point is way off the curve itself so no surprise there that your solver is failing ... — Spektre, Dec 18 '16 at 11:19
fun fact: "value t which is in the range [0, 1] that corresponds to a particular position on a bezier curve" does not exist. The best you can get in the generic sense is "value t which is in the range [0, 1] that corresponds to one or more positions on a bezier curve". As parametric curves, Bezier curves can always overlap themselves. Sometimes degenerately so (when the curve looks like a line), sometimes because of self-intersection. But: unless you know something about the curve form before hand, you can never assume one t-value corresponds to only one coordinate, and vice versa. — Mike 'Pomax' Kamermans, Dec 18 '16 at 19:53

score 1 · Accepted Answer · edited May 23 '17 at 12:00

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

Hey @Spektre, thanks so much for the detailed answer! This isn't the answer I was hoping for because the context of this is to split a bezier curve in an animation program and I got tx and ty from the program, but this means that the program is potentially drawing the curve properly. In any case thanks so much! — InsigMath, Dec 19 '16 at 14:43

Malcolm McLean · Answer 2 · 2016-12-18T14:20:32.470

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.

That does not look as easy as you might think on first look. As BEZIER is parametric curve and not a function so there are no,several or even infinite solutions possible for individual dimension and cross matching could get ugly `if` tree or even `O(n^2)` loops for 2D... — Spektre, Dec 18 '16 at 11:39
I've expanded this a bit. The point must be reasonably close to the curve, but the method should work except maybe for points on cusps. — Malcolm McLean, Dec 18 '16 at 14:05

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

2 Answers2