6
$\begingroup$

I've got a 2D cubic Bézier curve which, by construction, is a f(x) function : no loops, a single solution for each defined x.

Is there a common mean to convert this curve to a 3rd degree polynomial ? 3 should be enough since there can only be two "bumps".

Thanks!

$\endgroup$
4
  • $\begingroup$ There's no reason a cubic polynomial should have the right shape just because it looks similar. Are you okay with an approximation? How good does it need to be, and in what sense? $\endgroup$ Oct 16, 2010 at 11:53
  • $\begingroup$ I need the curve's extremity values and derivatives to be exact, and the polynomial to be a reasonably close match (perceptively speaking. This is for camera paths.). After investigation, 3rd degree really is not enough, because the 4 constraints (y and dy, both sides) already resolves the 4 parameters, and Bezier curves are more tweakable than that. I'll see what I can do with 4rth degree polynomial. $\endgroup$
    – Calvin1602
    Oct 16, 2010 at 14:24
  • $\begingroup$ I must be missing something (or maybe two things). First, if the curve is a quadratic Bezier curve, then it is certainly a (degenerate) cubic Bezier curve. Secondly, how can a quadratic Bezier curve have "two bumps" ?? A quadratic Bezier curve is a parabola ! $\endgroup$
    – bubba
    Jan 8, 2013 at 14:05
  • $\begingroup$ @bubba : my mistake, I meant cubic. $\endgroup$
    – Calvin1602
    Jan 8, 2013 at 17:55

2 Answers 2

2
$\begingroup$

I assume you want a polynomial function $y=f(x)$ that has the same shape as your original parametric cubic Bezier curve.

Well, you already have $y$ as a function of $x$, but the function is unpleasant. For a given value of $x$, there is no closed form formula for the corresponding $y$ -- you have to find $y$ numerically (by intersecting a vertical line with the given Bezier curve).

Let's denote this unpleasant function by $y=g(x)$. So, now the problem is just to approximate $g$ by a polynomial $f$. There are lots of standard ways to do this, depending on how you want to measure the approximation error and what extra conditions you want $f$ to satisfy. You say you want exact matching of end points and end tangents.

So, you choose a degree $m$ for $f$. As you say, $m$ will have to be bigger than 4. Then $f$ will have $m+1$ coefficients, which you can determine by solving a system of $m+1$ linear equations. You get 4 equations from the end-point constraints. Pick another $m-3$ points $(x_i,y_i)$ in the interior of the curve, and, for each $i$, write down the equation that expresses the requirement that $y_i = f(x_i)$. Solve the system of linear equations.

One subtlety is that the extra $m-3$ points have to be chosen fairly carefully. You can't just distribute them uniformly, or else $f$ might wiggle badly. They have to be more dense towards the ends of the curve, and less dense in the middle. The "Chebyshev nodes" are a good choice.

This process is called Hermite interpolation if you use derivative information, and Lagrange interpolation if you don't. Both are covered in Wikipedia articles.

$\endgroup$
1
$\begingroup$

Well, it turns out it's not really possible.

The following Processing code shows my results for a 4th order polynomial. The equations of the parameters are from Maple.

float x1 = 10;
float y1 = 20;
float x3 = 90;
float y3 = 50;
float d1 = 3;
float d3 = 1;
float f = 40;

float x2 = 30;
float y2 = mouseY;

void draw(){
background(100);
   x2 = mouseX;
   y2 = mouseY;

  noFill();
  stroke(0, 0, 0);
  bezier(x1, y1,  x1+f, y1+f*d1, x3-f, y3-f*d3,    x3,y3);

  stroke(255, 102, 0);

  for (float i=x1; i<x3;i++){
    point(i, approx(i));
  }
}

