1 .edu



Chapter 6. Bezier Curves

In this chapter, we will discuss a spline based upon a specific set of polynomials known as the Bernstein polynomials. The Bernstein polynomials are an approximation to a given function over an interval [pic]. The values of the function are required over a set of evenly distributed points in [pic] rather than an arbitrarily distributed set used in the previous sections. This seems, at first, to be a restriction that is not desirable. But as we shall learn, this type of spline is very useful in creating or constructing smooth curves that conform to a user-specified shape. These curves are called Bezier curves. So here we deal mainly with methods and procedures for generating shapes rather than function approximations to sets of data points.

6.1. Bernstein Polynomials

First we introduce the Bernstein polynomials which are the foundation for building Bezier curves. The Bernstein polynomials of degree [pic] associated with function [pic] on [pic] is defined as

[pic] (6.1.1)

where [pic] are the binomial coefficients and

[pic] (6.1.2)

is an evenly distributed set of points in [a, b] generated by Equation 6.1.2 and not given data values. Indeed, [pic] is not an interpolating polynomial.

In previous chapters, the problems we dealt with are: given a set of data points, try to produce a function to connect them. When the value of the function at a location in between the data points is needed, the value of the interpolation or spline function at that point can be used as an approximation. The data points can be arbitrary as long as they are discrete and arranged in some order.

The Bernstein polynomials exhibit distinctly different behavior. They are polynomials of degree [pic] which vanish at the end points [pic] and [pic]. Over the entire interval [pic], [pic] is a single function rather than a combination of piecewise functions. The coefficients of the polynomials are the same for the entire interval. In contrast, in the case of the polynomial splines and B-splines, the coefficients are generally different from sub-interval to sub-interval.

Although [pic] require values of [pic] over only a set of discrete points [pic] rather than over the entire interval, the values [pic] are part of the coefficients. The polynomials do not pass through externally supplied points [pic]. They are not splines by definition.

In this chapter, the generated points [pic] are only dependent on the degree [pic] once [pic] is set because positions [pic] vary according to Equation 6.1.2. The Bernstein polynomials require different [pic] for different degree [pic], then [pic] is determined from a function [pic]. So strictly speaking, the function [pic] cannot be viewed as data as it could be in dealing with interpolating polynomials or splines. A set of arbitrarily distributed discrete data points will not satisfy the construction requirements of the Bernstein polynomials. This appears to be a serious restriction, but as will be seen later, this is not disadvantageous to our purpose.

One would then ask, what is the use of the Bernstein polynomials? The answer is that the Bernstein polynomials are approximations to the function [pic]. As we will show later, when the degree [pic] increases, they converge uniformly to [pic].

The values of [pic] and [pic] are not essential in the construction of the Bernstein polynomial. For the sake of convenience, [pic] is chosen as the interval of [pic]. For instance, by a simple linear transformation, any [pic] can be transformed to [pic] by introducing a new independent variable [pic] per the linear transformation

[pic]

Clearly, [pic] for [pic]. Substituting [pic] for [pic] in the Bernstein polynomials, we get

[pic]

where

[pic]

However to comply with common notation, we revert to [pic] and use[pic]from here on, so the Bernstein polynomials are rewritten as

[pic] (6.1.3)

where [pic] are called the Bernstein basis polynomials and are defined as

[pic]

Clearly, the coefficients of the Bernstein basis polynomials are dependent on [pic] and [pic] and nothing else. There is no function [pic] in the basis formula; it appears in the polynomial, Equation 6.1.3, where it is evaluated at points [pic], not in the basis.

To get a sense of the polynomials, let’s first write all the Bernstein basis polynomials up to degree [pic].

[pic]

[pic]

[pic]

[pic]

[pic]

For every degree [pic], there are [pic] basis polynomials which are the building blocks for the Bernstein polynomials. Looking at these formulas, especially the coefficients, one may recognize that they are familiar. In fact, recalling the expanded formula for [pic], the above expressions are for the case [pic] and [pic]. So basically, [pic] are the individual terms of the expanded expression of [pic].

