COMPUTER AIDED GEOMETRIC DESIGN
Thomas W. Sederberg
January 10, 2012
ii
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
T. W. Sederberg iii
Preface
This semester is the 24th time I have taught a course at Brigham Young University titled, \Computer
Aided Geometric Design." When I rst taught such a course in 1983, the eld was young enough
that no textbook covered everything that I wanted to teach, and so these notes evolved.
The eld now has matured to the point that several semesters worth of valuable material could be
compiled. These notes, admittedly biased towards my own interests, re
ect my personal preferences
as to which of that material is most bene cial to students in an introductory course.
I welcome anyone who has an interest in studying this fascinating topic to make free use of these
notes. I invite feedback on typos and on material that could be written more clearly.
Thomas W. Sederberg
Department of Computer Science
Brigham Young University
tom@cs.byu.edu
January 2007
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
iv T. W. Sederberg
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Contents
1 Introduction 1
1.1 Points, Vectors and Coordinate Systems . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Vector Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Points vs. Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Rotation About an Arbitrary Axis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Matrix Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Parametric, Implicit, and Explicit Equations . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.1 Parametric equations of lines . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.2 Implicit equations of lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.3 Distance from a point to a line . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Conic Sections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6.1 Parametric equations of conics . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 B ezier Curves 17
2.1 The Equation of a B ezier Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 B ezier Curves over Arbitrary Parameter Intervals . . . . . . . . . . . . . . . . . . . . 20
2.3 The de Casteljau Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Degree Elevation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 The Convex Hull Property of B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Distance between Two B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.8 Three Dimensional B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.9 Rational B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.9.1 De Casteljau Algorithm and Degree Elevation on Rational B ezier Curves . . 29
2.9.2 First Derivative at the Endpoint of a Rational B ezier Curve . . . . . . . . . . 29
2.9.3 Curvature at an Endpoint of a Rational B ezier Curve . . . . . . . . . . . . . 30
2.10 Continuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.11 Circular Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.12 Reparametrization of B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.13 Advantages of Rational B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.14 Explicit B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.15 Integrating Bernstein polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
v
vi CONTENTS
3 Polynomial Evaluation and Basis Conversion 39
3.1 Horner's Algorithm in Power Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Horner's Algorithm in Bernstein Basis . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Basis Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.2 Closed Form Expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Forward Di erencing 43
4.1 Choosing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5 Properties of Blending Functions 47
5.1 Timmer's Parametric Cubic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 Ball's Rational Cubic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3 Overhauser Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6 B-Spline Curves 55
6.1 Polar Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.1.1 Subdivision of B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.2 Knot Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.3 Extracting B ezier Curves from B-splines . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.4 Multiple knots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.5 Periodic B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.6 B ezier end conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.7 Knot insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.8 The de Boor algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.9 Explicit B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.10 B-spline hodographs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.11 Symmetric polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.12 Combining B ezier curves into a B-spline . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.13 Knot Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.13.1 Knot Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.13.2 Interval Halving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.13.3 Degree-Two B-Splines using Knot Intervals . . . . . . . . . . . . . . . . . . . 70
6.13.4 Hodographs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.13.5 Degree elevation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.14 B-spline Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.14.1 B-Spline Basis-Functions using Knot Intervals . . . . . . . . . . . . . . . . . . 76
6.14.2 Re nement of B-Spline Basis Functions . . . . . . . . . . . . . . . . . . . . . 77
6.14.3 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7 Planar Curve Intersection 79
7.1 Bezout's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.1.1 Homogeneous coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.1.2 Circular Points at In nity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.1.3 Homogeneous parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.1.4 The Fundamental Theorem of Algebra . . . . . . . . . . . . . . . . . . . . . . 81
7.2 The Intersection of Two Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.2.1 Homogeneous Points and Lines . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.3 Intersection of a Parametric Curve and an Implicit Curve . . . . . . . . . . . . . . . 82
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
CONTENTS vii
7.3.1 Order of Contact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.4 Computing the Intersection of Two B ezier Curves . . . . . . . . . . . . . . . . . . . . 84
7.4.1 Timing Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.5 B ezier subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.6 Interval subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.7 B ezier Clipping method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.7.1 Fat Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.7.2 B ezier Clipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.7.3 Iterating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.7.4 Clipping to other fat lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.7.5 Multiple Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.7.6 Rational Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.7.7 Example of Finding a Fat Line . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.7.8 Example of Clipping to a Fat Line . . . . . . . . . . . . . . . . . . . . . . . . 92
8 O set Curves 95
9 Polynomial Root Finding in Bernstein Form 97
9.1 Convex Hull Marching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
9.2 Bernstein Combined Subdivide & Derivative Algorithm . . . . . . . . . . . . . . . . 99
9.3 Multiplication of Polynomials in Bernstein Form . . . . . . . . . . . . . . . . . . . . 103
9.4 Intersection between a Line and a Rational B ezier Curve . . . . . . . . . . . . . . . . 103
10 Polynomial Interpolation 105
10.1 Undetermined Coe cients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
10.2 Lagrange Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.3 Newton Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
10.4 Neville's Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
10.5 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
10.6 Error Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
10.6.1 Chebyshev Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
10.7 Interpolating Points and Normals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
11 Approximation 117
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
11.2 L2 Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
11.3 Approximating a Set of Discrete Points with a B-Spline Curve . . . . . . . . . . . . 118
11.3.1 Parametrization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
11.3.2 Knot vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
11.4 Fairing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
11.4.1 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.4.2 Constrained fairing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.4.3 Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
12 Interval B ezier Curves 127
12.1 Interval arithmetic and interval polynomials . . . . . . . . . . . . . . . . . . . . . . . 127
12.2 Interval B ezier curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
12.2.1 A ne maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
12.2.2 Centered form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
viii CONTENTS
12.2.3 Error monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
12.2.4 Envelopes of interval B ezier curves . . . . . . . . . . . . . . . . . . . . . . . . 136
12.2.5 Interval hodographs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
12.3 Approximation by interval polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . 137
12.3.1 Remainder formulae and interval approximants . . . . . . . . . . . . . . . . . 138
12.3.2 Hermite interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
12.3.3 Estimating bounds on derivatives . . . . . . . . . . . . . . . . . . . . . . . . . 141
12.4 Approximation by interval B ezier curves . . . . . . . . . . . . . . . . . . . . . . . . . 142
13 Floating Point Error 145
14 Free-Form Deformation (FFD) 149
14.0.1 Deformed Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
15 TENSOR-PRODUCT SURFACES 155
15.1 Tensor-Product B ezier Surface Patches . . . . . . . . . . . . . . . . . . . . . . . . . . 155
15.2 The de Casteljau Algorithm for B ezier Surface Patches . . . . . . . . . . . . . . . . . 157
15.3 Tangents and Normals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
15.4 Tessellation of B ezier Curves and Surfaces . . . . . . . . . . . . . . . . . . . . . . . . 159
15.4.1 The curve case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
15.4.2 The surface case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
15.5 Cn Surface Patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
15.6 NURBS Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
15.7 T-Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
15.7.1 Equation of a T-Spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
15.7.2 T-spline Local Re nement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
15.7.3 Blending Function Re nement . . . . . . . . . . . . . . . . . . . . . . . . . . 170
15.7.4 T-spline Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
15.7.5 Local Re nement Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
15.7.6 Converting a T-spline into a B-spline surface . . . . . . . . . . . . . . . . . . 173
15.8 E cient Computation of Points and Tangents on a B ezier surface patch. . . . . . . . 175
15.9 Curvature at the Corner of a B ezier Surface Patch . . . . . . . . . . . . . . . . . . . 178
15.9.1 Curvatures of tensor-product rational B ezier surfaces . . . . . . . . . . . . . 178
15.9.2 Curvatures of triangular rational B ezier surfaces . . . . . . . . . . . . . . . 181
15.9.3 Curvature of an Implicit Surface . . . . . . . . . . . . . . . . . . . . . . . . . 182
16 Algebraic Geometry for CAGD 183
16.1 Implicitization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
16.2 Brute Force Implicization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
16.3 Polynomial Resultants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
16.3.1 De nition of the Resultant of Two Polynomials . . . . . . . . . . . . . . . . . 185
16.3.2 Resultant of Two Degree One Polynomials . . . . . . . . . . . . . . . . . . . 186
16.3.3 Resultants of Degree-Two Polynomials . . . . . . . . . . . . . . . . . . . . . . 186
16.3.4 Resultants of Degree-Three Polynomials . . . . . . . . . . . . . . . . . . . . . 188
16.3.5 Resultants of Higher Degree Polynomials . . . . . . . . . . . . . . . . . . . . 189
16.4 Determining the Common Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
16.5 Implicitization and Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
16.6 Implicitization in B ezier Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
16.6.1 Inversion of B ezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
CONTENTS ix
16.7 Curve Inversion Using Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . 197
16.8 Curve-Curve Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
16.9 Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
16.10Base Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
16.11Ideals and Varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
16.11.1 Ideals of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
16.11.2 Ideals of Polynomials in One Variable . . . . . . . . . . . . . . . . . . . . . . 202
16.11.3Polynomials in Several Variables . . . . . . . . . . . . . . . . . . . . . . . . . 202
16.11.4Polynomial Ideals and Varieties . . . . . . . . . . . . . . . . . . . . . . . . . . 204
16.11.5 Gr obner Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
17 Implicitization using Moving Lines 207
17.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
17.1.1 Homogeneous Points and Lines . . . . . . . . . . . . . . . . . . . . . . . . . . 207
17.1.2 Curves and Moving Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
17.1.3 Weights and Equivalency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
17.2 Pencils and Quadratic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
17.2.1 Pencils of lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
17.2.2 Intersection of Two Pencils . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
17.2.3 Pencils on Quadratic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
17.3 Moving Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
17.3.1 Bernstein Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
17.3.2 Moving Line which Follows Two Moving Points . . . . . . . . . . . . . . . . . 216
17.3.3 Intersection of Two Moving Lines . . . . . . . . . . . . . . . . . . . . . . . . . 217
17.3.4 Base Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
17.3.5 Axial Moving Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
17.4 Curve Representation with Two Moving Lines . . . . . . . . . . . . . . . . . . . . . . 219
17.4.1 Axial Moving Line on a Curve . . . . . . . . . . . . . . . . . . . . . . . . . . 219
17.4.2 Axial Moving Line on a Double Point . . . . . . . . . . . . . . . . . . . . . . 220
17.4.3 Cubic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
17.4.4 Quartic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
17.4.5 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
17.4.6 Implicitization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
17.5 Tangent Moving Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
17.5.1 Tangent Moving Lines and Envelope Curves . . . . . . . . . . . . . . . . . . . 226
17.5.2 Reciprocal Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
17.5.3 Tangent Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
18 Genus and Parametrization of Planar Algebraic Curves 233
18.1 Genus and Parametrization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
18.2 Detecting Double Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
18.3 Implicit Curve Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
18.4 Discriminants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
18.5 Parametrizing Unicursal Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
18.6 Undetermined Coe cients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
x CONTENTS
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
List of Figures
1.1 Equivalent Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Vectors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Vector Addition and Subtraction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Vector Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Rotation about an Arbitrary Axis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Rotation about an Arbitrary Axis Using Vector Algebra. . . . . . . . . . . . . . . . . 7
1.7 Line given by A0 + A1t: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.8 A ne parametric equation of a line. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.9 Line de ned by point and normal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.10 Normalized line equation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1 Examples of cubic B ezier curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Font de nition using B ezier curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 B ezier Curves in Terms of Center of Mass. . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Cubic B ezier blending functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 B ezier curves of various degree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Subdividing a cubic B ezier curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7 Recursively subdividing a quadratic B ezier curve. . . . . . . . . . . . . . . . . . . . . 21
2.8 Subdividing a quadratic B ezier curve. . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.9 Degree Elevation of a B ezier Curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.10 Convex Hull Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.11 Di erence curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.12 Hodograph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.13 Rational B ezier curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.14 Rational curve as the projection of a 3-D curve. . . . . . . . . . . . . . . . . . . . . . 28
2.15 Osculating Circle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.16 Endpoint curvature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.17 C2 B ezier curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.18 Circular arcs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.19 Circle as Degree 5 Rational B ezier Curve. . . . . . . . . . . . . . . . . . . . . . . . . 34
2.20 Circle with negative weight. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.21 Explicit B ezier curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.1 Variation Diminishing Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Timmer's PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.3 Ball's Cubic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
xi
xii LIST OF FIGURES
5.4 Overhauser curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.1 Spline and ducks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2 Polar Labels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.3 A ne map property of polar values. . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.4 Subdividing a cubic B ezier curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.5 B ohm algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.6 Double knot. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.7 Special B-Spline Curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.8 Knot Insertion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.9 B-spline with knot vector [11115555]. . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.10 De Boor algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.11 Sample cubic B-spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.12 Periodic B-splines labelled with knot intervals . . . . . . . . . . . . . . . . . . . . . . 66
6.13 Periodic B-splines with double and triple knots. . . . . . . . . . . . . . . . . . . . . . 67
6.14 Inferring polar labels from knot intervals. . . . . . . . . . . . . . . . . . . . . . . . . 67
6.15 Knot Insertion using Knot Intervals. . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.16 \Interval Splitting" using Knot Intervals. . . . . . . . . . . . . . . . . . . . . . . . . 68
6.17 \Interval Splitting" using Knot Intervals. . . . . . . . . . . . . . . . . . . . . . . . . 69
6.18 Introducing Zero Knot Intervals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.19 Interval halving for a non-uniform quadratic B-spline curve. . . . . . . . . . . . . . . 70
6.20 Interval halving for a non-uniform cubic B-spline curve. . . . . . . . . . . . . . . . . 70
6.21 Quadratic B-Spline Curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.22 Interval Splitting of a Quadratic B-Spline Curve. . . . . . . . . . . . . . . . . . . . . 71
6.23 Interval Splitting of a Quadratic B-Spline Curve. . . . . . . . . . . . . . . . . . . . . 72
6.24 Hodograph of a Degree 3 Polynomial B-Spline Curve. . . . . . . . . . . . . . . . . . 72
6.25 Finding the Control Points of a B-Spline Hodograph. . . . . . . . . . . . . . . . . . . 73
6.26 Degree elevating a degree one and degree two B-spline. . . . . . . . . . . . . . . . . . 74
6.27 Degree elevating a degree three B-spline. . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.28 Cubic B-Spline Curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.29 Basis function B3
3 (t). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.30 Sample Cubic B-Spline Curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.31 B-Spline Basis Function for Control Point Pi in Figure 6.30. . . . . . . . . . . . . . . 76
7.1 Convex Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.2 Three iterations of B ezier subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.3 Interval preprocess and subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.4 Fat line bounding a quartic curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.5 B ezier curve/fat line intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.6 Explicit B ezier curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.7 After rst B ezier clip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.8 Two intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.9 Two intersections, after a split . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.10 Example of how to nd fat lines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.11 Clipping to a fat line. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.12 Clipping to Lmax. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.13 Clipping example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.14 Additional examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
LIST OF FIGURES xiii
8.1 O set Curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.2 O set Curves in which the O set Radius Exceeds the Radius of Curvature for a
Portion of the Base Curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
9.1 Bernstein root nding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
9.2 Root isolation heuristic (a-d). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.3 Root isolation heuristic (e-h). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
10.1 Interpolating Four Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
10.2 Interpolating Four Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.3 Error Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.4 Piecewise linear approximation of a B ezier curve . . . . . . . . . . . . . . . . . . . . 113
10.5 Two cases of (x x0)(x x1) (x x9) for 0 x 1. . . . . . . . . . . . . . . . . 115
11.1 Uniform vs. bad parametrization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
11.2 Arc length vs. bad parametrization. . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
11.3 Uniform vs. bad knots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
11.4 The fairing e ect. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
11.5 The shrank curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
11.6 The fairing e ect of bad parameter. . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.7 Fairing and interpolation with di erent constant. . . . . . . . . . . . . . . . . . . . . 125
11.8 Constrained fairing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.9 Constrained fairing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
12.1 A cubic interval B ezier curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
12.2 The a ne map of two scalar points. . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
12.3 The a ne map of two scalar intervals. . . . . . . . . . . . . . . . . . . . . . . . . . . 131
12.4 The a ne map of two vector intervals. . . . . . . . . . . . . . . . . . . . . . . . . . . 132
12.5 Interval de Casteljau algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
12.6 The envelope of an interval B ezier curve. . . . . . . . . . . . . . . . . . . . . . . . . . 136
12.7 Approximate arc length parametrization of circle. . . . . . . . . . . . . . . . . . . . . 143
13.1 A ne map in
oating point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
13.2 A ne map in
oating point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
14.1 FFD example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
14.2 FFD example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
14.3 FFD local coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
14.4 FFD undisplaced control points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
14.5 Continuity control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
14.6 FFD Applied to a Grid of Lines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
14.7 Control points of deformed line. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
14.8 FFD Applied to a horizontal line t = :3 . . . . . . . . . . . . . . . . . . . . . . . . . 153
14.9 Control points of deformed line. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
15.1 B ezier surface patch of degree 2 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
15.2 Surface in Figure 15.1.a viewed as a family of t-iso-parameter curves. . . . . . . . . . 157
15.3 Applying the de Casteljau algorithm to the surface in Figure 15.1.a. . . . . . . . . . 158
15.4 Partial derivative vectors for P[0;1] [0;1](s; t)(assuming weights are unity). . . . . . . 158
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
xiv LIST OF FIGURES
15.5 Surface Control Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
15.6 Teapot modeled using 32 bicubic B ezier surface patches . . . . . . . . . . . . . . . . 163
15.7 Two Cn bicubic B ezier surface patches. . . . . . . . . . . . . . . . . . . . . . . . . . 163
15.8 Knot insertions into a NURBS surface. . . . . . . . . . . . . . . . . . . . . . . . . . . 164
15.9 Splitting a NURBS surface into B ezier patches. . . . . . . . . . . . . . . . . . . . . . 164
15.10Head modeled (a) as a NURBS with 4712 control points and (b) as a T-spline with
1109 control points. The red NURBS control points are super
uous. . . . . . . . . . 165
15.11Car door modeled as a NURBS and as a T-spline. . . . . . . . . . . . . . . . . . . . 165
15.12NURBS head model, converted to a T-spline. . . . . . . . . . . . . . . . . . . . . . . 165
15.13A gap between two B-spline surfaces, xed with a T-spline. . . . . . . . . . . . . . . 166
15.14Pre-image of a T-mesh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
15.15Pre-image of a T-mesh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
15.16Knot lines for blending function Bi(s; t). . . . . . . . . . . . . . . . . . . . . . . . . . 168
15.17Example T-Mesh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
15.18Sample Re nement of B1(s; t). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
15.19Nested sequence of T-spline spaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
15.20Local re nement example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
15.21Semi-standard T-splines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
15.22Curve example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
15.23Curvature of a B ezier curve. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
15.24Part of a rectangular mesh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
15.25Part of a triangular mesh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
16.1 Two cubic curves intersecting nine times . . . . . . . . . . . . . . . . . . . . . . . . . 199
17.1 Intersection of Two Pencils of Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
17.2 Dual Point and Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
17.3 Pencil of Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
17.4 Pencil of Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
17.5 Pencil of Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
17.6 Intersection of Two Pencils of Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
17.7 Rational Quadratic Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
17.8 Quadratic B ezier Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
17.9 Cubic Moving Line which Follow Linear and Quadratic Moving Points . . . . . . . . 217
17.10Intersection of Linear and Quadratic Moving Lines . . . . . . . . . . . . . . . . . . . 218
17.11Cubic B ezier Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
17.12Quartic B ezier Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
17.13Quartic B ezier Curve with a Triple Point . . . . . . . . . . . . . . . . . . . . . . . . 223
17.14Envelope curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
17.15Dual and Reciprocal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
17.16Cusp , In
ection Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
17.17Crunode , Double Tangent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
18.1 Irreducible Cubic Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
18.2 Crunode: x3 + 9x2 12y2 = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
18.3 Cusp: x3 3y2 = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
18.4 Acnode: x3 3x2 3y2 = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
18.5 Circle and Hyperbola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
LIST OF FIGURES xv
18.6 Parametrizing a Circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
18.7 Parametrizing a Cubic Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Chapter 1
Introduction
Computer aided geometric design (CAGD) concerns itself with the mathematical description of
shape for use in computer graphics, manufacturing, or analysis. It draws upon the elds of geometry,
computer graphics, numerical analysis, approximation theory, data structures and computer algebra.
CAGD is a young eld. The rst work in this eld began in the mid 1960s. The term computer
aided geometric design was coined in 1974 by R.E. Barnhill and R.F. Riesenfeld in connection with
a conference at the University of Utah.
This chapter presents some basic background material such as vector algebra, equations for lines
and conic sections, homogeneous coordinates.
1.1 Points, Vectors and Coordinate Systems
Consider the simple problem of writing a computer program which nds the area of any triangle.
We must rst decide how to uniquely describe the triangle. One way might be to provide the lengths
l1, l2, l3 of the three sides, from which Heron's formula yields
Area =
p
s(s l1)(s l2)(s l3); s = l1 + l2 + l3
2 :
An alternative way to describe the triangle is in terms of its vertices. But while the lengths of
the sides of a triangle are independent of its position, we can specify the vertices to our computer
program only with reference to some coordinate system | which can be de ned simply as any
method for representing points with numbers.
Note that a coordinate system is an arti cial devise which we arbitrarily impose for the purposes
at hand. Imagine a triangle cut out of paper and lying on a
at table in the middle of a room.
We could de ne a Cartesian coordinate system whose origin lies in a corner of the room, and whose
coordinate axes lie along the three room edges which meet at the corner. We would further specify
the unit of measurement, say centimeters. Then, each vertex of our triangle could be described in
terms of its respective distance from the two walls containing the origin and from the
oor. These
distances are the Cartesian coordinates (x; y; z) of the vertex with respect to the coordinate system
we de ned.
Vectors A vector can be pictured as a line segment of de nite length with an arrow on one end.
We will call the end with the arrow the tip or head and the other end the tail.
Two vectors are equivalent if they have the same length, are parallel, and point in the same
direction (have the same sense) as shown in Figure 1.1. For a given coordinate system, we can
1
2 Points, Vectors and Coordinate Systems
V
V
V
V
Figure 1.1: Equivalent Vectors
describe a three-dimensional vector in the form (a; b; c) where a (or b or c) is the distance in the x
(or y or z) direction from the tail to the tip of the vector.
Z
X
Y
k
i
j
(a) Unit Vectors.
x
y
z
a i
b j
c k
V = a i+ b j + c k
(b) Vector in Component Form.
Figure 1.2: Vectors.
Unit Vectors The symbols i, j, and k denote vectors of \unit length" (based on the unit of
measurement of the coordinate system) which point in the positive x, y, and z directions respectively
(see Figure 1.2.a).
Unit vectors allow us to express a vector in component form (see Figure 1.2.b):
P = (a; b; c) = ai + bj + ck:
An expression such as (x; y; z) can be called a triple of numbers. In general, an expression
(x1; x2; : : : ; xn) is an n-tuple, or simply a tuple. As we have seen, a triple can signify either a point
or a vector.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Vector Algebra 3
Relative Position Vectors Given two points P1 and P2, we can de ne
P2=1 = P2 P1
as the vector pointing from P1 to P2. This notation P2=1 is widely used in engineering mechanics,
and can be read \the position of point P2 relative to P1"
In our diagrams, points will be drawn simply as dots or small circles, and vectors as line segments
with single arrows. Vectors and points will both be denoted by bold faced type.
1.2 Vector Algebra
Given two vectors P1 = (x1; y1; z1) and P2 = (x2; y2; z2), the following operations are de ned:
Addition:
P1 + P2 = P2 + P1 = (x1 + x2; y1 + y2; z1 + z2)
A
B
A+B
B
A
B+A=A+B
(a) Vector Addition.
A
-B
A-B
(b) Vector Subtraction.
Figure 1.3: Vector Addition and Subtraction.
Subtraction:
P1 P2 = (x1 x2; y1 y2; z1 z2)
Scalar multiplication:
cP1 = (cx1; cy1; cz1)
Length of a Vector
jP1j =
q
x21
+ y2
1 + z2
1
A vector of length one is called a unit vector.
P1
jP1j
is a unit vector in the direction of P1
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
4 Vector Algebra
Dot Product The dot product of two vectors is de ned
P1 P2 = jP1jjP2j cos (1.1)
where is the angle between the two vectors. Since the unit vectors i; j; k are mutually perpendicular,
i i = j j = k k = 1
i j = i k = j k = 0:
The dot product obeys the distributive law
P1 (P2 + P3) = P1 P2 + P1 P3;
As a result of the distributive law,
P1 P2 = (x1i + y1j + z1k) (x2i + y2j + z2k)
= (x1 x2 + y1 y2 + z1 z2) (1.2)
(1.2) enables us to compute the angle between any two vectors. From (1.1),
= cos1
P1 P2
jP1jjP2j
:
Example. Find the angle between vectors (1; 2; 4) and (3;4; 2).
Answer.
= cos1
P1 P2
jP1jjP2j
= cos1
(1; 2; 4) (3;4; 2)
j(1; 2; 4)jj(3;4; 2)j
= cos1
3
p
21
p
29
83:02
Figure 1.4: Vector Projection
An important application of dot products is in computing the projection of one vector onto
another vector. As illustrated in Figure 1.4, vector R is the projection of vector P onto vector Q.
Since
jRj = jPj cos =
P Q
jQj
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Vector Algebra 5
we have
R = jRj
Q
jQj
=
P Q
jQj
Q
jQj
=
P Q
Q Q
Q:
Example. Find the projection of P = (3; 2; 1) onto Q = (3; 6; 6).
Answer.
R =
P Q
Q Q
Q
=
(3; 2; 1) (3; 6; 6)
(3; 6; 6) (3; 6; 6)
(3; 6; 6)
=
27
81
(3; 6; 6)
= (1; 2; 2)
Cross Product: The cross product P1 P2 is a vector whose magnitude is
jP1 P2j = jP1jjP2j sin
(where again is the angle between P1 and P2), and whose direction is mutually perpendicular to
P1 and P2 with a sense de ned by the right hand rule as follows. Point your ngers in the direction
of P1 and orient your hand such that when you close your st your ngers pass through the direction
of P2. Then your right thumb points in the sense of P1 P2.
From this basic de nition, one can verify that
P1 P2 = P2 P1;
i j = k; j k = i; k i = j
j i = k; k j = i; i k = j:
The cross product obeys the distributive law
P1 (P2 + P3) = P1 P2 + P1 P3:
This leads to the important relation
P1 P2 = (x1i + y1j + z1k) (x2i + y2j + z2k)
= (y1z2 y2z1; x2z1 x1z2; x1y2 x2y1)
=
i j k
x1 y1 z1
x2 y2 z2
(1.3)
Area of a Triangle. Cross products have many important uses, such as nding a vector which is
mutually perpendicular to two other vectors and nding the area of a triangle which is de ned by
three points P1, P2, P3.
Area =
1
2jP1=2jjP1=3j sin 1 =
1
2jP1=2 P1=3j (1.4)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
6 Rotation About an Arbitrary Axis
For example, the area of a triangle with vertices P1 = (1; 1; 1), P2 = (2; 4; 5), P3 = (3; 2; 6) is
Area =
1
2jP1=2 P1=3j
=
1
2j(1; 3; 4) (2; 1; 5)j
=
1
2j(11; 3;5)j =
1
2
p
112 + 32 + (5)2
6:225
1.2.1 Points vs. Vectors
A point is a geometric entity which connotes position, whereas a vector connotes direction and mag-
nitude. From a purely mathematical viewpoint, there are good reasons for carefully distinguishing
between triples that refer to points and triples that signify vectors [Goldman '85]. However, no
problem arises if we recognize that a triple connoting a point can be interpreted as a vector from
the origin to the point. Thus, we could call a point an absolute position vector and the di erence
between two points a relative position vector. These phrases are often used in engineering mechanics,
where vectors are used to express quantities other than position, such as velocity or acceleration.
1.3 Rotation About an Arbitrary Axis
P !
P’
B
n
x
y
z
Figure 1.5: Rotation about an Arbitrary Axis
The problem of computing a rotation about an arbitrary axis is fundamental to CAGD and
computer graphics. The standard solution to this problem as presented in most textbooks on com-
puter graphics involves the concatenation of seven 4 4 matrices. We present here a straightforward
solution comprised of the four simple vector computations in equations (1.6) through (1.9) | a
compelling example of the power of vector algebra.
Figure 1.5 shows a point P which we want to rotate an angle about an axis that passes through
B with a direction de ned by unit vector n. So, given the angle , the unit vector n, and Cartesian
coordinates for the points P and B, we want to nd Cartesian coordinates for the point P0.
The key insight needed is shown in Figure 1.6.a.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Rotation About an Arbitrary Axis 7
C
! u
v
r
ucos!
v sin!
(a) Key Insight.
C P
!
v P’
r
u
B
n
x
y
z
(b) Labels.
Figure 1.6: Rotation about an Arbitrary Axis Using Vector Algebra.
Let u and v be any two three-dimensional vectors that satisfy u v = 0 (that is, they are
perpendicular) and juj = jvj 6= 0 (that is, they are they same length but not necessarily unit
vectors). We want to nd a vector r that is obtained by rotating u an angle in the plane de ned
by u and v. As suggested in Figure 1.6,
r = u cos + v sin : (1.5)
With that insight, it is easy to compute a rotation about an arbitrary axis. Note that (C B)
is the projection of vector (P B) onto the unit vector n. Referring to the labels in Figure 1.6.b,
we compute
C = B + [(P B) n]n: (1.6)
u = P C (1.7)
v = n u (1.8)
Then, r is computed using equation (3.1), and
P0 = C + r: (1.9)
Example
Find the coordinates of a point (5; 7; 3) after it is rotated an angle = 90 about an axis that points
in the direction (2; 1; 2) and that passes through the point (1; 1; 1).
Answer:
n = ( 2
3 ; 1
3 ; 2
3 ).
C = B + [(P B) n]n
= (1; 1; 1) + [((5; 7; 3) (1; 1; 1)) (
2
3;
1
3;
2
3
)](
2
3;
1
3;
2
3
)
= (5; 3; 5)
(1.10)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
8 Rotation About an Arbitrary Axis
u = P C = (0; 4;2)
v = n u = (
10
3 ;
4
3;
8
3
):
r = u cos + v sin = u 0 + v 1 = v:
1.3.1 Matrix Form
It is possible to take these simple vector equations and to create from them a single 4 4 transfor-
mation matrix for rotation about an arbitrary axis. While this is useful to do in computer graphics
(where, in fact, this matrix is typically created by concatenating seven 4 4 matrices), the simple
vector equations we just derived su ce for many applications. The derivation of this matrix is
presented here for your possible reference. We will not be using it in this course.
Let P = (x; y; z), P0 = (x0; y0; z0), B = (Bx;By;Bz), and n = (nx; ny; nz). We seek a 4 4
matrix M such that
M
8>><
>>:
x
y
z
1
9>>=
>>;
=
8>><
>>:
x0
y0
z0
1
9>>=
>>;
(Cx;Cy;Cz) = (Bx;By;Bz) + [xnx + yny + znz B n](nx; ny; nz) (1.11)
Cx = xn2
x + ynxny + znxnz + Bx (B n)nx (1.12)
Cy = xnxny + yn2
y + znynz + By (B n)ny (1.13)
Cz = xnxnz + ynynz + zn2z
+ Bz (B n)nz (1.14)
u = (x; y; z) (Cx;Cy;Cz) (1.15)
ux = x(1 n2
x) ynxny znxnz + (B n)nx Bx (1.16)
uy = xnxny + y(1 n2
y) znynz + (B n)ny By (1.17)
uz = xnxnz ynynz + z(1 n2z
) + (B n)nz Bz (1.18)
vx = nyuz nzuy (1.19)
vy = nzux nxuz (1.20)
vz = nxuy nyux (1.21)
rx = ux cos + (nyuz nzuy) sin (1.22)
ry = uy cos + (nzux nxuz) sin (1.23)
rz = uz cos + (nxuy nyux) sin (1.24)
(x0; y0; z0) = (Cx + rx;Cy + ry;Cz + rz) (1.25)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Parametric, Implicit, and Explicit Equations 9
x0 = xn2
x + ynxny + znxnz + Bx (B n)nx + (1.26)
[x(1 n2
x) ynxny znxnz + (B n)nx Bx] cos +
ny[xnxnz ynynz + z(1 n2z
) + (B n)nz Bz] sin
nz[xnxny + y(1 n2
y) znynz + (B n)ny By] sin
x0 = x[n2
x + (1 n2
x) cos ] + y[nxny(1 cos ) nz sin ]
+ z[nxnz(1 cos ) + ny sin ] + (Bx (B n)nx)(1 cos ) + (nzBy nyBz) sin :
Since n2
x + n2
y + n2z
= 1, (1 n2
x) = n2
y + n2z
. In like manner we can come up with an expression for
y0 and z0, and our matrix M is thus
2
664
n2
x + (n2
y + n2z
) cos nxny(1 cos ) nz sin nxnz(1 cos ) + ny sin T1
nxny(1 cos ) + nz sin n2
y + (n2
x + n2z
) cos nynz(1 cos ) nx sin T2
nxnz(1 cos ) ny sin nynz(1 cos ) + nx sin n2z
+ (n2
x + n2
y) cos T3
0 0 0 1
3
775
(1.27)
with
T1 = (Bx (B n)nx)(1 cos ) + (nzBy nyBz) sin
T2 = (By (B n)ny)(1 cos ) + (nxBz nzBx) sin
T3 = (Bz (B n)nz)(1 cos ) + (nyBx nxBy) sin
1.4 Parametric, Implicit, and Explicit Equations
There are basically three types of equations that can be used to de ne a planar curve: parametric,
implicit, and explicit. The parametric equation of a plane curve takes the form
x = x(t)
w(t) y = y(t)
w(t) : (1.28)
The implicit equation of a curve is of the form
f(x; y) = 0: (1.29)
An explicit equation of a curve is a special case of both the parametric and implicit forms:
y = f(x): (1.30)
In these notes, we restrict ourselves to the case where the functions x(t), y(t), w(t), f(x) and f(x; y)
are polynomials.
Any curve that can be expressed parametrically as in equation (1.28) is referred to as a rational
curve. In the classical algebraic geometry literature, a rational curve is sometimes called a unicursal
curve, which means that it can be sketched in its entirety without removing one's pencil from the
paper. In computer aided geometric design, rational curves are often called rational parametric
curves. The case where w(t) 1 is called a polynomial parametric curve (or a non-rational
parametric curve). A curve that can be expressed in the form of equation (1.29) is known as a
planar algebraic curve.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
10 Lines
The parametric equation of a curve has the advantage of being able to quickly compute the (x; y)
coordinates of points on the curve for plotting purposes. Also, it is simple to de ne a curve segment
by restricting the parameter t to a nite range, for example 0 t 1. On the other hand, the
implicit equation of a curve enables one to easily determine whether a given point lies on the curve,
or if not, which side of the curve it lies on. Chapter 16 shows that it is always possible to compute
an implicit equation for a parametric curve. It is trivial to convert en explicit equation of a curve
into a parametric equation (x = t, y = y(x)) or into an implicit equation (f(x) y = 0). However,
a curve de ned by an implicit or parametric equation cannot in general be converted into explicit
form.
A rational surface is one that can be expressed
x = x(s; t)
w(s; t) y = y(s; t)
w(s; t) z = z(s; t)
w(s; t)
(1.31)
where x(s; t), y(s; t), z(s; t) and w(s; t) are polynomials. Also, a surface that can be expressed by
the equation
f(x; y; z) = 0 (1.32)
where f(x; y; z) is a polynomial is called an algebraic surface.
A rational space curve is one that can be expressed by the parametric equations
x = x(t)
w(t) y = y(t)
w(t) z = z(t)
w(t) : (1.33)
The curve of intersection of two algebraic surfaces is an algebraic space curve.
1.5 Lines
The simplest case of a curve is a line. Even so, there are several di erent equations that can be used
to represent lines.
1.5.1 Parametric equations of lines
Linear parametric equation
A line can be written in parametric form as follows:
x = a0 + a1t; y = b0 + b1t
In vector form,
P(t) =
x(t)
y(t)
=
a0 + a1t
b0 + b1t
= A0 + A1t: (1.34)
In this equation, A0 is a point on the line and A1 is the direction of the line (see Figure 1.7)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Lines 11
A0
A1
Figure 1.7: Line given by A0 + A1t:
P0
t = t0
P1
t = t1
(a) Line given by P(t) = (t1t)P0+(tt0)P1
t1t0
.
P0
t = 1
P1
t = 4
t = 2
1/3
2/3
(b) A ne Example.
Figure 1.8: A ne parametric equation of a line.
A ne parametric equation of a line
A line can also be expressed
P(t) =
(t1 t)P0 + (t t0)P1
t1 t0
(1.35)
where P0 and P1 are two points on the line and t0 and t1 are any parameter values. Note that
P(t0) = P0 and P(t1) = P1. Note in Figure 1.8.a that the line segment P0{P1 is de ned by
restricting the parameter:
t0 t t1:
Sometimes this is expressed by saying that the line segment is the portion of the line in the parameter
interval or domain [t0; t1].
We will see that the line in Figure 1.8.a is actually a degree one B ezier curve. Most commonly,
we have t0 = 0 and t1 = 1 in which case
P(t) = (1 t)P0 + tP1: (1.36)
Equation 1.36 is called an a ne equation, whereas equation 1.34 is called a linear equation.
An a ne equation is coordinate system independent, and is mainly concerned with ratios and
proportions. An a ne equation can be thought of as answering the question: \If a line is de ned
through two points P0 and P1, and if point P0 corresponds to parameter value t0 and point P1
corresponds to parameter value t1, what point corresponds to an arbitrary parameter value t?"
Figure 1.8.b shows a line on which P0 corresponds to parameter t = t0 = 1 and P1 is assigned
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
12 Lines
parameter value t = t1 = 4. For example, the point corresponding to t = 2 is one third of the way
from P0 to P1.
Note that an a ne equation can be derived from any two points on a line, given the parameter
values for those points. If P( ) is the point corresponding to parameter value t = and if P( )
is the point corresponding to parameter value t = ( 6= ), then the point corresponding to
parameter value
is
P(
) = P( ) +
[P( ) P( )] =
(
)P( ) + (
)P( )
Rational parametric equations
A line can also be de ned using the following parametric equations:
x = a0 + a1t
d0 + d1t
; y = b0 + b1t
d0 + d1t
: (1.37)
This is often called rational or fractional parametric equations.
Recall that the homogeneous Cartesian coordinates (X; Y;W) of a point are related to its Carte-
sian coordinates by
(x; y) = ( X
W
;
Y
W
):
Thus, we can rewrite equation 1.37 as
X = a0 + a1t; Y = b0 + b1t; W = d0 + d1t:
This equation can be further re-written in terms of homogeneous parameters (T;U) where t = T
U .
Thus,
X = a0 + a1
T
U
; Y = b0 + b1
T
U
; W = d0 + d1
T
U
:
But since we can scale (X; Y;W) without changing the point (x; y) which it denotes, we can scale
by U to give
X = a0U + a1T; Y = b0U + b1T; W = d0U + d1T:
1.5.2 Implicit equations of lines
A line can also be expressed using an implicit equation:
f(x; y) = ax + by + c = 0; or F(X; Y;W) = aX + bY + cW = 0:
The line de ned by an implicit equation is the set of all points which satisfy the equation f(x; y) = 0.
An implicit equation for a line can be derived given a point P0 = (x0; y0) on the line and the
normal vector n = ai + bj. As shown in Figure 1.9, a point P = (x; y) is on this line if
(P P0) n = 0
from which
f(x; y) = (x x0; y y0) (a; b) = ax + by (ax0 + by0) = 0: (1.38)
From equation 1.38, a line whose implicit equation is ax+by+c = 0 has the normal vector n = ai+bj.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Lines 13
P - P0
P
n
P0
line
(P - P0) • n = 0
Figure 1.9: Line de ned by point and normal.
Implicit equation of a line through two points
Three points (X1; Y1;W1), (X2; Y2;W2) and (X3; Y3;W3) are collinear if
X1 Y1 W1
X2 Y2 W2
X3 Y3 W3
= 0:
Thus, the equation of the line through two points is
X Y W
X1 Y1 W1
X2 Y2 W2
= (Y1W2 Y2W1)X + (X2W1 X1W2)Y + (X1Y2 X2Y1)W = 0:
1.5.3 Distance from a point to a line
If n = ai+bj is a unit vector (that is, if a2+b2 = 1), then the value f(x; y) in equation 1.38 indicates
the signed perpendicular distance of a point (x; y) to the line. This can be seen from equation 1.38
and Figure 1.9. The dot product (PP0) n is the length of the projection of vector (PP0) onto
the unit normal n, which is the perpendicular distance from P to the line.
Since the coe cients of an implicit equation can be uniformly scaled without changing the curve
(because if f(x; y) = 0, then c f(x; y) = 0 also), the implicit equation of a line can always be
normalized:
f(x; y) = a0x + b0y + c0 = a
p
a2 + b2
x + b
p
a2 + b2
y + c
p
a2 + b2
= 0:
Then, f(x; y) is the signed distance from the point (x; y) to the line, with all points on one side
of the line having f(x; y) > 0 and the other side having f(x; y) < 0. Note that jc0j = jf(0; 0)j is
the distance from the origin to the line. Thus, if c = 0, the line passes through the origin. The
coe cients a0 and b0 relate to the slope of the line. Referring to Figure 1.10, a0 = cos( ), b0 = sin( ),
and c0 = p.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
14 Conic Sections
p
q
x
y
Figure 1.10: Normalized line equation.
1.6 Conic Sections
A conic section (or, simply conic) is any degree two curve. Any conic can be expressed using a
degree two implicit equation:
ax2 + bxy + cy2 + dx + ey + f = 0
or, in homogeneous form:
aX2 + bXY + cY 2 + dXW + eYW + fW2 = 0: (1.39)
Conics can be classi ed as hyperbolas, parabolas and ellipses (of which the circle is a special case).
What distinguishes these cases is the number of real points at which the curve intersects the line
at in nity W = 0. A hyperbola intersects W = 0 in two real points. Those points are located an
in nite distance along the asymptotic directions. A parabola is tangent to the line at in nity, and
thus has two coincident real intersection points. This point is located an in nite distance along the
parabola's axis of symmetry. Ellipses do not intersect the line at in nity at any real point | all real
points on an ellipse are nite.
To determine the number of real points at which a conic intersects the line at in nity, simply
intersect equation 1.39 with the line W = 0 by setting W = 0 to get:
aX2 + bXY + cY 2 = 0
from which
Y
X
= b
p
b2 4ac
2c
:
The two values Y=X are the slopes of the lines pointing to the intersections of the conic with the
line at in nity. Thus, if b2 4ac > 0, there are two distinct real intersections and the conic is a
hyperbola. If b2 4ac = 0, there are two coincident real intersections and the conic is a parabola,
and if b2 4ac < 0, there are no real intersections and the conic is an ellipse. The value b2 4ac is
known as the discriminant of the conic.
1.6.1 Parametric equations of conics
The parametric equation of any conic can be expressed:
x = a2t2 + a1t + a0
d2t2 + d1t + d0
; y = b2t2 + b1t + b0
d2t2 + d1t + d0
:
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Conic Sections 15
or, in homogeneous form,
X = a2T2 + a1TU + a0U2;
Y = b2T2 + b1TU + b0U2;
W = d2T2 + d1TU + d0U2:
It is also possible to classify a conic from its parametric equation. We again identify the points at
which the conic intersects the line at in nity. In the parametric form, the only places at which (x; y)
can be in nitely large is at parameter values of t for which
d2t2 + d1t + d0 = 0:
Thus, we note that d21
4d0d2 serves the same function as the discriminant of the implicit equation.
If d21
4d0d2 > 0, there are two real, distinct values of t at which the conic goes to in nity and
the curve is a hyperbola. If d21
4d0d2 < 0, there are no real values of t at which the conic goes
to in nity and the curve is an ellipse. If d21
4d0d2 = 0, there are two real, identical values of t at
which the conic goes to in nity and the curve is a parabola.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
16 Conic Sections
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Chapter 2
B ezier Curves
B ezier curves are named after their inventor, Dr. Pierre B ezier, an engineer with the Renault car
company who set out in the early 1960's to develop a curve formulation for use in shape design
that would be intuitive enough for designers and artists to use, without requiring a background in
mathematics.
Figure 2.1: Examples of cubic B ezier curves.
Figure 2.1 shows three di erent B ezier curves, with their corresponding control polygons. Each
control polygon is comprised of four control points that are connect with line segments. (These
control polygons are not closed, and might more properly be called polylines.) The beauty of the
B ezier representation is that a B ezier curve mimics the shape of its control polygon. A B ezier
curve passes through its rst and last control points, and is tangent to the control polygon at those
endpoints. An artist can quickly master the process of designing shapes using B ezier curves by
moving the control points, and most 2D drawing systems like Adobe Illustrator use B ezier curves.
Complicated shapes can be created by using a sequence of B ezier curves. Since B ezier curves are
tangent to their control polygons, it is easy to join together two B ezier curves such that they are
tangent continuous. Figure 2.2 shows the outline of a letter \g" created using several B ezier curves.
All PostScript font outlines are de ned using B ezier curves. Hence, as you read these notes, you are
gazing upon B ezier curves!
Although B ezier curves can be used productively by artists who have little mathematical training,
17
18 The Equation of a B ezier Curve
Figure 2.2: Font de nition using B ezier curves.
one of the main objectives in this course is to study the underlying mathematics. These notes attempt
to show that the power and elegance of B ezier curves are matched by the beauty of the underlying
mathematics.
2.1 The Equation of a B ezier Curve
The equation of a B ezier curve is similar to the equation for the center of mass of a set of point
masses. Consider the four masses m0, m1, m2, and m3 in Figure 2.3.a located at points P0, P1, P2,
P3.
P0
P1 P2
P3
P
(a) Center of mass of four points.
P0
P1 P2
P3
(b) Cubic B ezier Curve.
Figure 2.3: B ezier Curves in Terms of Center of Mass.
The equation for the center of mass is
P = m0P0 + m1P1 + m2P2 + m3P3
m0 + m1 + m2 + m3
:
Next, imagine that instead of being xed, constant values, each mass varies as a function of a
parameter t. Speci cally, let
m0(t) = (1 t)3; m1(t) = 3t(1 t)2; m2(t) = 3t2(1 t); m3(t) = t3: (2.1)
Now, for each value of t, the masses assume di erent weights and their center of mass changes
continuously. As t varies between 0 and 1, a curve is swept out by the moving center of mass.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
The Equation of a B ezier Curve 19
Figure 2.3.b shows the B ezier curve that results when the point masses in Figure 2.3.a are taken as
control points. This curve is a cubic B ezier curve | cubic because the mass equations are degree
three polynomials in t.
Notice that the mass equations in (2.1) sum identically to one:
(1 t)3 + 3t(1 t)2 + 3t2(1 t) + t3 = [(1 t) + t]3 = 13 1;
and so we can write the equation of this B ezier curve as P(t) = m0(t)P0 + m1(t)P1 + m2(t)P2 + m3(t)P3.
The mass functions are plotted in the graph in Figure 2.4. Note that when t = 0, m0 = 1 and
m
1
0
0 1
t
m0
m1 m2
m3
Figure 2.4: Cubic B ezier blending functions.
m1 = m2 = m3 = 0. This explains why the curve passes through P0. When t = 1, m3 = 1 and
m0 = m1 = m2 = 0, and the curve passes through point P3.
The variable masses mi(t) are usually called blending functions and, as noted before, the locations
Pi are known as control points. The blending functions, in the case of B ezier curves, are known as
Bernstein polynomials. We will later look at other curves formed with di erent blending functions.
B ezier curves of any degree can be de ned. Figure 2.5 shows sample curves of degree one through
four. A degree n B ezier curve has n+1 control points whose blending functions are denoted Bn
i (t),
Degree 1 Degree 2
Degree 3 Degree 4
Figure 2.5: B ezier curves of various degree.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
20 B ezier Curves over Arbitrary Parameter Intervals
where
Bn
i (t) =
n
i
(1 t)niti; i = 0; 1; :::; n:
Recall that
n
i
= n!
i!(n i)! :
n
i
is spoken \n { choose { i" and is called a binomial coe cient because it arises in the binomial
expansion
(a + b)n =
Xn
i=0
n
i
aibni:
In the degree three case, n = 3 and B3
0 = (1t)3, B3
1 = 3t(1t)2, B3
2 = 3t2(1t) and B3
3 = t3.
Bn
i (t) is also referred to as the ith Bernstein polynomial of degree n. The equation of a B ezier curve
is thus:
P(t) =
Xn
i=0
n
i
(1 t)nitiPi: (2.2)
2.2 B ezier Curves over Arbitrary Parameter Intervals
Equation 2.2 gives the equation of a B ezier curve which starts at t = 0 and ends at t = 1. It is
useful, especially when tting together a string of B ezier curves, to allow an arbitrary parameter
interval:
t 2 [t0; t1]
such that P(t0) = P0 and P(t1) = Pn. We will denote the B ezier curve de ned over an arbitrary
parameter interval by P[t0;t1](t): It's equation is a modi cation of (2.2):
P[t0;t1](t) =
Pn
i=0
n
i
(t1 t)ni(t t0)iPi
(t1 t0)n =
Xn
i=0
n
i
( t1 t
t1 t0
)ni( t t0
t1 t0
)iPi: (2.3)
If no parameter interval is speci ed, it is assumed to be [0; 1]. That is,
P(t) = P[0;1](t):
2.3 The de Casteljau Algorithm
The de Casteljau algorithm describes how to subdivide a B ezier curve P[t0;t2] into two segments
P[t0;t1] and P[t1;t2] whose union is equivalent to P[t0;t2]. This algorithm was devised in 1959 by Paul
de Casteljau, a French mathematician at the Citroen automobile company. It is an example of a
geometric construction algorithm.
To facilitate our description of the algorithm, we label the control points of a cubic B ezier curve
P[t0;t2] with P00
, P01
, P02
, and P03
as illustrated in Figure 2.6. The algorithm involves computing the
sequence of points
Pj
i = (1 )Pj1
i + Pj1
i+1 ; j = 1; : : : ; n; i = 0; : : : ; n j: (2.4)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
The de Casteljau Algorithm 21
P0
0
P1
0
P2
0
P3
0
P0
1
P1
1
P2
1
P0
2
P1
2
P0
3
! = .4
P0
0
P1
0
P2
0
P3
0
P0
1
P1
1
P2
1
P0
2
P1
2
P0
3
! = .6
Figure 2.6: Subdividing a cubic B ezier curve.
where = t1t0
t2t0
. Then, the control points for P[t0;t1](t) are P00
;P10
;P20
; : : : ;Pn0
and the control
points for P[t1;t2](t) are Pn0
;Pn1
1 ;Pn2
2 ; : : : ;P0
n. Although our example is for a cubic B ezier curve
(n = 3), the algorithm works for any degree.
A practical application of the de Casteljau algorithm is that it provides a numerically stable means
of computing the coordinates and tangent vector of any point along the curve, since P(t1) = Pn0
and the tangent vector is Pn1
1 Pn1
0 .
Figure 2.7 shows that when a B ezier curve is repeatedly subdivided, the collection of control
polygons converge to the curve. Thus, one way of plotting a B ezier curve is to simply subdivide it
1 curve 2 curves
4 curves 8 curves
Figure 2.7: Recursively subdividing a quadratic B ezier curve.
an appropriate number of times and plot the control polygons (although a more e cient way is to
use Horner's algorithm (see Chapter 3) or forward di erencing (see Chapter 4)).
The de Casteljau algorithm works even if 62 [0; 1], which is equivalent to t1 62 [t0; t2]. Fig. 2.8
shows a quadratic B ezier curve \subdivided" at = 2. The de Castelau algorithm is numerically
stable as long as the parameter subdivision parameter is within the parameter domain of the curve.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
22 Degree Elevation
P0
0
P1
0
P2
0
P0
1
P1
1
P0
2
! = 2
Figure 2.8: Subdividing a quadratic B ezier curve.
2.4 Degree Elevation
Any degree n B ezier curve can be exactly represented as a B ezier curve of degree n + 1 (and hence,
as a curve of any degree m > n). Given a degree n B ezier curve, the procedure for computing the
control points for the equivalent degree n + 1 B ezier curve is called degree elevation.
We now derive the degree elevation formula, using the identities:
(1 t)Bn
i (t) = (1 t)
n
i
(1 t)niti
=
n
i
(1 t)ni+1ti
=
n
i
n+1
i
n + 1
i
(1 t)ni+1ti
=
n
i
n+1
i
Bn+1
i =
n!
i!(ni)!
(n+1)!
i!(n+1i)!
Bn+1
i
= n!i!(n + 1 i)!
i!(n i)!(n + 1)!Bn+1
i = n!i!(n + 1 i)(n i)!
i!(n i)!(n + 1)n! Bn+1
i
= n + 1 i
n + 1 Bn+1
i (2.5)
and
tBn
i (t) = i + 1
n + 1Bn+1
i+1 (t): (2.6)
Degree elevation is accomplished by simply multiplying the equation of the degree n B ezier curve
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Degree Elevation 23
by [(1 t) + t] = 1:
P(t) = [(1 t) + t]P(t)
= [(1 t) + t]
Xn
i=0
PiBn
i (t)
=
Xn
i=0
Pi[(1 + t)Bn
i (t) + tBn
i (t)]
=
Xn
i=0
Pi[n + 1 i
n + 1 Bn+1
i + i + 1
n + 1Bn+1
i+1 (t)]
=
Xn
i=0
n + 1 i
n + 1
PiBn+1
i +
Xn
i=0
i + 1
n + 1
PiBn+1
i+1 (t)
=
Xn
i=0
n + 1 i
n + 1
PiBn+1
i +
nX+1
i=1
i
n + 1
Pi1Bn+1
i (t)
=
nX+1
i=0
n + 1 i
n + 1
PiBn+1
i +
nX+1
i=0
i
n + 1
Pi1Bn+1
i (t)
=
nX+1
i=0
[
(n + 1 i)Pi + iPi1
n + 1
]Bn+1
i (t)
=
nX+1
i=0
P i
Bn+1
i (t) (2.7)
where
P i
= iPi1 + (1 i)Pi; i = i
n + 1: (2.8)
P0
* P0
1/4
1/2
P1
*
P1
old P2
* P2
P3
*
P4
P * 3
new
(a) Degree Elevation of a Cubic B ezier Curve.
Degree 2 Degree 3 Degree 4
Degree 5 Degree 6 Degree 7
(b) Repeated degree elevation.
Figure 2.9: Degree Elevation of a B ezier Curve.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
24 The Convex Hull Property of B ezier Curves
For the case n = 3, the new control points P i
are:
P 0
= P0
P 1
=
1
4
P0 +
3
4
P1
P 2
=
2
4
P1 +
2
4
P2
P 3
=
3
4
P2 +
1
4
P3
P 4
= P3
Figure 2.9.a illustrates.
If degree elevation is applied repeatedly, as shown in Figure 2.9.b, the control polygon converges
to the curve itself.
2.5 The Convex Hull Property of B ezier Curves
An important property of B ezier curves is that they always lie within the convex hull of their control
points. The convex hull can be envisioned by pounding an imaginary nail into each control point,
stretching an imaginary rubber band so that it surrounds the group of nails, and then collapsing that
rubber band around the nails. The polygon created by that imaginary rubber band is the convex
hull. Figure 2.10 illustrates.
The fact that B ezier curves obey the convex hull property is assured by the center-of-mass
de nition of B ezier curves in Section 2.1. Since all of the control points lie on one side of an edge
of the convex hull, it is impossible for the center of mass of those control points to lie on the other
side of the line,
P0
P1 P2
P3
P0
P1
P2
P3
P0
P2 P1
P3
P0 P1 P2
P3
Figure 2.10: Convex Hull Property
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Distance between Two B ezier Curves 25
2.6 Distance between Two B ezier Curves
The problem often arises of determining how closely a given B ezier curve is approximated by a
second B ezier curve. For example, if a given cubic curve can be adequately represented by a degree
elevated quadratic curve, it might be advantageous to replace the cubic curve with the quadratic.
Given two B ezier curves
P(t) =
Xn
i=0
PiBn
i (t); Q(t) =
Xn
i=0
QiBn
i (t)
the vector P(t) Q(t) between points of equal parameter value on the two curves can itself be
expressed as a B ezier curve
D(t) = P(t) Q(t) =
Xn
i=0
(Pi Qi)Bn
i (t)
whose control points are Di = Pi Qi. The vector from the origin to the point D(t) is P(t)Q(t).
The convex hull property guarantees that the distance between the two curves is bounded by the
largest distance from the origin to any of the control points Di.
P0
P1 P2
P3
Q0
Q1 Q2
Q3
t=1/2
P3-Q3
P2-Q2
P1-Q1
P0-Q0
Figure 2.11: Di erence curve.
This error bound is attractive because it is very easy to compute. However, it is not always a
very tight bound because it is dependent on parametrization.
A more precise statement of the distance between two curves is the Hausdor distance. Given
two curves P[s0;s1](s) and Q[t0;t1](t). The Hausdor distance d(P;Q) is de ned
d(P;Q) = max
s2[s0;s1]
min
t2[t0;t1]
jP(s) Q(t)j
(2.9)
where jP(s)Q(t)j is the Euclidean distance between a point P(s) and the point Q(t). In practice,
it is much more expensive to compute the Hausdor distance than to compute a bound using the
di erence curve in Figure 2.11.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
26 Derivatives
2.7 Derivatives
The parametric derivatives of a B ezier curve can be determined geometrically from its control points.
For a polynomial B ezier curve P[t0;t1](t) of degree n with control points Pi, the rst parametric
derivative can be expressed as a polynomial B ezier curve of degree n 1 with control points Di
where
Di = n
t1 t0
(Pi+1 Pi):
For example, the cubic B ezier curve in Fig. 2.12 has a rst derivative curve as shown. Of course,
P0
P1
P2
P3
P(t)
D0
D1
D2
3(P1-P0)
3(P2-P1)
3(P3-P2)
(0,0) P’(t)
Figure 2.12: Hodograph.
the rst derivative of a parametric curve provides us with a tangent vector. This is illustrated in
Fig. 2.12 for the point t = :3. In this example, t0 = 0 and t1 = 1.
The rst derivative curve is known as a hodograph. We can compute the second derivative of a
B ezier curve by taking the hodograph of the hodograph (or, the second hodograph), etc.
It is interesting to note that if the hodograph passes through the origin, there is a cusp corre-
sponding to that point on the original curve!
Note that the hodograph we have just described relates only to polynomial B ezier curves, not
to rational B ezier curves or any other curve that we will study. The derivative of any other curve
must be computed by di erentiation. For a rational B ezier curve, that di erentiation will involve
the quotient rule. Consequently, the derivative of a degree n rational B ezier curve can be expressed
as a rational B ezier curve of degree 2n. As it turns out, the equations for those control points are
rather messy.
2.8 Three Dimensional B ezier Curves
If B ezier control points are de ned in three dimensional space, the resulting B ezier curve is three
dimensional. Such a curve is sometimes called a space curve, and a two dimensional curve is called
a planar curve. Our discussion of the de Casteljau algorithm, degree elevation, and hodographs
extend to 3D without modi cation.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Rational B ezier Curves 27
Since a degree two B ezier curve is de ned using three control points, every degree two curve is
planar, even if the control points are in a three dimensional coordinate system.
2.9 Rational B ezier Curves
A rational B ezier curve is one for which each control point Pi is assigned a scalar weight. The
equation of a rational B ezier curve is
Pn
i=0 wiBn
P i (t)Pi n
i=0 wiBn
i (t) :
The e ect of changing a control point weight is illustrated in Fig. 2.13. This type of curve is known
P0
P1
P2
P3
w2=0
w2=.5
w2=1
w2=2
w2=5 w2=10
Figure 2.13: Rational B ezier curve.
as a rational B ezier curve, because the blending functions are rational polynomials, or the ratio of
two polynomials. Note that if all weights are 1 (or if all weights are simply the same), a rational
B ezier curve reduces to a polynomial B ezier curve.
Rational B ezier curves have several advantages over polynomial B ezier curves. Clearly, rational
B ezier curves provide more control over the shape of a curve than does a polynomial B ezier curve.
In addition, a perspective drawing of a 3D B ezier curve (polynomial or rational) is a rational B ezier
curve, not a polynomial B ezier curve. Also, rational B ezier curves are needed to exactly express
all conic sections. A degree two polynomial B ezier curve can only represent a parabola. Exact
representation of circles requires rational degree two B ezier curves.
A rational B ezier curve can be interpreted as the perspective projection of a 3-D polynomial
curve. Fig. 2.14 shows two curves: a 3-D curve and a 2-D curve. The 2-D curve lies on the plane
z = 1 and it is de ned as the projection of the 3-D curve onto the plane z = 1. One way to consider
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
28 Rational B ezier Curves
x
y
z
z=1
(x0,y0,1)w0
(x1,y1,1)w1
(x2,y2,1)w2
(x3,y3,1)w3
(x0,y0,1)
(x1,y1,1)
(x2,y2,1)
(x3,y3,1)
z
x
z=1
x iwi
xi
wi
1
Figure 2.14: Rational curve as the projection of a 3-D curve.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Rational B ezier Curves 29
this is to imagine a funny looking cone whose vertex is at the origin and which contains the 3-D
curve. In other words, this cone is the collection of all lines which contain the origin and a point on
the curve. Then, the 2-D rational B ezier curve is the intersection of the cone with the plane z = 1.
What we see here can be viewed as the geometric interpretation of homogeneous coordinates dis-
cussed in Section 7.1.1. The 3D B ezier control points wi(xi; yi; 1) = (xiwi; yiwi;wi) can be thought
of as homogeneous coordinates (X; Y;Z) that correspond to 2D Cartesian coordinates (X
Z ; Y
Z ). If the
2-D rational B ezier curve has control points (xi; yi) with corresponding weights wi, then the homo-
geneous (X; Y;Z) coordinates of the 3-D control points are wi(xi; yi; 1) = (xiwi; yiwi;wi). Denote
points on the 3-D curve using upper case variables (X(t); Y (t);Z(t)) and on the 2-D curve using
lower case variables (x(t); y(t)). Then, any point on the 2-D rational B ezier curve can be computed
by computing the corresponding point on the 3-D curve, (X(t); Y (t);Z(t)), and projecting it to the
plane z = 1 by setting
x(t) = X(t)
Z(t) ; y(t) = Y (t)
Z(t) :
2.9.1 De Casteljau Algorithm and Degree Elevation on Rational B ezier
Curves
The de Casteljau algorithm and degree elevation algorithms for polynomial B ezier curves extend eas-
ily to rational B ezier curves as follows. First, convert the rational B ezier curve into its corresponding
polynomial 3D B ezier curve as discussed in Section 2.9. Next, perform the de Casteljau algorithm
or degree elevation on the 3D polynomial B ezier curve. Finally, map the resulting 3D B ezier curve
back to 2D. The Z coordinates of the control points end up as the weights of the control points for
the 2D rational B ezier curve.
This procedure does not work for hodographs, since the derivative of a rational B ezier curve
requires the use of the quotient rule for di erentiation. However, Section 2.9.2 describes how to
compute the rst derivative at the endpoint of a rational B ezier curve and Section 2.9.3 describes
how to compute the curvature at the endpoint of a rational B ezier curve. Used in conjunction with
the de Casteljau algorithm, this enable us to compute the rst derivative or curvature at any point
on a rational B ezier curve.
2.9.2 First Derivative at the Endpoint of a Rational B ezier Curve
The derivative equation for a rational B ezier involves the quotient rule for derivatives | it does not
work to simply compute the tangent vector and curvature for the three dimensional non-rational
B ezier curve and then project that value to the (x; y) plane. For a degree n rational B ezier curve
P[0;1](t),
x(t) = xn(t)
d(t)
=
w0x0
n
0
(1 t)n + w1x1
n
1
(1 t)n1t + w2x2
n
2
(1 t)n2t2 + : : :
w0
n
0
(1 t)n + w1
n
1
(1 t)n1t + w2
n
2
(1 t)n2t2 + : : :
;
y(t) = yn(t)
d(t)
=
w0y0
n
0
(1 t)n + w1y1
n
1
(1 t)n1t + w2y2
n
2
(1 t)n2t2 + : : :
w0
n
0
(1 t)n + w1
n
1
(1 t)n1t + w2
n
2
(1 t)n2t2 + : : :
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
30 Rational B ezier Curves
the equation for the rst derivative vector at t = 0 must be found by evaluating the following
equations:
x_ (0) = d(0)x_n(0) d_(0)xn(0)
d2(0)
; y_(0) = d(0)y_n(0) d_(0)yn(0)
d2(0)
from which
P0(0) = w1
w0
n(P1 P0): (2.10)
For a rational curve P[t0;t1](t), the rst derivative at t = t0 is:
P0(0) = w1
w0
n
t1 t0
(P1 P0): (2.11)
The second derivative of a rational B ezier curve at its endpoint is
P00(0) = n(n 1)
(t1 t0)2
w2
w0
(P2 P0)
2n
(t1 t0)2
w1
w0
nw1 w0
w0
(P1 P0) (2.12)
2.9.3 Curvature at an Endpoint of a Rational B ezier Curve
The curvature (denoted by ) of a curve is a measure of how sharply it curves. The curvature of a
circle of radius is de ned to be = 1= . A straight line does not curve at all, and its curvature is
zero. For other curves, the curvature is generally di erent at each point on the curve. The meaning
of curvature in this general case is illustrated by Figure 2.15 which shows a B ezier curve and the
osculating circle with respect to a point on the curve. The word \osculate" means to kiss, and the
osculating circle is the circle that \best ts" the curve at a particular point in the following sense.
An arbitrary line that passes through a point on a curve intersects the curve with multiplicity one;
the tangent line at that point intersects the curve with multiplicity two. An osculating circle is a
circle of radius that intersects the curve with multiplicity at least three, and the curvature is
de ned to be = 1= . (See Section 7.3.1 for a description of intersection multiplicity.) is called
the radius of curvature for the curve at that point.
C
ρ
Tangent line
Figure 2.15: Osculating Circle.
In Figure 2.15, the center of the circle, C, is located along the normal line a distance from the
point of contact.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Rational B ezier Curves 31
The equation for the curvature of a parametric curve is
= jx_ y y_x j
(x_ 2 + y_2) 32
where the dots denote di erentiation with respect to the curve parameter. If this equation is applied
to an endpoint of a rational B ezier curve, a beautifully simple and geometrically meaningful equation
results:
(t0) = w0w2
w2
1
n 1
n
h
a2 (2.13)
where n is the degree of the curve and a and h are as shown in Fig. 2.16 (a is the length of the rst
leg of the control polygon, and h is the perpendicular distance from P2 to the rst leg of the control
polygon). Curvature is independent of [t0; t1].
a
h
P0
P1
P2
Figure 2.16: Endpoint curvature.
While is is mathematically possible to write down an equation for the rst derivative vector and
for the curvature of a rational B ezier curve as a function of t, such equations would be extremely
complicated. The best way to nd the curvature or rst derivative vector at an arbitrary point
along a rational B ezier curve is to rst perform the de Casteljau algorithm (Section 2.3) to make
the desired point an endpoint of the curve, and then apply (2.11) or (2.13).
Example A rational quadratic B ezier curve has control points and weights:
P0 = (0; 0); w0 = 1; P1 = (4; 3); w1 = 2; P2 = (0; 5); w2 = 4:
What is the curvature at t = 0?
Solution
The distance equation for the line P0 P1 is 3
5x 4
5y, so plugging the Cartesian coordinates of
P2 into this distance equation give h = 4. The value of a is found as the distance from P0 to P1,
which is
p
42 + 32 = 5. So, the curvature is
(0) = w0w2
w2
1
n 1
n
h
a2 =
1 4
22
1
2
4
52 =
2
25
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
32 Continuity
2.10 Continuity
Two curve segments P[t0;t1] and Q[t1;t2] are said to be Ck continuous (or, to have kth order parametric
continuity) if
P(t1) = Q(t1); P0(t1) = Q0(t1); : : : ; P(k)(t1) = Q(k)(t1): (2.14)
Thus, C0 means simply that the two adjacent curves share a common endpoint. C1 means that the
two curves not only share the same endpoint, but also that they have the same tangent vector at
their shared endpoint, in magnitude as well as in direction. C2 means that two curves are C1 and
in addition that they have the same second order parametric derivatives at their shared endpoint,
both in magnitude and in direction.
In Fig. 2.17, the two curves P[t0;t1](t) and Q[t1;t2](t) are at least C0 because p3 q0. Furthermore,
p0
p1
p2 p3 q0
q1
q2
q3
Figure 2.17: C2 B ezier curves.
they are C1 if
3
t1 t0
(p3 p2) =
3
t2 t1
(q1 q0):
They are C2 if they are C1 and
6
(t1 t0)2 (p3 2p2 + p1) =
6
(t2 t1)2 (q2 2q1 + q0):
A second method for describing the continuity of two curves, that is independent of their
parametrization, is called geometric continuity and is denoted Gk. The conditions for geometric
continuity (also known as visual continuity) are less strict than for parametric continuity. For G0
continuity, we simply require that the two curves have a common endpoint, but we do not require
that they have the same parameter value at that common point. For G1, we require that line seg-
ments p2 p3 and q0 q1 are collinear, but they need not be of equal length. This means that
they have a common tangent line, though the magnitude of the tangent vector may be di erent. G2
(second order geometric continuity) means that the two neighboring curves have the same tangent
line and also the same center of curvature at their common boundary. A general de nition of Gn is
that two curves that are Gn can be reparametrized (see Section 2.12) to make them be Cn. Two
curves which are Cn are also Gn, as long as (2.15) holds.
P(t1) = Q(t1); P0(t1) = Q0(t1) 6= 0; : : : ; P(k)(t1) = Q(k)(t1) 6= 0: (2.15)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Circular Arcs 33
Second order continuity (C2 or G2) is often desirable for both physical and aesthetic reasons.
One reason that cubic NURBS curves and surfaces are an industry standard in CAD is that they
are C2. Two surfaces that are G1 but not G2 do not have smooth re
ection lines. Thus, a car body
made up of G1 surfaces will not look smooth in a show room. Railroad cars will jerk where G1
curves meet.
2.11 Circular Arcs
Circular arcs can be exactly represented using rational B ezier curves. Figure 2.18 shows a circular
!
P1; w1= cos!/2
P0; w0= 1
P2; w2= 1
d
r
!
Q1; w1= (1 + 2cos!/2)/3
Q0; w0= 1
Q2; w2= (1 + 2cos!/2)/3
Q3; w3= 1
e
e
r
Figure 2.18: Circular arcs.
arc as both a degree two and a degree three rational B ezier curve. Of course, the control polygons
are tangent to the circle. The degree three case is a simple degree elevation of the degree two case.
The length e is given by
e =
2 sin
2
1 + 2 cos
2
r:
The degree two case has trouble when approaches 180 since P1 moves to in nity, although this
can be remedied by just using homogeneous coordinates. The degree three case has the advantage
that it can represent a larger arc, but even here the length e goes to in nity as approaches 240 .
For large arcs, a simple solution is to just cut the arc in half and use two cubic B ezier curves. A
complete circle can be represented as a degree ve B ezier curve as shown in Figure 2.19. Here, the
weights are w0 = w5 = 1 and w1 = w2 = w3 = w4 = 1
5 .
2.12 Reparametrization of B ezier Curves
Reparametrization of a curve means to change how a curve is parametrized, i.e., to change which
parameter value is assigned to each point on the curve. Reparametrization can be performed by a
parameter substitution. Given a parametric curve P(t), if we make the substitution t = f(s), we
end up with a curve Q(s) which is geometrically identical to P(t). For example, let
P(t) = (t2 + t 1; 2t2 t + 3); t = 2s + 1
yields
Q(s) = ((2s + 1)2 + (2s + 1) 1; 2(2s + 1)2 (2s + 1) + 3) = (4s2 + 6s + 1; 8s2 + 6s + 4):
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
34 Reparametrization of B ezier Curves
p0 = (0,0) p1 = (4,0)
p 3 = (-2,4) p 2 = (2,4)
p4 = (-4,0) p5 = (0,0)
Figure 2.19: Circle as Degree 5 Rational B ezier Curve.
The curves P(t) and Q(s) consist of the same points (if the domains are in nite) but the correspon-
dence between parameter values and points on the curve are di erent.
A simple (and obvious) way to reparametrize a B ezier curve P[t0;t1](t) is to simply change the
values of t0 and t1 without changing the control points. Thus, two curves P[t0;t1](t) and Q[s0;s1](s)
that have the same degree, control point positions, and weights, but for which t0 6= s0 and/or t1 6= s1
are reparametrizations of each other. The reparametrization function is
t = t0s1 s0t1
s1 s0
+ t1 t0
s1 s0
s; or s = s0t1 t0s1
t1 t0
+ s1 s0
t1 t0
t:
Example
B ezier curves P[0;1](t) and Q[5;9](s) have the same degree, control point positions, and weights. The
curves look the same, but have di erent parametrizations. For example,
P(0) = Q(5); P(1) = Q(9); P(:5) = Q(7):
In general,
P(t) Q(5 + 4t) and Q(s) P(
5
4
+
1
4s):
A rational parametric curve can be reparametrized with the substitution t = f(u)=g(u). In
this case, it is possible to perform a rational-linear reparametrization which does not change the
endpoints of the curve segment. If we let
t = a(1 u) + bu
c(1 u) + du
and want u = 0 when t = 0 and u = 1 when t = 1, then a = 0 and b = d. Since we can scale then
numerator and denominator without a ecting the reparametrization, set c = 1 and we are left with
t = bu
(1 u) + bu
A rational B ezier curve
X(t) =
n
0
w0P0(1 t)n +
n
1
w1P1(1 t)n1t + ::: +
n
n
wnPntn
n
0
w0(1 t)n +
n
1
w1(1 t)n1t + ::: +
n
n
wntn
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Advantages of Rational B ezier Curves 35
can be raparametrized without changing its endpoints by making the substitutions
t = bu
(1 u) + bu
; (1 t) =
(1 u)
(1 u) + bu
:
After multiplying numerator and denominator by ((1 u) + bu)n, we obtain
X(u) =
n
0
(b0w0)P0(1 u)n +
n
1
(b1w1)P1(1 u)n1u + ::: +
n
n
(bnwn)Pnun
n
0
b0w0(1 u)n +
n
1
b1w1(1 u)n1u + ::: +
n
n
bnwnun
In other words, if we scale the weights wi by bi, the curve will not be changed!
Negative Weights
Normally, negative weights are discouraged for B ezier curves because they can cause a violation
of the convex hull property. However, an interesting situation arises if we choose b = 1 for the
rational reparametrization: the signs of the weights alternate, and the curve for u 2 [0; 1] is the
curve t 2 (1; 0] [ [1;1). If the original curve is a quarter circle, the reparametrized curve will be
the rest of the circle, as shown in Figure 2.20.
P0= (1,0), w=1
P2= (1,0), w=2 P1= (1,1), w=1
(a) Quarter circle.
P0= (1,0), w=1
P1= (1,1), w=-1
P2= (1,0), w=2
(b) After reparametrization with b = 1.
Figure 2.20: Circle with negative weight.
2.13 Advantages of Rational B ezier Curves
As we have seen, rational B ezier curves have several advantages over polynomial B ezier curves. We
here emphasize them.
1. Rational B ezier curves can represent conic sections exactly.
2. If you perform a perspective projection of a B ezier curve (either a polynomial or rational), the
result is a rational B ezier curve.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
36 Explicit B ezier Curves
3. Rational B ezier curves permit some additional shape control: by changing the weights, you
change the shape of the curve.
4. It is possible to reparametrize the curve by simply changing the weights in a speci c manner.
2.14 Explicit B ezier Curves
An explicit B ezier curve P[t0;t1](t) is one for which x t. For a polynomial B ezier curve, this
happens when the x-coordinates of the control points are evenly spaced between t0 and t1. That is,
Pi = ( t0(ni)+t1i
n ; yi); i = 0; : : : ; n. Such a B ezier curve takes on the form of a function
x = t
y = f(t)
or simply
y = f(x):
An explicit B ezier curve is sometimes called a non-parametric B ezier curve. It is just a polynomial
function expressed in the Bernstein polynomial basis. Figure 2.21 shows a degree ve explicit B ezier
curve over the domain [t0; t1] = [0; 1].
P0
P1
P2
P3
P4
P5
0
.2
.4 .6 .8 1
Figure 2.21: Explicit B ezier curve.
It is also possible to create an explicit rational B ezier curve. However, the representation of a
degree-n rational function
x = t; y =
Pn
i=0 wiyiBn
i (t) Pn
i=0 wiBn
i (t)
as an explicit B ezier curve is degree n + 1 because we must have
x = t = t
Pn
i=0 wiBn
i (t) Pn
i=0 wiBn
i (t)
which is degree n + 1. Since x(t) is degree n + 1, we must likewise degree elevate y(t).
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Integrating Bernstein polynomials 37
2.15 Integrating Bernstein polynomials
Recall that the hodograph ( rst derivative) of a B ezier curve is easily found by simply di erencing
adjacent control points (Section 2.7). It is equally simple to compute the integral of a Bernstein
polynomial. Since the integral of a polynomial in Bernstein form
p(t) =
Xn
i=0
piBn
i (t) (2.16)
is that polynomial whose derivative is p(t). If the desired integral is a degree n + 1 polynomial in
Bernstein form
q(t) =
nX+1
i=0
qiBn+1
i (t); (2.17)
we have
pi = (n + 1)(qi+1 qi): (2.18)
Hence, q0 = 0 and
qi =
Pi1
j=0 pj
n + 1 ; i = 1; n + 1: (2.19)
Note that if p(t) is expressed as an explicit B ezier curve, q(t) can be interpreted as the area under
p(t) between the lines x = 0 and x = t. Thus, the entire area under an explicit B ezier curve can be
computed as simply the average of the control points! This is so because
q(1) = qn+1 =
Pn
j=0 pj
n + 1 : (2.20)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
38 Integrating Bernstein polynomials
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Chapter 3
Polynomial Evaluation and Basis
Conversion
3.1 Horner's Algorithm in Power Basis
Horner's algorithm can evaluate a power basis polynomial
y(t) =
Xn
i=0
piti
using n multiplies and adds. The trick is to rewrite the polynomial in nested form:
y(t) = ( ((pnt + pn1)t + pn2)t + + p1)t + p0
This can be written
hn = pn
hi1 = t hi + pi1; i = n; : : : ; 1
y(t) = h0
or, as a C funtion,
float p_horner(float *p,int n, float t)
{
float h;
int i;
h = p[n];
for(i=n-1; i>=0; i--)
h = t*h + p[i];
return h;
}
This is the fastest algorithm for evaluating a power basis polynomial at a single point.
For evaluating a polynomial at several evenly spaced intervals (f(0), f(a), f(2a), f(3a), etc.)
forward di erencing works faster (see Chapter 4) but su ers from numerical instability.
39
40 Horner's Algorithm in Bernstein Basis
3.2 Horner's Algorithm in Bernstein Basis
We have seen that one way to evaluate a B ezier curve (that is, to compute the Cartesian coordinates
of a point on a B ezier curve) is to use the de Casteljau algorithm. Another option is to convert it to
power basis (see Section 3.3) and then use Horner's algorithm in Section 3.1. Alternatively, Horner's
algorithm can be modi ed to work directly on Bernstein polynomials. We can use the recurrence
relation for binomial coe cients
n
i
= n i + 1
i
n
i 1
to derive a nested multiplication which does not involve the binomial coe cients directly:
float b_horner(float *b, int n, float t)
{
float u, bc, tn, tmp;
int i;
u = 1.0 - t;
bc = 1;
tn = 1;
tmp = b[0]*u;
for(i=1; i<n; i++){
tn = tn*t;
bc = bc*(n-i+1)/i;
tmp = (tmp + tn*bc*b[i])*u;
}
return (tmp + tn*t*b[n]);
}
3.3 Basis Conversion
A fundamental problem in CAGD is that of polynomial basis conversion. We here consider the
common case of conversion between power and Bernstein bases. For example, given a B ezier curve
of any degree, we want to nd the equivalent power basis equation and vice versa.
Denote a polynomial in Bernstein form
B(t) =
Xn
i=0
bi
n
i
(1 t)niti
and a polynomial in power form
P(t) =
Xn
i=0
piti:
The problem we consider is, given the bi of a polynomial in Bernstein basis, nd the pi for the
equivalent power basis polynomial (Bernstein to power basis conversion) or given the pi nd the bi
(power to Bernstein conversion).
An elegant solution to this problem can be obtained by performing a Taylor's series expansion.
The Taylor's expansion of B(t) is:
B(t) B(0) + B0(0)t + B00(0)t2
2
+ : : : + B(i)(0)ti
i
+ : : : :
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Basis Conversion 41
A power basis polynomial is equivalent to a Bernstein basis polynomial (P(t) B(t)) if and only if
P(i)(0)ti
i!
B(i)(0)ti
i! ; i = 0; : : : ; n:
But, for power basis,
P(i)(0)
i!
= pi
so
pi = B(i)(0)
i! ; i = 0; : : : ; n: (3.1)
The terms B(i)(0) can be found by setting up a di erence table. Remember from our study of
hodographs that the coe cients of the derivative of a polynomial in Bernstein form (for example,
the x or y component of a B ezier curve) are:
n(b1 b0); n(b2 b1); : : : ; n(bn bn1):
The coe cients of the second derivative are:
n(n 1)(b2 2b1 + b0); n(n 1)(b3 2b2 + b1); : : : ; n(n 1)(bn 2bn1 + bn2):
Since B(0) =
Pn
i=0 bi
n
i
(1 0)ni0i = b0, we have
B0(0) = n(b1 b0); B00(0) = n(n 1)(b2 2b1 + b0)
B(i)(0) = n(n 1) (n i + 1)
Xi
j=0
(1)(ij+1)
i
j
bj :
This can be written more neatly if we de ne the recurrence
bj
i = bj1
i+1 bj1
i
with b0i
bi. Then
B(i)(0) = n(n 1) (n i + 1)bi
0 = n!
(n i)! bi
0:
From equation 3.1,
pi = n!
(n i)!i! bi
0 =
n
i
bi
0:
Thus, the problem reduces to one of nding the values bi
0. This is easily done using a di erence
table:
b00
= b0 = p0 b01
= b1 : : : b0
n = bn
b10
= b01
b00
= p1=
n
1
b11
= b02
b01
: : : b0
n = b0
n b0
n1
b20
= b11
b10
= p2=
n
2
b21
= b12
b11
: : : b2
n = b1
n b1
n1
: : : : : : : : : : : :
bn1
0 = bn2
1 bn2
0 = pn1=
n
n1
bn1
1 = bn2
2 bn2
1
bn0
= bn1
1 bn1
0 = pn
Thus, to perform Bernstein to power basis conversion, load the Bernstein coe cients into the top row
and compute the di erence table. Scale the left column by
n
i
, and you have the power coe cients.
To perform power to Bernstein conversion, divide the power coe cients by
n
i
, load them into
the left column, compute the di erence table backwards, and read the Bernstein coe cients o the
top row.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
42 Basis Conversion
3.3.1 Example
Convert to power basis the degree 4 Bernstein form polynomial with coe cients (1; 3; 4; 6; 8). This
is done by setting up the di erence table
1 3 4 6 8
2 1 2 2
-1 1 0
2 -1
-3
so the power coe cient are taken from the left column, times the binomial coe cients:
p0 = 1
4
0
= 1
p1 = 2
4
1
= 8
p2 = 1
4
2
= 6
p3 = 2
4
3
= 8
p4 = 3
4
4
= 3
3.3.2 Closed Form Expression
The conversion from Bernstein to power basis can be written concisely as follows:
pi =
Xi
k=0
bk
n
i
i
k
(1)ik:
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Chapter 4
Forward Di erencing
Horner's algorithm is the fastest method for evaluating a polynomial at a single point. For a degree
n polynomial, it requires n multiplies and n adds.
If a polynomial is to be evaluated at several evenly spaced values t; t + ; t + 2 ; : : : ; t + k , the
fastest method is to use forward di erences.
Consider a degree 1 polynomial
f(t) = a0 + a1t:
The di erence between two adjacent function values is
1(t) = f(t + ) f(t) = [a0 + a1(t + )] [a0 + a1t] = a1 :
Thus, f(t) can be evaluated at several evenly spaced points using the algorithm:
1 = a1
t0 = 0
f(0) = a0
for i = 1 to k do
ti = ti1 +
f(ti) = f(ti1) + 1
endfor
Thus, each successive evaluation requires only one add, as opposed to one add and one multiply
for Horner's algorithm.
This idea extends to polynomials of any degree. For the quadratic case,
f(t) = a0 + a1t + a2t2:
The di erence between two adjacent function values is
1(t) = f(t + ) f(t) = [a0 + a1(t + ) + a2(t + )2] [a0 + a1t + a2t2]
1(t) = a1 + a2 2 + 2a2t :
We can now write
43
44
t0 = 0
f(0) = a0
for i = 1 to k do
ti = ti1 +
1(ti) = a1 + a2 2 + 2a2ti1
f(ti) = f(ti1) + 1(ti1)
endfor
In this case, (t) is a linear polynomial, so we can evaluate it as above, by de ning
2(t) = 1(t + ) 1(t) = 2a2 2
and our algorithm now becomes
t0 = 0
f(0) = a0
1 = a1 + a2 2
2 = 2a2 2
for i = 1 to k do
ti = ti1 +
f(ti) = f(ti1) + 1
1 = 1 + 2
endfor
It should be clear that for a degree n polynomial, each successive evaluation requires n adds and no
multiplies! For a cubic polynomial
f(t) = a0 + a1t + a2t2 + a3t3;
the forward di erence algorithm becomes
t0 = 0
f(0) = a0
1 = a1 + a2 2 + a3 3
2 = 2a2 2 + 6a3 3
3 = 6a3 3
for i = 1 to k do
ti = ti1 +
f(ti) = f(ti1) + 1
1 = 1 + 2
2 = 2 + 3
endfor
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
45
Several questions remain. First, what are the initial values for the i if we want to start at
some value other than t = 0. Second, what is a general equation for the i for a general degree n
polynomial f(t). Also, what if our polynomial is not in power basis.
These questions can be answered almost trivially by observing the following. Since ti+1 = ti + ,
we have
1(ti) = f(ti+1) f(t);
j(ti) = j1(ti+1) j1(ti); j = 2; : : : ; n;
n(ti) = n(ti+1) = n(ti+k) = a constant
n+1 = 0
Thus, our initial values for j(ti) can be found by simply computing f(ti); f(ti+1); : : : ; f(ti+n)
and from them computing the initial di erences. This lends itself nicely to a table. Here is the table
for a degree four case:
f(ti) f(ti+1) f(ti+2) f(ti+3) f(ti+4)
1(ti) 1(ti+1) 1(ti+2) 1(ti+3)
2(ti) 2(ti+1) 2(ti+2)
3(ti) 3(ti+1)
4(ti)
0 0 0 0 0
To compute f(ti+5), we simply note that every number R in this table, along with its right hand
neighbor Rright and the number directly beneath it Rdown obey the rule
Rright = R + Rdown:
Thus, we can simply ll in the values
4(ti+1) = 4(ti) + 0
3(ti+2) = 3(ti+1) + 4(ti+1)
2(ti+3) = 2(ti+2) + 3(ti+2)
1(ti+4) = 1(ti+3) + 2(ti+3)
f(ti+5) = f(ti+4) + 1(ti+4)
Note that this technique is independent of the basis in which f(t) is de ned. Thus, even if it
is de ned in Bernstein basis, all we need to do is to evaluate it n + 1 times to initiate the forward
di erencing.
For example, consider the degree 4 polynomial for which f(ti) = 1, f(ti+1) = 3, f(ti+2) = 2,
f(ti+3) = 5, f(ti+4) = 4. We can compute f(ti+5) = 24, f(ti+6) = 117, and f(ti+7) = 328
from the following di erence table:
t : ti ti+1 ti+2 ti+3 ti+4 ti+5 ti+6 ti+7
f(t) : 1 3 2 5 4 24 117 328
1(t) : 2 1 3 1 28 93 211
2(t) : 3 4 4 27 65 118
3(t) : 7 8 23 38 53
4(t) : 15 15 15 15 15
5(t) : 0 0 0 0 0 0 0 0
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
46 Choosing
Example
For a certain cubic polynomial f(t), we have:
f(1) = 1; f(2) = 2; f(3) = 4; f(5) = 15:
Solve for f(4) using forward di erencing.
Solution
t : 1 2 3 4 5
f(t) : 1 2 4 x 15
1(t) : 1 2 x 4 15 x
2(t) : 1 x 6 19 2x
3(t) : x 7 25 3x
4(t) : 32 4x
For a cubic polynomial, 4(t) = 0, so 32 4x = 0 and x = 8.
4.1 Choosing
This raises the important question of how to select an appropriate value for when using forward
di erencing to plot a curve. One way to determine is so that distance from the the curve to its
polygonal approximation lies within a tolerance. A discussion of how to chose that will satisfy
such a requirement is found in Section 10.6.
A second criterion that might be used to choose arises in the problem of rasterizing a curve.
This means to \turn on" a contiguous series of pixels that the curve passes through, without any
gaps. If the control points of the degree n B ezier curve are Pi = (xi; yi) in pixel coordinates, then
let
d = maxfxi xi1; yi yi1g i = 1; : : : ; n
If you now evaluate the curve at n d + 1 evenly spaced values of t and paint each resulting pixel,
there will be no gaps in the drawing of the curve. Another way to say this, compute
=
1
n d
:
Then, compute the points P(i ), i = 0 : : : ; n d. Note that n d is an upper bound on the
magnitude of the x or y component of the rst derivative of the curve.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Chapter 5
Properties of Blending Functions
We have just studied how the Bernstein polynomials serve very nicely as blending functions. We
have noted that a degree n B ezier curve always begins at P0 and ends at Pn. Also, the curve is
always tangent to the control polygon at P0 and Pn.
Other popular blending functions exist for de ning curves. In fact, you can easily make up your
own set of blending functions. And by following a few simple rules, you can actually create a new
type of free-form curve which has desirable properties.
Consider a set of control points Pi, i = 0; :::; n and blending functions fi(t) which de ne the
curve
P(t) =
Xn
i=0
fi(t)Pi:
We can select our blending functions such that the curve has any or all of the following properties:
1. Coordinate system independence. This means that the curve will not change if the
coordinate system is changed. In other words, imagine that the control points are drawn on
a piece of paper and we move that piece of paper around so that the (x; y) coordinates of the
control points change. It would be nice if the curve did not change relative to the control
points. Actually, if we were to pick an arbitrary set of blending functions, the curve would
change. In order to provide coordinate system independence, the blending functions must
form a partition of unity, which is math jargon that means that the blending functions sum
identically sum to one:
Xn
i=0
fi(t) 1:
The property of coordinate system independence is also called a ne invariance.
2. Convex hull property. The convex hull property was introduced in Section 2.5. This
property exists in curves which are coordinate system independent and for which the blending
functions are all non- negative:
Xn
i=0
fi(t) 1; fi(t) 0; 0 t 1; i = 0; :::; n
47
48
3. Symmetry. Curves which are symmetric do not change if the control points are ordered in
reverse sequence. For a curve whose domain is [0; 1], symmetry is assured if and only if
Xn
i=0
fi(t)Pi
Xn
i=0
fi(1 t)Pni:
This holds if
fi(t) = fni(1 t):
For a curve whose domain is [t0; t1], symmetry requires
Xn
i=0
fi(t)Pi
Xn
i=0
fi(t1 + t2 t)Pni:
4. Variation Diminishing Property. This is a property which is obeyed by B ezier curves and
B-spline curves. It states that if a given straight line intersects the curve in c number of points
and the control polygon in p number of points, then it will always hold that
c = p 2j
where j is zero or a positive integer. This has the practical interpretation that a curve which
c=3
p=5
j=1
Figure 5.1: Variation Diminishing Property
obeys the variation diminishing property will \wiggle" no more than the control polygon.
The conditions under which a curve will obey the variation diminishing property are rather
complicated. Su ce it to say that B ezier curves and B-spline curves obey this property, and
most other curves do not.
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
49
5. Linear Independence. A set of blending functions is linearly independent if there do no
exist a set of constants c0; : : : ; cn, not all zero, for which
Xn
i=0
cifi(t) 0:
Linearly independent blending functions are desirable for many reasons. For example,if they
are not linearly independent, it is possible to express one blending function in terms of the
other ones. This has the practical disadvantage that any given curve can be represented by
in nitely many di erent control point positions. It also means that, for certain control point
arrangements, the curve collapses to a single point, even though the control points are not all
at that point.
If a set of blending functions are linearly independent, they can be called basis functions. Thus,
Bernstein polynomials are basis functions for B ezier curves, and B-spline blending functions
are basis functions.
6. Endpoint Interpolation If a curve over the domain [t0; t1] is to pass through the rst and
last control points, as in the case of B ezier curves, the following conditions must be met:
f0(t0) = 1; fi(t0) = 0; i = 1; :::; n
fn(t1) = 1; fi(t1) = 0; i = 0; :::; n 1:
Any set of blending functions can be analyzed in terms of the above properties.
Example
Check which of the above-mentioned properties are obeyed by the sample curve
P(t) = f0(t)P0 + f1(t)P1 + f2(t)P2 = t2 2t + 1
t2 + 1
P0 +
2t 2t2
t2 + 1
P1 +
2t2
t2 + 1
P2
Answer:
This curve is coordinate system independent because
t2 2t + 1
t2 + 1
+
2t 2t2
t2 + 1
+
2t2
t2 + 1
= t2 + 1
t2 + 1 1:
The curve also obeys the convex hull property because its blending functions are non-negative
for t 2 [0; 1]. This is most easily seen by factoring the blending functions:
t2 2t + 1
t2 + 1
=
(t 1)2
t2 + 1
is non-negative for any real number because the square of a real number is always non-negative.
2t 2t2
t2 + 1
=
2t(1 t)
t2 + 1
is clearly non-negative for t 2 [0; 1].
The curve is not symmetric because
(1 t)2 2(1 t) + 1
(1 t)2 + 1
= t2
t2 2t + 2 6=
2t2
t2 + 1
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
50 Timmer's Parametric Cubic
Variation diminishing is very di cult to prove, and will not be attempted here.
Linear independence is assessed by checking if there exist constants c0; c1; c2, not all zero, for
which
c0
t2 2t + 1
t2 + 1
+ c1
2t 2t2
t2 + 1
+ c2
2t2
t2 + 1 0:
This is equivalent to
c0(t2 2t + 1) + c1(2t 2t2) + c2(2t2) = (c0 2c1 + 2c2)t2 + (2c0 + 2c1)t + c0 0
which can only happen if
c0 2c1 + 2c2 = 0; 2c0 + 2c1 = 0; c0 = 0:
There is no solution to this set of linear equations, other than c0 = c1 = c2 = 0, so we conclude that
these blending functions are linearly independent.
The curve does interpolate the endpoints, because
f0(0) = 1; f1(0) = f2(0) = 0; f2(1) = 1; f0(1) = f1(1) = 0:
The B ezier and B-spline curves are currently the most popular curve forms. Historically, other
curve forms evolved independently at several di erent industrial sites, each faced with the common
problem of making free-form curves accessible to designers. In this section, we will review three
such curves: Timmer's Parametric Cubic, Ball's Cubic, and the Overhauser curve. Each of these
curves is coordinate system independent and symmetric, but only Ball's cubic obeys the convex hull
property.
5.1 Timmer's Parametric Cubic
Figure 5.2: Timmer's PC
Timmer's Parametric Cubic (or PC) was created by Harry Timmer of McDonnell Douglas [Tim80].
It was modeled after the B ezier curve. Timmer felt that he could improve upon the B ezier curve
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Ball's Rational Cubic 51
if he could make it follow the control polygon more tightly. This he did by forcing the curve to
interpolate the endpoints of the control polygon and to be tangent to the control polygon at those
points (just like B ezier curves) and in addition, he forced the curve to go through the midpoint of
the line segment P1 - P2. The resulting blending functions are:
f0(t) = (1 2t)(1 t)2 = 2t3 + 5t2 4t + 1
f1(t) = 4t(1 t)2 = 4t3 8t2 + 4t
f2(t) = 4t2(1 t) = 4t3 + 4t2
f3(t) = (2t 1)t2 = 2t3 t2
Figure 5.2 may mislead one into thinking that Timmer's curve is tangent to P1 P2. This is
not generally so (and is not exactly so even in Figure 5.2).
Example Problem
Given a Timmer curve with control points Q0, Q1, Q2, Q3, nd the control points P0, P1, P2, P3
of an equivalent cubic B ezier curve P(t).
Solution
Note that if P(t) Q(t),then P(0) = Q(0), P(1) = Q(1), P0(0) = Q0(0), and P0(1) = Q0(1). This
strategy provides a simple way to perform the conversion.
P(0) = Q(0) ! P0 = Q0:
P(1) = Q(1) ! P3 = Q3:
For derivatives, we di erentiate the Timmer basis functions (it does not work to use the B ezier
hodograph):
Q0(t) = (6t2 + 10t 4)Q0 + (12t2 16t + 4)Q1 + (12t2 + 8t)Q2 + (6t2 2t)Q3
so Q0(t) = 4(Q1 Q0) and Q0(1) = 4(Q3 Q2).
P0(0) = Q0(0) ! 3(P1 P0) = 4(Q1 Q0) ! Q1 =
P0 + 3P1
4
P0(1) = Q0(1) ! 3(P3 P2) = 4(Q3 Q2) ! Q2 =
P3 + 3P2
4
5.2 Ball's Rational Cubic
Alan Ball rst published his cubic curve formulation in 1974 [Bal74]. Ball worked for the British
Aircraft Corporation, and his cubic curve form was used in BAC's in-house CAD system.
Like Timmer's PC curve, Ball's cubic can be considered a variant of the cubic B ezier curve.
It's distinguishing feature is that it handles conic sections as a special case in a natural way. The
blending functions for the non-rational case are:
f0(t) = (1 t)2
f1(t) = 2t(1 t)2
f2(t) = 2t2(1 t)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
52 Overhauser Curves
f3(t) = t2
Notice that if P1 = P2, then the curve becomes a quadratic B ezier curve:
P0(1 t)2 + P12t(1 t)2 + P12t2(1 t) + P3t2
= P0(1 t)2 + P1[2t(1 t)2 + 2t2(1 t)] + P3t2
= P0(1 t)2 + P12t(1 t) + P3t2
Figure 5.3: Ball's Cubic
5.3 Overhauser Curves
Overhauser curves were developed and used at Ford Motor Company [Ove68]. They are also known
as cubic Catmull-Rom splines [CR74].
One complaint of B ezier curves is that the curve does not interpolate all of the control points.
Overhauser curves do interpolate all control points in a piecewise string of curve segments. A single
Overhauser curve is de ned with the following blending functions:
f0(t) =
1
2t + t2
1
2t3
f1(t) = 1
5
2t2 +
3
2t3
f2(t) =
1
2t + 2t2
3
2t3
f3(t) =
1
2t2 +
1
2t3
A single Overhauser curve segment interpolates P1 and P2. Furthermore, the slope of the curve at
P1 is only a function of P0 and P2 and the slope at P2 is only a function of P1 and P3:
P0(0) =
1
2
(P2 P0)
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Overhauser Curves 53
P0(1) =
1
2
(P3 P1)
This means that a second curve segment will be tangent to the rst curve segment if its rst three
control points are identical to the last three control points of the rst curve. This is illustrated in
Fig. 5.4.
Figure 5.4: Overhauser curves
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
54 Overhauser Curves
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Chapter 6
B-Spline Curves
Most shapes are too complicated to de ne using a single B ezier curve. A spline curve is a sequence
of curve segments that are connected together to form a single continuous curve. For example, a
piecewise collection of B ezier curves, connected end to end, can be called a spline curve. Over-
hauser curves are another example of splines. The word \spline" is sometimes used as a verb, as in
\Spline together some cubic B ezier curves." In approximation theory, spline is de ned as a piecewise
polynomial of degree n whose segments are Cn1.
The word \spline" comes from the ship building industry, where it originally referred to a thin
strip of wood which draftsmen would use like a
exible French curve. Metal weights (called ducks)
were placed on the drawing surface and the spline was threaded between the ducks as in Figure 6.1.
We know from structural mechanics that the bending moment M is an in nitely continuous function
Figure 6.1: Spline and ducks.
along the spline except at a duck, where M is generally only C0 continuous. Since the curvature of
the spline is proportional to M ( = M=EI), the spline is everywhere curvature continuous.
Curvature continuity is an important requirement for the ship building industry, as well as for
many other applications. For example, railroad tracks are always curvature continuous, or else a
moving train would experience severe jolts. Car bodies are G2 smooth, or else the re
ection of
straight lines would appear to be G0.
While C1 continuity is straightforward to attain using B ezier curves (for example, popular design
software such as Adobe Illustrator use B ezier curves and automatically impose tangent continuity
as you sketch), C2 and higher continuity is cumbersome. This is where B-spline curves come in.
B-spline curves can be thought of as a method for de ning a sequence of degree n B ezier curves that
join automatically with Cn1 continuity, regardless of where the control points are placed.
Whereas an open string of m B ezier curves of degree n involve nm + 1 distinct control points
(shared control points counted only once), that same string of B ezier curves can be expressed using
55
56 Polar Form
only m+n B-spline control points (assuming all neighboring curves are Cn1). The most important
operation you need to understand to have a working knowledge of B-splines is how to extract the
contituent B ezier curves. The traditional approach to teaching about B-Splines centered on basis
functions and recurrence relations. Experience has shown that polar form (Section 6.1) and knot
intervals (Section 6.13) provide students with such a working knowledge more quickly than recurrence
relations.
6.1 Polar Form
Polar form, introduced by Dr. Lyle Ramshaw [Ram87, Ram89b, Ram89c], can be thought of as
simply an alternative method of labeling the control points of a B ezier or B-Spline curve. These
labels are referred to as polar values. These notes summarize the properties and applications of
polar form, without delving into derivations. The interested student can study Ramshaw's papers.
All of the important algorithms for B ezier and B-spline curves can be derived from the following
four rules for polar values.
1. For a degree n B ezier curve P[a;b](t), the control points are relabeled Pi = P(u1; u2; : : : un) where
uj = a if j n i and otherwise uj = b. For a degree two B ezier curve P[a;b](t),
P0 = P(a; a); P1 = P(a; b); P2 = P(b; b):
For a degree three B ezier curve P[a;b](t),
P0 = P(a; a; a); P1 = P(a; a; b);
P2 = P(a; b; b); P3 = P(b; b; b);
and so forth.
P(0,0,0)
P(0,0,2)
P(0,2,2)
P(2,2,2)
P(2,2,3)
P(2,3,3)
P(3,3,3)
(a) B ezier curves with polar labels.
P(1,2,3)
P(2,3,4)
P(3,4,5)
P(4,5,6)
P(5,6,7)
P(6,7,8)
t=3 t=4
t=5
t=6
Knot Vector = [1,2,3,4,5,6,7,8]
(b) B-Spline Curve with Polar Labels
Figure 6.2: Polar Labels.
Figure 6.2.a shows two cubic B ezier curves labeled using polar values. The rst curve is de ned
over the parameter interval [0; 2] and the second curve is de ned over the parameter interval [2; 3].
Note that P(t; t; : : : ; t) is the point on a B ezier curve corresponding to parameter value t.
2. For a degree n B-spline with a knot vector (see Section 6.2) of
[t1; t2; t3; t4; : : :];
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
Polar Form 57
the arguments of the polar values consist of groups of n adjacent knots from the knot vector, with
the ith polar value being P(ti; : : : ; ti+n1), as in Figure 6.2.b.
3. A polar value is symmetric in its arguments. This means that the order of the arguments can be
changed without changing the polar value. For example,
P(1; 0; 0; 2) = P(0; 1; 0; 2) = P(0; 0; 1; 2) = P(2; 1; 0; 0); etc:
4. Given P(u1; u2; : : : ; un1; a) and P(u1; u2; : : : ; un1; b) we can compute P(u1; u2; : : : ; un1; c)
where c is any value:
P(u1; u2; : : : ; un1; c) =
(b c)P(u1; u2; : : : ; un1; a) + (c a)P(u1; u2; : : : ; un1; b)
b a
P(u1; u2; : : : ; un1; c) is said to be an a ne combination of P(u1; u2; : : : ; un1; a) and P(u1, u2,
: : : ; un1; b). For example,
P(0; t; 1) = (1 t) P(0; 0; 1) + t P(0; 1; 1);
P(0; t) =
(4 t) P(0; 2) + (t 2) P(0; 4)
2 ;
P(1; 2; 3; t) =
(t2 t) P(2; 1; 3; t1) + (t t1) P(3; 2; 1; t2)
(t2 t1) :
What this means geometrically is that if you vary one parameter of a polar value while holding all
others constant, the polar value will sweep out a line at a constant velocity, as in Figure 6.3.
P(0,c,d)
P(1,c,d)
P(2,c,d)
P(3,c,d)
P(4,c,d)
P(5,c,d)
P(6,c,d)
Figure 6.3: A ne map property of polar values.
6.1.1 Subdivision of B ezier Curves
To illustrate how polar values work, we now show how to derive the de Casteljau algorithm using
only the rst three rules for polar values.
Given a cubic B ezier curve P[0;1](t), we wish to split it into P[0;t] and P[t;1]. The control points
of the original curve are labeled
P(0; 0; 0); P(0; 0; 1); P(0; 1; 1); P(1; 1; 1):
The subdivision problem amounts to nding polar values
P(0; 0; 0); P(0; 0; t); P(0; t; t); P(t; t; t);
T. W. Sederberg, BYU, Computer Aided Geometric Design Course Notes January 10, 2012
58 Knot Vectors
and
P(t; t; t); P(t; t; 1); P(t; 1; 1); P(1; 1; 1):
These new control points can be derived by applying the symmetry and a ne map rules for polar
values. Refering to Figure 6.4, we can compute
STEP 1.
P(0; 0; t) = (1 t) P(0; 0; 0) + (t 0) P(0; 0; 1);
P(0; 1; t) = (1 t) P(0; 0; 1) + (t 0) P(0; 1; 1);
P(t; 1; 1) = (1 t) P(0; 1; 1) + (t 0) P(1; 1; 1):
STEP 2.
P(0; t; t) = (1 t) P(0; 0; t) + (t 0) P(0; t; 1);
P(1; t; t) = (1 t) P(0; t; 1) + (t 0) P(t; 1; 1);
STEP 3.
P(t; t; t) = (1 t) P(0; t; t) + (t 0) P(t; t; 1);
t = .6
P(0) = P(0,0,0)
P(0,0,1)
P(0,1,1)
P(1) = P(1,1,1)
P(0,0,t)
P(0,t,1)
P(t,1,1)
P(0,t,t) P(t,t,1)
P(t) = P(t,t,t)
Figure 6.4: Subdividing a cubic B ezier curve.
6.2 Knot Vectors
A k