Points evenly spaced along a bezier curve

Question

I have looked around for a while and I can't find a solution to this problem. Let's say I have a cubic bezier curve (defined by 4 points) and I want to get a set of points that are spaced evenly along the curve. Think of placing a text along a curve for an example.

Now the problem is that if I input t (interpolation value from 0-1) with a constant increment the points are not evenly spaced. The distance along the curve is smaller when the curve makes a turn and longer when the curve is straight.

So how do I place points evenly along a bezier curve?

Answer 1

It's more of a math question. So a bezier curve has the following formula, both in the x and y component.

B_x(t) = (1-t)^3 * P0_x + (1-t)^2 * t * P1_x + (1-t) * t^2 * P2_x + t^3 * P3_x
B_y(t) = (1-t)^3 * P0_y + (1-t)^2 * t * P1_y + (1-t) * t^2 * P2_x + t^3 * P3_y

Length traveled by t along a curve gamma is given by:

length_gamma(t) = integration( sqrt( derivative(  gamma_x(s)  ) ^2 + derivative(  gamma_y(s)  ) ^2 ) )

There's no human-writable solution to the integral, so you have to approximate.

Replace the gamma(t) by the expression B(t) to get the length length_B traveled by t along the bezier segment. Let's say it travels from 0 to L.

Now pick n values between 0 and L that correspond to the evenly spaced points. For examples, lengths of the form k*L/n for k from 0 to n.

Now you need to inverse the function length_B, so you can compute the t back from the length l. It's quite a lot of math and I'm lazy as hell, try doing it yourself. If you can't, you can go to the math stackexchange. For a more complete answer, you can go there anyway.

Once you have that inverse length_B function (or a reasonable approximation), you process is quite simple.

• Create lengths l[k] of given path distance away from the origin (P0_x,P1_x).
• Compute their corresponding t[k] using length_B_inverse.
• Positing the points using (B_x(t[k]),B_y(t[k])).

Answer 2

Well it has been some time...

But I was finally able to solve this problem!

Everything you need is in this post: Moving ships between two planets along a bezier, missing some equations for acceleration

Answer 3

Just to expand on what Marco said, a common technique for doing this is to walk down the curve in much smaller increments than the fixed length steps you want to take and store the resulting output point (and perhaps distance?) in a table.

Then, you go through the table and discard all the entries except those points that are closest to the integer multiples of the distances you want to walk.

Then you are left with a table you can index directly at runtime very quickly. If you want to go to the spot that is 5 times the size of your distance you look in your table at index [5].

Note that you could do the two steps in one and not actually store the extra items in the table to begin with, but it's easier to visualize and understand in two steps.

I once saw a technique for actually calculating this on the fly without precalculating a table (it didn't use iteration / root finding either!), but unfortunately I can't remember the details at all ):

If i remember it or find it, i'll post the info!

Answer 4

Step 1 - Generate N+1 points by interpolating the curve in increments of 1/N. N should be large enough for good visual results but small enough to be easily computed. A value of 50 should be OK for most situations but it should be tuned for your specific case. I will call this the "interpolated points".

Alternatively you can generate a short list of segments and recursively break each segment that is longer than the desired maximum segment length (initially you should generate at least four segments to account for S curves where the start is very close to the end).

Step 2 - "Walk the line" using the interpolated points and the spacing you want between each point.

I'll leave it here my Unity code:

public static Vector2[] InterpolateBezier(Vector2 start, Vector2 startControlPoint,
    Vector2 end, Vector2 endControlPoint, int segments)
{
    Vector2[] interpolated = new Vector2[segments + 1];
    interpolated[0] = start;
    interpolated[segments] = end;

    float step = 1f / segments;
    for (int i = 1; i < segments; i++)
    {
        interpolated[i] = GetBezierPosition(start, startControlPoint, end,
            endControlPoint, i * step);
    }

    return interpolated;
}

public static Vector2 GetBezierPosition(Vector2 start, Vector2 startControlPoint,
    Vector2 end, Vector2 endControlPoint, float t)
{
    float omt = 1f - t;
    float omt2 = omt * omt;
    float t2 = t * t;

    return
        start * (omt2 * omt) +
        startControlPoint * (3f * omt2 * t) +
        endControlPoint * (3f * omt * t2) +
        end * (t2 * t);
}

public static List<Vector2> WalkLine(Vector2[] points, float spacing, float offset = 0)
{
    List<Vector2> result = new List<Vector2>();

    spacing = spacing > 0.00001f ? spacing : 0.00001f;

    float distanceNeeded = offset;
    while (distanceNeeded < 0)
    {
        distanceNeeded += spacing;
    }

    Vector2 current = points[0];
    Vector2 next = points[1];
    int i = 1;
    int last = points.Length - 1;
    while (true)
    {
        Vector2 diff = next - current;
        float dist = diff.magnitude;

        if (dist >= distanceNeeded)
        {
            current += diff * (distanceNeeded / dist);
            result.Add(current);
            distanceNeeded = spacing;
        }
        else if (i != last)
        {
            distanceNeeded -= dist;
            current = next;
            next = points[++i];
        }
        else
        {
            break;
        }
    }

    return result;
}

Answer 5

Here's some algorithm that gives pretty ok results:

  Point Index(float pos) const
  {
    int count = p.NumPoints();
    Vector val(0.0,0.0,0.0);
    for(int i=0;i<count;i++)
      { 
        val += bin(pos,i,count-1)*Vector(p.Points(i));
      }
    return Point(val);
  }
  float bin(float pos, int i, int n) const
  { 
    return float(ni(n,i)) * pow(double(pos), double(i))*pow(double(1.0-pos), double(n-i));
  }
  int ni(int n, int i) const
  {
    if (i==0) { return 1; }
    if (n==i) { return 1; }
    return ni(n-1,i-1)+ni(n-1,i);
  }