Computer Aided Geometric Design

Introduction to Curve and Surface Geometry

One of the biggest problems that has been faced by vendors of Computer Aided Design
products has been the challenge of developing suitable software for drawing complex curves
and surfaces. These notes provide an introduction to the topic and explain the major techniques
that have been developed by mathematicians, engineers and programmers in order to make
possible the construction of complex 2D curves and 3D surfaces.

The ability to construct complex shapes, and subsequently manufacture products incorporating
them has been a major aspect of competition in many industries. Shapes such as wing profiles
and ship hulls are examples of complex functional shapes, but in many industries geometry is
employed to produce aesthetically pleasing surfaces. It is not surprising that many of the major
developments in curve and surface technology have occurred in the car industry where a
combination of function and style are vital.

Traditionally engineers drew curves using spline methods. These were techniques that
employed pliable materials (such as lead strips) that could be curved around pins attached to
pieces of wood to produce very smooth curves that could interpolate through control points (i.e.
the pins). In the shipbuilding industry, very long curves were required and normally the only part
of the building that was long enough to house this activity was the loft, so the practise of
drawing spline curves became known as 'lofting'. Today this expression is still used and the
computer analogies of splines bear the same names. Splines that pass through chosen control
points are called 'interpolation splines' and those that are merely pulled toward control points
are called 'approximation splines'. We will now consider the methods that have been used to
construct computer splines.

Simple Curves and Simple Geometry

We all know from our early maths that the equation of a straight line is as follows

Simple equation of a straight line

This equation is based on the description of a line as a gradient and intercept. To describe a line
segment we would specify two values of either x or y to bound the chosen line.
This method of describing a line is simple, but does have drawbacks. Firstly it does not cope
very well with vertical lines! We could of course revert to an explicit equation with x as a function
of y but that only transfers the problem to horizontal lines. A better way to describe line
segments may therefore be to use parametric curves, so our new straight line equation
becomes:

or in vector notation

Parametric equations of a straight line

This method allows us to easily draw robust straight lines. We can set the general nature of a
straight line by changing the coefficients A and B.

Straight lines therefore are easy, but now let us consider a simple curve. This can be
represented by say a quadratic, cubic, quartic, quintic etc. polynomial like so:

Power basis equation for a curve

This method of describing curves uses as its 'basis', a series of powers of the independent
variable and is therefore known as a 'power basis polynomial'. This may work well for the
straight line where the meaning of the coefficients A and B is clear, but what is the meaning of
C or D etc? If we want to draw higher order curves we might be better to use meaningful design
variables. Spline curves are usually drawn using design variables that are meaningful to the
designer, typically these are the positions of a set of control points through or near which the
curve will pass.

Interpolation Splines
Perhaps the simplest way of describing curves for the designer is to consider a set of co-
ordinates for each point to be interpolated, as with a parametric curve. These splines are clearly
analogous to our early example of the techniques used by the shipbuilding industry. This is
indeed a useful method, but given a set of m+1 points, we would need a curve of degree m to
describe our shape. With many points we end up with very high degree curves. In order to plot
the curves we have to find interpolating values of the polynomial coefficients and this involves
the solution of potentially large sets of simultaneous equations. These curves can also easily
become too 'squiggly' for the designer's liking and they offer no local control. In practice these
problems are usually overcome by using only, say, cubic curve segments and which are joined
or knotted together to form piecewise curves that can interpolate many points.
The simple method of making piecewise curves can use Lagrangian interpolation methods to fit
curves (typically cubic, ie degree m=3) through m+1 (typically therefore 4) control points.
Another method of developing piecewise interpolation splines is to use Hermite interpolation.
This involves design variables describing not just control points but also those describing the
tangent of the curve at that control point. This has the advantage that local control over the
curve is possible since any action taken at a control point will only affect the curve to either side
of the point since on reaching a subsequent point the position and slope of the curve is set.

Figure 1:Lagrange and Hermite interpolation used to construct a parametric cubic curve segment
In order to make the construction of curves and surfaces easy and fast, another effective means
of is to use approximation splines.

Approximation Splines
There are many methods that have been developed to produce approximation splines, e.g.
Bézier curves, B-splines (uniform, non-uniform or periodic), Beta-splines and NURBS (Non-
Uniform, Rational B-Splines) to name a few. We will now try to look at the most important of
these in order to give an introduction to them.

