Approximating cubic Bezier curves by quadratic ones

Fast, precision driven, piecewise degree reduction of cubic Bezier

In plain-speak translation: convert cubic Bezier to a chain of quadratic Bezier segments, with a precision at your choice.
Interested? Continue reading, you can check your email or play bingo later, there's a long way to discover why and how.
Impatients, skip the "why the methods are working" part and jump here to get only the "how" part

Sep. 2006, Author: Adrian Colomitchi

Abstract

The overall problem approached by the article is:
within a defined degree of precision, approximate a cubic Bezier curve:

  1. by one quadratic Bezier or
  2. if the first approach is not possible, find a division of the cubic such as each of the resulted curve segments can be approximated by quadratics.

The article presents some preliminary analysis of the problem and introduces the definition a cubic's Bezier zero-approximation and one-approximation quadratics, as the quadratics that approximates the best a cubic Bezier for values of the t parameter closer to 0 and 1 respectively. The distance between the control points of the 0- and 1-approximation quadratics is calculated, as it plays an important role in adaptive subdivision of a cubic Bezier.

The article introduces a measure of dissimilarity between two parametric curves and used this measure as the defect of approximation of a cubic Bezier by a quadratic one. Three special quadratics are analyzed in the light of this approximation defect, one of them - the mid-point approximation - showing good potential in solving the problem.

The mid-point approximation is used, in conjunction with subdivision of a cubic Bezier in two halves, to give a first solution to the problem - the mid-point half-splitting method; the method uses simple arithmetic for the approximation, being a very low computational expensive one.

Further, the article presents an important property of the distance between the control points of the 0- and 1- approximation quadratics for the first segment resulted by a subdivision of a cubic at an arbitrary value tsplit for the cubic Bezier's parameter: this distance varies with t3split. This allows the approach the subdivision in a true adaptive way, choosing better (and fewer) division points than in the case of half-splitting method, the price to be paid being the computation of a square and a cubic root at each subdivision iteration. The method is further refined such as the square and cubic root computation is required only every two subdivision iterations.

As usual, the article is supported by interactive java applets, so please feel free to interact and modify any of the configuration presented, by click-n-dragging any of the points represented by small squares (note :diamond shaped points are for position marking purposes only - use the square handles). The applets are compiled using Java 1.4, but a Java Runtime Environment as low as ver. 1.2 should be sufficient to run them.

Quick tests for cubic to quadratic conversion

A quadratic Bezier can be always represented by a cubic one by applying the degree elevation algorithm. The resulted cubic representation will share its anchor points with the original quadratic, while the control points will be at 2/3 of the quadratic handle segments:

C1 = (2·C + P1)/3
C2 = (2·C + P2)/3

As expected, not always a cubic Bezier curve can be represented exactly by a quadratic one. Here are some consequences of the 3rd degree term of a cubic Bezier:

  1. a cubic Bezier may have inflection points. A quadratic has a constant bending direction (thus, no inflection points).
  2. a cubic Bezier may display a loop (recurve behavior)note 1. A quadratic never recurve.

A quick test of whenever the approximation of cubic to a quadratic Bezier is possible or not would primarily address the differences above. If feel that it is possible to obtain some formulae to implement the tests above (in fact, the case of inflexion points was addressed previously), but such tests would not be to useful for our goals as they require a non-trivial computational effort.

Magnitude of the 3rd degree term of a cubic Bezier

A previous article brought the parametric expression of a cubic Bezier under the form:

P(t) = P1 + 3·t·(C1 - P1) + 3·t2·(C2 - 2·C1 + P1) + t3·(P2 - 3·C2 + 3·C1 - P1)

Now, if the magnitude of the 3rd degree term is small enough (ideally zero), the cubic can be approximate by a quadratic.

In fact, the 3rd degree term expresses the distance between the points corresponding to the same value of the parameter t, one the cubic and the other on the quadratic obtained by canceling the 3rd degree term of the cubic.
This distance will be:

