Approximating a cubic Bézier curves with a collection of quadratic ones

Question

I need to approximate a cubic Bézier curve with a minimal collection of quadratic ones given a maximum acceptable error.

Trying to read up on this problem, it seems like there are about as many approaches as there are people trying to solve it. Everything ranging from using a single curve with the control point being a weighted average of the start, two control, and end point of the cubic with weights -1, 3, 3, -1 respectively, to splitting the curve into an increasing number of equal-sized segments using de Casteljau's algorithm and then approximating every one with the method above, or even starting at one end of the cubic and moving the endpoint of a best-fit quadratic curve along the cubic until the error gets too big and then starting a new quadratic at that point. @Timo even claims it can be done exactly if you split the curve at all its extrema and points of inflection (although I haven't verified this yet): https://stackoverflow.com/questions/2009160/how-do-i-convert-the-2-control-points-of-a-cubic-curve-to-the-single-control-poi/14514491#14514491

Among all these different approaches, is there an accepted gold-standard way of doing this?

Answer 1

This is a common problem, of course, because people are always trying to convert Postscript fonts (which use cubic curves) into TrueType ones (which use quadratic curves).

To answer your question, I don't think there is any accepted "gold standard" approach.

Many of the algorithms you'll find on the net are heuristic. The developer thinks his results "look good", and that's the end of the analysis. If you want to be more rigorous, then you have to define "good" or "best" in order to find the best algorithm. Lets call the original cubic $C$ and the approximating piecewise quadratic $Q$. Then some possible criteria of goodness are:

1. The maximum distance between $C$ and $Q$ is small
2. The maximum value of $\|C(t) - Q(t)\|$ is small. This is not the same thing as #1.
3. The maximum angle between $C'(t)$ and $Q'(t)$ is small
4. Tangent discontinuities in $Q$ are small (perhaps even zero)
5. $Q$ and $C$ have the same turning points (important for font hinting)

and so on.

No matter what criteria you decide to choose, the "test-and-reduce" meta-algorithm you mentioned is reasonable: take two points on the cubic, and use these points and their tangent vectors to construct a quadratic. If the quadratic is acceptable (according to whatever criteria you decided), you're done; if not, choose two points that are closer together. Rinse and repeat.

Regardless of what @Timo said, there is no way to exactly represent a cubic curve as a string of quadratic ones unless the cubic curve was, (by some miraculous stroke of luck) a disguised quadratic in the first place. The string of quadratics you construct will be merely be an approximation of the cubic; all you can do is ensure that it's a "good" approximation.