11 3D Object Representations (Hermite and Bezier Splines)

T. Raghuveera

 

Objectives:

  • Hermite Spline
  • Bezier Spline

 

Discussion:

 

In the previous module, we had learnt about the two fundamental classes of splines, viz., Interpolating and Approximating. Let’s discuss about them with one example for each. ‘Hermite spline’ is an example for Interpolating splines and ‘Bezier spline’ is an example for approximating splines. The type of spline preferred, depends on the end application in context. A Spline is represented using a set of boundary conditions, a matrix that corresponds to coefficients, and a set of blending functions that make up the spline curve. Recall the spline terminology (Module-10), that has the terms, control points, blending functions, parametric forms, and boundary conditions.

 

Hermite Spline:

 

The Hermite spline is a cubic Interpolating spline. It touches all the control points that are placed in an orderly manner. Between two successive control points we need to identify a cubic curve section such that it satisfies the boundary conditions. The Hermite spline curve is thus a combination of many smaller cubic curves that are connected end to end, with each end being the position of a control point.

where ‘u’ is the parameter. The highest degree to which the parameter is raised is 3, so it is called a cubic curve. For a curve to be smooth enough the degree should be a minimum of 3, as quadratic curves are less smooth than the cubic ones.

 

We need to determine the values of a, b, c and d in the equation for the curve section. Each of these coefficients is a vector and has 3 components. For a, the components are (ax,ay,az), and similarly the other coefficients. By setting enough boundary conditions at the “joints” between curve sections we can obtain numerical values for all the coefficients.

For two curve sections to join smoothly at the boundary, they should satisfy zeroth order, first order and second order parametric continuity (refer to Module-10). Between two successive control points we need to fit a cubic parametric curve.

 

As shown above, say there are two consecutive control points, Pk, Pk+1. Let P(u) be the curve section that needs to be fit between the two control points. The curve should touch both Pk and Pk+1 on either ends and should be smooth enough. The directions at either ends represent tangents to the curve section at the ends. The four boundary conditions that the curve should satisfy are given as below.

 

a)    P(0) = Pk (substitute 0 for u, in the curve equation we should get the point Pk)

b)   P(1) = Pk+1 (substitute 1 for u, in the curve equation we should get the point Pk+1)

c)    P’(0) = DPk (substitute 0 for u, in the first derivative to curve equation, we should get the tangent to the curve at the point Pk)

d)   P’(1) = DPk+1 (substitute 1 for u, in the first derivative to curve equation, we should get the tangent to the curve at the point Pk+1)

 

From the first condition it is evident that for u=0, the curve should touch one end point Pk, and from the second condition it is clear that for u=1, the curve should touch other end point Pk+1. The curve P(u) can be written as a combination of a row matrix and a column matrix as shown below.

 

1

 

The first derivative to the curve also can be represented in matrix notation as

3  2  1 0

 

The four relations / boundary conditions can be conveniently represented in matrix notation as below.

0 0 0 1

1 1 1 1

0 0 1 0 .

3 2 1 0

 

For ex: as per the matrix notation above Pk = P(0) =

 

0 0 0 1

     For ex: as per the matrix notation above Pk+1=P(1) =

 

 ( ) =         1 1 1 1

 

For ex: as per the matrix notation above DPk=P’(0) =

 

′( ) =  0 0 1 0

 

For ex: as per the matrix notation above DPk+1=P’(1) =

 

′( ) =  3 2 1 0 

 

Thus when we combine the four conditions into a matrix form we get a 4×4 matrix as shown above. But our aim is to compute the coefficients a, b, c and d. So we can rewrite the matrix representation as below

 

 

When we multiply the three matrices, we get

 

2                                    3           1                    2              3                                    2

 

As can be observed from the above equation, P(u) is a combination of 4 cubic parametric polynomial curves, and each of these curves are called Hermite polynomials or blending functions.

where

2 3         3 2         1

 2 3        3 2

3   2 2

3      2

 

The four Hermite polynomials are called blending functions, and because for every value of the parameter in the interval 0 to 1, the four polynomials blend in some proportion to compute a point on the curve. To test whether the curve touches the two end points substitute for u, 0 in the equation for P(u) and we get Pk since the coefficient associated with Pk evaluates to 1 for u=0, and all other blending functions evaluate to 0 for u=0. These curves also satisfy a minimum of C1 continuity at the boundary.

 

 