t3·|P2 - 3·C2 + 3·C1 - P1|        (2)

 where |v| denotes the modulus of v  (i.e. sqrt(vx2 + vy2) ). The maximum distance is obtained for t = 1 and is |P2 - 3·C2 + 3·C1 - P1|.

Canceling the 3rd degree term of a cubic will result in a quadratic approximation of the original cubic; the magnitude the 3rd degree coefficient acts as the precision of approximation.

It worth noting that the quadratic approximation will share it's starting anchor point with the original cubic, but not its end point (unless the cubic can be exactly approximated by the quadratic). The followings explore the properties of the quadratic obtained by the canceling the 3rd degree term.

We'll start by computing the positions of the:

of the quadratic Bezier obtained by canceling the 3rd degree term of the original cubic.
The parametric expression of this quadratic is:

Q'(t) = P1 + 2·t·(C' - P1) + t2·(P'2 - 2·C' + P1)    (3)

By equaling the 1st and 2nd degree term coefficients of the relation above with the one parametric expression of the original cubic, one can derive the position of control and end points of the quadratic approximation as:

C' = (3·C1 - P1)/2
P'2 = P1 - 3·C1 + 3·C2

The applet on the left (above) depicts in yellow this quadratic. One can note that:

  1. it is the start endnote 2 of the original cubic that is the best approximated by this quadratic.
    The worst approximated is the finish end of the cubic.

    Definition: the quadratic obtained by canceling the 3rd degree term of a cubic Bezier will be called, in the followings, the 0(zero)-approximation quadratic;

  2. for the zero-approximation quadratic :
    • the start anchor point is common with the start anchor of the approximated cubic
    • the control point is outer of the first cubic handle segment and one and a half the distance between the anchor point and the first control point of the original cubic.
      The expression of the control point of the the zero-approximation quadratic is C' = (3·C1 - P1)/2  = (1 - 3/2P1 + 3/2·C1
    • the end of the zero-approximation quad is at the point with the position given by P'2 = P1 - 3·C1 + 3·C2.

    Note that the finish anchor point of the cubic is not involved in any of the above relation, therefore the 0-approximating quadratic can't be expected to deliver a good approximation near the finish anchor point (just modify the position of the finish anchor point - P2 - in the applet below to see that the 0-approximating quadratic - in yellow - does not change)

 

The same reasoning can be performed for the other end of the cubic Bezier, resulting in a quadratic that will start in the P2 anchor point, will have the control point in the location given by C" = (3·C2 - P2)/2 and the second anchor point will be at the location given by P"1 = P2 - 3·C2 + 3·C1.
This quadratic, which I'll name the 1(one)-approximation quadratic from now on, will approximate better the original cubic for values of the parameter t closer to 1 and worse for values closer to 0.
The applet in the left depicts both of these quadratics approximating the initial cubic, with the 0-approximating quadratic drawn in yellow and the 1-approximating quadratic in psychedelic purple.

It is interesting to note that:

  1. The distance between the control points of 0- and 1-approximation quadratic is
    D0-1 = |C' - C"| = |P2 - 3·C2 + 3·C1 - P1|/2      (*)

  2. the maximum distance between two points:

    • considered for the same value of parameter t ...
    • one on the cubic and the other one of the any of the zero- or one-approximating quadratics
    is twice the distance between the control points of the 0-approximation quadratic and the 1-approximation quadratic (see above): |P2 - 3·C2 + 3·C1 - P1| (just use (2) with t = 1).

D0-1 - It seems that the distance between the control points of the zero- and one-approximation (denoted for the followings with D0-1) gives an indication about the chance of approximating a cubic by a single quadratic: the closer to 0 the better the chance to find such an approximation.

Defect of approximating a cubic by a quadratic

To measure of how good the approximation of a cubic by a quadratic, I'll define a distancenote 3 between two parametric curves as the maximum distance between the points on the two curves that corresponds to the same value of the parameter t. Of course, the definition supposes that the two parametric curves are defined for a variation of the parameter in the same range (i.e. 0..1).

