A New Way To Machine Curves

 

A NEW WAY TO MACHINE CURVES
NURBS Interpolation Advanced Curve Translation Creates Innovative Cutting Technique 

by Jeff Wallace, Makino CAD/CAM applications engineer

Smooth curves and surfaces must be generated in many CAD/CAM applications. Computer graphics involves modeling the real world which most of the shapes of the objects are smooth and complex. Presenting curves and surfaces in mathematical equations is very important because we can hardly duplicate the same curve or surface exactly every time.

For years spline functions have provided a direct and effective representation of curves, understandable both to the computer and the person trying to manipulate the curves.

In the past several decades, researchers and mathematicians have spent considerable time and effort figuring out how best to fit curves to a set of data points. A lot of methods have developed according to the spline function. There are cubic splines, B-splines, Beta- splines and V-splines, and what we are concerned with: NURBS.

Non-Uniform Rational B-Splines (NURBS)

NURBS are Non-Uniform Rational B-Splines and is the term given to curves that are defined on a knot vector where the interior knot spans are not equal. The term Uniform means that the joints (knots) are spaced at equal intervals of the parameter t. The term Rational is used where x(t), y(t) and z(t) are each defined as the ration of two cubic polynomials. As an example, we may have interior knots with spans of zero. Some common curves require this type of non-uniform knot spacing. The use of this option allows better shape control and the ability to model a larger class of shapes.

NURBS are flexible and powerful, but for those unfamiliar with them and the mathematics involved, they can appear daunting and complex, therefore, some understanding of the underlying mathematical theory might help to explain why they are so useful. This paper presents an introduction to the basic mathematical concepts of the NURBS model and some examples.

The purpose of this paper is to give you a basic understanding of what NURBS are and how and why they work so well. Later, we will look at some example data structure to show what the machine control is looking for from your CAM system — but you really do not need to understand the theory before you can start putting it to practical use. So be patient while we review some of the mathematical concepts, we will get around to some actual examples. Note also that this article is only about NURBS interpolation; it does not deal with polynomials.(used by other machine controls and is not THE defacto standard for CAD/CAM systems)

Why NURBS?

Traditionally, the production of complicated molds and dies for the automobile, consumer products and aerospace components have been produced on CNC machines which required large programs that defined the X,Y,Z cutter locations. This traditional approach created small line segments that closely defined the desired shape. The smaller the tolerance, the more accurate the mold/die/part could be produced.

All graphics packages 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 — they’re resolution independent and unaffected by changes in position, scale, or orientation. This is key to understanding where some of the advantages are coming from.

One of the advantages of NURBS is that they offer a way to represent arbitrary shapes while maintaining mathematical exactness and resolution independence. Among their useful properties are the following:

 

  • Probably the most important reason is that they are invariant under perspective transformations of the control points.
  • They can represent virtually any desired shape, from a point to straight lines 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, knots and weights, 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. An example: approximating a circle 1 meter in diameter with a sequence of point-to-point 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 NURBS representation takes as little as seven control points! This is the same idea as the G02/G03 circular interpolation that is in all controls. A few lines of code to define the size and shape can go a long way. This is where interpolation rate becomes important and we will discuss this later.

Before we go into the specifics of NURBS, let’s review some of the basics of curve representation in general. Although NURBS Interpolation supports three-dimensional NURBS, we’ll limit our examples and discussions here to two dimensions. But everything we say about two-dimensional NURBS applies in three dimensions as well — the two-dimensional versions are just easier to visualize and easier to draw.

History of NURBS

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. Yes, I know this might seem like the stone age to some, but we actually accomplished quite a bit using these seemingly ancient yet effective methods. These tools included rulers and T-squares for drawing straight lines, compasses for drawing circles and triangles and protractors for making precise angles.

