Fastest way to calculate cubic bezier curves?

Question

Right now I calculate it like this:

    double dx1 = a.RightHandle.x - a.UserPoint.x;
    double dy1 = a.RightHandle.y - a.UserPoint.y;
    double dx2 = b.LeftHandle.x - a.RightHandle.x;
    double dy2 = b.LeftHandle.y - a.RightHandle.y;
    double dx3 = b.UserPoint.x - b.LeftHandle.x;
    double dy3 = b.UserPoint.y - b.LeftHandle.y;

    float len = sqrt(dx1 * dx1 + dy1 * dy1) + 
        sqrt(dx2 * dx2 + dy2 * dy2) + 
        sqrt(dx3 * dx3 + dy3 * dy3);




    int NUM_STEPS =  int(len * 0.05);

    if(NUM_STEPS > 55)
    {
        NUM_STEPS = 55;
    }
    double subdiv_step  = 1.0 / (NUM_STEPS + 1);
    double subdiv_step2 = subdiv_step*subdiv_step;
    double subdiv_step3 = subdiv_step*subdiv_step*subdiv_step;

    double pre1 = 3.0 * subdiv_step;
    double pre2 = 3.0 * subdiv_step2;
    double pre4 = 6.0 * subdiv_step2;
    double pre5 = 6.0 * subdiv_step3;



    double tmp1x = a.UserPoint.x - a.RightHandle.x * 2.0 + b.LeftHandle.x;
    double tmp1y = a.UserPoint.y - a.RightHandle.y  * 2.0 + b.LeftHandle.y;

    double tmp2x = (a.RightHandle.x - b.LeftHandle.x)*3.0 - a.UserPoint.x + b.UserPoint.x;
    double tmp2y = (a.RightHandle.y - b.LeftHandle.y)*3.0 - a.UserPoint.y + b.UserPoint.y;

    double fx = a.UserPoint.x;
    double fy = a.UserPoint.y;

    //a user
    //a right
    //b left
    //b user

    double dfx = (a.RightHandle.x - a.UserPoint.x)*pre1 + tmp1x*pre2 + tmp2x*subdiv_step3;
    double dfy = (a.RightHandle.y - a.UserPoint.y)*pre1 + tmp1y*pre2 + tmp2y*subdiv_step3;

    double ddfx = tmp1x*pre4 + tmp2x*pre5;
    double ddfy = tmp1y*pre4 + tmp2y*pre5;

    double dddfx = tmp2x*pre5;
    double dddfy = tmp2y*pre5;

    int step = NUM_STEPS;



    while(step--)
    {


        fx   += dfx;
        fy   += dfy;
        dfx  += ddfx;
        dfy  += ddfy;
        ddfx += dddfx;
        ddfy += dddfy;
        temp[0] = fx;
        temp[1] = fy;
        Contour[currentcontour].DrawingPoints.push_back(temp);
    }


    temp[0] = (GLdouble)b.UserPoint.x;
    temp[1] = (GLdouble)b.UserPoint.y;
    Contour[currentcontour].DrawingPoints.push_back(temp);

I'm wondering if there is a faster way to interpolate cubic beziers?

Thanks

Answer 1

Look into forward differencing for a faster method. Care must be taken to deal with rounding errors.

The adaptive subdivision method, with some checks, can be fast and accurate.

Answer 2

There is another point that is also very important, which is that you are approximating your curve using a lot of fixed-length straight-line segments. This is inefficient in areas where your curve is nearly straight, and can lead to a nasty angular poly-line where the curve is very curvy. There is not a simple compromise that will work for high and low curvatures.

To get around this is you can dynamically subdivide the curve (e.g. split it into two pieces at the half-way point and then see if the two line segments are within a reasonable distance of the curve. If a segment is a good fit for the curve, stop there; if it is not, then subdivide it in the same way and repeat). You have to be careful to subdivide it enough that you don't miss any localised (small) features when sampling the curve in this way.

This will not always draw your curve "faster", but it will guarantee that it always looks good while using the minimum number of line segments necessary to achieve that quality.

Once you are drawing the curve "well", you can then look at how to make the necessary calculations "faster".