The distance defined above acts as a measure of dissimilarity between the two parametric curves. With this definition, one can measure the quality of an approximation by how low this distance is. If this distance vanishes, the two curve will be identical, in both the shape and the mode in which they are traversednote 4 (i.e. both trajectory shape and the movement equation are considered in computing the distance) .

In the context of approximating a cubic Bezier with a quadratic one, the distance between the original cubic and its approximation will be named in the followings the defect of the approximation.

Examples:

  1. the defect of approximating a cubic by its 0-approximation quadratic will be |P2 - 3·C2 + 3·C1 - P1| (obtained for a t parameter value of 1)
  2. similarly, the defect of approximating a cubic by its 1-approximation quadratic will be |P2 - 3·C2 + 3·C1 - P1| (obtained for a t=1)

In the search for the perfect approximation

As seen above, using only one of the cubic anchors in the quadratic approximation leads to less precise approximation. What if trying quadratic approximations that shares both ends with the cubic to approximate?

The defect of approximating a cubic curve by a quadratic sharing the anchor points with the original cubic and having C as the position of its control point, is given by the expressionnote 5:

t·(1 - t)·|2·C - 3·C1 + P1 + 3·t·(P2 - 3·C2 + 3·C1 - P1)|                (4)

The applet on the left explores how the distance modeling the defect of approximation varies for the following particular cases, all of them being considered for quadratics that shares the ends with the approximated cubic. Displayed in red is the segment between two points (one on the cubic the other on the approximating quadratic) corresponding to the same of the t parameter (adjustable using the slider below the applet):

One can note that, when the control is chosen as at mid-distance between 0-approximation and 1-approximation quad controls (the 3rd cfg above), the approximating quad and the cubic look like they are sharing their mid-points.

A more in-depth exploration is possible by applying formula (4) for the three configuration above and studying the distance between two points, that corresponds to the same value of the t parameter, one of each on the cubic the other on the quadratic. The applet below assist this exploration; the chart at the applet's bottom displays the distance between the two points (one on cubic the other on the approximating quadratic). Play with the cubic and quadratic points, but expect that a cubic displaying inflexion points or recurve behavior never to have a good quadratic approximation.

The third configuration seems particularly promising: the defect of the approximation is less than 10% of the D0-1. For this reason it worth bearing a name: in short, this approximation will be called the mid-point approximation for the rest of the article.

I haven't discovered an analytic way to prove it, but it seems the mid-point approximation (the 3rd configuration) is the best. Or is it? Well, not quite so: here is one configuration that doesn't, and another one here (hint: establish any of the two configuration then click on the configuration 3 link; notice the defect being reported as smaller for cfg 3, even if the approximation is visibly worse then the initial one). For the special case of the last two configuration shown, the problem stays in the way the defect is defined: it keeps track not only on shape of the curve, but the way in which it is transversed as well.

Well, maybe the prefect approximation wasn't found, but let's see what's the good side of what was found so far. Particularly, focusing on equation (6), one may note that:

Quadratic approximation of a cubic Bezier by half-splitting

For the cases the cubic cannot be reasonably approximated by a single quadratic, one can try to divide the cubic in more than one segments that can be better approximated by quadratics.

Like for the case of flattening a cubic Bezier:

The applet on the left implements the above, using the mid-point approximation at the second step: the slider allows the adjustment of the desired precision (in the range of 0.01-100 points). As expected, the lesser the tolerance, the more divisions required.

What about the inflexion points, how the algorithm above deals with them? Well, simply by dividing the cubic around the inflexion point until it becomes so flat it can be approximated with a pretty flat quadratic. Here's a configuration that show this effect: for the start, reduce the required precision on over 10 points value for the accepted defect. Notice that the cubic segment, even exposing one inflexion point, will be approximated by a single quadratic segment. Imagine the scale reduced tenfold and you'll find the approximation to be a pretty good one.

