Pyramid Algorithms (eBook)

A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling

Ron Goldman (Autor)

eBook Download: PDF

2002 | 1. Auflage
576 Seiten
Elsevier Science (Verlag)
978-0-08-051547-2 (ISBN)

Infos

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

Ron Goldman is a researcher at Sun Microsystems Laboratories in California working on alternative software development methodologies and new software architectures inspired by biology. He has been working with open source since hacking on GDB at Lucid, Inc. back in 1992. Since 1998 he has been helping groups at Sun Microsystems understand open source and advising them on how to build successful communities around their open source projects.
Prior to Sun he developed a program to generate and manipulate visual representations of complex data for use by social scientists as part of a collaboration between NYNEX Science & Technology and the Institute for Research on Learning. He has worked on programming language design, programming environments, user interface design, and data visualization. He has a PhD in computer science from Stanford University where he was a member of the robotics group.

Inhalt

Front Cover 1
Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling 4
Copyright Page 5
Contents 8
Foreword 14
Preface 16
Chapter 1. Introduction: Foundations 26
1.1 Ambient Spaces 26
1.2 Coordinates 52
1.3 Curve and Surface Representations 63
1.4 Summary 68
Part I: Interpolation 70
Chapter 2. Lagrange Interpolation and Neville's Algorithm 72
2.1 Linear Interpolation 72
2.2 Neville's Algorithm 74
2.3 The Structure of Neville's Algorithm 79
2.4 Uniqueness of Polynomial Interpolants and Taylor's Theorem 81
2.5 Lagrange Basis Functions 83
2.6 Computational Techniques for Lagrange Interpolation 90
2.7 Rational Lagrange Curves 94
2.8 Fast Fourier Transform 102
2.9 Recapitulation 108
2.10 Surface Interpolation 109
2.11 Rectangular Tensor Product Lagrange Surfaces 111
2.12 Triangular Lagrange Patches 119
2.13 Uniqueness of the Bivariate Lagrange Interpolant 128
214 Rational Lagrange Surfaces 132
2.15 Ruled, Lofted, and Boolean Sum Surfaces 136
2.16 Summary 142
Chapter 3. Hermite Interpolation and the Extended Neville Algorithm 144
3.1 Cubic Hermite Interpolation 144
3.2 Neville's Algorithm for General Hermite Interpolation 149
3.3 The Hermite Basis Functions 155
3.4 Rational Hermite Curves 160
3.5 Hermite Surfaces 168
3.6 Summary 179
Chapter 4. Newton Interpolation and Difference Triangles 180
4.1 The Newton Basis 181
4.2 Divided Differences 182
4.3 Properties of Divided Differences 190
4.4 An Axiomatic Approach to Divided Difference 195
4.5 Forward Differencing 198
4.6 Summary 205
Part II: Approximation 210
Chapter 5. Bezier Approximation and Pascal's Triangle 212
5.1 De Casteljau's Algorithm 213
5.2 Elementary Properties of Bezier Curves 215
5.3 The Bernstein Basis Functions and Pascal's Triangle 219
5.4 More Properties of Bernstein/Bezier Curves 225
5.5 Change of Basis Procedures and Principles of Duality 237
5.6 Differentiation and Integration 263
5.7 Rational Bezier Curves 280
5.8 Bezier Surfaces 292
5.9 Summary 322
Chapter 6. Blossoming 332
6.1 Blossoming the de Casteljau Algorithm 332
6.2 Existence and Uniqueness of the Blossom 335
6.3 Change of Basis Algorithms 342
6.4 Differentiation and the Homogeneous Blossom 346
6.5 Blossoming Bezier Patches 352
6.6 Summary 365
Chapter 7. B-Spline Approximation and the de Boor Algorithm 372
7.1 The de Boor Algorithm 372
7.2 Progressive Polynomial Bases Generated by Progressive Knot Sequences 380
7.3 B-Spline Curves 383
7.4 Elementary Properties of B-Spline Curves 386
7.5 All Splines Are B-Splines 389
7.6 Knot Insertion Algorithms 392
7.7 The B-Spline Basis Functions 408
7.8 Uniform B-Splines 430
7.9 Rational B-Splines 443
7.10 Catmull-Rom Splines 447
7.11 Tensor Product B-Spline Surfaces 452
7.12 Pyramid Algorithms and Triangular B-Patches 455
7.13 Summary 462
Chapter 8. Pyramid Algorithms for Multisided Bezier Patches 470
8.1 Barycentric Coordinates for Convex Polygons 471
8.2 Polygonal Arrays 475
8.3 Neville's Pyramid Algorithm and Multisided Grids 479
8.4 S-Patches 482
8.5 Pyramid Patches and the General Pyramid Algorithm 498
8.6 C-Patches 501
8.7 Toric Bezier Patches 513
8.8 Summary 554
Index 556
About the Author 577

Produkt-Details

• Erscheint lt. Verlag: 16.7.2002
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Grafik / Design
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Geometrie / Topologie
• ISBN-10: 0-08-051547-9 / 0080515479
• ISBN-13: 978-0-08-051547-2 / 9780080515472