If the shapes of the Hermite polynomials are observed carefully, it can be inferred that H0(u) has max. value of 1 at u=0 and min. value of 0, at u=1, while H1(u) has a max. value of 1 at u=1 and min. value of 0 at u=0, and H2(u) has max. and min. values somewhere between 0 and 1 for all values of u in [0,1]. H3(u) being the exception, where the curve is on the –ve side while all others are on the positive side.

 

Properties of Hermite curves:

  • Hermite polynomials can be adjusted locally because each curve section is only dependent on its end point constraints.
  • One difficulty is we also need to supply the curve slopes for deriving coefficients.

 

Bezier Spline:

 

Unlike Hermite splines, Bezier splines are approximating splines, i.e., they do not touch all the control points, except for the first and last control points. If we assume a series of control points positioned in space, the curve starts with, touching the first control point, approximates all other in-between points and finally ends by touching the last control point. Bezier curves are based on Decasteljau procedure as described below.

 

Decasteljau algorithm: Given a set of control points placed in a sequence but positioned randomly, how can we form a curve that approximates them?

 

Consider a sequence of three control points P0, P1, P2 which are non-collinear. Start with a value of u.

 

Connect the 3 non-collinear control points with two straight lines. The sequence in which we process the points is important, i.e. a line say L01 connects P0 and P1 while the other line L12 connects P 1 and P2. Assume parametric form for lines L01 and L12 (slope-intercept form, slope point form are the standard types of representing lines, the third form is the parametric form with ‘u’ as the parameter ranging in the interval [0,1]. For u=0, we are at one end point of the line and for u=1, we are at the other end point of the line. For ex: Assume a line with two end points P0(x0, y0) and P1(x1, y1), the parametric form is given as, x = (1-u) x0+u x1, y = (1-u) y0+u y1 ). Consider the parametric forms for L01 and L12 as below.

 1

1

 

For u=0, we are at P0, on line L01, and for the same u, on line L12 we are at P1. For u=1, we are at P1, on line L01, and for the same u, on line L 12, we are at P2.

 

The idea is to choose a value for u (say u= 0.2) in the interval [0, 1], fix the value and find a point on the line L01 for the value of u. Now for the same value of u, find a point on the line L12 that starts from P 1 and ends at P2. Connect the two computed points on both the lines with another straight line, and again use the value of u to compute a point on the newly formed line (connecting points on L01 and L12). The point that falls on the line connecting L01 and L12 shall be the point on the curve P(u). If we continue this procedure for all values of u in [0,1], we get a smooth flowing curve as shown in the diagram below.

 

The curve P(u) is given by

 

1

 

Substituting for L01(u) and L12(u) in the equation for P(u) we get

1            1                          1

 

1                       2 

 

Points to ponder:

  • The degree of the polynomials = (no. of cps – 1)
  • The 3 polynomials associated with the three control points are called the blending functions.
  • The curves are smooth enough
  • The curve is a weighted combination of control points. The weight is nothing but the non-negative values Associated with each of the control points, for a given value of the parameter u.
  • The blending functions are non-negative, sum to unity for every ‘u’ in the range 0 to 1
  • The curve touches (interpolate) the first and last control points but approximate all other intermediate points.
  • The direction of the tangent to the curve at the end points is along the line connecting the end point with the immediate neighbor.

If we extend the Decasteljau procedure for 4 control points, the curves we get are called Cubic Bezier curves. With 3 control points we get a quadratic curve, with 4 control points we get a cubic curve and so on and in general a Bezier curve with n control points has the degree (n-1).

 

 

As shown in the above diagram, the dotted lines connecting the control points are called as control polyline or the convex hull. The name is because the Bezier curve always lies within or contained in the convex hull. Constructing a Bezier curve with 4 control points using the same Decasteljau iterative procedure is shown below.

 

 

No. of Control points = 4 (from P0 to P3)

Degree of polynomials = 3 (cubic)

No. of terms in the curve equation = 4

No. of blending functions = 4

 

Summary:

  • We have learnt how Hermite Interpolating spline is derived
  • Decasteljau algorithm for drawing approximate curves is discussed.
  • Drawing Bezier curves by extending Decasteljau algorithm is discussed.