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

- two anchor points (P1 and P2) - the curve starts and, respectively, ends in these points
- two control points (C1 and C2) - the control points influence how the "fast" the curve "leave" its ends

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 2^{nd} 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

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)

- at the first
step, connect the P1 with C1, C1 with C2, C2 with P2. Divide each of
the three line segments in a
/(1-**t**) ratio (resulting in the 3 points denoted A, B, C);**t** - 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; - 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:

- at the first
step, connect the P1 with C and C with P2. Divide each of the two line
segments in a
/(1-**t**) ratio (resulting in the 2 points denoted A and B);**t** - 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:

*how flat is a Bezier curve*? More precisely, with what precision can be approximated a Bezier curve by the segment connecting its anchor points?*quick non intersection test*- two Bezier curves are not intersecting if the two polygons defined by the points of the Bezier curves don't overlap.

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-

**D**_{x} = (1-** t**)•

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:

- after the step
1, the
**A**,**B**and**C**coordinates will be:

**A**= (1-)•*t***P**_{1}+•*t***C**_{1}

**B**= (1-)•*t***C**_{1}+•*t***C**_{2}

**C**= (1-)•*t***C**_{2}+•*t***P**_{2} - after step
2, the M and N coordinates will be:

**M**= (1-)•*t***A**+•*t***B**= (1-)*t*^{2}•**P**_{1}+ 2•(1-)*t*•*•t***C**_{1}+*t*^{2}•**C**_{2}

**N**= (1-)•*t***B**+•*t***C**= (1-)*t*^{2}•**C**_{1}+ 2•(1-)*t*•*•t***C**_{2}+*t*^{2}•**P**_{2} - after step
3, the coordinates of the P point will be:

**P**= (1-)•*t***M**+•*t***N**= (1-)*t*^{3}•**P**_{1}+

+ 3•(1-)*t*^{2}•*•t***C**_{1}+ 3•(1-)•*t**t*^{2}•**C**_{2}+*t*^{3}•**P**_{2}

The expression:

**P**
= (1-** t**)

with

`0`

, `1`

]
intervalis called the *parametric expression of a cubic Bezier curve*.

For example, applying the expression (3) for a `0.5`

parameter value, results in:

mid_{c} = (**P**_{1}
+ 3•**C**_{1} + 3•**C**_{2} + **P**_{2})/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:

- after the step
1, the location for the
**A**and**B**points will be:

**A**= (1-)•*t***P**_{1}+•*t***C**

**B**= (1-)•*t***C**+•*t***P**_{2} - after the
second (and final) step, the position for the P point on the quadratic
Bezier curve is:

**P**= (1-)•*t***A**+•*t***B**= (1-)*t*^{2}•**P**_{1}+ 2•(1-)*t*•*•t***C**+*t*^{2}•**P**_{2}**(5)**

The expression **(5)** above, for values of the ** t** parameter
in the [

`0`

, `1`

] range, is called **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:

mid_{q} = (**P**_{1} + 2•**C** + **P**_{2})/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:

- 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;
- 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;
- 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:

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

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:

- what would be the criteria for choosing the values of the parameters for obtaining an accurate enough approximation?
- how many is exactly the as many as possible?
- and, by the way, what it would mean an
*accurate enough approximation*?

The * flatness* of a Bezier curve, defined as the

The applets below depict this definition:

Considering the flatness in the context of subdivision of a Bezier curve, the following algorithm can be implemented:

- subdivide the Bezier curve in two halves (in fact, subdivide it at a
`1/2`

parameter value); - compute the maximum flatness of the resulted curve segments. If this value falls below a certain value, stop the algorithm;
- 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:

- 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
- 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-splitting**^{note
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**)+

(1-** t**)

((1-

(1-

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:

**C**_{1} = 2/3•**C** + 1/3•**P**_{1}

C_{2} = 2/3•**C** + 1/3•**P**_{2} **(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:

- first the quadratic is "upgraded" to a cubic ...
- then the
is applied for the resulted cubic, and ...**adaptive halving algorithm** - finally all the resulted cubic segments are converted back to 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:

- the subdivision of a quadratic Bezier requires the computation of 3 points (the two new control points and the curve division point). The subdivision of a cubic Bezier requires the computation of 6 points (the 4 new control points, the curve division point and one point that is not used in the final result - the point denoted by B on the diagram explaining the de Casteljau algorithm for cubic Bezier);
- the conversion of the resulted cubic segments to quadratic ones requires
a computation effort similar with the one involved in computation the location
of 1 point/segment.

By the way,*only*for this particular case in which the cubic segments are in fact segments of a quadratic, the conversion of a cubic segment to its quadratic form is always possible. To get the location of the quadratic control point, one simply needs to intersect of the cubic "handles" (segments that connects the cubic anchor points with their respective control points).

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

**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.~~

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

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.