float approx(float time){
  float a,b,c,d,e;

a = -(8*x1*pow(x3,2)*x2*y1-2*pow(x1,4)*y3+2*pow(x3,4)*y1-pow(x1,2)*d3*pow(x3,3)+2*pow(x1,4)*d3*x3-pow(x1,3)*d3*pow(x3,2)+pow(x1,2)*d1*pow(x3,3)+pow(x1,3)*d1*pow(x3,2)-2*x1*pow(x3,4)*d1-8*x1*pow(x3,2)*x2*y3-8*x3*pow(x1,2)*x2*y3+8*x3*pow(x1,2)*x2*y1-2*pow(x1,3)*x3*x2*d1-2*pow(x3,2)*pow(x1,2)*x2*d1+x3*pow(x1,2)*pow(x2,2)*d1-x3*pow(x1,2)*pow(x2,2)*d3-2*x3*pow(x1,3)*x2*d3+2*x1*pow(x3,3)*x2*d1+x1*pow(x3,2)*pow(x2,2)*d1-x1*pow(x3,2)*pow(x2,2)*d3+2*pow(x1,2)*pow(x3,2)*x2*d3+2*pow(x3,3)*x2*x1*d3+3*pow(x1,3)*pow(x2,2)*d3-2*pow(x1,4)*x2*d3+pow(x1,3)*pow(x2,2)*d1+4*pow(x1,3)*x3*y3+2*pow(x1,4)*y2-2*pow(x3,4)*y2-2*pow(x2,4)*y3+2*pow(x2,4)*y1+4*x1*y3*x3*pow(x2,2)-4*x1*y1*x3*pow(x2,2)+2*pow(x3,4)*x2*d1-3*pow(x3,3)*pow(x2,2)*d1-pow(x3,3)*pow(x2,2)*d3+pow(x2,4)*x3*d3-pow(x2,4)*x1*d3-pow(x2,4)*x1*d1+pow(x2,4)*x3*d1-4*pow(x3,3)*x1*y1+4*pow(x3,3)*x1*y2-4*pow(x3,2)*pow(x1,2)*y1-4*x3*pow(x1,3)*y2-4*pow(x1,2)*pow(x2,2)*y1+4*pow(x1,2)*pow(x2,2)*y3-4*pow(x3,2)*pow(x2,2)*y1+4*pow(x3,2)*pow(x2,2)*y3+4*pow(x3,2)*pow(x1,2)*y3)/((-pow(x3,3)-3*x3*pow(x1,2)+pow(x1,3)+3*x1*pow(x3,2))*(pow(x3,2)*pow(x1,2)-2*x3*pow(x1,2)*x2+pow(x1,2)*pow(x2,2)+4*x1*x3*pow(x2,2)-2*x1*pow(x3,2)*x2-2*x1*pow(x2,3)+pow(x2,4)-2*x3*pow(x2,3)+pow(x3,2)*pow(x2,2)));
b = (y1*pow(x3,5)-pow(x1,2)*pow(x3,4)*d1+2*pow(x1,3)*pow(x3,3)*d1-2*pow(x1,3)*pow(x3,3)*d3+pow(x1,4)*pow(x3,2)*d3+pow(x1,5)*x3*d3-pow(x1,4)*x3*y3-x1*pow(x3,5)*d1+x1*pow(x3,4)*y1-pow(x1,5)*y3-pow(x3,3)*d3*pow(x2,3)+pow(x3,5)*x2*d1-pow(x3,5)*y2-3*pow(x3,3)*d1*pow(x2,3)+pow(x3,2)*pow(x2,4)*d3-3*y3*x3*pow(x2,4)-3*pow(x1,3)*pow(x3,2)*x2*d1-pow(x1,3)*pow(x3,2)*x2*d3-pow(x1,4)*x3*x2*d3+pow(x1,2)*x3*d1*pow(x2,3)+3*pow(x1,2)*pow(x3,3)*x2*d3+pow(x1,2)*pow(x3,3)*x2*d1-pow(x1,2)*x3*d3*pow(x2,3)+x1*pow(x2,4)*x3*d3-x1*pow(x2,4)*x3*d1+2*pow(x2,4)*pow(x3,2)*d1+pow(x1,5)*y2+3*x3*pow(x2,4)*y1-pow(x1,5)*x2*d3+pow(x1,4)*x3*y2+3*pow(x1,3)*d3*pow(x2,3)+pow(x1,3)*d1*pow(x2,3)-2*pow(x1,2)*pow(x2,4)*d3-pow(x1,2)*pow(x2,4)*d1-3*x1*pow(x2,4)*y3-x1*pow(x3,4)*y2+3*x1*pow(x2,4)*y1+x1*pow(x3,4)*x2*d1-x1*pow(x3,2)*d3*pow(x2,3)+x1*pow(x3,2)*d1*pow(x2,3)+4*pow(x3,2)*y3*pow(x2,3)-12*pow(x1,2)*y3*pow(x3,2)*x2+12*pow(x1,2)*y1*pow(x3,2)*x2+4*x1*x3*pow(x2,3)*y3-4*x1*x3*pow(x2,3)*y1+8*pow(x1,3)*y3*pow(x3,2)-8*pow(x1,3)*pow(x3,2)*y2+4*pow(x1,2)*y3*pow(x2,3)-4*pow(x1,2)*y1*pow(x2,3)-8*pow(x1,2)*pow(x3,3)*y1+8*pow(x1,2)*pow(x3,3)*y2-4*pow(x3,2)*pow(x2,3)*y1)/((-x3+x1)*(pow(x3,2)*pow(x1,4)-2*pow(x1,4)*x3*x2+pow(x1,4)*pow(x2,2)-2*pow(x3,3)*pow(x1,3)+2*pow(x1,3)*x3*pow(x2,2)+2*pow(x1,3)*pow(x3,2)*x2-2*pow(x1,3)*pow(x2,3)+pow(x1,2)*pow(x2,4)+2*pow(x1,2)*x3*pow(x2,3)+pow(x3,4)*pow(x1,2)-6*pow(x1,2)*pow(x2,2)*pow(x3,2)+2*pow(x1,2)*pow(x3,3)*x2+2*x1*pow(x3,3)*pow(x2,2)-2*x1*x3*pow(x2,4)-2*x1*pow(x3,4)*x2+2*x1*pow(x3,2)*pow(x2,3)+pow(x2,4)*pow(x3,2)-2*pow(x3,3)*pow(x2,3)+pow(x3,4)*pow(x2,2)));
c = -(pow(x1,3)*pow(x3,4)*d1-pow(x1,4)*pow(x3,3)*d3+pow(x1,5)*pow(x3,2)*d3-2*pow(x1,5)*x3*y3-pow(x1,2)*pow(x3,5)*d1+2*pow(x1,4)*d3*pow(x2,3)+2*y1*pow(x3,5)*x1-2*x1*pow(x3,5)*y2+pow(x3,5)*pow(x2,2)*d1-2*d1*pow(x3,4)*pow(x2,3)-2*pow(x1,2)*pow(x2,4)*x3*d1-pow(x1,2)*pow(x2,4)*x3*d3-pow(x1,4)*x3*pow(x2,2)*d3+x1*pow(x3,4)*pow(x2,2)*d1+pow(x3,3)*pow(x1,2)*pow(x2,2)*d1+3*pow(x3,3)*pow(x1,2)*pow(x2,2)*d3-pow(x3,2)*pow(x1,3)*pow(x2,2)*d3-3*pow(x3,2)*pow(x1,3)*pow(x2,2)*d1+2*pow(x3,2)*pow(x2,4)*x1*d3+pow(x3,2)*pow(x2,4)*x1*d1+pow(x3,3)*pow(x2,4)*d1-pow(x1,3)*pow(x2,4)*d3-pow(x1,5)*pow(x2,2)*d3+2*pow(x1,5)*x3*y2-6*x3*x1*pow(x2,4)*y3+6*x3*x1*pow(x2,4)*y1+2*pow(x1,3)*x3*d1*pow(x2,3)+2*pow(x1,3)*x3*d3*pow(x2,3)+2*pow(x1,2)*pow(x3,2)*d1*pow(x2,3)-2*pow(x1,2)*pow(x3,2)*d3*pow(x2,3)-2*x1*pow(x3,3)*d3*pow(x2,3)-2*x1*pow(x3,3)*d1*pow(x2,3)+8*y3*pow(x2,3)*x3*pow(x1,2)+8*y3*pow(x2,3)*x1*pow(x3,2)-8*y1*pow(x2,3)*x3*pow(x1,2)-8*y1*pow(x2,3)*x1*pow(x3,2)-12*pow(x1,2)*pow(x3,2)*pow(x2,2)*y3+12*pow(x1,2)*pow(x3,2)*pow(x2,2)*y1+4*pow(x1,4)*pow(x3,2)*y3-4*pow(x1,4)*pow(x3,2)*y2-4*pow(x1,2)*pow(x3,4)*y1+4*pow(x1,2)*pow(x3,4)*y2)/((-x3+x1)*(pow(x3,2)*pow(x1,4)-2*pow(x1,4)*x3*x2+pow(x1,4)*pow(x2,2)-2*pow(x3,3)*pow(x1,3)+2*pow(x1,3)*x3*pow(x2,2)+2*pow(x1,3)*pow(x3,2)*x2-2*pow(x1,3)*pow(x2,3)+pow(x1,2)*pow(x2,4)+2*pow(x1,2)*x3*pow(x2,3)+pow(x3,4)*pow(x1,2)-6*pow(x1,2)*pow(x2,2)*pow(x3,2)+2*pow(x1,2)*pow(x3,3)*x2+2*x1*pow(x3,3)*pow(x2,2)-2*x1*x3*pow(x2,4)-2*x1*pow(x3,4)*x2+2*x1*pow(x3,2)*pow(x2,3)+pow(x2,4)*pow(x3,2)-2*pow(x3,3)*pow(x2,3)+pow(x3,4)*pow(x2,2)));
d = (3*x1*pow(x3,2)*pow(x2,4)*y1+2*x3*d3*pow(x1,4)*pow(x2,3)-pow(x3,5)*pow(x1,2)*x2*d1+pow(x3,4)*pow(x1,3)*x2*d1+pow(x3,4)*pow(x1,2)*pow(x2,2)*d1+pow(x3,5)*x1*pow(x2,2)*d1+2*pow(x3,3)*pow(x1,3)*pow(x2,2)*d3-pow(x3,3)*pow(x1,4)*x2*d3-2*pow(x3,3)*pow(x1,3)*pow(x2,2)*d1+pow(x3,3)*pow(x2,4)*x1*d1-pow(x3,2)*pow(x1,4)*pow(x2,2)*d3+pow(x3,2)*pow(x1,5)*x2*d3-x3*pow(x1,5)*pow(x2,2)*d3-3*x3*pow(x1,2)*pow(x2,4)*y3+pow(x3,2)*pow(x1,2)*pow(x2,4)*d3-x3*pow(x1,3)*pow(x2,4)*d3-pow(x3,2)*pow(x1,2)*pow(x2,4)*d1-3*pow(x3,3)*pow(x1,4)*y2-pow(x3,3)*pow(x2,4)*y1-pow(x3,5)*pow(x1,2)*y2+3*pow(x1,3)*pow(x3,4)*y2+pow(x1,3)*pow(x2,4)*y3+pow(x1,5)*pow(x3,2)*y2-2*y3*pow(x1,4)*pow(x2,3)+y3*pow(x1,5)*pow(x2,2)+2*y1*pow(x3,4)*pow(x2,3)-y1*pow(x3,5)*pow(x2,2)-2*y3*pow(x1,5)*x3*x2+y3*x3*pow(x1,4)*pow(x2,2)-2*x1*d1*pow(x3,4)*pow(x2,3)-y1*x1*pow(x3,4)*pow(x2,2)+2*y1*pow(x3,5)*x2*x1+pow(x1,3)*pow(x3,2)*d1*pow(x2,3)-pow(x1,3)*pow(x3,2)*d3*pow(x2,3)+pow(x1,2)*pow(x3,3)*d1*pow(x2,3)-pow(x1,2)*pow(x3,3)*d3*pow(x2,3)+4*pow(x1,4)*pow(x3,2)*y3*x2-4*pow(x1,2)*pow(x3,4)*y1*x2-4*pow(x1,2)*pow(x3,2)*pow(x2,3)*y1+4*pow(x1,2)*pow(x3,2)*y3*pow(x2,3)-4*pow(x3,3)*x1*pow(x2,3)*y1+8*pow(x3,3)*pow(x1,2)*pow(x2,2)*y1+4*pow(x1,3)*x3*pow(x2,3)*y3-8*pow(x1,3)*pow(x3,2)*pow(x2,2)*y3)/((-x3+x1)*(pow(x3,2)*pow(x1,4)-2*pow(x1,4)*x3*x2+pow(x1,4)*pow(x2,2)-2*pow(x3,3)*pow(x1,3)+2*pow(x1,3)*x3*pow(x2,2)+2*pow(x1,3)*pow(x3,2)*x2-2*pow(x1,3)*pow(x2,3)+pow(x1,2)*pow(x2,4)+2*pow(x1,2)*x3*pow(x2,3)+pow(x3,4)*pow(x1,2)-6*pow(x1,2)*pow(x2,2)*pow(x3,2)+2*pow(x1,2)*pow(x3,3)*x2+2*x1*pow(x3,3)*pow(x2,2)-2*x1*x3*pow(x2,4)-2*x1*pow(x3,4)*x2+2*x1*pow(x3,2)*pow(x2,3)+pow(x2,4)*pow(x3,2)-2*pow(x3,3)*pow(x2,3)+pow(x3,4)*pow(x2,2)));
e = (pow(x3,3)*y1-pow(x1,3)*y3-x1*pow(x3,3)*d1+pow(x1,2)*pow(x3,2)*d1-3*pow(x3,2)*y1*x1-pow(x3,2)*d3*pow(x1,2)+pow(x1,3)*x3*d3+3*x3*y3*pow(x1,2)+x3*d3*pow(x2,3)+pow(x3,3)*x2*d1-2*pow(x3,2)*pow(x2,2)*d1-pow(x3,2)*pow(x2,2)*d3+3*y3*x3*pow(x2,2)-3*y1*x3*pow(x2,2)+x3*d1*pow(x2,3)-pow(x3,3)*y2-2*y3*pow(x2,3)+2*y1*pow(x2,3)-2*pow(x1,2)*x3*x2*d1-pow(x1,2)*x3*x2*d3+x1*pow(x3,2)*x2*d1+2*x1*pow(x3,2)*x2*d3-x1*x3*pow(x2,2)*d3+6*x1*y1*x3*x2-6*x1*y3*x3*x2+x1*x3*pow(x2,2)*d1-x1*d1*pow(x2,3)+3*x1*y3*pow(x2,2)-3*x1*y1*pow(x2,2)+3*x1*pow(x3,2)*y2-pow(x1,3)*x2*d3+2*pow(x1,2)*pow(x2,2)*d3+pow(x1,2)*pow(x2,2)*d1-3*pow(x1,2)*x3*y2-x1*d3*pow(x2,3)+pow(x1,3)*y2)/(-pow(x2,4)*pow(x3,3)+pow(x1,5)*pow(x3,2)-3*pow(x1,4)*pow(x3,3)-pow(x3,5)*pow(x2,2)-pow(x1,2)*pow(x3,5)+3*pow(x1,3)*pow(x3,4)+pow(x2,4)*pow(x1,3)+pow(x1,5)*pow(x2,2)+2*pow(x3,4)*pow(x2,3)-2*pow(x1,4)*pow(x2,3)+3*pow(x2,4)*x1*pow(x3,2)-8*pow(x1,3)*pow(x3,2)*pow(x2,2)+2*pow(x3,5)*x2*x1-3*pow(x2,4)*x3*pow(x1,2)-x1*pow(x3,4)*pow(x2,2)+x3*pow(x1,4)*pow(x2,2)+4*pow(x1,4)*pow(x3,2)*x2-4*pow(x1,2)*pow(x3,4)*x2+8*pow(x3,3)*pow(x1,2)*pow(x2,2)-2*pow(x1,5)*x3*x2+4*pow(x1,3)*x3*pow(x2,3)-4*pow(x3,3)*x1*pow(x2,3));
  return 
  e*time*time*time*time+
  a*time*time*time+
  b*time*time+
  c*time+
  d;   
}

I'll try with adding the derivative of x2 and adding another point in the middle (with a 5rth order polynomial) but I'm not sure it'll appropriate for my use.

$\endgroup$
2
  • $\begingroup$ Wow, what heck is that? $\endgroup$ Mar 15, 2011 at 1:10
  • $\begingroup$ @muntoo : It's an approximation of a Bezier curve using a 4th degree polynomial, given the starting point, the end point, another point in the middle, and two derivatives. Equations are computed by Maple. But yeah it's ugly. $\endgroup$
    – Calvin1602
    Mar 15, 2011 at 8:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .