The NURBS Book

The two most common methods of representing curves and surfaces in geometric modeling are implicit equations and parametric functions.

Curves consisting of just one polynomial or rational segment are often inadequate. Their shortcomings are:

In this chapter we define nonrational B-spline curves and surfaces, study their properties, and derive expressions for their derivatives. For brevity we drop the word nonrational for the remainder of this chapter. The primary goal is to acquire an intuitive understanding of B-spline curves and surfaces, and to that end the reader should carefully study the many examples and figures given in this chapter. We also give algorithms for computing points and derivatives on B-spline curves and surfaces. The use of B-splines to define curves and surfaces for computer-aided geometric design was first proposed by Gordon and Riesenfeld [Gord74b; Ries73]. B-spline techniques are now covered in many books on curves and surfaces — see [DeBo78; Mort85; Bart87; Fari93; Yama88; Hosc93; Su89; Roge90; Beac91].

In this chapter we combine the concepts of Sections 1.4 and 1.5 of Chapter 1 and those of Chapter 3 to obtain NonUniform Rational B-Spline (NURBS) curves and surfaces. We present definitions and general properties and derive formulas and algorithms for the derivatives of NURBS curves and surfaces in terms of their nonrational counterparts. The earliest published works on NURBS are [Vers75; Till83]. A more recent survey can be found in [Pieg91a].

In this chapter we present five tools which axe fundamental in the implementation of B-spline curves and surfaces; these are knot insertion, knot refinement, knot removal, degree elevation, and degree reduction. We devote a section to each topic, and the layout of each section is roughly:

In this chapter we cover various topics which are rather fundamental in implementing NURBS geometry.

The conic sections and circles play a fundamental role in CADCAM applications. Undoubtedly one of the greatest advantages of NURBS is their capability of precisely representing conic sections and circles, as well as free-form curves and surfaces. We assume a knowledge of conics and circles; the purpose of this chapter is to study them in the framework of their representation as NURBS curves. In Section 7.2 we review various forms and properties of conics which are required in subsequent sections. Section 7.3 covers the quadratic rational Bézier representation of conic and circular arcs; Section 7.4 introduces infinite control points. In Sections 7.5 and 7.6 we present algorithms for constructing the NURBS representation of arbitrary circles and conics, respectively, including full circles and ellipses. Section 7.7 covers conversions between the various representation forms, and Section 7.8 gives examples of higher order circle representations.

Sections 2 through 5 of this chapter cover the NURBS representation of the four surface types: bilinear surfaces, general cylinders (extruded surfaces), ruled surfaces, and surfaces of revolution. As the reader surely realizes by now, these representations are not unique. Considerations such as parameterization, convex hull, continuity, software design, application area, data exchange, and even personal taste can influence the choice of representation method. Our presentation closely follows the constructions given by Piegl and Tiller [Pieg87a]. Section 6 uses nonuniform scaling to obtain additional surfaces such as the ellipsoid and elliptic paraboloid. Section 7 presents a method for constructing a three-sided patch on a sphere, whose boundary curves are circles whose radii are equal to the radius of the sphere. This patch is useful as a corner fillet surface.

In Chapters 7 and 8 we showed how to construct NURBS representations of common and relatively simple curves and surfaces such as circles, conics, cylinders, surfaces of revolution, etc. These entities can be specified with only a few data items, e.g., center point, height, radius, axis of revolution, etc. Moreover, the few data items uniquely specify the geometric entity. In this chapter we enter the realm of free-form (or sculptured) curves and surfaces. We study fitting, i.e., the construction of NURBS curves and surfaces which fit a rather arbitrary set of geometric data, such as points and derivative vectors. We distinguish two types of fitting, interpolation and approximation. In interpolation we construct a curve or surface which satisfies the given data precisely, e.g., the curve passes through the given points and assumes the given derivatives at the prescribed points. Figure 9.1 shows a curve interpolating five points and the first derivative vectors at the endpoints. In approximation, we construct curves and surfaces which do not necessarily satisfy the given data precisely, but only approximately. In some applications — such as generation of point data by use of coordinate measuring devices or digitizing tablets, or the computation of surface/surface intersection points by marching methods — a large number of points can be generated, and they can contain measurement or computational noise. In this case it is important for the curve or surface to capture the “shape” of the data, but not to “wiggle” its way through every point. In approximation it is often desirable to specify a maximum bound on the deviation of the curve or surface from the given data, and to specify certain constraints, i.e., data which is to be satisfied precisely. Figure 9.2 shows a curve approximating a set of m + 1 points. A maximum deviation bound, E, was specified, and the perpendicular distance, e _i , is the approximation error obtained by projecting Q _i on to the curve. The e _i , of each point, Q _i , is less than E. The endpoints Q₀ and Q _m were specified as constraints, with the result that e₀ = e _m = 0.