To make this even easier, the basis polynomials can be generated by recalling the Pascal (Yang Hui, Khayam) Triangle

|Power |Coefficients |

|0 |1 |

|1 |1 1 |

|2 |1 2 1 |

|3 |1 3 3 1 |

|4 |1 4 6 4 1 |

|5 |1 5 10 10 5 1 |

|6 |1 6 15 20 15 6 1 |

|…. |………………… |

which provides the coefficients for powers of [pic] and [pic], respectively.

Example 6.1.1: Develop a computer program for calculating [pic].

For sure, we can write a program to calculate the formula directly. But since we need it for any degree [pic], it is better to have a recursive algorithm. To do this, we introduce the following equation:

[pic] (6.1.4)

where [pic] and [pic] are not included. For [pic], the second term above would require [pic], which is not permitted. For [pic], the first term would require [pic] for degree [pic] which is not permitted either.

(Note: in [pic], [pic]is always greater than [pic]because for [pic].)

For the [pic] and [pic] term, we have

[pic] (6.1.5)

where [pic] and [pic] are already obtained from the previous computational cycle.

To prove the recursive formula, we have

[pic]

The algorithm of the MATLAB code “bernstein_basis.m” is as follows

1) Input the degree n of B and[pic] where the interpolation value is needed;

2) Check to see if [pic] is out of range; if yes, abort the program; if no, proceed;

3) Building [pic] through [pic]: Assign [pic]; Calculate [pic] using the recursive scheme (Equations 6.1.4 and 6.1.5);

Let’s write the recursive formula in MATLAB language

function b = bernstein_basis(n,xx)

%BERNSTEIN_BASIS Bernstein basis polynomials;

%BERNSTEIN_BASIS returns values of Bernstein basis

% polynomials Bn,i(xx),n>=1 at xx;

%b is a vector of length n+1, b(i+1)=Bn,i(xx), i=0,1,..,n;

if ( (xx1.0) );

error('xx out of range in function "bernstein_basis"!');

end;

xx_1=1.0-xx;

b=1:n+1; % index shifted from [0,n] to [1,n+1];

for i=1:n; %starting from B_1,1, build Bn,i from Bn-1,i;

b(i+1)=xx*b(i); %2nd term in Equation 6.1.5;

for j=i-1:-1:1;

b(j+1)=xx_1*b(j+1)+xx*b(j); % Equation 6.1.4;

end;

b(1)=xx_1*b(1); % 1st term in Equation 6.1.5;

end;

6.2. Building Bernstein Polynomials

Of course, one would note that [pic] for all [pic]’s. Then from the binomial theorem, for any given [pic], the summation of [pic] over all [pic] is also exactly [pic].

[pic]

Thus, for the function [pic], the Bernstein polynomial, [pic] so that in this case Equation 6.1.3 matches the function y = 1 exactly. In general, (6.1.3) only approximates a function y.

Differentiating the above equation, we get

[pic]

Multiplying by [pic], we get

[pic]

which means for the function [pic], the Bernstein polynomial is also exactly the function itself.

Example 6.2.1. Prove that the Bernstein polynomial [pic] is linear in regard to function y.

Proof: For any constants [pic] and [pic], and two functions [pic] and [pic], we get

[pic]

Then for any linear function [pic], we have

[pic]

which means the Bernstein polynomials for a linear function is also exactly the function itself.

Could this be true for all polynomial functions? The answer is no. Let’s consider [pic] as a quadratic function, the simplest of which would be [pic]. Differentiating [pic], we get

[pic]

then multiplying by [pic]

[pic]

So [pic], but rather it is an approximation to [pic]. And the error term is

[pic]

Generally, we have the following theorem stating that the Bernstein polynomials are an approximation to the function [pic].

