Farin G. Curves and Surfaces for CAGD. A Practical Guide
Подождите немного. Документ загружается.
Curves and Surfaces
for CAGD
A Practical Guide
Fifth Edition
The Morgan Kaufmann Series in
Computer Grapiiics and Geometric Modeling
Series
Editor:
Brian
A.
Barsl^y, University of
California,
Berl^eley
Curves and Surfaces for CAGD: A Practical
Guide, Fifth Edition
Gerald Farin
Subdivision Methods for Geometric Design:
A Constructive Approach
Joe Warren and Henrik Weimer
The Computer Animator's Technical
Handbook
Lynn Pocock and Judson Rosebush
Computer Animation: Algorithms and
Techniques
Rick Parent
Advanced RenderMan: Creating CGI for
Motion Pictures
Anthony A. Apodaca and Larry Gritz
Curves and Surfaces in Geometric Modeling:
Theory and Algorithms
Jean GaUier
Andrew Glassner's Notebook: Recreational
Computer Graphics
Andrew S. Glassner
Warping and Morphing of Graphical Objects
Jonas Gomes, Lucia Darsa, Bruno Costa,
and Luis Velho
Jim Blinn's Corner: Dirty Pixels
Jim BUnn
Rendering with Radiance: The Art and
Science of Lighting Visualization
Greg Ward Larson and Rob Shakespeare
Introduction to Implicit Surfaces
Edited by Jules Bloomenthal
Jim Blinn's Corner: A Trip Down the
Graphics Pipeline
Jim Blinn
Interactive Curves and Surfaces: A
Multimedia Tutorial on CAGD
Alyn Rockwood and Peter Chambers
Wavelets for Computer Graphics: Theory
and Applications
Eric J. Stollnitz, Tony D. DeRose,
and David H. Salesin
Principles of Digital Image Synthesis
Andrew S. Glassner
Radiosity & Global Illumination
Francois X. Sillion and Claude Puech
Knotty: A B-Spline Visualization Program
Jonathan Yen
User Interface Management Systems:
Models and Algorithms
Dan R. Olsen, Jr.
Making Them Move: Mechanics, Control,
and Animation of Articulated Figures
Edited by Norman L Badler,
Brian A. Barsky, and David Zeltzer
Geometric and Solid Modeling:
An Introduction
Christoph M. Hoffmann
An Introduction to Splines for Use in
Computer Graphics and Geometric Modeling
Richard H. Bartels, John C. Beatty,
and Brian A. Barsky
Curves and Surfaces
for CAGD
A Practical Guide
Fifth Edition
Gerald Farin
Arizona State University
U
MORGAN KAUFMANN PUBLISHERS
AN IMPRINT
OF
ACADEMIC PRESS
A Harcourt Science and Technology Company
SAN FRANCISCO
SAN
DIEGO
NEW
YORK BOSTON
LONDON SYDNEY TOKYO
Executive Director Diane D. Cerra
Publishing Services Manager Scott Norton
Senior Production Editor Cheri Palmer
Assistan Editor Belinda Breyer
Editorial Assistant Mona Buehler
Cover Design Yvo Riezbos Design
Cover Image © 1999 Jeff Greenberg / Rainbow / PictureQuest
Glass,
curved rods of steel meet in the center to form a shape similar to the bow
of a boat at the Tampa Aquarium, Tampa, Florida.
Text Design Rebecca Evans & Associates
Composition Windfall Software, using ZzT^X
Technical Illustration LM Graphics
Copyeditor Robert Fiske
Proofreader Erin Milnes
Printer Edwards Brothers
Designations used by companies to distinguish their products are often claimed as
trademarks or registered trademarks. In all instances in which Morgan Kaufmann
Publishers is aware of a claim, the product names appear in initial capital or all capital
letters. Readers, however, should contact the appropriate companies for more complete
information regarding trademarks and registration.
Morgan Kaufmann Publishers
340 Pine Street, Sixth Floor, San Francisco, CA 94104-3205, USA
http://www.mkp.com
ACADEMIC PRESS
A Harcourt Science and Technology Company
525 B Street, Suite 1900, San Diego, CA 92101-4495, USA
http://www.academicpress.com
Academic Press
Harcourt Place, 32 Jamestown Road, London, NWl 7BY, United Kingdom
http://www.academicpress. com
© 2002 by Academic Press
All rights reserved
Printed in the United States of America
06 05 04 03 02 5 4 3 2 1
No part of this publication may be reproduced, stored in a retrieval system, or
transmitted in any form or by any means—electronic, mechanical, photocopying,
recording, or otherwise—without the prior written permission of the publisher.
Library of Congress Control Number: 2001094373
ISBN: 1-55860-737-4
This book is printed on acid-free paper.
To My Parents
This Page Intentionally Left Blank
Contents
Preface
Chapter
1
Chapter
2
Chapter
3
P. Bezier:
How a
Simple System
Ws
Introductory Material
2.1
2.2
2.3
2.4
2.5
Points and Vectors
Affine Maps
Constructing Affine Maps
Function Spaces
Problems
Linear Interpolation
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
Linear Interpolation
Piecewise Linear Interpolation
Menelaos' Theorem
Blossoms
Barycentric Coordinates
in the
Plane
Tessellations
Triangulations
Problems
Chapter 4 The de Casteljau Algorithm
4.1 Parabolas
4.2 The de Casteljau Algorithm
4.3 Some Properties of Bezier Curves
XV
1
13
13
17
20
22
24
25
25
29
30
31
34
37
39
41
43
43
45
47
vii
viii Contents
4.4 The Blossom
4.5 Implementation
4.6 Problems
Chapter 5 The Bernstein Form of a Bezier Curve
5.1 Bernstein Polynomials
5.2 Properties of Bezier Curves
5.5 The Derivatives of a Bezier Curve
5.4 Domain Changes and Subdivision
5.5 Composite Bezier Curves
5.6 Blossom and Polar
5.7 The Matrix Form of a Bezier Curve
5.8 Implementation
5.9 Problems
Chapter 6 Bezier Curve Topics
6.1 Degree Elevation
6.2 Repeated Degree Elevation
6.5 The Variation Diminishing Property
6.4 Degree Reduction
6.5 Nonparametric Curves
6.6 Cross Plots
6.7 Integrals
6.8 The Bezier Form of a Bezier Curve
6.9 The Weierstrass Approximation Theorem
6.10 Formulas for Bernstein Polynomials
6.11 Implementation
6.12 Problems
Chapter 7 Polynomial Curve Constructions
7.1 Aitken's Algorithm
7.2 Lagrange Polynomials
7.5 The Vandermonde Approach
7.4 Limits of Lagrange Interpolation
7.5 Cubic Hermite Interpolation
7.6 Quintic Hermite Interpolation
7.7 Point-Normal Interpolation
50
53
54
57
57
60
62
68
71
73
74
75
78
81
81
83
84
85
86
87
88
89
90
91
92
93
95
95
98
99
101
102
106
107
Chapter 8
Chapter 9
Chapter 10
7.8
7.9
7.10
7.11
7.12
7.13
Least Squares Approximation
Smoothing Equations
Designing with Bezier Curves
The Newton Form and Forward Differencing
Implementation
Problems
B-Spline
Curves
8.1
8.2
8.3
8.4
8.5
8.6
8.7
8.8
8.9
8.10
8.11
Motivation
B-Spline
Segments
B-Spline
Curves
Knot Insertion
Degree Elevation
Greville Abscissae
Smoothness
B-Splines
B-Spline
Basics
Implementation
Problems
Constructing Spline Curves
9.1
9.2
9.3
9.4
9.5
9.6
9.7
9.8
9.9
9.10
Greville Interpolation
Least Squares Approximation
Modifying
B-Spline
Curves
C^ Cubic Spline Interpolation
More End Conditions
Finding a Knot Sequence
The Minimum Property
C^ Piecewise Cubic Interpolation
Implementation
Problems
W. Boeiim: Differential Geometry 1
10.1
10.2
10.3
10.4
Parametric Curves and Arc Length
The Frenet Frame
Moving the Frame
The Osculating Circle
Contents ix
108
110
112
114
116
117
119
120
122
126
130
133
134
135
140
143
144
146
147
147
149
153
154
157
161
167
169
174
176
179
179
181
182
184