In this chapter we cover several advanced surface construction techniques, namely swung, skinned, swept, Gordon, and Coons surfaces. Roughly speaking, the idea in this chapter is to take one or two curves, or sets of curves, and to create a NURBS surface which interpolates these curves; i.e., the given curves are isoparametric curves in the NURBS surface. Notice that this is fundamentally different from the interpolation to discrete point and derivative data presented in Chapter 9. In some of the constructions, it may not be obvious to the reader that the surfaces created do indeed satisfy the desired constraints. We leave it as an exercise for the reader to convince himself of this, either by mathematical proof or by software implementation.

The purpose of this chapter is to develop tools which allow a designer to interactively make local modifications to an existing NURBS curve or surface, in a way that is natural and intuitive. A NURBS curve or surface is defined by its control points, weights, and knots; modifying any of these changes the shape of the curve or surface. Generally designers do not want to work with such concepts; they prefer to specify constraints and shapes which apply directly to the curve or surface. In this chapter we develop tools which take such constraints and shape specifications and convert them into modifications in control point locations or weight values. Specifically, Sections 11.2 and 11.3 are based on specifying point constraints (i.e., the curve or surface is to change locally so that it passes through a given point); multiple point and derivative constraints are handled in Section 11.5, allowing control of tangent and curvature; and the methods of Section 11.4 allow a designer to specify the “shape” that a curve or surface is to assume in a selected region. These geometrically intuitive inputs are converted into control point relocations in Sections 11.2, 11.4, and 11.5, and into weight modifications in Section 11.3. The influence of control points and weights on shape is geometrically clear and intuitive. This was already shown, qualitatively, in previous figures, e.g., Figures 3.7, 3.23, 4.4, 4.6, 4.11, and 4.12; this chapter quantifies this influence. Although knot locations also affect shape, we know of no geometrically intuitive or mathematically simple interpretation of this effect, hence we present no techniques for moving knot locations.

The central theme of this chapter is the relationship of NURBS geometry, as practiced in this book, to other methods of representing curves and surfaces, and to several important standard formats for the exchange of geometric data between two systems. We have used a specific form of knot vector throughout this book; Section 12.2 discusses another type of knot vector and the conversion between the two types. Section 12.3 describes how NURBS curves and surfaces are defined within the three standards: IGES, STEP, and PHIGS. We remark that our NURBS are compatible with the NURBS of these standards (with the exception that IGES and PHIGS allow discontinuous curves and surfaces). Finally, Section 12.4 gives some general guidelines for exchanging geometric data between a NURBS system and another system.

In the previous twelve chapters we introduced different aspects of modeling with NURBS. These chapters covered basically two things: (1) the underlying mathematics, and (2) algorithms illustrating how the tools can be turned into computer code. Although the pseudocodes presented in each chapter are fairly detailed, containing all the necessary information to turn them into workable routines, it is a long way from the algorithmic sketch to a useful system. How to design a useful system is a very difficult question (contrary to many researchers who consider it as a minor “implementation issue”). A NURBS system has to satisfy many requirements in order to be useful in a complex surface or solid modeler. In this chapter we introduce a number of programming concepts that, we believe, contribute to good programming practices. We are fully aware of the diversity of programming styles and conventions. Consequently, we do not attempt to present the best or the ultimate solution simply because there is none.