Curves and Surfaces (Advanced Methods in Computer Graphics) Part 3

Bezier Curves

Bezier splines are approximating curves generated using Bernstein polynomials as the blending functions (see Box 2.4, Sect. 2.7). Denoting n + 1 control points by P1… Pn+1, the parametric representation of the nth degree Bezier curve is given by

where, ß,,n(t) denotes Bernstein polynomials of degree n. Since Bernstein polynomials always yield non-negative values for 0 < t < 1, and form a partition of unity, every point on a Bezier curve is a convex combination of the control points. In this section, we discuss the construction of piecewise cubic splines using Bezier curves, and outline an important algorithm that will be later extended to develop the framework for B-splines.

Cubic Bezier Splines

The parametric equation of the cubic Bezier curve is given by

where P1 … P4 are the control points.

 

Fig. 7.8 Cubic Bezier curves

The Bezier spline interpolates between the first and the last control points. The two middle control points are used to define the tangent directions at the end points. In the matrix form, the cubic Bezier curve is given as

Differentiating Eq. 7.36 with respect to t, we get the tangent directions on the Bezier curve:

From the above equation, the tangent directions at P1 and P4 are obtained as follows:

The control points and the tangent directions are shown in Fig. 7.8a. Clearly, the Bezier cubic curve is a special case of the Hermite polynomial curve where m1 = 3(P2 — P1) and m2 = 3(P4 — P3). The following equation relates the input vector [P1, P2, m1, m2] of a Hermite curve as given in Eq. 7.30, with the input vector [P1, P2, P3, P4] of the Bezier curve, so that the resulting splines coincide.

Fig. 7.9 A Bezier spline passing through a set of control points

Given a set of n control points P1,… Pn, the Bezier spline consisting of piecewise cubic polynomial curves can be made to pass through the first and every fourth point P3k+1, k = 0, 1,2____The remaining points are used for specifying tangent directions. For G1 continuity of the spline, we need to make sure that the three points P3k, P3k+1, P3kC2 are collinear for k = 1,2,____An example of a piecewise cubic Bezier spline satisfying this condition is shown in Fig. 7.9. The knot positions are the same as those used earlier in Figs. 7.2 and 7.5.

Bezier splines are widely used in computer graphics and therefore graphics packages commonly support methods for creating Bezier curves of different orders. We could also make use of the functionality provided by such libraries for generating other types of splines (Hermite, Catmull-Rom etc.), if we can compute the Bezier equivalent set of control points for the required spline. As an example, by computing the inverse of the 4 x 4 matrix in Eq. 7.40, we can obtain the Bezier control points for the required Hermite curve as follows:

In a general case, we express the parametric curve P(t) in terms of the required spline’s basis (denoted by Ms) as well as the Bezier basis as

from which we obtain

where

The above matrix is the inverse of the 4 x 4 matrix in Eq. 7.37.

de-Casteljau’s Algorithm

The de-Casteljau’s algorithm provides an alternative representation of a Bezier curve in terms of a combination of linear interpolation functions. Given three control points P1, P2, P3, we can construct parametric equations of two straight lines

For each parameter value t e [0,1], the above equations give two points. We now further interpolate between these two points using the same parameter value:

The resulting point will lie on the quadratic Bezier curve generated using the control points P1, P2 and P3. This can be easily proved by substituting for P11 and P21 from Eq. 7.45 in the above equation:

Figure 7.10 shows the geometrical interpretation of the above equation. Using the same method, we can obtain the cubic Bezier curve from four control points (Fig. 7.8b). Using a parameter value in the range [0, 1], we interpolate between consecutive pairs of control points to get three points, further interpolate between them to get two points, and again interpolate between the two points to get a single point on the cubic curve. This interpolation sequence is shown in Fig. 7.11. The whole process is repeated for the next parameter value.

Fig. 7.10 Interpolation between three control points using de-Casteljau’s algorithm

Fig. 7.11 Iteration sequence for de-Casteljau’s algorithm with four control points

The de-Casteljau’s algorithm for a general n — 1 degree Bezier curve with control points P1 :::Pn can be written as follows:

For the above iteration, the index d is varied from 1 to n — 1, and for each d the index k is varied from 1 to n — d. After each level of iteration (see Fig. 7.11), the number of points reduces by one. At level n — 1, we get a single point P1,n _ 1 which lies on the Bezier curve P(t) of degree n — 1.

Fig. 7.12 (a) Effect of varying homogeneous coordinates on Bezier curve. (b) Conic sections formed using rational Bezier curves

Rational Bezier Curves

Rational Bezier curves are formed using control points specified in homogeneous coordinates. A three-dimensional point P = (x, y, z) has an equivalent homogeneous representation (xh, yh, zh, h), h ^ 0 (see Box 2.1). The Bezier curve equation in Eq. 7.35 is applied to each of the components, and correspondingly every point P(t) also gets a fourth component. The x, y, and z coordinates of P(t) are divided by its fourth component to get the Cartesian coordinates. The additional parameter h acts as a weight that can be adjusted to change the shape of the curve. An example showing the variation of a cubic curve’s shape for three equivalent representations of the control point P3 is given in Fig. 7.12a. In this 2-D example, the third component is the homogeneous coordinate h.

The homogeneous coordinate system also allows the representation of points at infinity, by setting the last component to zero. Defining a control point at infinity causes the control polygonal line to have disjoint and parallel edges. This feature is useful for the generation of conic sections using Bezier curves. Figure 7.12b shows a semi-circular arc and a semi-ellipsoidal arc formed using quadratic Bezier curves. Among the three control points P1, P2, P3, the point P2 is at infinity along the + y direction. The control polygonal line therefore degenerates into two parallel vertical lines meeting at P2.