eScience Lectures Notes : Spline

Slide 1 : 1 / 42 : Spline



Slide 2 : 2 / 42 : Spline


Hearn & Baker, Ch 10

The term computer graphics was often associated with creation of realistic scenes and animated images. With the advent of both computers and applied mathematics more ambitious applications of computer graphics were sought in the last few decades. Today, one of the most important areas where computer graphics plays a central role is computer-aided design (CAD) and computer-aided manufacture (CAM). Both CAD and CAM are extensively used in a large number of areas, including aerospace, automotive engineering, marine engineering, civil engineering, and electronic engineering. The successful applications of computer graphics in engineering is largely due to the progress of computer aided geometric design (CAGD) which provides the mathematical basis for describing and processing geometric shapes and data. The term geometric modeling(which includes curve modeling, surface modeling, and solid modeling) is often used as the synonym of computer aided geometric design, although some authors argue that geometric modeling means the building up of computer representations of complex shapes from representations of similar components.

The most promising description method of geometric shape is the parametric curves and surfaces. The theory of parametric curves and surfaces are well understood in algebraic geometry and differential geometry. However, their possibilities and advantages for representing geometric entities in a CAD environment were not known until the late 1950s. The major breakthroughs in CAGD were undoubtedly the theory of Ferguson curves and patches, Coons patches, Bézier curves and surfaces, later combined with B-spline methods. Today, Bézier and B-spline representations of curves and surfaces have been the industrial standard.

In this chapter, we shall briefly review different curve representation methods and tell you why the parametric representation of curves is of mots importance. Then, we shall discuss the mathematics on Bézier and B-spline curves, which is the foundation of surface and solid modeling.

Slide 3 : 3 / 42 : Convex Hull

Convex Hull

Convex : A subset S of the plane is called convex if and only if for every pair of points p,q in S, the line segment pq is completely contained in S.

Convex Hull : The convex hull CH(S) of a set S is the smallest convex set that contains S.

A Point which is defined by P = S ai Mi is inside the convex hull of {Mi}

Sai = 1

ai >= 0

lemme : the convex Hull of of a subset of a set is inside the convex hull of the set

Slide 4 : 4 / 42 : Convex Hull (2)

Convex Hull (2)

A Point which is defined by P = S ai Mi is inside the convex hull of {Mi}

Sai = 1

ai >= 0

lemme : the convex Hull of of a subset of a set is inside the convex hull of the set

recurrence demonstration

n = 1 => P = M

n = 2 => M1 M2        for 0<=t<=1   P = (1-t) M1 + t M2 = M1 + t M1M2

H : true for n, what about n+1

Pn+1 = S ai Mi = (1-an+1)S ai/(1-an+1) Mi + an+1Mn+1

= (1-an+1)M' + an+1 Mn+1

Slide 5 : 5 / 42 : Types of Curves (1)

Types of Curves/Surface


An explicit representation of curve enables us to directly compute y at any value of x.

Surface equation in 3D space : x and y are independent variables and z is the dependant variable

y = f(x)

z = f( x, y)

y = mx + b  or x = c

z = - (Ax + By + D) / C

x = cos (3y +1/y)

z = sin(3x) * cos (xy) + ln(y)

Not Symmetric definition !

The explicit form is satisfactory when the function is single-valued and the curve has no vertical tangents

In the Cartesian plane, an explicit equation of a planar curve is given by y = f(x), where f(x) is a prescribed function of x. An explicit representation of curve enables us to directly compute y at any value of x. If we are asked to represent a straight line in the Cartesian coordinate by an explicit form, we will probably give the following equation:

y = kx + b,
provided that this line is not vertical to the x-axis. Otherwise, we have to represent vertical lines as x = c, where c is some constant value. Such problems inherent in explicit form is easily dealt with when solving a problem by hand. However, it is a nuisance when programming geometrical problems for a computer. Another drawback with respect to the use of explicit form is numerical stability. Referring to the above straight line, we note that the computation of y is numerically unstable if k goes to infinity, indicating the line is nearly vertical. In general, if a curve has nearly vertical tangents, we may expect overflow or rounding error problems when computing the function values. For these reasons, the use of explicit form in computer aided geometric design is very limited.

