Pyramid Algorithms

Pyramid Algorithms

by Ron Goldman
Released July 2002
Publisher(s): Morgan Kaufmann
ISBN: 9780080515472

Explore a preview version of Pyramid Algorithms right now.

O’Reilly members get unlimited access to live online training experiences, plus books, videos, and digital content from 200+ publishers.

Start your free trial

Book description



Pyramid Algorithms presents a unique approach to understanding, analyzing, and computing the most common polynomial and spline curve and surface schemes used in computer-aided geometric design, employing a dynamic programming method based on recursive pyramids.
The recursive pyramid approach offers the distinct advantage of revealing the entire structure of algorithms, as well as relationships between them, at a glance. This book-the only one built around this approach-is certain to change the way you think about CAGD and the way you perform it, and all it requires is a basic background in calculus and linear algebra, and simple programming skills.

* Written by one of the world's most eminent CAGD researchers
* Designed for use as both a professional reference and a textbook, and addressed to computer scientists, engineers, mathematicians, theoreticians, and students alike
* Includes chapters on Bezier curves and surfaces, B-splines, blossoming, and multi-sided Bezier patches
* Relies on an easily understood notation, and concludes each section with both practical and theoretical exercises that enhance and elaborate upon the discussion in the text
* Foreword by Professor Helmut Pottmann, Vienna University of Technology

Table of contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling
  5. Copyright
  6. Dedication
  7. Foreword
  8. Preface
  9. Chapter 1: Introduction: Foundations
    1. 1.1 Ambient Spaces
    2. 1.2 Coordinates
    3. 1.3 Curve and Surface Representations
    4. 1.4 Summary
  10. Part I: Interpolation
    1. Chapter 2: Lagrange Interpolation and Neville’s Algorithm
      1. 2.1 Linear Interpolation
      2. 2.2 Neville’s Algorithm
      3. 2.3 The Structure of Neville’s Algorithm
      4. 2.4 Uniqueness of Polynomial Interpolants and Taylor’s Theorem
      5. 2.5 Lagrange Basis Functions
      6. 2.6 Computational Techniques for Lagrange Interpolation
      7. 2.7 Rational Lagrange Curves
      8. 2.8 Fast Fourier Transform
      9. 2.9 Recapitulation
      10. 2.10 Surface Interpolation
      11. 2.11 Rectangular Tensor Product Lagrange Surfaces
      12. 2.12 Triangular Lagrange Patches
      13. 2.13 Uniqueness of the Bivariate Lagrange Interpolant
      14. 2.14 Rational Lagrange Surfaces
      15. 2.15 Ruled, Lofted, and Boolean Sum Surfaces
      16. 2.16 Summary
    2. Chapter 3: Hermite Interpolation and the Extended Neville Algorithm
      1. 3.1 Cubic Hermite Interpolation
      2. 3.2 Neville’s Algorithm for General Hermite Interpolation
      3. 3.3 The Hermite Basis Functions
      4. 3.4 Rational Hermite Curves
      5. 3.5 Hermite Surfaces
      6. 3.6 Summary
    3. Chapter 4: Newton Interpolation and Difference Triangles
      1. 4.1 The Newton Basis
      2. 4.2 Divided Differences
      3. 4.3 Properties of Divided Differences
      4. 4.4 An Axiomatic Approach to Divided Difference
      5. 4.5 Forward Differencing
      6. 4.6 Summary
  11. Part II: Approximation
    1. Chapter 5: Bezier Approximation and Pascal’s Triangle
      1. 5.1 De Casteljau’s Algorithm
      2. 5.2 Elementary Properties of Bezier Curves
      3. 5.3 The Bernstein Basis Functions and Pascal’s Triangle
      4. 5.4 More Properties of Bernstein/Bezier Curves
      5. 5.5 Change of Basis Procedures and Principles of Duality
      6. 5.6 Differentiation and Integration
      7. 5.7 Rational Bezier Curves
      8. 5.8 Bezier Surfaces
      9. 5.9 Summary
    2. Chapter 6: Blossoming
      1. 6.1 Blossoming the de Casteljau Algorithm
      2. 6.2 Existence and Uniqueness of the Blossom
      3. 6.3 Change of Basis Algorithms
      4. 6.4 Differentiation and the Homogeneous Blossom
      5. 6.5 Blossoming Bezier Patches
      6. 6.6 Summary
    3. Chapter 7: B-Spline Approximation and the de Boor Algorithm
      1. 7.1 The de Boor Algorithm
      2. 7.2 Progressive Polynomial Bases Generated by Progressive Knot Sequences
      3. 7.3 B-Spline Curves
      4. 7.4 Elementary Properties of B-Spline Curves
      5. 7.5 All Splines Are B-Splines
      6. 7.6 Knot Insertion Algorithms
      7. 7.7 The B-Spline Basis Functions
      8. 7.8 Uniform B-Splines
      9. 7.9 Rational B-Splines
      10. 7.10 Catmull-Rom Splines
      11. 7.11 Tensor Product B-Spline Surfaces
      12. 7.12 Pyramid Algorithms and Triangular B-Patches
      13. 7.13 Summary
    4. Chapter 8: Pyramid Algorithms for Multisided Bezier Patches
      1. 8.1 Barycentric Coordinates for Convex Polygons
      2. 8.2 Polygonal Arrays
      3. 8.3 Neville’s Pyramid Algorithm and Multisided Grids
      4. 8.4 S-Patches
      5. 8.5 Pyramid Patches and the General Pyramid Algorithm
      6. 8.6 C-Patches
      7. 8.7 Toric Bezier Patches
      8. 8.8 Summary
  12. Index
  13. About the Author

Product information

  • Title: Pyramid Algorithms
  • Author(s): Ron Goldman
  • Release date: July 2002
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080515472