Bernstein Polynomials

Bernstein form of a Bézier Curve

 

Bernstein Polynomials --

Bernstein polynomials: The Bernstein polynomials of degree n are defined by

Bni(t) = ( n
i 		) ti(1-t)n-i, i = 0, 1, 2, ..., n

Here is an easy way to remember them: In order to find the Bernstein polynomials of degree 3, we simply expand
(t+(1-t))3 = t3 + 3t2(1-t) + 3t(1-t)2 + (1-t)3
Now, B33(t)=t3, B32(t)=3t2(1-t), B31(t)=3t(1-t)2, B30(t)=(1-t)3

In general, (t+(1-t))n = n
S
i=0 		( n
i 		)ti(1-t)n-i = n
S
i=0 		Bni(t)

Propositions of Bernstein Polynomials

  1. (Recursion) The Bernstein polynomials satisfy the following recursion formula: Bni(t) = (1-t)Bn-1i(t) + tBn-1i-1(t)
    Proof:
    Bni(t) = ( n
    i     		) ti(1-t)n-i = ( n-1
    i     		) ti(1-t)n-i + ( n-1
    i-1     		) ti(1-t)n-i
      = (1-t)Bn-1i(t) + tBn-1i-1(t)
  2. (Forming a partition of unity) The set of Bernstein polynomials of degree n {Bni(t) | t= 0, 1, ..., n} form a partition of unity over the interval [0,1].
    Proof:
    Bni(t) = ( n
    i     		) ti(1-t)n-i > 0 for 0 < t < 1.
    = n
    S
    i=0     		Bni(t) = n
    S
    i=0     		( n
    i     		) ti(1-t)n-i = [t+(1-t)]n = 1

Bernstein polynomials in barycentric coordinates

Example: Consider the line segment I=[0,1] in R1. Using the barycentric coordinates of the line segment I, every point p in I can be described by coordinates u=t, v=1-t, with t in I. With respect to these coordinates, the Bernstein polynomial can be written as

Bni(t) = Bni,j(u,v) = n!
i! j! 		uivj

with i+j=n; u+v=1; u,v,i,j > 0. The Bni,j(u,v) can thus be thought of as terms in the binomial expansion of (u+v)n. This principle can be carried over to triangles in R2which leads to the generalized Bernstein polynomials.

Generalized Bernstein polynomials: Recall that every point p in the interior of a triangle with vertices U, V, and W can be expressed in terms of the barycentric coordinates (u,v,w) which are determined by p(u,v,w) = uU + vV + wW, subject to the constraints u+v+w=1; u,v,w > 0. With the help of barycentric coordinates it is now easy to define the Bernstein polynomials associated with a base triangle. Using the following relations,

(u+v+w)n = S
i,j,k>0
i+j+k=n 		n!
i! j! k! 		uivjwk
(u+[v+w])n = n
S
i=0 		( n
i 		) ui(v+w)n-i
(v+w)n-1 = n-1
S
i=0 		( n-i
j 		) vjwn-i-j

the generalized Bernstein polynomials of degree n are defined as

Bni,j,k(u,v,w) = n!
i! j! k! 		uivjwk

with i+j+k=n, u+v+w=1, i,j,k,u,v,w > 0

For ease of notation, we define I:=(i,j,k)T, u:=(u,v,w)T and |I|=i+j+k, |u|=u+v+w. Then the generalized Bernstein polynomials reduce to

BnI(u) = n!
i! j! k! 		uivjwk with |u|=1.

On the edges of the base triangle, the generalized Bernstein polynomials reduce to the ordinary Bernstein polynomials. For example, Bn0,j,k(0,v,w) = Bnj(v) = Bnk(w). Clearly, every generalized Bernstein polynomial BnI can be interpreted as a (polynomial) parametric formula for a surface patch (function) over the base triangle. The maximum of this function occurs at u=I/n.
Propositions:

  1. By their definition, it is clear that the Bernstein polynomials satisfy the normalization condition
    S
    |I|=n     		BnI(u)=1
    where the sum is taken over all possible vectors I which satisfy the conditions |I|= n and I > 0. This involves a total of
    ( n+2
    2     		) = (n+1)(n+2)
    2
    terms.
  2. Since the generalized Bernstein polynomials are linearly independent, they form a basis for an (n+1)(n+2)/2 dimensional linear subspace of the space of polynomials of degree (n, n). Every element X in the linear subspace spanned by the BnI has a unique expansion
    X(u)= S
    |I|=n     		bIBnI(u)

Bernstein Form of a Bézier Curve

Using the Bernstein polynomials as a basis function, we can define a Bézier curve or Bézier polynomial of degree n (in terms of Bernstein polynomials) to be a curve in parametric form

X(t) = n
S
i=0 		biBni(t)

with coefficients bi in Rd, d=1, 2, 3. In general we take the bi to be vectors in R2 or R3, and refer to them as Bézier points. In the case where the bi are real numbers, we call them Bézier ordinates. The polygon formed by connecting the Bézier points is called the Bézier polygon.