7
\$\begingroup\$

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?

\$\endgroup\$
  • 4
    \$\begingroup\$ Are you looking for a "purely mathematical" (or particularly efficient) solution? Otherwise, the straightforward approach is: Convert the curve into a polyline, by walking along the curve, increasing the t in, say, 100 steps, and measure the distances between the resulting points. Then, interpolate along this polyline as desired. \$\endgroup\$ – Marco13 Aug 6 '15 at 15:35
  • \$\begingroup\$ I think you are looking for keyword "arc length parametrization", which was answered for example in this question. \$\endgroup\$ – wondra Aug 6 '15 at 16:07
  • \$\begingroup\$ What @Marco13 said! \$\endgroup\$ – david van brink Aug 6 '15 at 20:14
  • \$\begingroup\$ According to the answers/comments, the approach that I mentioned is not only straightforward, but also rather common. Is this for a particular language? Maybe someone would post a few lines of code then... \$\endgroup\$ – Marco13 Aug 6 '15 at 21:08
  • \$\begingroup\$ @Macro, you can also do a "binary-like" search to approximate the next point on the curve that is d pixels away each time. \$\endgroup\$ – wolfdawn Sep 7 '15 at 11:25
2
\$\begingroup\$

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])).
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you! Turns out the math you need to integrate the bernstein polynomial is a nightmare. I was able to use this solution \$\endgroup\$ – Foaly Feb 4 '17 at 19:16
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
-1
\$\begingroup\$

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);
  }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.