BéZIER_CURVE

(Redirected from Bezier curve)

In the mathematical field of numerical analysis, a 'Bézier curve' is a parametric curve important in computer graphics.
Generalizations of Bézier curves to higher dimensions are called Bézier surfaces, of which the Bézier triangle is a special case.
Bézier curves were widely publicised in 1962 by the French engineer Pierre Bézier, who used them to design automobile bodies. The curves were first developed in 1959 by Paul de Casteljau using de Casteljau's algorithm,
a numerically stable method to evaluate Bézier curves.

Contents

Examination of cases

Linear Bézier curves

Quadratic Bézier curves

Cubic Bézier curves

Generalization

Terminology

Notes

Constructing Bézier curves

Linear curves

Quadratic curves

Higher-order curves

Polynomial form

Applications

Computer graphics

Code example

Rational Bézier curves

See also

References

External links

Examination of cases

Linear Bézier curves

Given points 'P'₀ and 'P'₁, a linear Bézier curve is just a straight line between those two points. The curve is given by
:$mathbf\{B\}(t)=mathbf\{P\}\_0\; +\; (mathbf\{P\}\_1-mathbf\{P\}\_0)t=(1-t)mathbf\{P\}\_0\; +\; tmathbf\{P\}\_1\; mbox\{\; ,\; \}\; t\; in\; [0,1]$
and is equivalent to linear interpolation.

Quadratic Bézier curves

A quadratic Bézier curve is the path traced by the function 'B'(''t''), given points 'P'₀, 'P'₁, and 'P'₂,
: $mathbf\{B\}(t)\; =\; (1\; -\; t)^\{2\}mathbf\{P\}\_0\; +\; 2t(1\; -\; t)mathbf\{P\}\_1\; +\; t^\{2\}mathbf\{P\}\_2\; mbox\{\; ,\; \}\; t\; in\; [0,1].$
TrueType fonts use Bézier splines composed of quadratic Bézier curves.

Cubic Bézier curves

Four points 'P'₀, 'P'₁, 'P'₂ and 'P'₃ in the plane or in three-dimensional space define a cubic Bézier curve.
The curve starts at 'P'₀ going toward 'P'₁ and arrives at 'P'₃ coming from the direction of 'P'₂. Usually, it will not pass through 'P'₁ or 'P'₂; these points are only there to provide directional information. The distance between 'P'₀ and 'P'₁ determines "how long" the curve moves into direction 'P'₂ before turning towards 'P'₃.
The parametric form of the curve is:
:$mathbf\{B\}(t)=(1-t)^3mathbf\{P\}\_0+3t(1-t)^2mathbf\{P\}\_1+3t^2(1-t)mathbf\{P\}\_2+t^3mathbf\{P\}\_3\; mbox\{\; ,\; \}\; t\; in\; [0,1].$
Modern imaging systems like PostScript, Asymptote and Metafont use Bézier splines composed of cubic Bézier curves for drawing curved shapes.

Generalization

The Bézier curve of degree $n$ can be generalized as follows. Given points 'P'₀, 'P'₁,..., 'P'_n, the Bézier curve is
:$mathbf\{B\}(t)=sum\_\{i=0\}^n\; \{nchoose\; i\}mathbf\{P\}\_i(1-t)^\{n-i\}t^i\; =mathbf\{P\}\_0(1-t)^n+\{nchoose\; 1\}mathbf\{P\}\_1(1-t)^\{n-1\}t+cdots+mathbf\{P\}\_nt^n\; mbox\{\; ,\; \}\; t\; in\; [0,1].$
For example, for $n=5$:
:$mathbf\{B\}(t)=mathbf\{P\}\_0(1-t)^5+5mathbf\{P\}\_1t(1-t)^4+10mathbf\{P\}\_2t^2(1-t)^3+10mathbf\{P\}\_3t^3(1-t)^2+5mathbf\{P\}\_4t^4(1-t)+mathbf\{P\}\_5t^5\; mbox\{\; ,\; \}\; t\; in\; [0,1].$
This formula can be expressed recursively as follows:
Let $mathbf\{B\}\_\{mathbf\{P\}\_0mathbf\{P\}\_1ldotsmathbf\{P\}\_n\}$ denote the Bézier curve determined by the points 'P'₀, 'P'₁,..., 'P'_n. Then
:$mathbf\{B\}(t)\; =\; mathbf\{B\}\_\{mathbf\{P\}\_0mathbf\{P\}\_1ldotsmathbf\{P\}\_n\}(t)\; =\; (1-t)mathbf\{B\}\_\{mathbf\{P\}\_0mathbf\{P\}\_1ldotsmathbf\{P\}\_\{n-1\}\}(t)\; +\; tmathbf\{B\}\_\{mathbf\{P\}\_1mathbf\{P\}\_2ldotsmathbf\{P\}\_n\}(t)$
In words, the degree $n$ Bézier curve is a linear interpolation between two degree $n-1$ Bézier curves.

