Converting between Bezier Curves of different degree(order)

Question

I'm working on a personal project involving Bezier curves. I have seen many implementations that handle quadratic and cubic curves individually, but I'm looking to create a more generalized algorithm where I can add and remove control points by increasing and decreasing the degree(order) of the curve.

This is not a part of my main question, but if anyone knows an example of a generalized algorithm that I can look at, I will be grateful if they can point me that direction.

First of all, I understand that any conversion from a low order to a high order curve is an approximation, and not equivalent. I am satisfied with computationally "close enough".

Secondly, I also understand that there is a loss of information when stepping down from a higher order to a lower order curve. This is unavoidable as the higher order curve has more "bends" in the curve that the lower order curve simply cannot approximate.

I'm fine with these limitations as it is necessary to be able to add and subtract control points within the curve for desired functionality.

My first question is related to this one asked approximately 5 years ago: Convert quadratic curve to cubic curve

A quadratic curve has three (3) control points:

Vector3 Start;
Vector3 Control1;
Vector3 End;

The conversion to a cubic we introduce a fourth control point...

Vector3 Control2;

..."Between" Control1 and End. We then set Control1 and Control2 accordingly:

Control2 = new Vector3(
    End.x + ((2.0f / 3.0f) * (Control1.x - End.x)), 
    End.y + ((2.0f / 3.0f) * (Control1.y - End.y)), 
    End.z + ((2.0f / 3.0f) * (Control1.z - End.z))
); 
Control1 = new Vector3(
    Start.x + ((2.0f / 3.0f) * (Control1.x - Start.x)), 
    Start.y + ((2.0f / 3.0f) * (Control1.y - Start.y)), 
    Start.z + ((2.0f / 3.0f) * (Control1.z - Start.z))
);

I am not certain that this is correct. In the example, only the 'x' component was set. I merely extrapolated 'y' and 'z' from it. If this is not correct, then I'd appreciate knowing what is correct.

This example only covers converting from quadratic to cubic curves. The controlling value appears to be the (2.0f/3.0f) in setting the coordinates. So, does that mean that converting from cubic to quartic would be (2.0f/4.0f) or (3.0f/4.0f) or something else entirely? What is the properly generalized function for this conversion for an arbitrary order of curve?

My project is also going to be working with splines. I am using an edge to edge method for constructing my splines where an edge is defined as an arbitrarily ordered curve from 1 (a line) to n, where the first and last Vector3 in the list of control points are the start and end points of the edge, and connecting edges share the end point of the previous edge with the start point of the next.

Unlike Bezier Curves, I'm not adding and subtracting control points. Instead, I'm dividing and combining edges. What would be a good method for subdividing a curve into two lower order curves with an order no lower than 2 approximating the original curve? Likewise, what would be a good method for combining two curves into a single high order curve?

I realize this is a lot to ask in a single post, but I felt it better to keep it together in one topic rather than dividing it up.

Thanks for any help!

Thanks, Mike. I think this is exactly what I am looking for. — memBrain
let me turn that into an answer, since that's basically what it is. — Mike 'Pomax' Kamermans

Mike 'Pomax' Kamermans Mike 'Pomax' Kamermans · Accepted Answer · 2017-05-22T17:21:10

You'll want to read over http://pomax.github.io/bezierinfo/#reordering for how to raising a curve to a higher order, which is almost trivial:

That may look scary, but if you actually look at what each of the three terms is, all three are stupidly simple bits of grade school maths. You typically just want the new weights, so generating those as a new list of coordinates is absolutely trivial and written in about a minute. In Javascript:

function getOneHigher(x, y):
  n = x.length;
  k = n + 1;
  s = n - 1;

  let nx = [], ny =[];
  nx[0] = x[0]; nx[n] = x[s];
  ny[0] = y[0]; ny[n] = y[s];

  for (let i=1; i<n; i++) {
    nx[i] = (n*x[i] + i*x[i-1]) / k;
    ny[i] = (n*y[i] + i*y[i-1]) / k;
  }

  return {nx, ny};
}

And we're done. Calling getOneHigher(x, y) will yield two arrays of new coordinates for the same curve, represented as a Bezier curve of a degree one higher than we put in. Note that what this means is that we've kept the set of curve coordinates the same (literally: the functions are identical ) while reducing the tangents at each coordinate (because the derivatives are not identical), effectively "slowing down" anything that travels the path that this curve traces.

You'll then also want to follow the link to Sirver's Castle in that section which explains how to do the lossy conversion down in a way that minimizes loss of information. And this should have been multiple questions: this is a Q&A site, future visitors can't find answers to specific questions if you don't ask specific questions but instead combine several technically unrelated ones in a single post.

Converting between Bezier Curves of different degree(order)

1 Answers