# An Introduction to Splines for Use in Computer Graphics and Geometric Modeling

As the field of computer graphics develops, techniques for modeling complex curves and surfaces are increasingly important. A major technique is the use of parametric splines in which a curve is defined by piecing together a succession of curve segments, and surfaces are defined by stitching together a mosaic of surface patches.

An Introduction to Splines for Use in Computer Graphics and Geometric Modeling discusses the use of splines from the point of view of the computer scientist. Assuming only a background in beginning calculus, the authors present the material using many examples and illustrations with the goal of building the reader's intuition. Based on courses given at the University of California, Berkeley, and the University of Waterloo, as well as numerous ACM Siggraph tutorials, the book includes the most recent advances in computer-aided geometric modeling and design to make spline modeling techniques generally accessible to the computer graphics and geometric modeling communities.

Paperback, 476 Pages

Published: September 1995

Imprint: Morgan Kaufmann

ISBN: 978-1-55860-400-1

## Contents

• An Introduction to Splines for Use in Computer Graphics and Geometric Modeling
by Richard H. Bartels, John C. Beatty, and Brian A. Barsky
• 1 Introduction
• 1.1 General References
• 2 Preliminaries
• 3 Hermite and Cubic Spline Interpolation
• 3.1 Practical Considerations - Computing Natural Cubic Splines
• 3.2 Other End Conditions For Cubic Interpolating Splines
• 3.3 Knot Spacing
• 3.4 Closed Curves
• 4 A Simple Approximation Technique - Uniform Cubic B-splines
• 4.1 Simple Preliminaries - Linear B-splines
• 4.2 Uniform Cubic B-splines
• 4.3 The Convex Hull Property
• 4.4 Translation Invariance
• 4.5 Rotation and Scaling Invariance
• 4.6 End Conditions for Curves
• 4.7 Uniform Bicubic B-spline Surfaces
• 4.8 Continuity for Surfaces
• 4.9 How Many Patches Are There?
• 4.10 Other Properties
• 4.11 Boundary Conditions for Surfaces
• 5 Splines in a More General Setting
• 5.1 Preliminaries
• 5.2 Continuity
• 5.3 Segment Transitions
• 5.4 Polynomials
• 5.5 Vector Spaces
• 5.6 Polynomials as a Vector Space
• 5.7 Bases and Dimension
• 5.8 Change of Basis
• 5.9 Subspaces
• 5.10 Knots and Parameter Ranges: Splines as a Vector Space
• 5.11 Spline Continuity and Multiple Knots
• 6 The One-Sided Basis
• 6.1 The One-Sided Cubic
• 6.2 The General Case
• 6.3 One-Sided Basis
• 6.5 Linear Combinations and Cancellation
• 6.6 Cancellation as a Divided Difference
• 6.7 Cancelling the Quadratic Term - The Second Difference
• 6.8 Cancelling the Linear Term - The Third Difference
• 6.9 The Uniform Cubic B-Spline - A Fourth Difference
• 7 Divided Differences
• 7.1 Differentiation and One-Sided Power Functions
• 7.2 Divided Differences in a General Setting
• 7.3 Algebraic and Analytic Properties
• 8 General B-splines
• 8.1 A Simple Example - Step Function B-splines
• 8.2 Linear B-splines
• 8.3 General B-spline Bases
• 8.4 Examples - Quadratic B-splines
• 8.5 The Visual Effect of Knot Multiplicities - Cubic B-splines
• 8.6 Altering Knot Spacing - More Cubic B-splines
• 9 B-spline Properties
• 9.1 Differencing Products - The Leibniz Rule
• 9.2 Establishing a Recurrence
• 9.3 The Recurrence and Examples
• 9.4 Evaluating B-splines Through Recurrence
• 9.5 Compact Support, Positivity, and the Convex Hull Property
• 9.6 Practical Implications
• 10 Bezier Curves
• 10.1 Increasing the Degree of a Bezier Curve
• 10.2 Composite Bezier Curves
• 10.3 Local vs. Global Curves
• 10.4 Subdivision and Refinement
• 10.5 Midpoint Subdivision of Bezier Curves
• 10.6 Arbitrary Subdivision of Bezier Curves
• 10.7 Bezier Curves From B-Splines
• 10.8 A Matrix Formulation
• 10.9 Converting Between Representations
• 10.10 Bezier Surfaces
• 11. Knot Insertion
• 11.1 Knots and Vertices
• 11.2 Representation Results
• 12 The Oslo Algorithm
• 12.1 Discrete B-spline Recurrence
• 12.2 Discrete B-spline Properties
• 12.3 Control Vertex Recurrence
• 12.4 Illustrations
• 13 Parametric vs. Geometric Continuity
• 13.1 Geometric Continuity
• 13.2 Continuity of the First Derivative Vector
• 13.3 Continuity of the Second Derivative Vector
• 14 Uniformly-Shaped Beta-spline Surfaces
• 14.1 Uniformly-Shaped Beta-spline Surfaces
• 14.2 An Historical Note
• 15 Geometric Continuity, Reparametrization, and the Chain Rule
• 16 Continuously-Shaped Beta-splines
• 16.1 Locality
• 16.2 Bias
• 16.3 Tension
• 16.4 Convex Hull
• 16.5 End Conditions
• 16.6 Evaluation
• 16.7 Continuously-Shaped Beta-spline Surfaces
• 17 An Explicity Formulation for Cubic Beta-splines
• 17.1 Beta-splines with Uniform Knot Spacing
• 17.2 Formulas
• 17.3 Recurrence
• 17.4 Examples
• 18 Discretely-Shaped Beta-splines
• 18.1 A Truncated Power Basis for the Beta-splines
• 18.2 A Local Basis for the Beta-splines
• 18.3 Evaluation
• 18.4 Equivalence
• 18.5 Beta2-splines
• 18.6 Examples
• 19 B-spline Representations for Beta-splines
• 19.1 Linear Equations
• 19.2 Examples
• 20 Rendering and Evaluation
• 20.1 Values of B-splines
• 20.2 Sums of B-splines
• 20.3 Derivatives of B-splines
• 20.4 Conversion to Segment Polynomials
• 20.5 Rendering Curves: Horner's Rule and Forward Differencing
• 20.6 The Oslo Algorithm - Computing Discrete B-splines
• 20.7 Parial Derivatives and Normals
• 20.8 Locality
• 20.9 Scan-Line Methods
• 20.10 Ray-Tracing B-spline Surfaces
• 21 Selected Applications
• 21.1 The Hermite Basis and C1 Key-Frame Inbetweening
• 21.2 A Cardinal Basis Spline for Interpolation
• 21.3 Interpolation Using B-splines
• 21.4 Catmull-Rom Splines
• 21.5 B-splines and Least Squares Fitting
• References
• Index