How do I convert the 2 control points of a cubic curve to the single control point of a quadratic curve?

Question

Having searched the web, I see various people in various forums alluding to approximating a cubic curve with a quadratic one. But I can't find the formula.

What I want is this:

input: startX, startY, control1X, control1Y, control2X, control2Y, endX, endY output: startX, startY, controlX, controlY, endX, endY

Actually, since the starting and ending points will be the same, all I really need is...

input: startX, startY, control1X, control1Y, control2X, control2Y, endX, endY output: controlX, controlY

Answer 1

As mentioned, going from 4 control points to 3 is normally going to be an approximation. There's only one case where it will be exact - when the cubic bezier curve is actually a degree-elevated quadratic bezier curve.

You can use the degree elevation equations to come up with an approximation. It's simple, and the results are usually pretty good.

Let's call the control points of the cubic Q0..Q3 and the control points of the quadratic P0..P2. Then for degree elevation, the equations are:

Q0 = P0
Q1 = 1/3 P0 + 2/3 P1
Q2 = 2/3 P1 + 1/3 P2
Q3 = P2

In your case you have Q0..Q3 and you're solving for P0..P2. There are two ways to compute P1 from the equations above:

P1 = 3/2 Q1 - 1/2 Q0
P1 = 3/2 Q2 - 1/2 Q3

If this is a degree-elevated cubic, then both equations will give the same answer for P1. Since it's likely not, your best bet is to average them. So,

P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3

To translate to your terms:

controlX = -0.25*startX + .75*control1X + .75*control2X -0.25*endX

Y is computed similarly - the dimensions are independent, so this works for 3d (or n-d).

This will be an approximation. If you need a better approximation, one way to get it is by subdividing the initial cubic using the deCastlejau algorithm, and then degree-reduce each segment. If you need better continuity, there are other approximation methods that are less quick and dirty.

Answer 2

The cubic can have loops and cusps, which quadratic cannot have. This means that there are not simple solutions nearly never. If cubic is already a quadratic, then the simple solution exists. Normally you have to divide cubic to parts that are quadratics. And you have to decide what are the critical points for subdividing.

http://fontforge.org/bezier.html#ps2ttf says: "Other sources I have read on the net suggest checking the cubic spline for points of inflection (which quadratic splines cannot have) and forcing breaks there. To my eye this actually makes the result worse, it uses more points and the approximation does not look as close as it does when ignoring the points of inflection. So I ignore them."

This is true, the inflection points (second derivatives of cubic) are not enough. But if you take into account also local extremes (min, max) which are the first derivatives of cubic function, and force breaks on those all, then the sub curves are all quadratic and can be presented by quadratics.

I tested the below functions, they work as expected (find all critical points of cubic and divides the cubic to down-elevated cubics). When those sub curves are drawn, the curve is exactly the same as original cubic, but for some reason, when sub curves are drawn as quadratics, the result is nearly right, but not exactly.

So this answer is not for strict help for the problem, but those functions provide a starting point for cubic to quadratic conversion.

To find both local extremes and inflection points, the following get_t_values_of_critical_points() should provide them. The

function compare_num(a,b) {
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}

function find_inflection_points(p1x,p1y,p2x,p2y,p3x,p3y,p4x,p4y)
{
  var ax = -p1x + 3*p2x - 3*p3x + p4x;
  var bx = 3*p1x - 6*p2x + 3*p3x;
  var cx = -3*p1x + 3*p2x;

  var ay = -p1y + 3*p2y - 3*p3y + p4y;
  var by = 3*p1y - 6*p2y + 3*p3y;
  var cy = -3*p1y + 3*p2y;
  var a = 3*(ay*bx-ax*by);
  var b = 3*(ay*cx-ax*cy);
  var c = by*cx-bx*cy;
  var r2 = b*b - 4*a*c;
  var firstIfp = 0;
  var secondIfp = 0;
  if (r2>=0 && a!==0)
  {
    var r = Math.sqrt(r2);
    firstIfp = (-b + r) / (2*a);
    secondIfp = (-b - r) / (2*a);
    if ((firstIfp>0 && firstIfp<1) && (secondIfp>0 && secondIfp<1))
    {
      if (firstIfp>secondIfp)
      {
        var tmp = firstIfp;
        firstIfp = secondIfp;
        secondIfp = tmp;
      }
      if (secondIfp-firstIfp >0.00001)
        return [firstIfp, secondIfp];
      else return [firstIfp];
    }
    else if (firstIfp>0 && firstIfp<1)
      return [firstIfp];
    else if (secondIfp>0 && secondIfp<1)
    {
      firstIfp = secondIfp;
      return [firstIfp];
    }
    return [];
  }
  else return [];
}

