Curves and Surfaces for Computer Graphics

By David Salomon. Published by Springer Verlag August 2005. ISBN 0-387-24196-5. LCCN T385.S2434 2005. xvi+461 pages.

A BibTeX style file and an Errata list are available.

Written in late 2003 and most of 2004, the book consists of nine chapters, four appendixes, a bibliography, answers to exercises, and an index.

Dedicated To the memory of Pierre Etienne Bezier (1910-1999, see photos below).

From the Preface.

The chief aim of computer graphics is to display and print realistic-looking images. This task is achieved by computing the outer surface of the object or objects to be displayed, and rendering it by simulating the way it is seen in real life. Most real objects are visible because they reflect light, so the main task of rendering is to simulate light reflection. (Relatively few objects are visible because of light that they generate. A completely transparent object is visible by the light it refracts. Most objects, however, do not generate light and are not transparent. They are seen because they reflect some of the light that falls on them.)

Rendering is therefore an important part of computer graphics, but this book is concerned with the computations of surfaces. In order to render a real object, such as a teapot or a car, its surface has first to be calculated and stored in the computer as a mathematical expression. This expression is a model of the real object, which is why the process of generating the model is known as geometric modeling. The rendering algorithm then scans the surface point by point, computes the normal vector to the surface at every point, and uses the normal to compute the amount and color of light reflected from the point.

The book also deals with curves, because an understanding of curves is a key to understanding surfaces. Most mathematical methods for curves can be extended to surfaces, which is why this book covers various approaches to curve design and shows that many curve methods can be generalized to surfaces.

The most important term in the field of curve and surface design is interpolation. It comes from the Latin inter (between) and polare (to polish) and it means to compute new values that lie between (or that are an average of ) certain given values. A typical algorithm for curves starts with a set of points and employs interpolation to compute a smooth curve that passes through the points. Such points are termed data points and they define an interpolating curve. Some methods start with both points and vectors and compute a curve that passes through the points and at certain points also moves in the directions of the given vectors.

Another important term in this field is approximation. Certain curve and surface methods start with points and perhaps also vectors and compute a curve or a surface that passes close to the points but not necessarily through them. Such points are known as control points and the curve or the surface defined by them is referred to as an approximating curve or surface. Most chapters of this book describe interpolation or approximation methods.

A listing of all the Mathematica codes in the book is available here.

Table of Contents

Book Cover
Preface v

1 Basic Theory 1
1.1 Points and Vectors 1
1.2 Parametric Blending 10
1.3 Parametric Curves 11
1.4 Properties of Parametric Curves 13
1.5 PC Curves 18
1.6 Curvature and Torsion 26
1.7 Special and Degenerate Curves 35
1.8 Basic Concepts of Surfaces 35
1.9 The Cartesian Product 38
1.10 Connecting Surface Patches 40
1.11 Fast Computation of a Bicubic Patch 41
1.12 Subdividing a Surface Patch 43
1.13 Surface Normals 46

2 Linear Interpolation 49
2.1 Straight Segments 49
2.2 Polygonal Surfaces 53
2.3 Bilinear Surfaces 59
2.4 Lofted Surfaces 64

3 Polynomial Interpolation 71
3.1 Four Points 72
3.2 The Lagrange Polynomial 76
3.3 The Newton Polynomial 85
3.4 Polynomial Surfaces 87
3.5 The Biquadratic Surface Patch 87
3.6 The Bicubic Surface Patch 89
3.7 Coons Surfaces 93
3.8 Gordon Surfaces 108

4 Hermite Interpolation 111
4.1 Interactive Control 112
4.2 The Hermite Curve Segment 113
4.3 Degree-5 Hermite Interpolation 122
4.4 Controlling the Hermite Segment 123
4.5 Truncating and Segmenting 127
4.6 Hermite Straight Segments 129
4.7 A Variant Hermite Segment 131
4.8 Ferguson Surfaces 132
4.9 Bicubic Hermite Patch 134
4.10 Biquadratic Hermite Patch 137

5 Spline Interpolation 141
5.1 The Cubic Spline Curve 141
5.2 The Quadratic Spline 156
5.3 The Quintic Spline 158
5.4 Cardinal Splines 161
5.5 Catmull-Rom Surfaces 165
5.6 Kochanek-Bartels Splines 167