Now, with the same configuration and required precision, mark the "Detect inflexion" check-box: this will detect the inflexion point, divide the cubic first at this point and apply the algorithm on the two resulted cubic segments. By doing so, the resulted approximation will be more precise, since the algorithm will be required to approximate only cubic segments with constant bending direction. Granted, dividing first the cubic in its inflexion point may result in increasing the number of quadratic segments, and most of the times this will be the result: more quadratic segments and a better approximation.
But there are configurations for which the division in the inflexion points will decrease the number of resulted quadratic segments, without impacting on the precision of the approximation. For example, for a required precision of 0.5, this configuration that will require less quadratic segments if first divided at the inflexion point position: establish 0.5 for the precision and toggle on and off the "Detect inflexion" check-box. However, when using the inflexion points detection, the very same configuration performs worse in the number of quadratic segments if the required precision is extremely high (try 0.01, which is 10-4 — 10-5 of the maximum curve extension).

Quadratic approximation of a cubic Bezier by adaptive division

The algorithm of halving the cubic until the segments can be reasonably approximated by a quadratic is easy to implement and requires low computation effort. However, it simply does not attempt to exploit the cubic characteristics, but only to adjust to them, resulting in a possible higher then necessary number of segments.

The idea behind adaptive division is:

If the first step can be easily achieved, one can expect fewer quadratic segments to result in approximation.

Let's try to use the mid-point approximation with this, knowing that the precision of the approximation is governed by the distance between the control points of the 0- and 1-approximation quadratics D0-1.
Suppose that a cubic Bezier defined by the points P1, C1, C2 and P2 is subdivided at a parameter value of tsplit. Well, if one cares to calculate the distance between the 0- and 1-quadratic approximation for the first cubic segment - d10-1(t), a nice surprise expects just around the cornernote 6. For the impatiens, here is the spoiler:

d10-1(tsplit) = t3split · |P2 - 3·C2 + 3·C1 - P1|/2 = t3split · D0-1     (6)

Now, the formula (6) is quite remarcablenote 6: it simply states that the distance between the control points of 0- and 1-approximations for the first cubic segment obtained by subdividing a cubic Bezier at a value tsplit of the parameter simply varies with the cube of tsplit. It is so simple that allows allow the following approach when attempting to approximate a cubic Bezier by a daisy-chain of quadratics when imposing a maximum tolerance of prec:

  1. compute the distance D0-1 between the control points of 0- and 1-approximation quadratics (use formula *)
  2. compute tmaxas the root of equation:
    sqrt(3)/18 · D0-1 · t3max = prec
  3. if tmax is less than 1.0:
    • subdivide the cubic at tmax
    • approximate the first segment using mid-point approximation
    • enter again the first step with the second cubic segment
  4. if tmax is greater than 1.0, the cubic Bezier can be directly approximated by the mid-point approximation within the specified tolerance (i.e. use mid-point approximation and exit the cycle)

The applet on the left implements the above algorithm, which I'd like to call the "simple adaptive division using mid-point approximation".

Note that, in concerning the computational cost, the adaptive division requires higher cost per division than the half-splitting one: the division effort and the computation of the D0-1 distance is pretty much the same, but the adaptive division requires the computation of a square root (at step 1) and a cubic root (at step 2). The only chance of having the adaptive division performing better in concerning the computational effort is to have a significant reduction in the number of required divisions (number of resulted segments).

But let us postpone a while the comparison in the number of resulted segments. Please note first that the adaptive division algorithm above remains the same if one substitutes t with 1 - t (i.e. the cubic is explored backwards). Therefore, running through step 1. and 2., one finds not one but two division points, corresponding to tmax and 1 - tmax (adaptive symmetric division). This means:

