The NURBS Representation Problem

How to Express Procedural Surfaces in NURBS Form

The NURBS Representation Problem

A Case History
By Richard Fuhr 

Purpose

The purpose of this writeup is to describe how The NURBS Representation Problem led to a useful and interesting application that arose in geometric modeling.

I have tried to keep the technical level moderate, and more details on our approach appear in the article "An Object-Oriented Paradigm for NURBS Curve and Surface Design", written with Lwo Hsieh and Michael Kallay, which appeared in Volume 27 Number 2 (February 1995) of the journal Computer-Aided Design.

Background

In 1980 I started working on the TIGER project, a Boeing research and development project in Computer-Aided Design (CAD). The purpose of our work was to develop a prototype CAD system that would implement some new ideas that might also find their way into software provided by Boeing's CAD vendors.

We recognized that in a well-designed CAD system, the geometric entities, including curves, surfaces, and solids, should have internal representations in the computer that:

  • are able to represent most commonly-encountered shapes compactly and accurately
  • are easy to evaluate
  • are easy to transform

To this end, we selected, as the internal form for the TIGER system, the Non-Uniform Rational B-Spline form (also known as NURBS) .

Without going in to a lot of detail here, suffice it to say that the NURBS form represents curves and surfaces as fractions, in which the numerators are 3D-valued splines and the denominators are real-valued splines. A spline is just a function that is made up of polynomials joined together in a more-or-less smooth manner.

For example, one of the simplest splines is the function f(x) = |x|, which is made up of the two polynomials f(x) = -x when x < 0 and f(x) = x when x >= 0. In this example, the two polynomial pieces do not join up smoothly at x = 0; in fact the first derivative is discontinuous there. More typically, splines that occur in practical applications are piecewise polynomials of degree 3, and usually they are constructed so that their first and second derivatives are continuous everywhere.

Splines are a useful form for the representation of curves and surfaces. Since splines are formed by piecing together polynomials, one can represent, or closely approximate, many entities without the need to use high-degree polynomials. Just as polynomials can be expressed in terms of a simple set of basis functions (the power basis 1, x, x^2, x^3, ...) so also can splines be expressed in terms of a simple basis known as the B-spline basis. When we use ratios of spline functions to get NURBS, the set of entities that we can represent grows enormously, and includes such items as conic curves and quadric surfaces.

Not only did we successfully use the NURBS form in the TIGER system, but we led the effort to have NURBS curve and surface representations added to the collection of entities that comprise the ANSI-standard IGES specification for the exchange of geometry data between different CAD systems. In turn, the presence of the NURBS standard in IGES (and STEP, the successor to IGES as an exchange specification) encouraged the use of NURBS technology in a myriad of CAD systems.

Over the years, TIGER evolved into Axxyz, a system that Boeing had considered using for the design of its new airplanes. Boeing had also considered marketing the system to other companies that were heavy users of CAD/CAM. In 1988 Boeing decided to use the CATIA system to design the new 777 and the Axxyz software and people moved on to EDS. During the time that TIGER, Axxyz, and its EDS descendants were under development, there were many interesting technical challenges.

Coons Patches

For instance, as requirements for the system grew, among them was the need to represent a wider variety of curves and surfaces using the NURBS form. One of the surfaces that presented a challenge was the Coons Patch , a surface that looks like a deformed rectangle, bounded by four arbitrary curves that met at the corners.

The most straightforward analytic description of a Coons Patch is to express it as a combination of the four boundary curves; call them Top, Bottom, Left,and Right. In what follows, we are not so much interested in the specific formula; we just want to point out that there is a formula, and then we shall return to the task at hand, namely finding a NURBS representation for the Coons Patch, assuming that the four boundary curves are already in NURBS form.

We can assume that all four curves are parameterized on [0,1]. Also assume

Top intersects Left at the point TL,

Top intersects Right at the point TR,

Bottom intersects Left at the point BL,

Bottom intersects Right at the point BR,

Then the Coons patch S(u,v) can be expressed as follows

S(u,v) = (1-u)*Left(v) +(u)*Right(v) +(1-v)*Bottom(u) +(v)*Top(u)

-{ (1-u)(v)*TL + (u)(v)*TR + (1-v)(u)*BR + (1-v)(1-u)*BL }

The above formula, while a bit daunting looking, says that a Coons patch can be constructed by adding together the ruled surface between the Left and Right curves and the ruled surface between the Bottom and Top curves and then subtracting off a surface formed by bilinear blending of the four corner points.

So, before we get too lost in the specific details of this case, suffice it to say that the problem we are faced with is to represent the above algebraic combination of NURBS curves and points as a NURBS surface.

Representing Coons Patches as NURBS