Of course, a lot of interesting-shaped objects could not be drawn with just these simple tools, because they had curved parts that were not 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 nearly impossible. Because of their great size, such drawings were often done in the loft areas 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 or metal, called SPLINES. This spline was warped into a smooth curve passing through specified points by attaching suitable numbers of weights, called ducks. The spline assumed the shape of minimal strain and, therefore, was both mechanically and visually pleasing.

Figure

Figure 1. A 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.

The 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

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 (and boring ) development of this idea into what are known as cubic spline curves, eventually leading to the theory of NURBS. Such explanations are interesting, but not very intuitive, so we will not go into that discussion here.

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 not loop back on themselves. Because of this we can make some nice smooth curves this way, there are a lot of interesting curves we can not make — not even something as simple as a circle.

An alternative method, and the one we will 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 point 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 point 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, which you can verify by plugging in some values of t between 0 and 2 and plotting the results.

Smoothness

One very important motivation for using NURBS is the ability to control smoothness. The NURBS model allows you to define curves with no kinks or sudden changes of direction (such as an computer monitor case, CPU housing or the cross section of an airfoil) or with precise control over where kinks and bends occur (like the sharp corners of a triangle, square or polygon).

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 point 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. This intuitive notion can be expressed in precise mathematical terms: Imagine an arrow that always points in the direction in which our hypothetical point 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 does not 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

Figure 3. Tangent (derivative) of a spline

Now look at the point marked Q(tB), where there is a visible kink in the curve. The direction vector just a tiny bit to the left of that point, Q’(tB- a), is wildly different from the one just a tiny bit to the right, Q’(tB+a). In fact, the direction vector jumps instantaneously from one direction to another at point Q(tB). Mathematically, this is called a discontinuity.

Many of you will hopefully recall from your 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 therefore, characterizes the curve’s degree of curvature, and so a C2-continuous curve is said to have curvature continuity. (WHEW!) We’ll come back to these important concepts after we’ve introduced NURBS themselves.

Applying It To NURBS

Now that we know how parametric functions work, let us see how we can use them to build up a definition for NURBS. 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 will 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

Figure 4. Plotting a parametric function

Control Points

One of the key characteristics of NURBS 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 a control polygon. (It would actually make more sense to call it a "control polyline," but the other is the conventional term.)

FigureFigure

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 (B7) moved a bit. Notice that the curve’s shape is not changed throughout its entire length, but only in a small area near the changed control point. This is a very desirable property, since it allows us to make localized changes by moving individual control points, without affecting the overall shape of the curve. Each control point influences the part of the curve nearest to it but has little or no effect on parts of the curve that are farther away.

One way to think about this is to consider how much influence each of the control points has over the path of our moving point at each instant of time. At any time t, the point will be a weighted average of all the control points, but with the control points closer to the point carrying more weight than those farther away. We can express this intuitive notion mathematically this way:

Formula

In other words, to find the position of the moving point at a particular time, add up the positions of all the control points (Bi) but vary the strength of each control point’s contribution over time (Ni,k(t)). We will explain the meaning of the subscript k shortly.

Basis Functions

The function Ni,k(t), which determines how strongly control point Bi influences the curve at time t, is called the basis function for that control point. In fact, the B in "B-splines" stands for "basis." The value of this function is a real number such as 0.5, so that a particular point Q(t) can be defined as, say, 25% of one control point’s position, plus 50% of another’s, plus 25% of yet a third’s. To complete our NURBS equation, we have to specify the basis function for each control point.

So how do we go about defining the basis functions? Remember that we want each region of the spline to be a local average of some small number of control points close to that region. When the moving point is far away from a given control point, that control point has little influence on it; as the point gets closer, the control point affects it more and more. Then the effect diminishes again as the point recedes past the control point.