Finally, concerning the number of resulted segments: I didn't run (yet) the adaptive division algorithm(s) on a random generated set of cubics to extract statistic data, but my explorations suggest that the adaptive division performs 0%-45% better than the half-splitting one (both using the mid-point approximation).
One may find here an applet can be used to explore the performance of the 3 algorithms (half-split, simple adaptive and symmetric adaptive) in the term of the number of quadratic segments use in subdivision.

Conclusion

The article presented:

  1. a measure of dissimilarity between two parametric curves
  2. a very simply to compute, yet a fairly good approximation of a cubic segment by a quadratic one: the mid-point approximation quadratic, sharing the anchor points with the cubic Bezier and with the control point at the mid-distance between the control points of zero- and one approximation: C = (3·C2 - P2 + 3·C1 - P1)/4. The approximation is very easy to compute, requiring only arithmetic operations (even better, addition/subtraction/bit-shifting are sufficient if only positive integer operands are assumed);
  3. the defect of approximating a cubic segment by the mid-point quadratic segment:  (sqrt(3)/36)·|P2 - 3·C2 + 3·C1 - P1|;
  4. the half-splitting mid-point algorithm to subdivide a cubic Bezier until the resulted segments can be approximated by quadratics Bezier within an imposed precision. The advantage is the simplicity of implementation and a small computational effort;
  5. two adaptivenote 7 algorithms to subdivide a cubic Bezier such that the resulted segments can be approximated by quadratics Bezier within an imposed precision. This one has the advantage of generating a smaller number of segments, possiblenote 8 with the price of slighter increase in the computational effort.

  1. Note: I reckon that a proper demonstration for the statement "if a cubic Bezier displays a recurve behavior, then the curve's handle segments intersect" is possible. I feel that is possible to find other necessary conditions for a cubic Bezier to display recurve behavior, conditions that are stronger but still computational easy. Though, as I said, I don't really have time for the dig, and besides presenting them would be are out of the scope of the present article.

  2. Note: the quadratic Bezier obtained in this way is the 2nd degree truncation of the Taylor "series" of the original cubic around t = 0 (yeah ...right... - a serie with 3 terms only) . It's quite natural to offer a better approximation near the starting end of the cubic and the worst one for the finish end.
  3. Note: it can be shown that the definition above describes a distance:
    • dist(u,v)>=0 and dist(u, v)=0 if and only when u=v
    • dist(u, v)=dist(v, u)
    • |u-v|<=|u-w|+|w-v| (the triangle inequality)
  4. Note: because the definition also includes the mode in which the parametric curves are traversed, it acts as a very strong criterion of the way in which one curve approximates the other. As an example, the curves:
    C1(t) = (x(t)=cos(t), y(t)=sin(t)) and
    C2(t) = (x(t)=-cos(t), y(t)=-sin(t))
    are both describing the same shape (unit-radius circle), but the distance defined previously will be always 2 (the length of the diameter).
  5. Note: the expression was obtained by considering the parametric expressions for a cubic and a quadratic that share the same anchor points. The calculus can be laborious if done by paper and pencil. Fortunately, there are tools for symbolic calculus; personally, I used a trial version of MuPad from SciFace - same result quicker and with no financial pressure on my budget.
  6. Note: so simple that, after performing the calculus using MuPad, I couldn't believe my eyes and went into doing it by hand, which I wouldn't advice anyone to repeat it unless one have a sick pleasure in performing long calculi with pen-and-paper. My advice: better use the spoiler and be convinced of this result by seeing it used in the implementation of the interactive applets.
  7. I'll reiterate my opinion in a previous article: recursively halving a cubic Bezier until a certain precision is attained does not expose a degree of adjustment to the cubic specific high enough to call the algorithm adaptive: halving is still "splitting at t=0.5". By contrast, the adaptive algorithms exposed attempt to adjust the location of the division point to the specific of the particular cubic Bezier to be divided.
  8. Note: the increase in effort is very much dependent on the platform used for performing the computation: for a math library using directly the CPU's floating point unit, there is likely to pay pretty much the same price due to the reduction in the number of quadratic segments required for a decent approximation.