1. NURBS Representation Using Power Basis as Intermediary

When I first tackled the NURBS representation problem, I took the path of least resistance. I already had written code to convert curves and surfaces back and forth between the NURBS form and the rational piecewise power basis form ( RPWPB). Moreover, it was easy to write code to represent algebraic combinations of RPWPB entities in RPWPB form. So I combined these ingredients to get a NURBS representation of a Coons patch as follows.
  1. Convert the boundary curves from NURBS to RPWPB form
  2. Express the ruled surfaces and the bilinearly-blended surface in RPWPB form.
  3. Add together the ruled surfaces and subtract the bilinearly-blended surface, expressing the result (which is the Coons patch) in RPWPB form.
  4. Convert the RPWPB representation of the Coons patch to a NURBS representation.

2. NURBS Representation Using Dual Basis Functionals

While the above method worked, I realized that it was not necessary to convert the NURBS entities to RPWPB form, if I would just learn to take better advantage of the B in B-spline.

Any polynomial spline curve C can be written as a linear combination of appropriate B-spline basis functions b[i] as follows

C(t) = P[0]b[0](t) + P[1]b[1](t) + ... + P[n]b[n](t)

where the P[i] are 3D points, known as the B-spline coefficients of the curve.

Similarly, any rational spline curve and any polynomial or rational spline surface can be written as a linear combination of such basis functions. In the rational case, we can view the B-spline coefficients as 4D points.

Our challenge is to find the B-spline coefficients for the Coons patch, given that we somehow know what the B-spline basis functions are.

For simplicity of illustration, we will outline the approach for finding the B-spline coefficients of a polynomial spline curve C; a similar approach applies to rational spline curves, polynomial and rational spline surfaces.

In order to do this, we need to know the following about the spline to be represented.

  1. Its degree. (the highest exponent that would appear if the curve were written in piecewise power basis form)
  2. Its breakpoints. (the set of parameter values at which we switch from one polynomial to another)
  3. Its level of derivative continuity at the breakpoints. (when we switch from one polynomial to another at a breakpoint, how many of the derivatives from the left and from the right agree)
  4. Its evaluator (we need to be able to evaluate the position and all derivatives of the curve at any parameter value in its domain)
Equipped with the above information, we can constructively define a set of dual basis functionals L[0],..., L[n], i.e., linear operators that operate on the set of all splines determined by the above information, that satisfy L[i](b[j]) = 1 if i = j, and = 0 otherwise. These L[i] are often known as the deBoor-Fix Functionals and are discussed in deBoor's book "A Practical Guide to Splines".

Because of the linearity of the L[i], we can use them to extract the B-spline coefficients of the polynomial spline curve C; i.e., L[i](C) = P[i].

Extensions of this approach can be used to extract the B-spline coefficients of rational spline curves as well as polynomial and rational spline surfaces. Thus, we can use deBoor-Fix Functionals to find the NURBS representation of a Coons patch, as well as of many other curve and surface entities.

In the rational case, the evaluator that needs to be supplied must allow you to get at the numerator and denominator of the expression separately. Thus, if you have a curve of the form

C(t) = N(t)/w(t)

where N(t) = (x(t), y(t), z(t))

then you must provide the 4D-valued homogeneous evaluator H

where H(t) = (x(t), y(t), z(t), w(t))

Similar considerations hold when working with rational surfaces. In particular, if you want to represent a rational surface that is defined in terms of rational curves (e.g., a Coons Patch), you need to provide a homogeneous evaluator for the surface. This typically requires that you must have access to homogeneous evaluators for the defining curves.

3. NURBS Representation Using Systems of Linear Equations

While the deBoor-Fix Functionals worked well for finding the NURBS representations for a wide variety of curves and surfaces, there was one disadvantage to this approach. The formula for the functionals L[i] required that an evaluator be supplied that could evaluate all derivatives (and in the case of surfaces, all mixed-partial derivatives). While this posed some interesting technical challenges, it slowed down the process of constructing new NURBS curves and surfaces.

My colleague, Michael Kallay realized this and replaced this approach with one that found the B-spline coefficients by setting up and solving a system of linear equations. Because of the way that we had designed the software, it was possible to unplug the deBoor-Fix machine and plug in the linear algebra machine very quickly with very little disruption to the overall scheme of things.

One of the more interesting applications of this scheme was carried out by my colleague Lwo Hsieh, who used the approach to construct smooth extensions of NURBS surfaces across a boundary.

Conclusion

I hope that I have conveyed something of the flavor of this effort. It was a nice combination of technical challenges, teamwork, and the unreasonable effectiveness of mathematics. If you would like to discuss any of this at greater length, please send me email.