The explicit form is satisfactory when the function is single-valued and the curve has no vertical tangents. However, this precludes many curves of practical importance such as circles, ellipses and the other conic sections. An implicit equation of the form f(x,y) = 0 can avoid the difficulties of multiple values and vertical tangents inherent in the explicit form. For example, a unit circle with its centre at the origin is given by x2+y2-1 = 0. If we require an explicit equation of the same circle, then it must be divided into two segments, with y = +[(r2-x2)] for the upper half and y = -[(r2-x2)] for the lower half. This kind of segmentation creates cases which are a nuisance in computer programs.

Although an implicit form of curve can overcome some limitations inherent in an explicit form, it does not enable us to compute points on a curve directly. Usually, implicitly defined curves require the solution of a non-linear equation for each point and thus numerical procedures have to be employed. Furthermore, both explicit and implicit represented curves are axis-dependent. The choice of coordinate system directly affects the ease of use.

Explicitly and implicitly defined curves are sometimes called non-parametric curves. An alternative way of describing curves is the parametric form, which uses an auxiliary parameter to represent the position of a point. For example, a unit circle with centre at origin may be represented by an angle parameter u [0, 2p]:

x(u) = cosu,     y(u) = sinu.
Curves having parametric form are called parametric curves. A parametric curve that has a polynomial parameterization is called a polynomial curve, which is a standard in CAD systems for describing curves and surfaces. Since a point on a parametric curve is specified by a single value of parameter, the use of parametric techniques free us from dependence on any particular system of coordinates. Therefore, the parametric description of a curve enables coordinate transformations such as translation and rotation, required for graphical display, to be performed very simply. The parametric form also avoids problems which can arise in representing closed or multiple-valued curves and curves with vertical tangents in a fixed coordinate system. Furthermore, the parametric method lends itself to the piecewise description of curves and surfaces, which is a basic technique for the description of free form shapes. Due to these advantages, parametric curves are most commonly used in computer aided geometric design.


Slide 6 : 6 / 42 : Types of Curves (2)

Types of Curves/Surface (2)


Curve defined in terms of cartesian coordinates:

f( x, y) = 0

f( x, y, z) = 0

Ax + By + C = 0

Ax + By + Cz + D = 0

(x - x0)2 + (y - y0)2 - r2 =  0

(x - x0)2 + (y - y0)2 + (z - z0)2 - r2 =  0

Useful in maths, not so useful in computer, except to define inside and outside :

Slide 7 : 7 / 42 : Types of Curves (3)

Types of Curves (3)

Parametric Curve

Parametrically defined curve in three/two dimensions is given by three/two univariate functions:

x = f(u)
y = g(u)
(   z = h(u)   )

where u varies between two explicit values (could be [0;1] or [- ; +])

Parametric surface

Parametrically defined surface in three dimensions is given by three bivariate functions:

x = f(u,v)
y = g(u,v)
z = h(u,v)

where u an v vary between two explicit values (could be [0;1] or [- ;+])

x = x0 + r cos q
y = y0 + r sin q

