from SIAM News 29(5) June 1996

B-Splines and Geometric Design

Paul Davis, Worcester Polytechnic Institute

The morphing of Arnold Schwarzenegger's adversary into the various forms he takes on in Terminator 2 is really a bit of mathematical magic: It is B-splines that drive the sophisticated computer graphics. B-splines are also responsible for the slower but economically more important transformation that has brought geometric design from the era of clay models and hand measurements to megaflop computation and three-dimensional renderings on desktop computers. Whenever free-form curves and surfaces are represented mathematically, as they are in computer-aided design, analysis, and manufacturing, B-splines are the foundation of an efficient implementation.

B-splines are especially important in the aircraft and automotive industries, where shape is all important. Asking about the impact of B-splines in geometric design, says Ray Sarraga of General Motors Research, "is like asking 'What is the impact of the gasoline engine in the use of cars?'" Tom Grandine of The Boeing Company adds, "No plane leaves Boeing without many billions of B-spline evaluations behind it. Splines demonstrate some of the good things that happen when you get the math right!"

From the Designer's Vision To the Production Line

Until recently, designers in the automotive industry did their dreaming in clay. To transfer the shapes envisioned by the designers to the dies used to stamp body panels for a new car, full-sized clay models were painstakingly measured along hundreds of profiles.

The polygonal shapes outlined by measurements made along individual profiles were too rough for production. Connecting the measured points with a long, flexible ruler---a drafting spline---smoothed the profiles sufficiently for use in the construction of stamping dies. This process of hand lofting was slow and expensive, especially for complex shapes like automobiles and aircraft. And it left undone the work of blending adjacent profiles into a smooth surface.

Today, B-splines enable mathematical representations of surfaces that are far beyond the range of hand techniques. At Boeing, computations involving 30--50,000 data points are routine. Imagine measuring, plotting, and smoothing 50,000 data points by hand!

And spline-based computations in the aircraft industry go far beyond geometric design. Dave Ferguson of Boeing Computer Services describes the new electronic replacements for the flight manuals in the Boeing 777: "Flight test data like take-off distance as a function of temperature, altitude, weight, and many other variables used to be stored in a succession of look-up tables in a bulky flight manual. Now the 777 pilot enters the flight parameters into a computer, and a spline-based interpolation of that multivariate function immediately returns the take-off distance. The look-up process has been completely abandoned."

Another important application of splines at Boeing is in the computation of optimal orbit and flight trajectories. The continuous variables representing the physics of the vehicle and the control mechanisms---flaps and thrusters, for example---are replaced by spline approximations. The problem variables are then the discrete set of spline coefficients.

The Beginnings of Computer-Aided Design

"The decision to use computers in the design process forces the designer to describe all shapes in mathematical terms," explains Gerald Farin of Arizona State University. The mathematical representation of curves and surfaces is the crux of the transition from hand lofting to computer-aided design.

The first attempts in the late 1950s to use computers replaced the drafting spline with polynomial interpolation. Interpolating through lots of points called for polynomials of high order, and, as every sophomore numerical analyst knows, high-order polynomials often wiggle rather than smooth.

