Simplify high-order Bezier curve

Question

I have an array of control points that represent a Bezier curve. It could be a fifth-order or 100-order Bezier curve, or anything in-between. I am looking for a way to simplify that Bezier curve into multiple cubic Bezier curves. An illustration below shows how tenth-degree curve can be simplified to three-degree curve, but I want to go further and simplify it to several cubic Bezier curves to achieve better approximation.

Code example would be very helpful.

In general : a segmented bezier curve is nothing else than a b-spline curve. — Christian

Mike 'Pomax' Kamermans Mike 'Pomax' Kamermans · Accepted Answer · 2015-05-25T04:09:53

As mohsenmadi already pointed out: in general this is not a thing you can do without coming up with your own error metric. Another idea is to go "well let's just approximate this curve as a sequence of lower order curves", so that we get something that looks better, and doesn't really require error metrics. This is a bit like "flattening" the curve to lines, except instead of lines we're going to use cubic Bezier segments instead, which gives nice looking curves, while keeping everything "tractable" as far as modern graphics libraries are concerned.

Then what we can do is: split up that "100th order curve" into a sequence of cubic Beziers by sampling the curve at regular intervals and then running those points through a Catmull-Rom algorithm. The procedure's pretty simple:

Pick some regularly spaced values for t, like 0, 0.2, 0.4, 0.6, 0.8 and 1, then
create the set of points tvalues.map(t => getCoordinate(curve, t)). Then,
build a virtual start and end point: forming a point 0 by starting at point 1 and moving back along its tangent, and forminga point n+1 by starting at n and following its tangent. We do this, because:
build the poly-Catmull-Rom, starting at virtual point 0 and ending at virtual point n+1.

Let's do this in pictures. Let's start with an 11th order Bezier curve:

enter image description here

And then let's just sample that at regular intervals:

enter image description here

We invent a 0th and n+1st point:

enter image description here

And then we run the Catmull-Rom procedure:

i = 0
e = points.length-4
curves = []
do {
  crset = points.subset(i, 4)
  curves.push(formCRCurve(crset))
} while(i++<e)

What does formCRCurve do? Good question:

formCRCurve(points: p1, p2, p3, p4):
  d_start = vector(p2.x - p1.x, p2.y - p1.y)
  d_end = vector(p4.x - p3.x, p4.y - p3.y)
  return Curve(p2, d_start, d_end, p3)

So we see why we need those virtual points: given four points, we can form a Catmull-Rom curve from points 2 to point 3, using the tangent information we get with a little help from points 1 and 4.

Of course, we actualy want Bezier curves, not Catmull-Rom curves, but because they're the same "kind" of curve, we can freely convert between the two, so:

i = 0
e = points.length-4
bcurves = []
do {
  pointset = points.subset(i, 4)
  bcurves.push(formBezierCurve(pointset))
} while(i++<e)

formBezierCurve(points: p1, p2, p3, p4):
  return bezier(
    p2,
    p2 + (p3 - p1)/6
    p3 - (p4 - p2)/6
    p3
  )

So a Catmull-Rom curve based on points {p1,p2,p3,p4}, which passes through points p2 and p3, can be written as an equivalent Bezier curve that uses the start/control1/control2/end coodinates p2, p2 + (p3 - p1)/6, p3 - (p4 - p2)/6, and p3.

Simplify high-order Bezier curve

2 Answers