Up to now, we have been using the words "near" and "far" in a rather vague way, but the time has come to pin them down more rigorously. Because we have defined our curve parametrically with respect to time, we can regard what we have been calling a "part" or "region" of the curve as a portion of the time interval the curve covers. For example, if our curve goes from time t = 0.0 to t = 10.0, we can specify a particular region as extending from, say, t = 3.3 to t = 7.5. So we can say, for instance, that a control point Bi is centered at time t = 5.0 and has an effect in the range from t = 3.3 to t = 7.5.

Figure 6 shows a typical example of what a basis function might look like: it has its maximum effect at some definite point in time and tapers off smoothly as it gets farther away from that point. If you were awake during your statistics course, you might recognize this as the familiar "bell curve" that we all learned to know and despise. The curve Ni,k(t) in the figure shows that control point Bi has its greatest effect (about 95%) at time t = 3.0 and tapers off to about 50% at t = 1.7 and t = 4.3.

Figure

Figure 6. Basis function for a control point

Since each control point has its own basis function, a spline with, say, five control points will have five such functions, each covering some region of the curve (that is, some interval of time). At time t = 2.3 in Figure 7, for example, control point B0 has a weight of about 0.2, B1 about 0.7, and B2 about 0.05. As t goes from 0.0 to 7.0, each control point’s effect on the shape of the curve is initially 0, increases gradually to a maximum, and then gradually tapers off again to 0 as we reach the end of its effective range.

Figure

Figure 7. Uniform basis functions for a set of control points

Knots

Notice that all of the basis functions in Figure 7 have exactly the same shape and cover equal intervals of time. In general, we would like to be able to vary the width of the intervals (so that some control points affect a larger region of the curve and others a smaller region) and the maximum height of the curves (so that some control points affect the shape of the curve more strongly than others). This is where the NU in NURBS comes from: it stands for Non-Uniform.

The solution is to define a series of points that partition the time into intervals, which we can then use in the basis functions to achieve the desired effects. By varying the relative lengths of the intervals, we can vary the amount of time each control point affects the point. The points demarcating the intervals are known as knots, and the ordered list of them is a knot vector (Figure 8). The knot vector for the basis functions shown in Figure 7 is {0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0}. This is an example of a uniform knot vector, which is why all the functions in the figure cover equal intervals of time. Figure 9 shows an example of a curve created with such a knot vector.

Figure

Figure 8. A knot vector

Figure

Figure 9. NURBS curve with uniform knot vector

If we change the knot vector to {0.0, 1.0, 2.0, 3.75, 4.0, 4.25, 6.0, 7.0}, we get a set of nonuniform basis functions like the ones shown in Figure 10, and a curve that looks like Figure 11 (using the same set of control points as in Figure 9). Notice that the basis functions N2,3(t) and N3,3(t), associated with control points B2 and B3, respectively, are taller and narrower than the others. If you compare Figures 9 and 11, you will see that the curve in Figure 11 is pulled more strongly toward control points B2 and B3 than the one in Figure 9. This is because the basis functions for these control points have a greater maximum value. Also, the curve rapidly approaches these control points and rapidly moves away: compare how tightly curved it is near these points, relative to the curve in Figure 9. This is a result of the narrower basis functions for these two control points: intuitively, our moving point has to traverse more space in relatively less time. Looking at the knot vector, you can see that the knot intervals for these two control points are narrower than the others — {3.75, 4.0} and {4.0, 4.25} — meaning that their effects on the curve are concentrated in shorter time intervals.

Figure

Figure 10. Non-Uniform basis functions for a set of control points

Figure

Figure 11. NURBS curve with non-uniform knot vector

Defining the Basis Functions

We are now ready to complete our definition of a NURBS curve by giving an exact specification of the basis functions. In some respects, we are free to use any sort of functions we would like, but by choosing them carefully, we can get certain desirable effects. The definitions we will be using are as follows:

Formula

where xi is the conventional notation for the ith knot in the knot vector.