Terminology

Some terminology is associated with these parametric curves. We have
:$mathbf\{B\}(t)\; =\; sum\_\{i=0\}^n\; mathbf\{P\}\_imathbf\{b\}\_\{i,n\}(t),quad\; tin[0,1]$
where the polynomials
:$mathbf\{b\}\_\{i,n\}(t)\; =\; \{nchoose\; i\}\; t^i\; (1-t)^\{n-i\},quad\; i=0,ldots\; n$
are known as Bernstein basis polynomials of degree ''n'',
defining t⁰ = 1 and (1 - t)⁰ = 1.
The points 'P'_''i'' are called ''control points'' for the Bézier curve. The polygon formed by connecting the Bézier points
with lines, starting with 'P'₀ and finishing with 'P'_''n'', is called the ''Bézier polygon'' (or ''control polygon''). The convex hull of the Bézier polygon contains the Bézier curve.

Notes

★ The curve begins at 'P'₀ and ends at 'P'_n; this is the so-called ''endpoint interpolation'' property.

★ The curve is a straight line if and only if all the control points lie on the curve. Similarly, the Bézier curve is a straight line if and only if the control points are collinear.

★ The start (end) of the curve is tangent to the first (last) section of the Bézier polygon.

★ A curve can be split at any point into 2 subcurves, or into arbitrarily many subcurves, each of which is also a Bézier curve.

★ Some curves that seem simple, such as the circle, cannot be described exactly by a Bézier or piecewise Bézier curve (though a four-piece Bézier curve can approximate a circle, with a maximum radial error of less than one part in a thousand, when each inner control point is the distance $4left(sqrt\; \{2\}-1$
ight)/3 horizontally or vertically from an outer control point on a unit circle).

★ The curve at a fixed offset from a given Bézier curve, often called an ''offset curve'' (lying "parallel" to the original curve, like the offset between rails in a railroad track), cannot be exactly formed by a Bézier curve (except in some trivial cases). However, there are heuristic methods that usually give an adequate approximation for practical purposes.

Constructing Bézier curves

Linear curves

]

Animation of a linear Bézier curve, ''t'' in [0,1]

The ''t'' in the function for a linear Bézier curve can be thought of as describing how far 'B'(''t'') is from 'P'₀ to 'P'₁. For example when ''t=0.25'', 'B'(''t'') is one quarter of the way from point 'P'₀ to 'P'₁. As ''t'' varies from 0 to 1, 'B'(''t'') describes a straight line from 'P'₀ to 'P'₁.

Quadratic curves

For quadratic Bézier curves one can construct intermediate points 'Q'₀ and 'Q'₁ such that as ''t'' varies from 0 to 1:

★ Point 'Q'₀ varies from 'P'₀ to 'P'₁ and describes a linear Bézier curve.

★ Point 'Q'₁ varies from 'P'₁ to 'P'₂ and describes a linear Bézier curve.

★ Point 'B'(''t'') varies from 'Q'₀ to 'Q'₁ and describes a quadratic Bézier curve.

Construction of a quadratic Bézier curve		]
Construction of a quadratic Bézier curve		Animation of a quadratic Bézier curve, ''t'' in [0,1]

Higher-order curves

For higher-order curves one needs correspondingly more intermediate points. For cubic curves one can construct intermediate points 'Q'₀, 'Q'₁ & 'Q'₂ that describe linear Bézier curves, and points 'R'₀ & 'R'₁ that describe quadratic Bézier curves:

Construction of a cubic Bézier curve		]
Construction of a cubic Bézier curve		Animation of a cubic Bézier curve, ''t'' in [0,1]

For fourth-order curves one can construct intermediate points 'Q'₀, 'Q'₁, 'Q'₂ & 'Q'₃ that describe linear Bézier curves, points 'R'₀, 'R'₁ & 'R'₂ that describe quadratic Bézier curves, and points 'S'₀ & 'S'₁ that describe cubic Bézier curves:

