Since their first appearance in 1974, subdivision algorithms for generating surfaces of arbitrary topology have gained widespread popularity in computer graphics and are being evaluated in engineering applications. This development was complemented by ongoing efforts to develop appropriate mathematical tools for a thorough analysis, and today, many of the fascinating properties of subdivision are well understood. This book summarizes the current knowledge on the subject. It contains both meanwhile classical results as well as brand-new, unpublished material, such as a new framework for constructing C^2-algorithms. The focus of the book is on the development of a comprehensive mathematical theory, and less on algorithmic aspects. It is intended to serve researchers and engineers - both new to the beauty of the subject - as well as experts, academic teachers and graduate students or, in short, anybody who is interested in the foundations of this flourishing branch of applied geometry.

Contenu

1 Introduction and Overview 1.1 Refined polyhedra 1.2 Control nets 1.3 Splines with singularities 1.4 Focus and scope 1.5 Overview 1.6 Notation 1.7 Analysis in the shift-invariantsetting 1.8 Historical notes on subdivision on irregular meshes 2 Geometry near Singularities 2.1 Dot and cross products 2.2 Regular surfaces 2.3 Surfaces with a singular point 2.4 Criteria for injectivity 2.5 Bibliographic notes 3 Generalized Splines 3.1 An alternative view of spline curves 3.2 Continuous bivariate splines 3.3 Ck -splines 3.4 Ckr-splines 3.5 A bicubic illustration 3.6 Bibliographic notes 4 Subdivision Surfaces 4.1 Refinability 4.2 Segments and rings 4.3 Splines infinite-dimensional subspaces 4.4 Subdivision algorithms 4.5 Asymptotic expansion of sequences 4.6 Jordan decomposition 4.7 The subdivision matrix 4.8 Bibliographic notes 5 Ck1 -subdivision algorithms 5.1 Generic initial data 5.2 Standard algorithms 5.3 General algorithms 5.4 Shiftinvariant algorithms 5.5 Symmetric algorithms 5.6 Bibliographic notes 6 Case Studies of Ck 1-Subdivision Algorithms 6.1 Catmull-Clark algorithm and variants 6.2 Doo-Sabin algorithm and variants 6.3 Simplest subdivision 6.4 Bibliographic notes 7 Shape analysis and Ck 2-algorithms 7.1 Higher order asymptotic expansions 7.2 Shape assessment 7.3 Conditions for Ck2 -algorithms 7.4 A framework for Ck2 -algorithms 7.5 Guided subdivision 7.6 Bibliographical notes 8 Approximation and Linear Independence 8.1 Proxy splines 8.2 Local and global linear independence 8.3 Bibliographic notes 9 Conclusion 9.1 Function spaces 9.2 Recursion 9.3 Combinatorial structure References Index