q [ 0 ; 2P

x = u
y = v
z = - (Au + Bv + D) / C

x = x0 + (x1 - x0)t
y = y0 + (y1 - y0)t
z = z0 + (z1 - z0)t

t [- ;+]

x = x0 + r . cos u . cos v
y = y0 + r . sin u . cos v
z = z0 + r . sin v

u[ 0 ; 2P ] / v[ - P/2; P/2] 


Slide 8 : 8 / 42 : Parametric curves

Parametric curves

Parametric curves are very flexible

They are not required to be functions
Curves can be multi-valued with respect to any coordinate system

(a functions return one unique value for a given entry)

Parameter count generally gives the objects's dimension

Hyperplane : (n-1 parameter) in space of dimension n ,

Decouples dimension of object from the dimension of the space

r(u) (instead of [x(u), y(u), z(u)]) : vector-valued parametric curve

notion of finite or infinite lenght : close (could always be bring back to [0 ; 1]) or open interval for u

In Cartesian space, a point is defined by distances from the origin along the three mutually orthogonal axes x, y, and z. In vector algebra, a point is often defined by a position vector r, which is the displacement with the initial point at the origin. The path of a moving point is then described by the position vectors at successive values of the parameter, say u . Hence, the position vector r is a function of u, i.e., r = r(u). In the literature, r(u) is called the vector-valued parametric curve. Representing a parametric curve in the vector-valued form allows a uniform treatment of two-, three-, or n-dimensional space, and provides a simple yet highly expressive notation for n-dimensional problems. Thus, its use allows researchers and programmers to use simple, concise, and elegant equations to formalize their algorithms before expressing them explicitly in the Cartesian space. For these reasons, a vector-valued parametric form is used intensively for describing geometric shapes in computer graphics and computer aided geometric design.

It should be noted that the curve r(u) is said to have an infinite length if the parameter is not restricted in any specific interval, i.e., u (-,+). Conversely, the curve r(u) is said to have a finite length if u is within a closed interval, for example, u [a,b] where a, b . Given a finite parametric interval [a,b], a simple reparametrization t = (u-a)/(b-a) would normalize the parametric interval to t [0,1].

A comprehensive study on curves, including polynomial parametric curves, is beyond the scope of this chapter. Interested readers may find such information in many text books on algebraic curves. In this chapter, we discuss only two types of parametric curves, namely Bézier curves and B-spline curves. In particular, we are concerned with the representation of Bézier and B-spline curves as well as some essential geometric processing methods required for displaying and manipulating curves.

Slide 9 : 9 / 42 : Specifying Curves

Specifying Curves

Take an hammer and some nails, fix the nails and try to make a piece of wood go through all the nails. You'll get a B spline...
Spline [n.] : A flexible strip (wood or rubber) used in drawing curved lines.

Control Points

a set of points that influence the curve's shape


control points that lie on the curve

Interpolating spline

curve passes through the control points knots

Approximating spline

control points merely influence shape

Convex Hull

convex polygon boundary that encloses a set of control points

If some data points are used to construct a curve the curve can either pass through the points, in which case the curve is interpolating, or the points can just be used to control the general shape of the curve and the curve doesn't actually pass through the points, in which case the curve is approximating.

Slide 10 : 10 / 42 : Continuity

Piecewise Curve Segments : Continuity

Often we will want to represent a curve as a series of curves pieced together

But we will want these curves to fit together reasonably ...

... Continuity !

Zero order parametric continuity

The curves meet

First order parametric continuity

the tangents are shared

Second order parametric continuity

the"speed" is the same before and after

animation paths ...

no infection points ? no


A Spline Curve : Any Composite curve formed with polynomial sections satisfying specified continuity conditions at the boundary of the pieces.

Equations can be classified according to the terms contained in them. Equations that only contain variables raised to a power are polynomial equations. If the highest power is one, then the equation is linear. If the highest power is two, then the equation is quadratic. If the highest power is three then it is cubic. If the equation contains sins, cosines, log or a variety of other functions, then it is called transcendental.

Continuity refers to how well behaved the curve is in a mathematical sense. If, for a value arbitrarily close to a value x0 the function is arbitrarily close to f(x0), then it has positional, or zeroth order continuity at that point. If the slope of the curve (or the first derivative of the function) is continuous, then the function has first order continuity. This is extended to all of the functions derivatives.

If a curve is pieced together from individual curve segments then one can speak of piecewise continuity if each individual segment is continuous and the values at the junctions of the curve segments are continuous.

Slide 11 : 11 / 42 : Parametric Cubic Curves

Parametric Cubic Curves

In order to assure C1 continuity  at two extremities, our functions must be of at least degree 3

Here's what a parametric cubic spline function looks like: Alternatively, it can be written in matrix form:

Slide 12 : 12 / 42 : Solving for Coefficients

Solving for Coefficients

The whole story of polynomial slines is deriving their coefficients


By satisfying the constraints set by the knots and continuity conditions

C0, C1, continuity at the extremities

Slide 13 : 13 / 42 : An Illustrative Example

An Illustrative Example

Cubic Hermite Splines:

Slide 14 : 14 / 42 : The Gradient of a Cubic Spline

The Gradient of a Cubic Spline

Slide 15 : 17 / 42 : The Hermite Specification as a Matrix Equation

The Hermite Specification as a Matrix Equation

Slide 16 : 16 / 42 : Solve for the Hermite Coefficients

Solve for the Hermite Coefficients

Slide 17 : 17 / 42 : The Hermite Specification as a Matrix Equation

The Hermite Specification as a Matrix Equation

Slide 18 : 18 / 42 : Spline Basis and Geometry Matrices

Spline Basis and Geometry Matrices

Slide 19 : 19 / 42 : Resulting Cubic Hermite Spline Equation

Resulting Cubic Hermite Spline Equation

Slide 20 : 20 / 42 : Another Way to Think About Splines

Another Way to Think About Splines

The contribution of each geometric factor can be considered separately, this approach gives a so-called blending function associated with each factor.

Beginning with our spline formulation:

By reording our multiplications we get:

= f1(t).P1 + f2(t).P2 +f3(t).P'1 + f4(t).P'2

Slide 21 : 21 / 42 : Hermite Blending Functions

Hermite Blending Functions

Slide 22 : 22 / 42 : Bézier Curves

Bézier Curves

another Spline class that has more intuitive controls

A Cubic Bézier Spine has four control points, two of which are knots.


Bezier spline is a way to define a curve by sequence of two end points and one or more control points which control
the curve.
Two end points are called Anchor Points.
The bezier splines with two control points are called Cubic Bezier Spline.

Slide 23 : 23 / 42 : Coefficients for Cubic Bezier Splines

Coefficients for Cubic Bezier Splines

It just so happens that the knot gradients of a Bezier Spline can be expressed in terms of the adjacent control points:

Note: this approach is entirely synthetic!
Using the vector is reasonable, but what makes 3 a magic number?

Slide 24 : 24 / 42 : Here's the Trick!

Here's the Trick!

Knowing this we can formulate a Bezier spline in terms of the Hermite geometry spec

And substituting gives:

Slide 25 : 25 / 42 : Basis and Geometry Matrices for Bezier Splines

Basis and Geometry Matrices for Bezier Splines


While cute, this derivation was not very natural

Slide 26 : 26 / 42 : Bezier Blending Functions

Bezier Blending Functions

The reasonable justification for Bezier spline basis can only be approached by considering its blending functions:

This family of polynomials (called order-3 Bernstein polynomials) have the following unique properties:

Slide 27 : 27 / 42 : Plots of Bezier Blending Functions

Plots of Bezier Blending Functions

Thus, every point on the curve is a linear combination of the control points.

The weights of this combination are all positive.

The sum of these weights is 1.

Therefore, the curve is a convex combination of the control points!


CARREFUL : There is a subdirectory to explore/print : Import/JBook

Slide 31 : 31 / 3 : Summary of Bézier curve properties

Summary of Bézier curve properties

Some of theses properties may sound somewhere obvious, but they are presented here because they are still valid for Bézier curves of higher degree

A Bézier cure is a polynomial.

The degree of the polynomial is always one less than the number of control points. In computer graphics, we generally use degree 3. Quadratic curves are not flexible enough and going above degree 3 gives rises to complications and so the choice of cubics is the best compromise for most computer graphics applications.

The curves follows the shape of the control point polygon.

It is constrained within the convex hull formed by the control points.

The control points do not exert 'local' control.

Moving any control point affects all of the curve to a greater or lesser extent. All the basis functions are everywhere non-zero except at the point u = 0 and u = 1

The first and last control points are the end points of the curves segment

The tangent vectors to the curve at the end points are coincident with the first and last edge of the control point polygon.

Moving the control points alters the magnitude and direction of the tangent vectors

This is the basis of the intuitive 'feel' of a Bézier curve interface.

Variation diminishing property

The curve does not oscillate about any straight line more often than the control point polygon

Affine transformation compatibility

The curve is transformed by applying any affine transformation (that is, any combination of linear transformations) to its control point representation. The curve is invariant (does not change shape) under such a transformation.

Strange mix of points on and off the curve

Non localness

As soon as you move one control point, you affect the entire curve

relationship between the degree of the curve and the number of control points

There exist some other way to construct Bézier curves...


Slide 32 : 32 / 3 : Another Way to build a Bézier curve

Another Way to build a Bézier curve...

Bernstein-Bezier Formulation of Bezier Curve (Spline)

The Bernstein-Bezier formulation is based on the subdivision property of Bezier curves.

The subdivision property completes the definition of the spacing of the control points.

The subdivision construction is:

Draw lines connecting the control points, and then recursively draw lines between the midpoints of those lines for a total of n-2 iterations, where n is the degree of the Bezier curve (Figure 3.1.). For a cubic Bezier curve, n=3, so there is just one subdivision.

deCasteljau algorithm

Points P0 , P01 , P02 , P(t) and P(t) , P12 , P21 , P3 are control points of new small splines again.

To learn more..."Cubic Bezier Patches Used to Draw Utah Teapot"

Slide 33 : 33 / 3 : B-spline Curve

B-spline Curve : why

overcomes problems with Bézier

Slide 34 : 34 / 3 : B Spline : Formulation

B Spline : Formulation

(From Basis Spline)

Slide 35 : 35 / 3 : B Spline Segment 1

Slide 36 : 36 / 3 : B Spline functions

B Spline functions


Bi(u) = (u^3)/6Bi-1(u) = (-3*(u^3) + 3*(u^2) + 3*u +1)/6
Bi-2(u) = (3*(u^3) - 6*(u^2) +4)/6
Bi-3(u) = (1 - u)^3/6
Bi(u) = (u^3)/6Bi-1(u) = (-3*((u-1)^3) + 3*((u-1)^2) + 3*(u-1) +1)/6
Bi-2(u) = (3*((u-2)^3) - 6*((u-2)^2) +4)/6
Bi-3(u) = (1 - (u-3))^3/6
Bi(u) = (u^3)/6
Bi-1(u) = (-3*((u-1)^3) + 3*((u-1)^2) + 3*(u-1) +1)/6
Bi-2(u) = (3*((u-2)^3) - 6*((u-2)^2) +4)/6
Bi-3(u) = (1 - (u-3))^3/6
B(u) = Bi(u) when 0 <= u < 1,
       Bi-1(u) when 1 <= u < 2,
       Bi-2(u) when 2 <= u < 3,
       Bi-3(u) when 3 <= u < 4
Bi(u) = (u^3)/6
Bi1(u) = (-3*((u-1)^3) + 3*((u-1)^2) + 3*(u-1) +1)/6
Bi2(u) = (3*((u-2)^3) - 6*((u-2)^2) +4)/6
Bi3(u) = (1 - (u-3))^3/6

B(u) = Bi(u) when 0 <= u < 1,
       Bi1(u) when 1 <= u < 2,
       Bi2(u) when 2 <= u < 3,
       Bi3(u) when 3 <= u < 4

B1(u) = B(u-1)
B2(u) = B(u-2)
B3(u) = B(u-3)
B4(u) = B(u-4)


To calculate the curve at any parameter t we place a gaussian curve over the parameter space. This curve is actually an approximation of a gaussian; it does not extend to infinity at each end, just to +/- 2 by using the following equations:

The Approximate Gaussian Curve

This curve peaks at a value of 2/3, and at +/- 1 its value is 1/6. When this curve is placed over the array of control points, it gives the weighting of each point. As the curve is drawn, each point will in turn become the heaviest weighted, therefore we gain more local control.


Slide 37 : 37 / 3 : B Spline Segment 2 : Forcing Interpolation

Slide 38 : 38 / 3 : B Spline Segment 3 : Forcing interpolation

CARREFUL : There is a subdirectory to explore/print : Import/JBook

Slide 40 : 40 / 1 : B-Spline Summary

Summary of B-spline curve properties

Some of the properties that we listed for Bézier Curves apply to B-spline curves, in particular :

Controls points following

The curve follows follows the shape of the control point polygon and is constrained to lie in the convex hull of the control points.

Variation diminishing property

The curve does not oscillate about any straight line more often than the control point polygon

Affine transformation compatibility

The curve is transformed by applying any affine transformation (that is, any combination of linear transformations) to its control point representation.

In addition B-splines posses the following properties

Local Control

A B-Spline curve exhibits local control - a control point is connected to four segments (in the case of a cubic) and moving a control point can influence only these segments

Number of piece you get for n comtrol points



(n - 1)/3



Slide 41 : 41 / 1 : To be continued

To be continued

Non Uniform B-spline

to permit the spline to interpolate control points

Rational Curves

Adding some relative weight to the control point


Non Uniform Rational B-spline

interactive placement and movement of control points

interactive placement and movement of knots

interactive control of control point weights

3D curves and surfaces

Slide 42 : 42 / 1 : B Spline vs Bezier

B Spline vs Bezier curves

In CAGD applications, a curve may have a so complicated shape that it cannot be represented by a single Bézier cubic curve since the shape of a cubic curve is not rich enough. Increasing the degree of a Bézier curve adds flexibility to the curve for shape design. However, this will significantly increase processing effort for curve evaluation and manipulation. Furthermore, a Bézier curve of high degree may cause numerical noise in computation. For these reasons, we often split the curve such that each subdivided segment can be represented by a lower degree Bézier curve. This technique is known as piecewise representation. A curve that is made of several Bézier curves is called a composite Bézier curve or a Bézier spline curve. In some area (e.g., computer data exchange), a composite Bézier cubic curve is known as the PolyBézier. If a composite Bézier curve of degree n has m Bézier curves, then the composite Bézier curve has in total m×n+1 control vertices.

A curve with complex shape may be represented by a composite Bézier curve formed by joining a number of Bézier curves with some constraints at the joints. The default constraint is that the curves are jointed smoothly. This in turn requires the continuity of the first-order derivative at the joint, which is known as the first-order parametric continuity. We may relax the constraint to require only the continuity of the tangent directions at the joint, which is known as the first-order geometric continuity. Increasing the order of continuity usually improves the smoothness of a composite Bézier curve. Although a composite Bézier curve may be used to describe a complex shape in CAGD applications, there are primarily two disadvantages associated the use of the composite Bézier curve:

  1. It is considerably involved to join Bézier curves with some order of derivatives continuity.
  2. For the reason that will become clear later, a composite Bézier curve requires more control vertices than a B-spline curve.

These disadvantages can be eliminated by working with spline curves. Originally, a spline curve was a draughtsman's aid. It was a thin elastic wooden or metal strip that was used to draw curves through certain fixed points (called nodes). The resulting curve minimizes the internal strain energy in the splines and hence is considered to be smooth. The mathematical equivalent is the cubic polynomial spline. However, conventional polynomial splines are not popular in CAD systems since they are not intuitive for iterative shape design. B-splines (sometimes, interpreted as basis splines) were investigated by a number of researchers in the 1940s. But B-splines did not gain popularity in industry until de Boor and Cox published their work in the early 1970s. Their recurrence formula to derive B-splines is still the most useful tool for computer implementation.

It is beyond the scope of this section to discuss different ways of deriving B-splines and their generic properties. Instead, we shall take you directly to the definition of a B-spline curve and then explain to you the mathematics of B-splines. Given M control vertices (or de Boor points) di (i = 0,1,,M-1), a B-spline curve of order k (or degree n = k-1) is defined as

r(u) = M-1

i = 0 
di Ni,k(u),
where, Ni,k(u) are polynomials of degree n and known as B-splines of order k. Analogous to Bézier curves, Ni,k(u) are also called the B-spline basis functions. In most practical applications, the B-spline basis functions are derived from the following knot vector (or knot sequence):
u0 = u1 = = un, uk uj uM-1, uM = uM+1 = = uM+n
where, ui are called knots. The reason to select the first and last k knots to be equal is that the control vertices d0 and dM-1 are the points on the curve. Furthermore, the tangent direction of the curve at d0 is from d0 to d1 and the tangent direction at dM-1 is from dM-2 to dM-1. Due to these properties, the shape of a B-spline curve resembles the shape of its control polygon formed by the control vertices di, although such resemblance is not as intuitive as that of a Bézier curve. In the literature, the M-k knots uk, uk+1, , uM-1 are sometimes called the interior knots. If the interior knots are all distinct, then the B-spline curve has M-k non-vanishing spans (i.e., the arc length of each span is not zero).

As we said previously, there are several methods to derive the B-spline basis functions Ni,k(u) in terms of the knot vector. We present only the recursive formula derived by de Boor and Cox as follows:

Ni,k(u) = u-ui
Ni,k-1(t)+ ui-u
Ni,1 =

1, u [ui,ui+1)
0, elsewhere
These basis functions have the following properties:


Slide 43 : 43 / 1 : Uniform B-spline

Uniform B-spline