Construction of a quartic Bézier curve		]
Construction of a quartic Bézier curve		Animation of a quartic Bézier curve, ''t'' in [0,1]

(See also a .)

Polynomial form

Sometimes it is desirable to express the Bézier curve as a polynomial instead of a sum of less straightforward Bernstein polynomials. Application of the binomial theorem to the definition of the curve followed by some rearrangement will yield:
:$$
mathbf{B}(t) = sum_{j = 0}^n mathbf{C}_j t^j

where
:$$
mathbf{C}_j = rac{n!}{(n - j)!} sum_{i = 0}^j rac{mathbf{P}_i (-1)^{i + j}}{i! (j - i)!} =
prod_{m = 0}^{j - 1} (n - m) sum_{i = 0}^j rac{mathbf{P}_i (-1)^{i + j}}{i! (j - i)!}
.
This could be practical if $mathbf\{C\}\_j$ can be computed prior to many evaluations of $mathbf\{B\}(t)$; however one should use caution as high order curves may be numerically unstable (de Casteljau's algorithm should be used if this occurs). Note that the product of no numbers is 1.

Applications

Computer graphics

Bézier curves are widely used in computer graphics to model smooth curves. As the curve is completely contained in the convex hull of its control points, the points can be graphically displayed and used to manipulate the curve intuitively. Affine transformations such as translation, scaling and rotation can be applied on the curve by applying the respective transform on the control points of the curve.
Quadratic and cubic Bézier curves are most common; higher degree curves are more expensive to evaluate. When more complex shapes are needed, low order Bézier curves are patched together. This is commonly referred to as a "path" in programs like Adobe Illustrator or Inkscape. These poly-Bézier curves can also be seen in the SVG file format. To guarantee smoothness, the control point at which two curves meet and one control point on either side must be collinear.
The simplest method for scan converting (rasterizing) a Bézier curve is to evaluate it at many closely spaced points and scan convert the approximating sequence of line segments. However, this does not guarantee that the rasterized output looks sufficiently smooth, because the points may be spaced too far apart. Conversely it may generate too many points in areas where the curve is close to linear. A common adaptive method is recursive subdivision, in which a curve's control points are checked to see if the curve approximates a line segment to within a small tolerance. If not, the curve is subdivided parametrically into two segments, $0\; le\; t\; le\; 0.5$ and $0.5\; le\; t\; le\; 1$ and the same procedure is applied recursively to each half. There are also forward differencing methods, but great care must be taken to analyse error propagation. Analytical methods where a spline is intersected with each scan line involve finding roots of cubic polynomials (for cubic splines) and dealing with multiple roots, so they are not often used in practice.

Code example

The following code is a simple practical example showing how to plot a cubic Bezier curve using the C programming language. Note, this simply computes the coefficients of the polynomial and runs through a series of t values from 0 to 1—in practice this is not how it is usually done—a recursive solution is often faster, taking fewer processor cycles at the expense of requiring more memory temporarily. However the direct method illustrated here is easier to understand and produces the same result. The following code has been factored to make its operation clear—an optimization in practice would be to compute the coefficients once and then re-use the result for the actual loop that computes the curve points—here they are recomputed every time, which is less efficient but helps to clarify the code.
The resulting curve can be plotted by drawing lines between successive points in the curve array—the more points, the smoother the curve.
On some architectures, the code below can also be optimized by dynamic programming. E.g. since ''dt'' is constant, ''cx''
★ ''t'' changes a constant amount with every iteration. By repeatedly applying this optimization, the loop can be rewritten without any multiplications (though such a procedure is not numerically stable).

/
★
Code to generate a cubic Bezier curve

★ /
typedef struct
{
float x;
float y;
}
Point2D;
/
★
cp is a 4 element array where:
cp[0] is the starting point, or P0 in the above diagram
cp[1] is the first control point, or P1 in the above diagram
cp[2] is the second control point, or P2 in the above diagram
cp[3] is the end point, or P3 in the above diagram
t is the parameter value, 0 <= t <= 1

★ /
Point2D PointOnCubicBezier( Point2D
★ cp, float t )
{
float ax, bx, cx;
float ay, by, cy;
float tSquared, tCubed;
Point2D result;
/
★ calculate the polynomial coefficients
★ /
cx = 3.0
★ (cp[1].x - cp[0].x);
bx = 3.0
★ (cp[2].x - cp[1].x) - cx;
ax = cp[3].x - cp[0].x - cx - bx;
cy = 3.0
★ (cp[1].y - cp[0].y);
by = 3.0
★ (cp[2].y - cp[1].y) - cy;
ay = cp[3].y - cp[0].y - cy - by;
/
★ calculate the curve point at parameter value t
★ /
tSquared = t
★ t;
tCubed = tSquared
★ t;
result.x = (ax
★ tCubed) + (bx
★ tSquared) + (cx
★ t) + cp[0].x;
result.y = (ay
★ tCubed) + (by
★ tSquared) + (cy
★ t) + cp[0].y;
return result;
}
/
★
ComputeBezier fills an array of Point2D structs with the curve
points generated from the control points cp. Caller must
allocate sufficient memory for the result, which is


★ /
void ComputeBezier( Point2D
★ cp, int numberOfPoints, Point2D
★ curve )
{
float dt;
int i;
dt = 1.0 / ( numberOfPoints - 1 );
for( i = 0; i < numberOfPoints; i++)
curve[i] = PointOnCubicBezier( cp, i
★ dt );
}

Another application for Bézier curves is to describe paths for the motion of objects in animations, etc. Here, the x, y positions of the curve are not used to plot the curve but to position a graphic. When used in this fashion, the distance between successive points can become important, and in general these are not spaced equally—points will cluster more tightly where the control points are close to each other, and spread more widely for more distantly positioned control points. If linear motion speed is required, further processing is needed to spread the resulting points evenly along the desired path.

Rational Bézier curves

The rational Bézier adds adjustable weights to provide closer approximations to arbitrary shapes. The numerator is a weighted Bernstein-form Bézier curve and the denominator is a weighted sum of Bernstein polynomials.
Given ''n'' + 1 control points 'P'_''i'', the rational Bézier curve can be described by:
:$$
mathbf{B}(t) =
rac{
sum_{i=0}^n b_{i,n}(t) mathbf{P}_{i}w_i
}
{
sum_{i=0}^n b_{i,n}(t) w_i
}

or simply
:$$
mathbf{B}(t) =
rac{
sum_{i=0}^n {n choose i} t^i (1-t)^{n-i}mathbf{P}_{i}w_i
}
{
sum_{i=0}^n {n choose i} t^i (1-t)^{n-i}w_i
}.

See also

★ de Casteljau's algorithm

★ Spline (mathematics)

★ NURBS

★ string art - Bézier curves are also formed by many common forms of string art, where strings are looped across a frame of nails.

★ Hermite curve

References

★ Paul Bourke: ''Bézier curves'', http://astronomy.swin.edu.au/~pbourke/curves/bezier/

★ Donald Knuth: ''Metafont: the Program'', Addison-Wesley 1986, pp. 123-131. Excellent discussion of implementation details; available for free as part of the TeX distribution.

★ Dr Thomas Sederberg, BYU ''Bézier curves'', http://www.tsplines.com/resources/class_notes/Bezier_curves.pdf

★ J.D. Foley ''et al.'': ''Computer Graphics: Principles and Practice in C'' (2nd ed., Addison Wesley, 1992)

External links

★ Bezier Curves interactive applet

★ 3rd order Bezier Curves applet

★ Living Math Bézier applet

★ Living Math Bézier applets of different spline types, JAVA programming of splines in An Interactive Introduction to Splines

★ Don Lancaster's Cubic Spline Library describes how to approximate a circle (or a circular arc, or a hyperbola) by a Bézier curve; using cubic splines for image interpolation, and an explanation of the math behind these curves.

★

★ Module for Bezier Curves by John H. Mathews

★ Quadratic Bezier Curve Construction - An interactive applet showing how to construct a quadratic Bezier curve geometrically. (Requires Java.)

★ Cubic Bezier Curve Construction - An interactive applet showing how to construct a cubic Bezier curve geometrically. (Requires Java.)

★ Bezier / Parabola - An interactive applet showing the relationship between the quadratic Bezier curve and the parabola. (Requires Java.)

★ PolyBezier - The Microsoft Win32 GDI API function, which draws Bezier curves in Windows graphic applications, like MS Paint.

★ Finding All Intersections of Two Bezier Curves. - Locating all the intersections between two Bezier curves is a difficult general problem, because of the variety of degenerate cases. By Richard J. Kinch.

★ SketchPad - A small program written in C and Win32 that implements the functionality to create and edit Bezier curves. Demonstrates also the use of de Casteljau's algorithm to split a Bezier curve.