3

I've found about a 1000 answers to this question, but none of them I can use, because I'm using 4 control points with my curves.

That said, I stumbled on this guy here:

double BezierArcLength(point2d p1, point2d p2, point2d p3, point2d p4)
{
    point2d k1, k2, k3, k4;

    k1 = -p1 + 3*(p2 - p3) + p4;
    k2 = 3*(p1 + p3) - 6*p2;
    k3 = 3*(p2 - p1);
    k4 = p1;

    q1 = 9.0*(sqr(k1.x) + sqr(k1.y));
    q2 = 12.0*(k1.x*k2.x + k1.y*k2.y);
    q3 = 3.0*(k1.x*k3.x + k1.y*k3.y) + 4.0*(sqr(k2.x) + sqr(k2.y));
    q4 = 4.0*(k2.x*k3.x + k2.y*k3.y);
    q5 = sqr(k3.x) + sqr(k3.y);

    double result = Simpson(balf, 0, 1, 1024, 0.001);
    return result;
}

It looks like it'd be the perfect solution, but that beginning part is utterly confusing to me:

k1 = -p1 + 3*(p2 - p3) + p4;
k2 = 3*(p1 + p3) - 6*p2;
k3 = 3*(p2 - p1);
k4 = p1;

How on earth am I supposed to do operations like add, subtract and multiply on 2-dimensional objects (I presume point2d is an object structure like {x: 0, y: 0})? I feel idiotic, but this is the only thing keeping me from actually implementing this monstrosity.

FWIW, I'm using this equation to normalize an entity's speed when traversing the curve in a game. If you know a better way of doing this altogether, I'm all ears.

dclowd9901
  • 6,756
  • 9
  • 44
  • 63
  • 2
    Question: How on earth am I supposed to do operations like add, subtract and multiply on 2-dimensional objects? Answer: You do them on one coordinate (x or y) at a time. – geowar Feb 27 '17 at 21:10

2 Answers2

17

Here’s how to traverse your cubic bezier curve at uniform speed

There isn't one simple formula for getting even length segments along a cubic bezier curve (meaning even arc-length segments). What's involved is calculating many points along the curve and then using interpolation to “nudge” each point into being roughly equidistant.

I can get you nearly there without your having to get a PH.D in Mathematics.

Start by using the common formula to calculate x/y points on the curve from t=0 to t=1 where t=0 represents the startpoint of the curve and t=1 represents the endpoint of the curve. This is the common formula:

// calc the x/y point at t interval
// t=0 at startPt, t=1 at endPt
var x=CubicN(t,startPt.x,controlPt1.x,controlPt2.x,endPt.x);
var y=CubicN(t,startPt.y,controlPt1.y,controlPt2.y,endPt.y);

// cubic helper formula at t interval
function CubicN(t, a,b,c,d) {
    var t2 = t * t;
    var t3 = t2 * t;
    return a + (-a * 3 + t * (3 * a - a * t)) * t
    + (3 * b + t * (-6 * b + b * 3 * t)) * t
    + (c * 3 - c * 3 * t) * t2
    + d * t3;
}

If you calculate enough intervals, say 100 intervals (t += .01 each loop) then you will get a very good approximation of the curve.

That means if you connect the 100 points with lines, the result would look very much like a cubic bezier curve.

But you're not done!

The series of x/y points calculated above are not uniform in arc-distance from each other.

Some neighboring points are close together and some neighboring points are farther apart.

To calculate evenly distributed points:

  1. Connect all the points with lines (creating a polyline).
  2. Calculate the total distance (T) of that polyline.
  3. Divide (T) by the number of uniform segments you desire, getting the uniform segment length (SL)
  4. Finally, walk the polyline from start to end, calculating each point that is (SL) distance from the previous point.

Result: you can use these equidistant points to traverse your curve.

Additional Refinement: This should result in a visually smooth movement along your Bezier path. But if you desire even more smoothness, just calculate more than 100 points--more points == more smoothness.

clstrfsck
  • 14,715
  • 4
  • 44
  • 59
markE
  • 102,905
  • 11
  • 164
  • 176
  • Just to try and attempt to expand point 4 for anyone else who (like me) struggles with it. In my instance I had taken 10 samples of my various intervals (represented as "t", in the above example). Once i got the "SL", instead of dividing each sample by 10, I divided it by the result of it's interval's average length. The equation is something like `single sample from interval (t) / (length of interval / average length of all intervals)`. You may also need to adjust your power of tens, but I'm not sure if that's for certain or just in my case. – atomictom Jun 28 '17 at 15:27
1

A 2-dimensional object, or a Point2D, is simply a Vector, and Vector Arithmetic is well-defined in mathematics. For example:

          k*(x,y) = (k*x, k*y)
           -(x,y) = (-1)*(x,y)
(x1,y1) + (x2,y2) = (x1+x2, y1+y2)

Those are all the formulas you need to calculate k1, k2, k3, and k4

torquestomp
  • 3,304
  • 19
  • 26