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.

- Convert the boundary curves from NURBS to RPWPB form
- Express the ruled surfaces and the bilinearly-blended surface in RPWPB form.
- Add together the ruled surfaces and subtract the bilinearly-blended surface, expressing the result (which is the Coons patch) in RPWPB form.
- 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.

- Its
**degree**.*(the highest exponent that would appear if the curve were written in piecewise power basis form)* - Its
**breakpoints**.*(the set of parameter values at which we switch from one polynomial to another)* - 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)* - Its
**evaluator***(we need to be able to evaluate the position and all derivatives of the curve at any parameter value in its domain)*

**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.