Weierstrass Theorem: If [pic]is continuous on [pic], then [pic] converges uniformly to[pic].

Please refer to Buchanan and Turner (1992) for the proof of this theorem. Let’s see how well Bernstein polynomials do in approximating a function.

Example 6.2.2. Evaluate the Bernstein polynomials for [pic] on [pic].

A MATLAB program “bernstein_example.m” is written for this example. It uses the function bernstein_basis.m.

[pic]

Figure 6.2.1 Evaluation of sin4x using the Bernstein polynomials

As can be seen in Figure 6.2.1, the Bernstein polynomials are not very good at converging towards [pic]. Generally, this is true for all functions other than those simple ones discussed above. Well, our interest here is to create the Bezier curve, which is discussed in the following section, not particularly to approximate functions.

6.3. Bezier Curve

The Bezier curves are intended to develop shapes. For instance, if we view the curves in Figure 6.2.1 as the generation of a sequence of shapes rather than an approximation to a function, we might be satisfied with the results. Indeed, this is the objective of the Bezier curves: the generation of shapes in design.

Let’s run “bezier_example_1.m”

[pic]

Figure 6.3.1 Bezier curves for polygons

First, we have four control points in this example

|i |1 |2 |3 |4 |

|xp |0.0 |0.3 |0.7 |1.0 |

|yp |0.1 |0.6 |0.8 |0.2 |

Let the function [pic]be the linear spline passing through these points. The shape of the function is then a polygon. This and the resulting Bernstein polynomials for [pic]3 to 6 are plotted in Figure 6.3.1a. It is clear that these smooth curves converge towards the polygon. Beside the two endpoints, these curves do not pass through the polygon.

The polygon is of a concave shape, and so are the curves. When the shape of the polygon is convex, so are the curves as shown in Figure 6.3.1b. This conclusion is generally true. These curves are called “Bezier curves”.

Let’s move the second control point in Figure 6.3.1a to (0.3, 0.0). The resulting polygon (Figure 6.3.1c) is convex at the beginning and concave near the end. The Bezier curves also are convex at the beginning and concave near the end. Similar things happen when the third control point in Figure 6.3.1d is changed to (0.7,0.8).

So by setting up several control points, the Bezier curves are created from the resulting polygon. These curves have certain shapes like concave, convex or more generally complicated. We are not interested in converging the Bezier curves to the polygon by increasing the degree n. That would be very slow and unnecessary. Our interest is to generate a smooth curve to our liking while n is relatively low. This process is fast and easy to implement in a computer code. And this is the beauty of the Bezier curve.

To further illustrate the essence and power of the Bezier curve, let’s look at the following example. It is more complex, but the code remains the same, other than the control points.

Example 6.3.2. Create a smooth curve, which satisfying the following requirements

1). Must pass through endpoints (0,0) and (1,0.1);

2). Be convex and increase initially;

3). Be convex and decrease near the end;

4). Reach its maximum value of 0.6 near x=0.6;

5). The maximum should be its only stationary point on [0,1].

We do this exercise in “bezier_example_2.m”

As a first step, the following 7 points are selected as control points. The function [pic]is the linear spline across these points. Then the Bernstein polynomials of the orders 3 to 6 are plotted in Figure 6.3.2a.

|i |1 |2 |3 |4 |5 |6 |7 |

|xp |0 |0.2 |0.4 |0.5 |0.7 |0.9 |1 |

|yp |0 |-0.1 |0.45 |0.6 |0.6 |-0.1 |0.1 |

• The selection of points 1 and 7 are obvious. That is according to requirement No.1 above and should be kept in all subsequent tries.

• Because of the requirements of the convexity of the curve near both ends, we put

y = -0.1 at x = 0.2 and 0.9.

Then, we put two points in the middle, (0.5, 0.6) and (0.7, 0.6), in trying to get the curve to pass through (0.6, 0.6).

[pic]

Figure 6.3.2 Bezier Curve

