Introduction to cubic and quadratic Bezier curves

Sep. 2004, Author: Adrian Colomitchi

Abstract

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

Preliminaries

Cubic Bezier curves - 3rd degree curves - to fully define such a curve, one will need to specify 4 points:

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.

Finding points on a Bezier curve
- the de Casteljaualgorithm -

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)

  1. at the first step, connect the P1 with C1, C1 with C2, C2 with P2. Divide each of the three line segments in a t/(1-t) ratio (resulting in the 3 points denoted A, B, C);
  2. at the second step, connect the three points resulted at step 1, and divide the two resulted segment in the same t/(1-t) ratio, resulting in the points noted as M, N;
  3. finally, divide the MN segment in the t/(1-t) ratio. The resulted point (P) is the point on the cubic Bezier curve corresponding to the t parameter value.

Similar with the cubic Bezier curve, for a quadratic Bezier curve the de Casteljau algorithm is:

  1. at the first step, connect the P1 with C and C with P2. Divide each of the two line segments in a t/(1-t) ratio (resulting in the 2 points denoted A and B);
  2. at the second step, connect the A and B points resulted at step 1, and divide the two resulted segment in the same t/(1-t) ratio. The resulted point (P) is the point on the quadratic Bezier curve corresponding to the t parameter value.

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:

The parametric expression of a cubic Bezier

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+tFx and Dy = (1-t)•Ey+tFy   (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:

D = (1-t)•E + tF   (1')

With this notation:

The expression:

P = (1-t)3P1 + 3•(1-t)2tC1 + 3•(1-t)•t2C2 + t3P2    (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.

The parametric expression for a quadratic Bezier

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)

Subdividing a Bezier curve

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:

  1. at the first step, the A division point is the first control point for the first Bezier segment, while the C division point is the second control point for the second Bezier segment;
  2. at the second step, the M point is the second control point for the first Bezier segment, while the N point is the first control point for the second Bezier segment;
  3. the point resulted of the third step is the end anchor point for first Bezier segment and the start anchor point for the second Bezier segment (the splitting point).

A similar approach can be followed to subdivide a quadratic Bezier curve:

  1. at the first step, the A division point is the control point for the first Bezier segment, while the B division point is the control point for the second Bezier segment;
  2. at the second step, the P point is the end of the first Bezier segment and the start of the second Bezier segment;

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.

Bezier curve flattening

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. subdivide the Bezier curve in two halves (in fact, subdivide it at a 1/2 parameter value);
  2. compute the maximum flatness of the resulted curve segments. If this value falls below a certain value, stop the algorithm;
  3. if the maximum value is less then the desired precision, restart the algorithm at step 1, subdividing all the segments resulted until now.

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:

  1. if the flatness of a curve is lesser than a desired precision (e.g. half of the device resolution), draw the line segment that connects the curve anchor points and stop. Otherwise, continue with the next step
  2. subdivide the curve at a 1/2 parameter value and recursively apply the algorithm to the two resulted curve segments.

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:

 

Transforming a quadratic Bezier in a cubic Bezier (degree elevation)

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)2P1 + 2•(1-t) •tC + t2P2 =
    ((1-t)2P1 + 2•(1-t) •tC + t2P2)•[(1-t)+t] =
    (1-t)3P1 + (1-t)2•t•(2•C+P1) + (1-t)•t2•(2•C+P2) + t3P2

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.

Cubic equivalent of a quadratic and the quadratic flattening

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".


  1. Note: searching the Web, I found the algorithm under the name of adaptive flatening, but personally I don't quite agree with the term: it is only the half-splitting process that adapts to the curve specific. More advanced algorithms could try to adjust the division points as well - i.e. consider the position of subdivision points at better locations that mid-points of the Bezier - in an attempt to lesser the number of resulted segments. The later would better worth the name of adaptive division.

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.

Update in late Nov 2010: I decided that I can't get past the shame of sharing an ugly code (the one for the applets) - while nothing wrong with it for the purpose of supporting the interractive aplet, it is not very friendly when it comes understanding how explained the algorithms work. I don't know who said it, but I agree strongly with an ugly code is like dirty underwear: you just don't show it to everyone
Instead, please visit the download section and grab a clean room implementations of the algorithms (the part of interactiveness in the applets is not available... uummmm, actually, have a look in the com.caffeineowl.graphics.samples package, maybe you can pick something useful from there?).

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.