function get_t_values_of_critical_points(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y) {
    var a = (c2x - 2 * c1x + p1x) - (p2x - 2 * c2x + c1x),
    b = 2 * (c1x - p1x) - 2 * (c2x - c1x),
    c = p1x - c1x,
    t1 = (-b + Math.sqrt(b * b - 4 * a * c)) / 2 / a,
    t2 = (-b - Math.sqrt(b * b - 4 * a * c)) / 2 / a,
    tvalues=[];
    Math.abs(t1) > "1e12" && (t1 = 0.5);
    Math.abs(t2) > "1e12" && (t2 = 0.5);
    if (t1 >= 0 && t1 <= 1 && tvalues.indexOf(t1)==-1) tvalues.push(t1)
    if (t2 >= 0 && t2 <= 1 && tvalues.indexOf(t2)==-1) tvalues.push(t2);

    a = (c2y - 2 * c1y + p1y) - (p2y - 2 * c2y + c1y);
    b = 2 * (c1y - p1y) - 2 * (c2y - c1y);
    c = p1y - c1y;
    t1 = (-b + Math.sqrt(b * b - 4 * a * c)) / 2 / a;
    t2 = (-b - Math.sqrt(b * b - 4 * a * c)) / 2 / a;
    Math.abs(t1) > "1e12" && (t1 = 0.5);
    Math.abs(t2) > "1e12" && (t2 = 0.5);
    if (t1 >= 0 && t1 <= 1 && tvalues.indexOf(t1)==-1) tvalues.push(t1);
    if (t2 >= 0 && t2 <= 1 && tvalues.indexOf(t2)==-1) tvalues.push(t2);

    var inflectionpoints = find_inflection_points(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y);
    if (inflectionpoints[0]) tvalues.push(inflectionpoints[0]);
    if (inflectionpoints[1]) tvalues.push(inflectionpoints[1]);

    tvalues.sort(compare_num);
    return tvalues;
};

And when you have those critical t values (which are from range 0-1), you can divide the cubic to parts:

function CPoint()
{
  var arg = arguments;
  if (arg.length==1)
  {
    this.X = arg[0].X;
    this.Y = arg[0].Y;
  }
  else if (arg.length==2)
  {
    this.X = arg[0];
    this.Y = arg[1];
  }
}

function subdivide_cubic_to_cubics()
{
    var arg = arguments;
    if (arg.length!=9) return [];
    var m_p1 = {X:arg[0], Y:arg[1]};
  var m_p2 = {X:arg[2], Y:arg[3]};
  var m_p3 = {X:arg[4], Y:arg[5]};
  var m_p4 = {X:arg[6], Y:arg[7]};
  var t = arg[8];
  var p1p = new CPoint(m_p1.X + (m_p2.X - m_p1.X) * t,
                       m_p1.Y + (m_p2.Y - m_p1.Y) * t);
  var p2p = new CPoint(m_p2.X + (m_p3.X - m_p2.X) * t,
                       m_p2.Y + (m_p3.Y - m_p2.Y) * t);
  var p3p = new CPoint(m_p3.X + (m_p4.X - m_p3.X) * t,
                       m_p3.Y + (m_p4.Y - m_p3.Y) * t);
  var p1d = new CPoint(p1p.X + (p2p.X - p1p.X) * t,
                       p1p.Y + (p2p.Y - p1p.Y) * t);
  var p2d = new CPoint(p2p.X + (p3p.X - p2p.X) * t,
                       p2p.Y + (p3p.Y - p2p.Y) * t);
  var p1t = new CPoint(p1d.X + (p2d.X - p1d.X) * t,
                       p1d.Y + (p2d.Y - p1d.Y) * t);
  return [[m_p1.X, m_p1.Y, p1p.X, p1p.Y, p1d.X, p1d.Y, p1t.X, p1t.Y],
          [p1t.X, p1t.Y, p2d.X, p2d.Y, p3p.X, p3p.Y, m_p4.X, m_p4.Y]];
}

subdivide_cubic_to_cubics() in above code divides an original cubic curve to two parts by the value t. Because get_t_values_of_critical_points() returns t values as an array sorted by t value, you can easily traverse all t values and get the corresponding sub curve. When you have those divided curves, you have to divide the 2nd sub curve by the next t value.

When all splitting is proceeded, you have the control points of all sub curves. Now there are left only the cubic control point conversion to quadratic. Because all sub curves are now down-elevated cubics, the corresponding quadratic control points are easy to calculate. The first and last of quadratic control points are the same as cubic's (sub curve) first and last control point and the middle one is found in the point, where lines P1-P2 and P4-P3 crosses.