BÉZIER CURVES
The first application of approximation splines is credited to the French mathematician Pierre
Bézier who worked for the Renault motor company. He proposed a method of drawing curves
that would provide an intuitive feel for automotive body designers, allowing shapes to be
manipulated by pulling out the curves. These curves interpolated end points, but approximated
intermediate points. This, it is argued, makes the curves easy to join together and simple to
calculate as well as manipulate. A Bézier curve for a simple cubic curve (degree 3) will have 4
control points as we might expect, and might look like this:

Figure 2: A Bézier curve of degree 3

The most convenient equation used to describe a Bézier curve uses 'blending functions' which
are used to 'blend' the effect of the control points on each part of the curve. A Bézier curve then
is described by the following equation:

For degree d, where

d 
Where   is the binomial coefficient, Bi , d (t ) is the Bernstein Basis function and P the control
i 
points.
The equation of a Bezier curve
Perhaps the easiest way to understand how a curve might be constructed is to use the de
Casteljau construction (blossom) of a Bezier curve. This is based on a physical analogy of
points travelling in straight lines along tracks.
Consider a simple quadratic curve with 3 control points as shown below:
 Figure 3: The de Casteljau construction
The curve generated from the above can be represented by the following set of linear equations
thus:

By substitution we get,

Thus the basis of the polynomial is not a power series, but a set of functions as follows:

The basis function describes the blending of the point ‘attraction’ along the curve. We can plot
these to observe the effect that each control point has.
1 1

B3,3
B0,2 B2,2 B0,3

B1,2
B1,3 B2,3

0 0
1 0 0 1
t t
 Figure 4: The Bernstein basis blending functions: degree 2 and 3

As already mentioned the Bézier curve passes through its first and last control points. This
property derives from the Bernstein Basis function as at the endpoints (t=0,1) the functions are
zero except for the first and last functions e.g. degree 3 – B0,3 and B3,3. The curve is also
tangent to the first and last segments of the control polygon.

It is possible to create higher order Bézier curves however this can become unwieldy and
intensive to compute. One solution to this is the use of many lower order curves joined together.
This is made relatively easy as the first and last points are interpolated however the problem
then becomes that of continuity.

The notion of continuity was developed for explicit functions to describe when a curve does not
break or tear. If it meets these conditions, it is described as C0. If the derivative curve is also
continuous, then the curve is first-order differentiable and is said to be C1 continuous. By
ensuring equality of the dth parametric derivative at each joint we also ensure Cd continuity.

Figure 5: Parametric continuity

Practically, this means that a C1 continuous curve will not kink. Higher degrees of continuity
imply a smoother curve. CAGD thus introduces the idea of geometric continuity. If a curve is C0,
it is G0 continuous. If a curve's tangent direction changes continuously then it is G1 continuous.
Its magnitude may jump discontinuously but the curve is still G1. If a C1 curve has kinks because
its derivative goes to zero at a point, then this curve will not be G1, since the tangent direction
changes discontinuously at the kink. Hence the notion of geometric continuity provides a useful
way to understand the smoothness of a curve or surface.

Bézier curves also have a number of other useful properties. It can be seen from figure 4 that
the basis function always sums to 1. This ensures that the curve is always contained within its
convex hull a fact useful for intersection computations and the like. Bézier curves are also said
to be affinely invariant with respect to their control points. This means that a Bézier curve is
transformed simply by transforming its control points. Another useful property is that the curve is
variation diminishing indicating that the curve intersects any plane only as often as its control
polygon.

The major downside to Bézier curves is that through ensuring continuity, most usefully and
usually C2, little control is left to be exercised over the individual components.
B-Splines

B-splines consist of curve segments that have many similarities with single Bézier curves. A
cubic B-spline curve might look as follows:

Figure 6: Possible cubic B-spline curves – Linear, quadratic and cubic

The major advantage of B-splines over Bézier curves is that we achieve continuity in piecewise
curves by sharing control points. The number of points shared is dependent on the degree of
continuity required. This means that local changes to the curve are possible.

A B-spline curve can be defined in a similar way to a Bézier:

n
P (t ) = ∑ Pi N i ,k (t )
i =0

where {Pi:i =0,1,2….,n} are the control points, k is the order of the polynomial segments of the
B-spline curve and N i ,k (t ) the are the normalised B-spline blending functions (this is different to
the Bernstein Basis blending function used with Bézier curves).

The normalised B-spline blending function is given by

1, (t i ≤ t ≤ t i +1 )
N i ,1 (t ) =
0, (otherwise)

t − ti t −t
N i ,k (t ) = N i ,k −1 (t ) + i + k N i +1,k −1 (t )
t i + k −1 − t i t i + k − t i +1

where tI are the ‘knot variables’ given by {tI : i=0,…n+k}