The resulting curves (n = 3 to 6), plotted in Figure 6.3.2a, do not have a convex shape at the beginning for n = 3, but they do for higher degrees. For n = 5 and 6, the curves decrease from zero. So we probably need to raise the second control point a bit. Also, the high point of the curves only reach y = 0.4, not 0.6 as required. This can be corrected by raising the 4th and 5th control points.

Implementing these two changes in the second try, we get curves in Figure 6.3.2b. They are better. The decrease of y at the beginning is eliminated. The high value of y is raised from 0.4 to 0.55. Raising y at x = 0.5 and 0.7 further to 0.9 from 0.8, generates the Bezier curves plotted in Figure 6.3.2c.

This time the curves are generally good. Let’s use n = 6 for our final solution. The only adjustment is to move the peak a bit lower and to the right. This is accomplished by setting the two high control points to (0.52, 0.88) and (0.72, 0.88). The n = 6 curve in Figure 6.3.2d is pretty satisfactory with respect to all the requirements.

From this example, we can appreciate the flexibility and convenience of the Bezier curves. Setting up the program is simple. It is easy to just have several control points and move them around, or even deleting or adding new control points. These moves do not require any change in the core of the code.

6.4 Bezier Curves with Closed Ends

So far we discussed the Bezier curves with open ends. Sometimes we would like to generate a closed curve, or a curve having[pic] going back and forth on the x- axis. Obviously the formula above does not permit this.

This problem is actually easy to fix. A dummy variable [pic] is introduced and both [pic] and [pic]are treated as functions of [pic]. They can be written as

[pic]

For a closed or self-crossed curve, or more precisely, a closed or self-crossed polygon from the control points chosen, we can start from any control point and let [pic] there. Then chose a path to go through all the other points while t increases. Finally we go back to the starting control point and use it again for [pic]. This scheme is a parametric representation of the curve, a very important concept in computer graphics.

Example 6.4.2. Generate the infinity sign ( using “bezier_example_3.m”

The plots in Figures 6.4.2 (a), (b) and (c) illustrate Bezier curves for three degrees:

• n = 7, 9, 11.

The control curves for each plot are given by the following data:

• Plot (a):

xp |-1 |-2/3 |-1/3 |1/3 |2/3 |1 |2/3 |1/3 |-1/3 |-2/3 |-1 | |yp |0 |2/3 |2/3 |-2/3 |-2/3 |0 |2/3 |2/3 |-2/3 |-2/3 |0 | |

• Plot (b):

xp |-1 |-2/3 |-1/3 |1/2 |1 |3/2 |1 |1/2 |-1/3 |-2/3 |-1 | |yp |0 |1 |1 |-3/2 |-3/2 |0 |3/2 |3/2 |-1 |-1 |0 | |

• Plot (c):

xp |-0.8 |-0.6 |-1/4 |1/2 |1 |3/2 |1 |1/2 |-1/4 |-0.6 |-0.8 | |yp |0 |0.9 |0.9 |-3/2 |-3/2 |0 |3/2 |3/2 |-0.9 |-0.9 |0 | |

where xp, yp are the control points for the curves. Note: the control lines are not shown for plots (b) and (c).

[pic]

Figure 6.4.1. Creating the infinite sign with the Bezier Curve.

6.5 Interactive Curve Generation

A MATLAB code “bezier_interactive.m” is used for interactive plotting of the Bezier curves. It has the following capabilities

1) Add, delete and move control points interactively;

2) Show any of the Bezier curves of degrees [pic];

3) Write the curves as lines or their polynomial coefficients to files;

The detail of using the code is explained in “bezier_int_readme.m”. The user should review this file before running the code.

References:

Cheney, W. and Kincaid, D., “Numerical Mathematics and Computing,” Third Edition, Brooks/Cole Publishing Company, 1994.

Buchanan, J.L. and Turner, P.R., “Numerical Methods and Analysis,” McGraw-Hill, 1992.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download