This definition has a lot of stuff in it, and lots of subscripts — we are getting into the real theoretical aspects of NURBS here. Notice that the functions for higher values of the subscript k (called the order of the basis function) are built up recursively from those of lower orders. If k is the highest order of basis function we define, the resulting NURBS curve is said to be of order k or of degree k-1. At the very bottom of the hierarchy, the functions of order 1 are simply 1 if t is between the ith and (i+1)st knots, and 0 otherwise.

The specifics of this particular set of basis functions, and how they came to be this way, are beyond the scope of this article (and me); if you are interested in learning more, you will find all the detail you could possibly want (and then some) in An Introduction to Splines for Use in Computer Graphics and Geometric Modeling. However, we can at least mention a number of important characteristics that this choice of basis functions exhibits:

 

  • At any time t, the values of all the basis functions add up to exactly 1.
  • If all control points have positive weights, the curve is contained within a bounding region known as the convex hull.
  • At any time t, no more than k basis functions affect the curve, where k is the order of the curve.
  • A curve of order k is defined only where k of the basis functions are nonzero.

This last characteristic is of more than theoretical interest: a cubic (degree-3 or order-4) NURBS curve with a knot vector of, say, {0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0} only goes from t = 3.0 to t = 4.0! The rule is that the curve begins at the kth knot from the beginning of the knot vector and ends at the kth knot from the end.

KNOTS AND KINKS

I should point out here that non-uniform knot vectors are not really very useful for controlling the shape of a curve. In fact, moving control points around directly is not that useful ether. Instead, non-uniform knot vectors have two important uses:

 

  • You have probably noticed that all of our NURBS curves so far have had their endpoints just "floating in space"; that is, the curve’s endpoints don’t coincide with any control point. In real life, though, we generally want to be able to control the exact placement of the endpoints, and most often we want them to coincide exactly with the first and last control points.
  • You may also have noticed that the curves displayed so far are quite smooth. While this is usually a good thing, we sometimes need to create a curve with a kink or corner.

We can accomplish both of these goals by using a rather extreme case of non-uniformity: giving several consecutive knots the same value of t. For example, a knot vector like {0.0, 0.0, 0.0, 3.0, 4.0, 5.0, 6.0, 7.0} produces a set of basis functions like those in Figure 12 and a curve (using the same control points as before) that looks like Figure 13. Looking at Figure 12, you can see that at t = 0, the basis functions associated with all but the first control point have a 0 value — so basis function N0,3(t) (the one for control point B0) has total control over the curve. Thus the curve at t = 0 coincides with the first control point.

Figure

Figure 12. Basis functions for a curve with multiple identical knots at the beginning

Figure

Figure 13. NURBS curve with multiple identical knots at the beginning

If we bunch up some knots in the middle of the knot vector {0.0, 1.0, 2.0, 3.0, 3.0, 5.0, 6.0, 7.0}, we get the basis functions shown in Figure 14 and the curve in Figure 15. At t = 3.0, all the basis functions except N2,3(t) have a 0 value — so control point B2 is the only one to affect the curve at that instant, and thus the curve coincides with that control point.

Figure

Figure 14. Basis functions for a curve with multiple identical knots in the middle

Figure

Figure 15. NURBS curve with multiple identical knots in the middle

In mathematical terms, continuity (smoothness) is an issue only at the joints defined by the curve’s knots, where two segments of the curve meet; between the joints, the curve is perfectly smooth and continuous. A typical curve, in which each joint corresponds to a single knot, has continuity Cn-1 where n is the degree of the curve. So a cubic (degree-3 or order-4) curve has second-derivative continuity (C2) at each joint if all the knots are distinct. If two knots coincide, the continuity at that joint goes down by one degree; if three coincide, the continuity goes down another degree; and so on.

This means you can put a kink in the curve at a particular point by adding knots to the knot vector at that point.

Rational Curves

Now that we have learned all about control points and knots and basis functions, we understand NUB (Non-Uniform B-spline) curves. But what about the rest of the acronym? We’re still missing the R in NURBS. It is time to talk about rational curves.