if i < k then tI = 0
if k ≤ i ≤ n then ti = i-k+1
if i > n then ti = n-k+2

The points where curves are joined together are called 'knots' and to generate a B-spline we
must specify a 'knot vector' which is a list of the positions of these knots. These are usually
normalised along the parameter space to give values between 0 and 1 and may or may not be
uniformly spaced. There are m – 1 knots in a curve since the start and end points are
considered as knots.

Where the knots are uniformly spaced the curve’s blending functions have equal weight. Figure
7 shows the normalised blending function for a quadratic (k=3) B-spline over 5 points.

Figure 7: Quadratic B-spline blending function

k Degree of Polynomial Continuity

1 0 Disjointed points
2 1 C0
3 2 C1
4 3 C2

Typically, the common CAD systems use C2 continuity between cubic curve segments. Thus
we can set a cubic B-spline with any number of control points. The algorithm for generating the
curve will then have to set the required number of curve segments and the continuity between
them. A cubic B-spline with C2 continuity then approximates a series of n+1 control points where
n ≥ 3 and there are n - 2 curve segments. A piecewise curve might look as follows:
 Figure 8: A possible cubic piecewise B-spline curve

Non uniform spacing allows the weight of the functions to vary in their ‘pull’ along the curve and
can therefore offer greater control. Where the curve is required to interpolate a particular point,
multiple control points can be placed at one position (for a cubic this is 3).

Non-Uniform Rational B-Splines (or NURBS)

One drawback with Bézier curves and simple B-splines is that they cannot describe exactly
conic sections such as a parabola or circle. A means to overcome this is the use of rational
parametric curves. Rational curves are defined on the basis of homogeneous co-ordinates,
which represent three-dimensional points in terms of four dimensions with an additional w-axis
co-ordinate. To draw the curve in three-dimensional space the first three co-ordinates of each
point are divided by the forth. This essentially uses one spline as the numerator and another as
the denominator.
This approach can be used with Bézier curves but also with non-uniform B-splines to produce
NURBS.

This forth dimension does come at some cost as calculations become larger and more draining
on computer resources. However most modern CAD systems do use NURBS, fortunately much
of the work is already done by these systems leaving the designer to think about the shape and
as little as possible about the maths.

Surfaces
The major advantage of parametric methods of representing curves is that they can be
generalised into surface representation. Both the Bézier curve and the B-Spline can be
extended into 3D to create surface patches.

Bézier Surface Patches

If each point on a Bézier curve were moved along a curve of its own a Bézier Surface patch
would be traced out. The patches are defined by the network of points that form the control
polyhedron. Many of the properties of the patch are born from those belonging to the Bézier
curve. The surface approximates all of the points except the four corner points that are
interpolated, they are tangent to the start and end segments, contained within the convex hull of
its control points, affinely Invariant and variation diminishing.

The general equation is obtained by extending the curve equation with another parametric
variable:
du dv
Q(u, v) = ∑∑ Pij Bi ,d (u ) Bi ,d (v)
i =0 j =0

where b is the same Bernstein basis functions as with the Bézier curve and du and dv are the
degrees of the polynomials for the control points.

Bézier surface patches suffer the same problems as Bézier curves. The primary problem being
that the number of control points is directly related to the order and thus continuity. For example
the above equation expands, for a 4x3 patch, to:
  P00 P01 P02 
P   (1 − v) 2 
[ ]
Q(u , v) = (1 − u ) 3 3u (1 − u ) 2 3u 2 (1 − u )u 3  10
 P20
P11
P21
P12  
P22   2v(1 − v)


  v 
2
 
 P30 P31 P32 

It can be seen that the above surface provides curvature continuity C2 in one direction and
tangency continuity C1 in the other. Thus again it is preferable to create a surface using a series
of patches. Also as with the curves the continuity requirement prevents the ability to make local
manipulations. For this reason NURBS for the basis of most modern surface modelling
packages.

B-Spline Surface Patches

We move to B-Spline surfaces for the same reason as we moved from Bézier curves to B-
Spline Curves as again the surface properties are analogous to the curve properties. Thus
importantly this gives us a surface with which the continuity is independent of the number of
control points and can be locally manipulated. The rest of the useful B-Spline properties also
remain in tact.

Again the equation is obtained by the addition of another parametric variable

m n
P (u , v) = ∑∑ Pij N i ,k (u ) N j ,l (v)
i =0 j =0

Rational Parametric Surfaces

These too are analogous to their curve roots and are defined by the equations of the Bézier or
B-spline surfaces written in homogeneous co-ordinates. This results in surface representation
that is capable of modelling spheres and cylinders as well as more abstract surfaces.