 |
 |
Sep. 2006, Author: Adrian Colomitchi
The overall problem approached by the article is:
within a defined degree of precision, approximate
a cubic Bezier curve:
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.
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:
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.
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:
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:
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;
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:
0- and 1-approximation
quadratic is0-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.
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:
0-approximation
quadratic will be |P2 - 3·C2 + 3·C1 - P1|
(obtained for a t parameter value of 1)1-approximation
quadratic will be |P2 - 3·C2 + 3·C1 - P1|
(obtained for a t=1)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.
0-approximation
quadratic (C = (3·C1 - P1)/2),
leads to the defect of approximation be the maximum of the expression:0- and 1-approximation quadratics
(C = (3·C2 - P2 + 3·C1 - P1)/4)
and the same anchor points as the original cubic, formula (3) above leads
to an approximation defect of only: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:
0-
and 1-approximation quadratics (D0-1 = |P2 - 3·C2 + 3·C1 - P1|/2)
is approx. 10 times greater than the acceptable
defect (sqrt(3)/18 < 0.096).
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).
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:
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.
The article presented:
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.
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.0 and dist(u, v)=0
if and only when u=v |
|