Introduction to the mathematics of subdivision surfaces

Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
Dedication......Page 6
Contents\0......Page 8
List of Figures\0......Page 12
List of Tables\0......Page 16
Preface\0......Page 18
Notation, Conventions, Abbreviations\0......Page 22
1.1 A brief overview\0......Page 27
1.2.1 Polyhedral meshes\0......Page 35
1.2.2 Primal and dual subdivision methods\0......Page 42
1.2.3 Stencils\0......Page 46
1.3 Examples and classification\0......Page 47
1.3.1 The methods of Catmull¨CClark, Doo¨CSabin, and Loop\0......Page 48
1.3.2 A classification of subdivision methods\0......Page 59
1.4.1 The global subdivision matrix\0......Page 64
1.4.2 Global subdivision matrices for B-spline functions\0......Page 66
1.4.3 Local subdivision matrices\0......Page 68
1.5 Generating fractal-like objects\0......Page 71
1.7 Exercises\0......Page 73
1.8 Projects\0......Page 75
2 B-Spline Surfaces\0......Page 77
2.1 Mathematical preliminaries\0......Page 78
2.2.1 Definition of B-spline basis functions using convolution\0......Page 81
2.2.2 Recursion formulas for uniform B-splines\0......Page 84
2.2.3 The Lane¨CRiesenfeld algorithm\0......Page 93
2.2.4 Two important principles\0......Page 97
2.3 Tensor-product surfaces\0......Page 100
2.4 B-spline methods for finite meshes\0......Page 105
2.5.1 Differentiation\0......Page 106
2.5.2 Partition of unity\0......Page 109
2.5.3 Linear independence\0......Page 110
2.5.4 A linear function space\0......Page 111
2.5.5 Computation of exact values\0......Page 112
2.5.6 Application to the tensor-product-surface case\0......Page 116
2.7 Exercises\0......Page 117
3.1 Notation and definitions\0......Page 119
3.2 Properties of box-spline nodal functions\0......Page 123
3.3 Continuity properties of box splines\0......Page 137
3.4 Box-spline subdivision polynomials\0......Page 138
3.5.1 Centered nodal functions and subdivision polynomials\0......Page 142
3.5.2 Recursion formulas for control points of box-spline surfaces\0......Page 143
3.6 Partition of unity and linear independence for box splines\0......Page 152
3.7 Box-spline methods and variants for finite meshes\0......Page 156
3.7.1 The Loop method and its extension to higher orders\0......Page 157
3.7.2 The Midedge and 4-8 subdivision methods\0......Page 159
3.9 Exercises\0......Page 167
4 Generalized-Spline Surfaces\0......Page 171
4.1 General subdivision polynomials\0......Page 172
4.2.1 Examples of non-box-spline schemes: 4pt ?á 4pt, Butterfly,?ì 3-subdivision (regular case)\0......Page 175
4.2.2 Comparison of 4-8 and ?ì3-subdivision (regular case)\0......Page 185
4.2.3 Some Generalized-spline methods:?ì3-subdivision, Modified Butterfly, and Kobbelt\0......Page 187
4.3 Fourier analysis of nodal functions\0......Page 192
4.4 Support of nodal functions generated by subdivision polynomials\0......Page 196
4.5 Affine invariance for subdivision defined by a subdivision polynomial\0......Page 198
4.6.1 The two-dimensional manifold\0......Page 199
4.6.2 A topology on the manifold\0......Page 202
4.6.4 Construction of the local homeomorphisms\0......Page 204
4.7 Generalized splines and Generalized-spline subdivision methods\0......Page 207
4.9 Exercises\0......Page 212
5 Convergence and Smoothness\0......Page 215
5.1 Preliminary results for the regular case\0......Page 216
5.2 Convergence of box-spline subdivision processes\0......Page 223
5.2.1 Linear convergence\0......Page 224
5.2.2 Quadratic convergence\0......Page 228
5.3 Convergence and smoothness for general subdivision polynomials\0......Page 233
5.3.1 Convergence analysis\0......Page 234
5.3.2 Smoothness\0......Page 241
5.4 General comments on the nonregular case\0......Page 245
5.5.1 The parametric domain\0......Page 249
5.5.2 Spectral analysis\0......Page 250
5.5.3 Convergence\0......Page 258
5.6 Smoothness analysis for the Catmull¨CClark scheme\0......Page 260
5.7 Conditions for single sheetedness\0......Page 265
5.8 Further reading on convergence and smoothness\0......Page 269
5.10 Exercises\0......Page 271
5.11 Project\0......Page 272
6 Evaluation and Estimation of Surfaces\0......Page 273
6.1.1 Evaluation stencils\0......Page 274
6.1.2 Tangent stencils\0......Page 277
6.2 Evaluation and tangent stencils for subdivision-polynomial methods\0......Page 281
6.2.1 Evaluation of nodal functions at grid points\0......Page 282
6.2.2 Evaluation of derivatives of the nodal functions\0......Page 284
6.3.1 A method of de Boor\0......Page 286
6.3.2 Stam?ˉs method\0......Page 289
6.4 Precision sets and polynomial reproduction\0......Page 292
6.4.1 Conditions for given reproduction and generation degree\0......Page 293
6.4.2 Polynomial precision for box splines\0......Page 300
6.4.3 Polynomial precision for non-box-splines\0......Page 302
6.5 Bounding envelopes for patches\0......Page 306
6.5.1 Modified nodal functions\0......Page 307
6.5.2 Bounding linear functions\0......Page 308
6.8 Exercises\0......Page 310
6.9 Projects\0......Page 312
7.1 Shape control for primal methods\0......Page 313
7.1.1 Surface boundaries and sharp edges\0......Page 314
7.1.2 The Biermann¨CLevin¨CZorin rules for sharp edges\0......Page 318
7.1.3 Interpolation of position and normal direction\0......Page 320
7.2 Shape control for dual methods\0......Page 321
7.2.1 Control-point modification\0......Page 322
7.3 Further reading on shape control\0......Page 323
7.3.1 Subdivision-based multiresolution editing\0......Page 324
7.3.2 Mesh-decimation multiresolution editing\0......Page 329
7.5 Exercises\0......Page 330
7.6 Projects\0......Page 331
A.1 Equivalence of Catmull¨CClark rules\0......Page 333
A.2.1 The Fourier transform: Univariate case\0......Page 336
A.2.2 The Fourier transform: Bivariate case\0......Page 338
A.2.4 Discrete complex Fourier series\0......Page 340
A.3.1 Fourier transforms of box-spline nodal functions\0......Page 341
A.3.2 Proof of Theorem 3.3.2\0......Page 343
A.4 Products of convergent subdivision polynomials\0......Page 346
A.5 Exercises\0......Page 349
Notes\0......Page 351
Bibliography\0......Page 363
Index\0......Page 375