6 Bezier Approximation 175
6.1 The Bezier Curve 176
6.2 The Bernstein Form of the Bezier Curve 178
6.3 Fast Calculation of the Curve 185
6.4 Properties of the Curve 190
6.5 Connecting Bezier Curves 192
6.6 The Bezier Curve as a Linear Interpolation 194
6.7 Blossoming 198
6.8 Subdividing the Bezier Curve 202
6.9 Degree Elevation 205
6.10 Reparametrizing the Curve 207
6.11 Cubic Bezier Segments with Tension 210
6.12 An Interpolating Bezier Curve: I 212
6.13 An Interpolating Bezier Curve: II 214
6.14 Nonparametric Bezier Curves 217
6.15 Rational Bezier Curves 217
6.16 Rectangular Bezier Surfaces 219
6.17 Subdividing Rectangular Patches 224
6.18 Degree Elevation 225
6.19 Nonparametric Rectangular Patches 227
6.20 Joining Rectangular Bezier Patches 228
6.21 An Interpolating Bezier Surface Patch 230
6.22 Rational Bezier Surfaces 232
6.23 Triangular Bezier Surfaces 234
6.24 Joining Triangular Bezier Patches 242
6.25 Reparametrizing the Bezier Surface 246
6.26 The Gregory Patch 248

7 B-Spline Approximation 251
7.1 The Quadratic Uniform B-Spline 252
7.2 The Cubic Uniform B-Spline 256
7.3 Multiple Control Points 263
7.4 Cubic B-Splines with Tension 265
7.5 Cubic B-Spline and Bezier Curves 268
7.6 Higher-Degree Uniform B-Splines 268
7.7 Interpolating B-Splines 270
7.8 A Knot Vector-Based Approach 271
7.9 Recursive Definitions of the B-Spline 280
7.10 Open Uniform B-Splines 281
7.11 Nonuniform B-Splines 286
7.12 Matrix Form of the Nonuniform B-Spline 295
7.13 Subdividing the B-spline Curve 299
7.14 Nonuniform Rational B-Splines (NURBS) 302
7.15 Uniform B-Spline Surfaces 308
7.16 Relation to Other Surfaces 312
7.17 An Interpolating Bicubic Patch 315
7.18 The Quadratic-Cubic B-Spline Surface 317

8 Subdivision Methods 319
8.1 Introduction 319
8.2 Chaikin's Refinement Method 319
8.3 Quadratic Uniform B-Spline by Subdivision 325
8.4 Cubic Uniform B-Spline by Subdivision 327
8.5 Biquadratic B-Spline Surface by Subdivision 331
8.6 Bicubic B-Spline Surface by Subdivision 336
8.7 Polygonal Surfaces by Subdivision 341
8.8 Doo Sabin Surfaces 341
8.9 Catmull-Clark Surfaces 343
8.10 Loop Surfaces 344

9 Sweep Surfaces 347
9.1 Sweep Surfaces 348
9.2 Surfaces of Revolution 353
9.3 An Alternative Approach 355
9.4 Skinned Surfaces 360

A Conic Sections 363

B Approximate Circles 369
B.1 Circles and Bzier Curves 369
B.2 The Cubic B-Spline as a Circle 373

C Graphics Gallery 377

D Mathematica Notes 381

Answers to Exercises 387

Bibliography 447

Index 451

Auxiliary Material

1. Readers of this book may find this Mathematica package very useful. "Computer Aided Geometric Design in Mathematica" was written by Bohumir Bastl and published in the 2005 Wolfram Technology Conference in Champaign, IL. This package is also available from http://library.wolfram.com/infocenter/Conferences/5812/. The package provides functions for the following CAGD objects:

* splines (quadratic and cubic with the possibility to choose boundary conditions and the type of parametrization)

* Bezier curves and surfaces

* rational Bezier curves and surfaces

* B-spline curves and surfaces

* NURBS curves and surfaces

2. The Mathematica notebooks available here have been developed by Bill Wilburn who graciously made them available to the readers. I hope they will prove valuable.

3. Bill Wilburn has also brought to my attention that the following sites offer Mathematica notebooks on curves and surfaces and may thus prove useful to readers:

Wolfram demonstrations of Bezier curves at http://demonstrations.wolfram.com/search.html?query=Bezier

A downlodable NURBS package for Mathematica. This is located at http://thebushman.net/drupal/node/4

Naturally, there may be many other useful sites.

4. Figure 7.19 (page 289) was originally drawn by hand and is only an approximation. Pieter Barendrecht has written Matlab code to compute this figure accurately. The code is available here and the accurate figure (in JPEG) is here.

Photos

Bezier curves and surfaces are popular and are discussed in detail in the book. The photos of Pierre Bezier (1 September 1910--25 November 1999) shown here are rare. Pierre Bezier Pierre Bezier

Last Updated 29 Feb 2012.