If you have seen CAD/CAM NURBS definitions, you may have wondered why it uses a four-dimensional representation for three-dimensional control points: {x, y, z, w} instead of just {x, y, z}. The reason for the extra coordinate is that it allows us to exactly represent conic curves (circles, ellipses, parabolas, and hyperbolas), as well as giving us more control over the shape of other curves. The fourth coordinate, w, is customarily referred to as the weight of the control point. Ordinarily, each control point carries a weight of 1.0, meaning that they all have equal influence on the shape of the curve. Increasing the weight of an individual control point gives it more influence and has the effect of "pulling" the curve toward that point (see Figure 16).

Figure

Figure 16. Increasing the weight of a control point

Curves that are defined in this way, with a weight w for each control point, are called rational curves. Mathematically, such curves are defined in four-dimensional space (since the control points have four components) and are projected down into three-dimensional space. Visualizing objects in four dimensions is a bit difficult (let alone drawing them in a diagram), but we can understand the basic idea by considering rational two-dimensional curves: that is, curves defined in three-dimensional space and projected onto a plane, as shown in Figure 17.

Figure

Figure 17. Projecting a three-dimensional curve into two dimensions

This is essentially the same process as projecting a three-dimensional model onto a two-dimensional screen with perspective. The basic method for such perspective projection is to divide by the homogeneous component of the vertex (that is, w); we use an analogous approach to project our four-dimensional rational curve into three-dimensional space. Mathematically, then, we must incorporate this division into our earlier definition for a B-spline curve:

Formula

The Bi are the projections of the four-dimensional control points and the wi are their weights.

There are two different conventions for representing the control points in terms of their four-dimensional coordinates {x, y, z, w}:

 

  • Homogeneous, in which the coordinates represent the point’s position in four-dimensional space. To project it into three dimensions, the components must all be divided through by w. Therefore, the point’s three-dimensional position is actually {x/w, y/w, z/w}. (Note that w/w is always 1.)
  • Weighted Euclidean, in which the coordinates are already considered to have been divided through. Thus the first three components {x, y, z} directly represent the point’s position in three-dimensional space and the fourth (w) represents its weight.

Knot Insertion

In general, the more control points we define for a NURBS curve, the more control we have over its shape. It would seem reasonable that we could add more control points without changing the shape of the curve, and in fact this turns out to be true. Remember, though, that there is a fundamental relationship among the knots, the control points, and the order of the curve: the number of knots is equal to the number of control points plus the order. For example, a cubic curve (order 4) with 9 control points will require 13 knots. So every time we add a control point, we also have to add an extra knot — and make sure all the control points are in the correct locations to keep the curve’s shape the same as before.

In practice, we actually take the reverse approach: we decide where to add a new knot, then compute the location of the corresponding new control point (as well as the new locations of some of the existing ones). For example, if we take the curve depicted earlier in Figure 9 and insert a new knot at t = 3.6, we get a new curve with exactly the same shape but with a new set of control points (Figure 18).

Figure

Figure 18. Inserting a knot

This operation of knot insertion is a fundamental one in working with NURBS curves. It is directly useful in both modifying and rendering curves.

NURBS Interpolation

Enough theory already — what does this have to do with programming for the machine. Let’s look at some data structures for working with NURBS.

Some General Rules

Most of this is pretty straightforward, but here are a few things to keep in mind:

  • The order of the curve must be between 2 and 16, inclusive. Order 2 gives you a polyline effect; the most common orders are 3 (quadratic) and 4 (cubic).
  • The control points are represented in homogeneous form, meaning that you have to divide the x, y, and z components by the w component to find the point’s actual position in three-dimensional space.
  • The w component of each control point must be positive.
  • The number of control points must be equal to or greater than the order.
  • The number of knots must be equal to the number of control points plus the order of the curve.
  • The knots must be specified in non-de