To banish the wiggles, the early practitioners of computer-aided design switched to piecewise interpolation, typically using polynomials or conics: de Casteljau at Citroen, Be/zier at Renault, Birkhoff and Garabedian at General Motors, J. Ferguson at Boeing, and many others. (Be/zier's work also found its way into typography: Scalable fonts like PostScript are stored as piecewise cubic Be/zier curves.) But two fundamental questions could not be laid to rest: Is there a relatively easy way to control behavior---slope, curvature, and so forth---where two polynomial pieces meet? How can the polynomial pieces between interpolation points be efficiently evaluated, as repeatedly required in design, analysis, and manufacturing?

Basis Splines

To answer questions about representation, a natural approach is to look for a basis, a small set of fundamental building blocks from which every desired instance can be constructed. If the recipe for combining the basis functions is flexible but robust, then they can be blended to achieve a representation with the desired smoothness properties. If the basis functions can be evaluated quickly, the same will be true for representations built from them.

In 1946, Schoenberg had introduced such a basis for piecewise polynomials, the B-splines ("B" for "basis"). But neither their computational power nor their geometric flexibility was appreciated (or needed) at the time. Schoenberg derived his B-splines by forming divided differences (difference quotients of progressively higher order) of truncated power functions that were defined in terms of a sequence of knot points rather than interpolation points.

Surprisingly, these strange creatures could be combined to form functions that were even smoother than their component parts. Unfortunately, the divided difference process that defines them is a fundamentally unstable numerical process. According to Ferguson, "Nobody used B-splines because nobody knew how to compute with them, even in the late 1960's."

Recursion

Carl de Boor of the University of Wisconsin, Madison, who will be giving The John von Neumann Lecture at the 1996 SIAM Annual Meeting in Kansas City, put B-splines on the road to computational fame and fortune with his 1972 paper describing a recursion formula for evaluating them. The formula is simple and stable: A convex combination of two lower-order B-splines gives the value of the next one. The recursion is stable because it combines positive terms. There is no subtraction, no danger of introducing catastrophic cancellation from a finite-precision calculation of the difference of two nearly equal numbers.

De Boor came by his interest in splines quite naturally. After a year of graduate work at Harvard in the early 1960s, he joined the mathematics group at GM Research. Garrett Birkhoff (another von Neumann lecturer), who was then a consultant to GM, helped de Boor get the job. One of de Boor's first contributions was to introduce the use of tensor products of splines for surface interpolation, an idea that remained in place for many years at GM for the manufacture of dies.

De Boor left GM to complete his PhD at the University of Michigan; for his dissertation he used B-splines for what are now known as projection methods---collocation and Galerkin methods, for example---for linear, second-order boundary-value problems. The combination of differential equations and splines, he says, grew out of his association in Europe with Collatz and his experience at GM with piecewise polynomials. His thesis was never published because he discovered similar ideas in the Russian literature. "In hindsight," he says, "I should have published it. The only examples in the Russian work use polynomials, a poor choice for general boundary-value problems."

After joining the faculty at Purdue, de Boor's interests seemed to veer away from geometric design. In 1970 he was trying to prove the stability of least squares approximation using splines. Like most of his work at that time, this attack was based on B-splines; he points out, however, that "we only understood them at that point as divided differences." Since he was trying to use mathematical induction on the degree of the approximation to prove the stability conjecture, it seemed natural to look for a relation connecting B-splines of a given order with those of the next higher order.

It was only several months later, while preparing a general talk on splines, that he recognized the value of the simple B-spline recurrence relation---because the recursion weights are positive on the interval of interest, it is the perfect tool for the practical, stable evaluation of B-splines. M. Cox and others made similar discoveries at about the same time, but de Boor's work may have had the widest reverberations because of his emphasis on computational implementation.

A Practical Guide to Splines

De Boor's A Practical Guide to Splines became a bible of sorts in the geometric design community. It contained all the essential theory, clearly and carefully explained. (In an early chapter, de Boor spelled out his intentions: "We will record various properties of the B-spline, in hopes of making it thereby as familiar and real an object for the reader as, say, the sine function.") And it provided Fortran subroutines for evaluating B-splines and applying them to a variety of problems. The Practical Guide packaged theory and practice in one accessible volume. Indeed, the pppack code from the Practical Guide continues to be a popular listing on netlib.

The snowball that built up around B-splines had other contributors as well. Cohen, Lyche, and Riesenfeld developed the so-called Oslo algorithm that facilitated the use of B-splines and caused a considerable stir in the geometric design community. Boehm then showed that de Boor's recursion scheme had essentially the same power in spite of its simplicity.

Numerical Linear Algebra

The use of B-splines in geometric design was encouraged by the nearly simultaneous development of modern numerical linear algebra. In the 1940s and 1950s, designers avoided numerical linear algebra at all costs, even when mechanical calculators were available. For example, the author of the World War II volume Practical Analytic Geometry with Applications to Aircraft Design puts aside the problem of solving five simultaneous equations as if he had been asked to square the circle.

Unhappily for those with an aversion to solving linear equations, linear algebra must be used to find the appropriate coefficients for many mathematical representations of curves and surfaces. Brute-force approaches to interpolation lead to systems of equations that are poorly conditioned---the solution is swamped by the round-off error inherent in the computer's finite-precision arithmetic.

Fortunately, B-splines lead to relatively well conditioned equations, ones that respond well to the techniques of numerical linear algebra. Furthermore, because each B-spline is zero on all but a minimal interval, those systems are relatively sparse and efficient to store in memory.

In his Practical Guide, de Boor gave B-splines yet another advantage by demonstrating robust techniques for converting between piecewise polynomial representations of functions and the B-spline representation. Consequently, even geometric representation techniques that had not been formulated with splines could have B-splines as their robust, efficient computational foundation. Designers, then, may not see B-splines---they may manipulate a handle on the end of curve to control its curvature instead---but B-splines are likely to be the hidden bearings on which the design engine runs.

B-splines are not the only available tool for geometric design. But Bill Frey of GM Research makes a convincing case for their importance: "If the process is based on mathematics and if it uses curves or surfaces, then splines are indispensable. If the representation isn't piecewise, then it isn't flexible enough for complex geometries."

When asked about his sense of satisfaction for his role in the B-spline revolution in geometric design, de Boor replies, "Of course, Schoenberg created B-splines. Things that I thought were good about them were not clearly understood at first. But now they are seen as obvious, and I am pleased to have helped bring that about."

========================

Sidebar: De Boor, Splines, Schoenberg, and SIAM

Carl de Boor will touch some of these ideas when he delivers the 1996 von Neumann lecture at the SIAM Annual Meeting in Kansas City.

Much of the software described in de Boor's A Practical Guide to Splines first appeared in the open literature in the paper "Package for calculating with B-splines" in SIAM Journal on Numerical Analysis, 14(1977), p. vii, 143.

I.J. Schoenberg provides a concise exposition of the basis properties of B-splines in his 1973 CMBS monograph Cardinal Spine Interpolation, published by SIAM. It begins with a delightful quotation from Phil Davis: "Spline approximation contains the delicious paradox of Prokofieff's Classical Symphony: it seems as though it might have been written several centuries ago, but of course it could not have been."

SIAM has published many other volumes related to splines and geometric design. Authors or editors include Barnhill, Chui, Farin, Gardner, Goldman, Hagen, Lyche, Micchelli, Sapidis, and Wahba.

SIAM's Geometric Design Activity Group meets every two years in the fall; the next meeting will be in October of 1997 in Nashville, TN.