Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
method to evaluate polynomials in Bernstein form or Bézier curve
Bézier curve
A Bézier curve is a parametric curve frequently used in computer graphics and related fields. Generalizations of Bézier curves to higher dimensions are called Bézier surfaces, of which the Bézier triangle is a special case....
Paul de Casteljau is a French physicist and mathematician. In 1959, while working at Citroën, he developed an algorithm for computation of Bézier curves, which would later be formalized and popularized by engineer Pierre Bézier...
. De Casteljau's algorithm can also be used to split a single Bézier curve into two Bézier curves at an arbitrary parameter value.
Although the algorithm is slower for most architectures when compared with the direct approach, it is more numerically stable.
Definition
Given a polynomial B in Bernstein form of degree n
In the mathematical field of numerical analysis, a Bernstein polynomial, named after Sergei Natanovich Bernstein, is a polynomial in the Bernstein form, that is a linear combination of Bernstein basis polynomials....
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
Then, the evaluation of at point can be evaluated in steps of the algorithm. The result is given by :
Moreover, the Bézier curve can be split at point into two curves with respective control points :
Example implementation
Here is an example implementation of De Casteljau's algorithm in Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
:
deCasteljau :: Double -> [(Double, Double)] -> (Double, Double)
deCasteljau t [b] = b
deCasteljau t coefs = deCasteljau t reduced
where
reduced = zipWith (lerpP t) coefs (tail coefs)
lerpP t (x0, y0) (x1, y1) = (lerp t x0 x1, lerp t y0 y1)
lerp t a b = t * b + (1 - t) * a
Example
We want to evaluate the Bernstein polynomial of degree 2 with the Bernstein coefficients
at the point t0.
We start the recursion with
and with the second iteration the recursion stops with
which is the expected Bernstein polynomial of degree n.
Bézier curve
When evaluating a Bézier curve of degree n in 3 dimensional space with n+1 control points Pi
with .
we split the Bézier curve into three separate equations
which we evaluate individually using De Casteljau's algorithm.
Geometric interpretation
The geometric interpretation of De Casteljau's algorithm is straightforward.
Consider a Bézier curve with control points . Connecting the consecutive points we create the control polygon of the curve.
Subdivide now each line segment of this polygon with the ratio and connect the points you get. This way you arrive at the new polygon having one less segment.
Repeat the process till you arrive at the single point - this is the point of the curve corresponding to the parameter .
The following picture shows this process for a cubic Bézier curve:
Note that the intermediate points that were constructed are in fact the control points for two new Bezier curves, both exactly coincident with the old one. This algorithm not only evaluates the curve at , but splits the curve into two pieces at , and provides the equations of the two sub-curves in Bezier form.
The interpretation given above is valid for a nonrational Bezier curve. To evaluate a rational Bezier curve in , we may project the point into ; for example, a curve in three dimensions may have its control points and weights projected to the weighted control points . The algorithm then proceeds as usual, interpolating in . The resulting four-dimensional points may be projected back into three-space with a perspective divide.
In general, operations on a rational curve (or surface) are equivalent to operations on a nonrational curve in a projective space
Projective space
In mathematics a projective space is a set of elements similar to the set P of lines through the origin of a vector space V. The cases when V=R2 or V=R3 are the projective line and the projective plane, respectively....
. This representation as the "weighted control points" and weights is often convenient when evaluating rational curves.
A Bézier curve is a parametric curve frequently used in computer graphics and related fields. Generalizations of Bézier curves to higher dimensions are called Bézier surfaces, of which the Bézier triangle is a special case....
In the mathematical subfield of numerical analysis the de Boor's algorithm is a fast and numerically stable algorithm for evaluating spline curves in B-spline form. It is a generalization of the de Casteljau's algorithm for Bézier curves. The algorithm was devised by Carl R. de Boor...
In numerical analysis, the Horner scheme , named after William George Horner, is an algorithm for the efficient evaluation of polynomials in monomial form. Horner's method describes a manual process by which one may approximate the roots of a polynomial equation...
In numerical analysis, the Clenshaw algorithm is a recursive method to evaluate a linear combination of Chebyshev polynomials. In general it applies to any class of functions that can be defined by a three-term recurrence relation.-Clenshaw algorithm:...
to evaluate polynomials in Chebyshev form
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
at point 
can be evaluated in 
steps of the algorithm. The result 
is given by :
can be split at point 
into two curves with respective control points :
.
, but splits the curve into two pieces at 
, and provides the equations of the two sub-curves in Bezier form.
, we may project the point into 
; for example, a curve in three dimensions may have its control points 
and weights 
projected to the weighted control points 
. The algorithm then proceeds as usual, interpolating in 
. The resulting four-dimensional points may be projected back into three-space with a perspective divide.
. Connecting the consecutive points we create the control polygon of the curve.
and connect the points you get. This way you arrive at the new polygon having one less segment.
.