Exercise for the Reader

November 1, 2009

The B-spline Series: Motivation

Filed under: 3D Graphics — Seth Porter @ 3:51 pm

The B-Spline family of curves are a nice way to make smooth curves from a series of control points. The idea is that the control points give you “handles” to pull the curve around; it won’t actually pass through any of them (except for the first and last ones), but it will be attracted to them while retaining some nice smoothness properties.

That much I knew coming in. For various reasons, I wanted to write a program to evaluate B-splines, with a particular eye to rendering them in 3D. This seemed like it was going to be a very easy task; instead, I learned a lot along the way.

A Motivation for B-Splines

Ignoring the math for a moment, let’s talk about the basic idea of B-splines. There are quite a few ways to fit a smooth (roughly meaning “at least twice differentiable, and with at least the first derivative being continuous across the function) curves to a set of control points. (And in fact there are a lot more if the curve doesn’t even have to pass through the control points!)

The simplest approach is to observe that you can always fit a quadratic (degree = 2) polynomial to any three points, or a cubic (degree = 3) to any four points, and so forth. I don’t think anyone uses this approach in serious modelling or drawing software, but it’s kind of the benchmark against which other approaches can be compared. One key benefit, which I’ll discuss below, is that this approach gives you a single function across the entire length of the curve, making them naturally uniform. There are a few problems, however:

  • They get uglier as you have more and more control points, since the degree of the polynomial rises along with the control point count
  • More fatally, they wiggle. This is most easily seen in a picture:

 

pts : [[0, 0], [1, 3], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0]]; load(interpol); plot2d([[discrete,pts], lagrange(pts)], [x, 0, 6.1], [style, [points, 1], [lines]], [legend, false]);

Polynomial interpolation demonstrating "wiggle"

Notice how the curve repeatedly dips below the y=0 line, even though the control points are strictly non-negative. (It also overshoots at the top, going up into y=4 territory before hitting the (1, 2) point on the downstroke.) These would be annoying enough, but the worst part is that it never becomes a straight line, even when fed 5 linear control points. This makes simple polynomial interpolation pretty much useless for industrial design: imagine if your mouse had ripples all through its surface, simply because of a stylishly sharp curve at the nose. Even worse, the direction of the wiggles can actually flip in response to relatively small changes in the control points!

 

A much better family of functions (for geometric modeling purposes) are the Bézier curves. These very useful curves are used in many drawing programs. These curves don’t actually go through the control points, except for the first and last ones, but instead use the control points as “handles” (you can think of them as pulling the curve toward them with springs, rather than having the curve attached to them). Bézier curves exhibit the “convex hull property”, meaning (casually) that if you draw lines connecting the control points, the curve will be contained within those lines. In other words, they don’t have the overshoot problems of simple polynomial interpolation. The fact that they don’t go through the control points is disconcerting at first, but isn’t fundamentally a problem for many design and modeling tasks.

Here’s a Bézier curve through the same control points:

 

Bezier(i, n, u) := binomial(n, i) * u^i * (1-u)^(n-i); BCurve(P, n, u) := sum(P[i+1]*Bezier(i, n, u), i, 0, n); plot2d([[discrete,pts], [parametric, BCurve(pts, 6, u)[1], BCurve(pts, 6, u)[2], [u, 0.001, 1], [nticks, 80]]], [x, 0, 6.1], [style, [points, 1], [lines]], [legend, false]);

A Bézier curve through the same control points

Notice that this curve is much more restrained; it doesn’t come close to the (1, 3) control point, but it doesn’t overshoot or wiggle. This is a curve you could use to design a mouse. There is still one key problem, however: if you move one of the control points, the entire shape of the curve will be affected. To see why this is a problem, imagine that you’ve got the mouse almost perfect. The shape fits perfectly in your hand, is big enough to hold the electronics — everything’s done except that one VP decides that the stylish sharp curve at the end is perhaps a bit too sharp. You adjust the control points slightly and the VP is happy. But now, the entire rest of the shape has changed — maybe you don’t have enough clearance for the electronics, maybe the hand-rest isn’t quite as comfortable. Of course you can go and change those control points, too, but each time you touch something, everything changes. This is known in the trade as global propagation of local changes. As a result, Bézier curves are perhaps best suited for freehand work.

 

By now you can probably guess what the nice properties of B-splines are. They act a lot like Bézier curves, having the convex hull property and interpolating only the first and last control points, with the key difference that a change to a control point will only change a limited portion of the curve. To accomplish this trick, B-splines are made up of a number of separate curve segments, rather than a single high-degree polynomial. These segments are cleverly constructed so that when they meet, both segments are curving the same way (their first derivatives are the same). In fact, B-splines have an extra parameter, k, which controls both the polynomial degree of these segments and how continuous they are when they meet (how many derivatives are equal at the intersection point). In common usage, k is 3 or 4, leading to either quadratic or cubic curve segments. (Lower values of k aren’t “curves” in the common sense; k=2 produces straight lines connecting the control points, and k=1 is the disjoint set of control points, not connected at all. Higher k values lead to a “stiffer” spline, as the requirement of equal second and third and fourth derivatives forces the curve closer and closer to a straight line.)

As an example, here’s a k=3 B-spline (each segment is a quadratic curve) through the same control points as the curves above. As before, the control points are shown as blue circles. Additionally, the segments are each drawn in different colors, and the boundaries between segments are marked by red squares:

 

pts2 : [[0, 0], [1, 3], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0]]; mySegments7 : makelist(at(basis_indep_spline3(P, seg, u), [P[0]=2*P[0]-P[1], P[7]=2*P[7]-P[6]]), seg, 1, 6); accumX : mySegments7; for idx : 0 step 1 thru 7 do accumX : subst(pts2[idx+1][1], P[idx], accumX); accumY : mySegments7; for idx : 0 step 1 thru 7 do accumY : subst(pts2[idx+1][2], P[idx], accumY); makePlotList(u0, u1) := makelist([parametric, accumX[i], accumY[i], [u, u0, u1]], i, 1, 6); plot2d(append([[discrete, pts2]], makePlotList(0, 1),   [[discrete, makelist([at(accumX[i], u=1), at(accumY[i], u=1)], i, 1, 6)]]),      [x, -1, 6.1], [y, -0.2, 3.2],     [style, [points, 1],      [lines], [lines], [lines], [lines], [lines], [lines],     [points, 1,2,6]],     [legend, false]);

A k=3 B-spline curve through the same control points

To make things a little clearer (perhaps), here’s the same curve with each segment drawn from u=-0.1 to u=1.1. This “overdraw” demonstrates how each segment really is a parabola, carefully chosen so that the slopes are momentarily equal at the point where the segments meet:

 

B-spline Example with Segment Overdraw

B-spline Curve with segments rendered from u=-0.1 to u=1.1

Notice that we have the nice non-wiggling behavior of the Bézier curve, combined with a much narrower range of influence for each control point. The control points only influence nearby segments, meaning that this curve “flattens out” much more quickly than the Bézier version.

Advertisements

2 Comments »

  1. […] — sketch141421 @ 4:24 pm This is the second part of a so-far three part series. See part one for some […]

    Pingback by The B-spline Series: Definitions (Abridged) « Exercise for the Reader — November 1, 2009 @ 11:00 pm

  2. […] Seth Porter @ 9:13 pm In the previous three parts of this series, we’d sorted out why B-splines are interesting curves, attempted to sort out B-splines terminology, and decided that it would be really nice to be able […]

    Pingback by B-Splines: Better Math « Exercise for the Reader — December 5, 2009 @ 9:14 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: