March 96 - NURB Curves: A Guide for the Uninitiated
NURB Curves: A Guide for the Uninitiated
Philip J. Schneider
QuickDraw 3D supports a mathematical model for arbitrary curves and surfaces
known as NURB (nonuniform rational B-splines). NURB curves are flexible and
powerful, but using them effectively requires some understanding of the underlying
mathematical theory. This article presents an intuitive introduction to the
mathematical concepts of the NURB model and how to use them in your QuickDraw 3D
programs.
One of the more powerful features of QuickDraw 3D is its ability to work with curves
and surfaces of arbitrary shape. The mathematical model it uses to represent them is
powerful, but for those unfamiliar with the mathematics, it can appear dauntingly
complex. The existing books and articles on the subject tend to be rigorous, lengthy,
and theoretical, and often seem to require that you already understand the subject in
order to follow the explanations.
The mathematics really aren't so frightening, though, once you understand them. The
aim of this article is to give you an intuitive understanding of how NURBcurves work.
Later in the article, we'll look at some code to show you how you can start using NURB
curves in your own programs -- but you really do need to understand the theory
before you can start putting it to practical use. So please be patient while we slog
through the mathematical concepts: I promise we'll get around to some actual
programming before we're through. Note also that this article is only about NURB
curves; perhaps a future article will cover NURB surfaces and how to use curves and
surfaces together.
Some writers also use the s from "spline," resulting in the acronym
NURBS -- but most avoid this usage because phrases like "a NURBS curve
sound awkward, and "a NURBS surface" sounds perfectly hideous.*
WHY NURB CURVES?
Like any graphics package, QuickDraw 3D offers low-level geometric primitives for
objects such as lines, points, and triangles. Because the representations of these
objects are mathematically exact -- lines being defined by their two endpoints,
triangles by their three vertices, and so forth -- they're resolution independent and
unaffected by changes in position, scale, or orientation.
The low-level primitives can also be used to define arbitrarily shaped objects, such
as a football or an automobile hood, but at the cost of these desirable mathematical
properties; for example, a circle that's approximated by a sequence of line segments
will change its shape when rotated. One of the advantages of NURB curves is that they
offer a way to represent arbitrary shapes while maintaining mathematical exactness
and resolution independence. Among their useful properties are the following:
• They can represent virtually any desired shape, from points, straight
lines, and polylines to conic sections (circles, ellipses, parabolas, and
hyperbolas) to free-form curves with arbitrary shapes.
• They give you great control over the shape of a curve. A set of control
points and knots, which guide the curve's shape, can be directly manipulated to
control its smoothness and curvature.
• They can represent very complex shapes with remarkably little data. For
instance, approximating a circle three feet across with a sequence of line
segments would require tens of thousands of segments to make it look like a
circle instead of a polygon. Defining the same circle with a NURB
representation takes only seven control points!
In addition to drawing NURB curves directly as graphical items, you can use them in
various other ways that exploit their useful mathematical properties, such as for
guiding animation paths or for interpolating or approximating data. You can also use
them as a tool to design and control the shapes of three-dimensional surfaces, for
purposes such as
• surfaces of revolution (rotating a two-dimensional curve around an axis
in three-dimensional space)
• extruding (translating a curve along a curved path)
• trimming (cutting away part of a NURB surface, using NURB curves to
specify the cut)
CURVES 101
Before we go into the specifics of NURB curves, let's review some of the basics of
curve representation in general.
Although QuickDraw 3D supports three-dimensional NURB curves, we'll limit all of
our examples and discussions here to two dimensions. But everything we say about
two-dimensional curves applies in three dimensions as well -- the two-dimensional
versions are just easier to visualize and easier to draw.
A BIT OF HISTORY
Back in the days before computers, architects, engineers, and artists would draw their
designs for buildings, roads, machine parts, and the like by using pencil, paper, and
various drafting tools. These tools included rulers and T-squares for drawing straight
lines, compasses for drawing circles and circular arcs, and triangles and protractors
for making precise angles.
Of course, a lot of interesting-shaped objects couldn't be drawn with just these
simple tools, because they had curved parts that weren't just circles or ellipses.
Often, a curve was needed that went smoothly through a number of predetermined
points. This problem was particularly acute in shipbuilding: although a skilled artist
or draftsman could reliably hand-draw such curves on a drafting table, shipbuilders
often needed to make life-size (or nearly life-size) drawings, where the sheer size of
the required curves made hand drawing impossible. Because of their great size, such
drawings were often done in the loft area of a large building, by a specialist known as a
loftsman. To aid in the task, the loftsman would employ long, thin, flexible strips of
wood, plastic, or metal, called splines. The splines were held in place with lead
weights, called ducks because of their resemblance to the feathered creature of the
same name (see Figure 1).
Figure 1. A draftsman's spline
The resulting curves were smooth, and varied in curvature depending on the position
of the ducks. As computers were introduced into the design process, the physical
properties of such splines were investigated so that they could be modeled
mathematically on the computer.
DIRECT FUNCTIONS
Our goal is to represent curves in a mathematically precise fashion. One simple way is
to think of the curve as the graph of a function:
y = f(x)
Take a simple one like the trigonometric sine function:
y = sin x
By plotting the value of the function for various values of x and connecting them
smoothly, we obtain the curve shown in Figure 2.
Figure 2. Plot of sine function values
In the case of curves drawn by the spline method, it turned out that with some
reasonable simplifying assumptions, they could be mathematically represented by a
series of cubic (third-degree) polynomials, each having the form
y = Ax3 + Bx2 + Cx + D
At this point, the standard references typically go into a long, involved development of
this idea into what are known as cubic spline curves, eventually leading to the theory
of NURB curves. Such explanations are interesting, but not terribly intuitive. If
you're interested in pursuing this subject further, you'll find a good discussion in
Mathematical Elements for Computer Graphics. (Complete information on this and
other literature references in this article can be found in the bibliography at the end.)
PARAMETRIC FUNCTIONS
Using direct functions to represent a curve fits our criterion of being mathematically
exact, but it has one serious drawback: since we can have only one value of y for each
value of x, our curves can't loop back on themselves. Thus, although we can make some
nice smooth curves this way, there are a lot of interesting curves we can't make --
not even something as simple as a circle.
An alternative method, and the one we'll be using, is to define the curve with a
parametric function. In general, such functions have the form
Q(t) = {X(t), Y(t)}
where X(t) and Y(t) are functions of the parameter t (hence parametric). Given a
value of t, the function X(t) gives the corresponding value of x, and Y(t) the value of y.
One way to understand such functions is to imagine a particle traveling across a sheet
of paper, tracing out a curve. If you think of the parameter t as representing time, the
parametric function Q(t) gives the {x, y} coordinates of the particle at time t. For
example, defining the functions X(t) and Y(t) as
X(t) = cos t
Y(t) = sin t
produces a circle, as you can verify by plugging in some values of t between 0 and
2[[pi]] and plotting the results.
SMOOTHNESS
One very important motivation for using NURB curves is the ability to control
smoothness. The NURB model allows you to define curves with no kinks or sudden
changes of direction (such as an airplane-wing cross section) or with precise control
over where kinks and bends occur (sharp corners of machined objects, for instance).
We all know (or think we do) what a nice, smooth curve looks like: it has no kinks or
corners. If we were to sit on that moving particle as it traces out a parametric curve,
we would experience a nice smooth ride with no stopping, restarting, or sudden
changes in speed or direction: we wouldn't be heading north, say, and then turn
completely east in an instant. This intuitive notion can be expressed in precise
mathematical terms: Imagine an arrow that always points in the direction in which our
hypothetical particle is traveling as it moves along the curve. Mathematically, the
direction arrow corresponds to the tangent of the curve, which can be computed as the
derivative of the curve's defining function with respect to the time parameter t:
Q'(t)
In Figure 3, for example, the point on the curve corresponding to time tA is labeled as
Q(tA), and the direction vector (tangent) at that point as Q'(tA). If the tangent doesn't
jump suddenly from one direction to another, the curve's function is said to have
first-derivative continuity, denoted by C1: this corresponds to our intuitive notion of
smoothness.
Figure 3. Tangent (derivative) of a curve
Now look at the point marked Q(tB), where there's a visible kink in the curve. The
direction vector just a tiny bit to the left of that point, Q'(tB-[[alpha]]), is wildly
different from the one just a tiny bit to the right, Q'(tB+[[alpha]]). In fact, the
direction vector jumps instantaneously from one direction to another at point Q(tB).
Mathematically, this is called adiscontinuity.
Many of you will recall from your college calculus that the derivative of a function is
also a function, whose degree is one less than that of the original function. For
example, the derivative of a fourth-degree function is a third-degree function. The
derivative of the derivative, called the second derivative, will then be of degree 2. This
second derivative may or may not be continuous: if it is, we say that the original
function has second-derivative continuity, or C2. As the first derivative describes the
direction of the curve, the second derivative describes how fast that direction is
changing. The second derivative thus characterizes the curve's degree of curvature,
and so a C2-continuous curve is said to have curvature continuity. We'll come back to
these important concepts after we've introduced NURB curves themselves.
NURB CURVES
Now that we know how parametric functions work, let's see how we can use them to
build up a definition for NURB curves. If we call our function Q, the left side of our
equation will look like this:
Q(t) =
where t is a parameter representing time. By evaluating this function at a number of
values of t, we'll get a series of {x, y} pairs that we can use to plot our curve, as
shown in Figure 4. Now all we have to do is define the right-hand side.
Figure 4. Plotting a parametric function
CONTROL POINTS
One of the key characteristics of NURB curves is that their shape is determined by
(among other things) the positions of a set of points called control points, like the ones
labeled Bi in Figure 5. As in the figure, the control points are often joined with
connecting lines to make them easier to see and to clarify their relationship to the
curve. These connecting lines form what's known as acontrol polygon. (It would
actually make more sense to call it a "control polyline," but the other is the
conventional term.)
Figure 5. Defining a curve with control points
The second curve in Figure 5 is the same curve, but with one of the control points