 |
 |
Sep. 2004, Author: Adrian Colomitchi
The present article is a short introduction to cubic and quadratic Bezier curves construction, their parametric expressions, splitting/subdividing them using deCasteljau algorithm, the approximation of Bezier curves by line segments and the conversion of a quadratic Bezier to an equivalent cubic Bezier. If you are looking for a method to convert cubics to (chains of) quadratics, good news: try the article on "Approximating cubic Bezier curves by quadratic ones" also on this site (there are 3 algos).
The article requires a rather minimal mathematical background. The intention was to explore practical approaches to the background of the Bezier curves used by the "day-by-day" vectorial graphics applications: something that's comprehensible rather the comprehensive.
Note: the interactive Bezier graphical support for this article is implemented as Java applets, one will need the Java Runtime Environment (jre) version 1.2+ installed and integrated with(in) the browser. The Bezier applets were developed using Java ver. 1.4
Anyone that used a vectorial drawing application (like Adobe Illustrator, Corel Draw or Macromedia Freehand) will recognize a cubic Bezier curve in the applet on left.
Note: dragging any of the 4 points will modify the represented curve.
A quadratic Bezier curve - a 2nd degree curve - is defined in a similar way as the cubic one, but requires a single control point.
The quadratic Bezier curves are used by the Macromedia Flash and in encoding/rendering TrueType fonts.
The algorithm is named after its author: de Casteljau - an engineer working for Peugeot back in 1970's. Depicted in the applet on the left, the algorithm allows finding the location of any point of a cubic Bezier curve.
Each point of a cubic Bezier point corresponds to a value between 0
and 1 for a parameter that will be noted with t
in the followings. The de Casteljau algorithm consists of the following steps
(follow the links embedded in the explanation of the algorithm steps
for depicting the specific step configuration)
Similar with the cubic Bezier curve, for a quadratic Bezier curve the de Casteljau algorithm is:
The first consequence of applying the algorithm above is the convex hull property a cubic or quadratic Bezier curve has:
Convex hull property: all the points of a Bezier curve lay within the polygon defined by the curve's anchor points and control points.
This property becomes important when considering various quick tests, like:
Now, the de Casteljau algorithm by itself is not very useful in drawing a cubic Bezier curve, since this would require the computation of a large number of the points on the curve for obtain a certain precision. Nevertheless, for further practical exploitation of the Bezier curves, the parametric expression of the coordinates of points on a cubic Bezier curve is necessary.
Let's start by note that the point D that divides the EF segment in a t/(1-t) ratio has the coordinates given by the expressions:
Dx = (1-t)•Ex+t•Fx and Dy = (1-t)•Ey+t•Fy (1)
Since the expressions for the x and y coordinates are similar, in the followings the non-indexed notation will be used as a shortcut for expressions (1) above:
With this notation:
The expression:
P
= (1-t)3•P1 + 3•(1-t)2•t•C1
+ 3•(1-t)•t2•C2
+ t3•P2 (3)
with t taking values in the [0, 1]
interval
is called the parametric expression of a cubic Bezier curve.
For example, applying the expression (3) for a 0.5
parameter value, results in:
midc = (P1 + 3•C1 + 3•C2 + P2)/8 (4)
for the location of the middle point of a Bezier curve.
Below, the de Casteljau algorithm is applied for a quadratic Bezier curve:
The expression (5) above, for values of the t parameter
in the [0, 1] range, is called the parametric
expression of a quadratic Bezier curve.
Note: the reason for calling this type of curves quadratic is the quadratic dependence of the points on the curve on the t parameter value.
Applying the expression (5) for the value of parameter of 1/2, one obtains the "middle" point of a quadratic Bezier curve as:
midq = (P1 + 2•C + P2)/4 (6)
The de Casteljau algorithm is useful for splitting a Bezier curve into two segments at a given value for the t curve parameter.
The applet below shows the procedure for the case of cubic Bezier curves:
A similar approach can be followed to subdivide a quadratic Bezier curve:
Note: of course, in both cases (cubic and quadratic), the first division segment shares its start point with the original curve, while the end points of the second segment and the original curve are the same.
With what is defined until now, the only way of drawing a Bezier curve would be by using the parametric expressions (either as they are or by using the de Casteljau algorithm) in computing the location as many points as necessary for drawing an accurate enough approximation of the curve, connecting the points with line segments. In other words, approximate the Bezier curve by a polygonal path (flattening - linearization).
However, one have to solve the following problems:
The flatness of a Bezier curve, defined as the maximum distance between all the Bezier control points and the line passing through its anchor points, is a measure of how exact is the approximated a the Bezier curve by the segment that connects the anchor points. An this because all the points of a Bezier curve are inner points of the polygon defined by the anchor and control points (the convex hull property).
The applets below depict this definition:
Considering the flatness in the context of subdivision of a Bezier curve, the following algorithm can be implemented:
1/2
parameter value);The applets above implements this algorithm, except the fact that the stop criterion at step 2 is the number of division steps performed rather than the maximum value of the flatness of all the resulted curve segments. By modifying the number of division steps performed, one can see that once the maximum flatness falls far below the drawing device resolution (e.g. the display in this case), further subdivision steps does not add more "visual quality" to the polygonal paths approximating the original curves.
An accurate enough criterion for approximating a Bezier curve by the segment connecting its anchor point would be: the flatness of the curve should lesser or equal to the half of the distance between two points/dots/pixels that are still considered as distinct on the representation device (display, printer, etc): half of the device resolution.
An improvement to the previous representation algorithms would be:
This way, flat enough curve segments that may result at some steps in the first version of algorithm don't get unnecessarily subdivided. I like to call this algorithm the adaptive flattening by half-splittingnote 1 of a Bezier curve, or adaptive halving in short.
The following applets implements the immediately previous version of algorithm, showing the resulted number of segments and allowing the adjustment of the desired level of precision:
By analyzing the parametric expression of quadratic
curves (5) and cubic curves (3), one can feel
that for each quadratic Bezier curve there is a cubic Bezier curve that describes
exactly the original quadratic curve. At this stage, the intuition can be
justified by the fact that a cubic expression can equal a quadratic one if
the coefficient of the cubic term is always 0. So, being given
a quadratic curve, we're looking for the position of two control points that
would make the cubic Bezier behave as a quadratic one.
Of course, one can expand the parametric expression of a cubic Bezier and, by equaling the coefficients between the parametric expression of the quadratic and the one for the cubic, find the control points that will make the cubic behave like the quadratic. Even the approach is correct, here is another one that will make the computation easier: multiply the parametric expression of the quadratic with 1 = [(1-t)+t] and separate the terms in (1-t) and t in the resulted expression:
(1-t)2•P1 + 2•(1-t)
•t•C + t2•P2
=
((1-t)2•P1
+ 2•(1-t) •t•C + t2•P2)•[(1-t)+t]
=
(1-t)3•P1
+ (1-t)2•t•(2•C+P1)
+ (1-t)•t2•(2•C+P2)
+ t3•P2
Equaling the coefficients in the above expression with their correspondents in the parametric expression of a cubic Bezier, one can obtain the position for the control points of a cubic Bezier that behave exactly like a quadratic Bezier:
C1 = 2/3•C + 1/3•P1
C2 = 2/3•C + 1/3•P2 (7)
In other words, the points that divide the sides of the triangle in an 1/3 vs 2/3 ratio.
In the context of transforming a quadratic Bezier into a cubic equivalent, one can note that the cubic equivalent has a lesser flatness: a 2/3 of the flatness of the original quadratic.
This leads to an interesting development: what if, in the course of the flattening algorithm for a quadratic:
Since the flatness of the cubic equivalent is lesser that the one of the original quadratic, the flatness test performed at step one of the adaptive halving algorithm is easier to be satisfied by the cubic equivalent: this way, one should expect a number of segments lesser than if applying the adaptive halving directly on the quadratic, but no degradation in the quality of the resulted drawing.
The applet above implements the last described algorithm. The results shows that, even there are many cases in which the number of the resulted segments a lesser by "upgrading" first the quadratic to a cubic, on the average the supplementary computational effort seems not to justify this approach:
As a result, "upgrading" the quadratic to a cubic prior to halving and transforming back the cubic segments into quadratic ones would be justified only if the improvement in the number of resulted segments would be 3/(6+1)<0.5.
Experimentation on the above applet never revealed such cases, thus my recommendation would be "think again: it's simply too computational expensive for relatively minor results".
PS: I would make available the sources for all the applets above, but I feel
there are much too code used for user interaction and very little code really
dealing with Bezier curves. Besides, all the algorithms implemented for are
simple enough and, I hope, well explained above. If anyone would like to see
the code: drop me an email and
I'll send it in reply.
If in dire need, drop me an email and, in depending the time available, I'll see if/how I can help you.
The content of this site is copyrighted by Adrian Colomitchi. Please consult the copyright notice before doing anything except reading/browsing/printing pages of this site.
|
|