Curves and Surfaces
for Computer Graphics
To the memory of Pierre Etienne B´ezier (1910–1999).
Only for you, children of doctrine and learning, have we
written this work. Examine this book, ponder the meaning
we have dispersed in various places and gathered again;
what we have concealed in one place we have disclosed
in another, that it may be understood by your wisdom.
–Heinrich Agrippa von Nettesheim, De Occulta Philosophia, (1531)
David Salomon
Curves and Surfaces
for Computer Graphics
With 207 Figures, 12 in Full Color
David Salomon (Emeritus)
Department of Computer Science
California State University, Northridge
Northridge, CA 91330-8281
U.S.A.
dsalomon@csun.edu
ISBN-10: 0-387-24196-5
ISBN-13: 978-0-387-24196-8
e-ISBN: 0-387-28452-4
Printed on acid-free paper.
© 2006 Springer Science+Business Media, Inc.
All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the
publisher (Springer Science+Business Media, Inc., 233 Spring St., New York, NY 10013, USA), except for brief excerpts
in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval,
electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is
forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified
as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.
Printed in the United States of America.
(HAM)
9 8 7 6 5 4 3 2 1
SPIN 11360285
springeronline.com
Preface
Images are all around us. We see them in color and in high resolution.
In fact, the
natural images we see with our eyes seem perfectly smooth, with no jagged edges and
no graininess. Computer graphics, on the other hand, deals with images that consist
of small dots, pixels. When we first hear of this feature of computer graphics, we tend
to dismiss the entire field as trivial.
It seems intuitively obvious that an image that
consists of dots would always look artificial, rough, and inferior to what we see with our
eyes. Yet state-of-the-art computer-generated images are often difficult or impossible to
distinguish from their real counterparts, even though they are discrete, made of pixels,
and not continuous.
A similar dichotomy exists in painting. Many painters try to mimic nature and
paint smooth and continuous pictures. Others choose to be pointillists. They paint by
placing many small dots on their canvas. The most important pointillist was the 19th
century French impressionist Georges Seurat.
Georges Seurat (1859–1891) was a leader in the late 19th century neo-impressionism
movement, a school of painting that uses tiny brushstrokes of contrasting colors to
achieve a delicate play of light and create subtle changes in form (Figure C.1). Seurat
used this technique, which became known as pointillism or divisionism, to create huge
paintings that are made entirely of small dots of pure color. The dots are too small to
be distinguished when looking at the work in its entirety, but they make his paintings
shimmer with brilliance. His most well-known works are Une Baignade (1883–84) and
Un dimanche apr`es-midi `a l’Ile de la Grande Jatte (1884–86). The art critic Ars`ene
Alexandre had this to say about the latter painting: “Everything was so new in this
immense painting—the conception was bold and the technique one that nobody had
ever seen or heard before. This was the famous pointillism.”
Even though it generates discrete images made of dots, the field of computer graph-
ics has been extremely successful.
It has started from nothing in the 1960s and has
since attracted many workers and researchers. They developed general techniques and
specialized algorithms to generate and manipulate images and thereby turned computer
graphics into the useful, practical discipline it is today.
vi
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.
Chapter 1 presents the basic theory of curves and surfaces.
It discusses the all-
important parametric representation and covers basic concepts such as curvature, tan-
gent vectors, normal vectors, curve and surface continuity, and Cartesian products.
Chapter 2 introduces the simplest curves and surfaces. Straight lines, flat planes,
triangles, and bilinear and lofted surfaces are presented and illustrated with examples.
Chapter 3 discusses polynomial interpolation. Given a set of points, the problem is
to compute a polynomial that passes through them. This problem is then extended to
a surface patch that passes through a given two-dimensional set of points. The chapter
starts with the important parametric cubic (PC) curves. It continues with the general
method of Lagrange interpolation and its relative, the Newton interpolation method.
Simple polynomial surfaces are presented, followed by Coons surfaces, a family of simple
surface patches based on polynomials.
Preface
vii
The mathematically-elegant Hermite interpolation technique is the topic of Chap-
ter 4. The chapter discusses cubic and higher-order Hermite curve segments, special
and degenerate hermite segments, Hermite interpolation curves, the Ferguson surface
patch, the Coons surface patch, the bicubic surface patch, and Gordon surfaces. A few
less-important topics are also touched upon.
The important concept of splines is covered in Chapter 5. Spline methods for curves
and surfaces are more practical than polynomial methods and several spline methods are
based on Hermite interpolation. The main topics in this chapter are cubic splines (sev-
eral varieties are discussed), cardinal splines, Kochanek–Bartels splines, spline surface
patches, and cardinal spline patches.
Chapter 6 is devoted to B´ezier methods for curves and surfaces. The Bernstein
form of the B´ezier curve is introduced, followed by techniques for fast computation of
the curve and by a list of the properties of the curve. This leads to a discussion of
how to smoothly connect Bezier segments. The de Casteljau construction of the B´ezier
curve is described next. It is followed by the technique of blossoming and by methods for
subdividing the curve, for degree elevation and for controlling its tension. Sometimes one
wants to interpolate a set of points by a B´ezier curve and this problem is also discussed.
Rational B´ezier curves have important advantages and are assigned a separate section.
The chapter continues with material on B´ezier surfaces. The topics discussed are
rectangular B´ezier surfaces and their smooth joining, triangular B´ezier surfaces and their
smooth joining, and the Gregory surface patch and its tangent vectors.
The last of the “interpolation/approximation” chapters is Chapter 7, on the all-
important B-spline technique. B-spline curve topics are the quadratic uniform B-spline
curve, the cubic uniform B-spline curve, multiple control points, cubic B-splines with
tension, higher-degree uniform B-splines, interpolating B-splines, open uniform B-spline,
nonuniform B-splines, matrix form of the nonuniform B-spline curve, subdividing the
B-spline curve, and NURBS. The B-spline surface topics are uniform B-spline surfaces,
an interpolating bicubic patch, and a quadratic-cubic B-spline patch.
Subdivision methods for curves and surfaces are discussed in Chapter 8. These
methods are also based on interpolation, but are different from the traditional interpo-
lation methods discussed in the preceding chapters. The following important techniques
are described in this chapter: The de Casteljau refinement process, Chaikin’s algorithm,
the quadratic uniform B-spline curve, the cubic uniform B-spline curve, bi-quadratic
B-spline patches, bicubic B-spline patches, Doo–Sabin subdivision methods, Catmull–
Clark surfaces, and Loop subdivision surfaces.
Chapter 9 presents the various types of sweep surfaces. This is a completely dif-
ferent approach to surface design and representation. A sweep surface is generated by
constructing a curve and moving it along another curve, while optionally also rotating
and scaling it, to create a surface patch. A special case of sweep surfaces is surfaces of
revolution. They are created when a curve is rotated about an axis.
Appendix A is a short discussion of conic sections, a family of simple curves that
have special applications.
Appendix B discusses simple methods for the approximate representation of circles
by polynomials.
Appendix C is a small collection of color images, most of which appear elsewhere
in the book in grayscale.
viii
Preface
Finally, Appendix D discusses several useful and interesting commands and tech-
niques employed in the various Mathematica code listings sprinkled throughout the book.
History of Curves and Surfaces
Section 2.4 discusses lofted surfaces but does not explain the reason for this unusual
name. Historically, shipbuilders were among the first to mechanize their operation by
developing mathematical models of surfaces. Ships tend to be big and the only dry place
in a shipyard large enough to store full-size drawings of ship parts was in the sail lofts
above the shipyard’s dry dock. Certain parts of a ship’s surface are flat in one direction
and curved in the other direction, so such surfaces became known as lofted.
In the 1960s, both car and aircraft manufacturers became interested in applying
computers to automate the design of their vehicles. Traditionally, artists and designers
had to make clay models of each part of the surface of a car or airplane and these models
were later used by the production people to produce stamp molds. With the help of
the computer it became possible to design a section of surface on the computer in an
interactive process, then have the computer drive a milling machine to actually make
the part.
The box on page 175 mentions the work of Pierre B´ezier at Renault and Paul
de Casteljau at Citro¨en, the contributions of Steven Coons to Ford Motors and William
Gordon and Richard F. Riesenfeld to General Motors, and the efforts of James Ferguson
in constructing airplane surfaces.
As a result of these developments in the 1960s and 1970s, the area of computer
graphics that deals with curves and surfaces has become known, in 1974, as computer
assisted geometric design (CAGD). Several sophisticated CAGD software systems have
been developed in the 1980s for general use in manufacturing and in other fields such as
chemistry (to model molecules), geoscience (for specialized maps), and architecture (for
three-dimensional models of buildings).
Hardware developments in the 1980s made it possible to use CAGD techniques
in the 1990s to produce computer-generated special effects for movies (an example is
Jurassic Park), followed by full-length movies, such as Toy story, Finding Nemo, and
Shrek, that were entirely generated by computer.
A detailed survey of the history of this field can be found in [Farin 04]. Several
first-person historical accounts by pioneers in this field are collected in [Rogers 01].
Resources for Curves and Surfaces
As is natural to expect, the World Wide Web has many resources for CAGD. In addition
to the many texts available in this field, the journals CAD and CAGD carry state-of-
the-art papers and articles. See [CAD 04] and [CAGD 04]. Following is a list of some
of the most important resources for computer graphics, not just CAGD, current as of
mid-2005.
http://www.siggraph.org/ is the official home page of SIGGRAPH, the special
interest group for graphics, one of many SIGs that are part of the ACM.
The Web page http://www.siggraph.org/conferences/fundamentals has useful
course notes from SIGGRAPH conferences.