Wavelet Subdivision Methods: GEMS for Rendering Curves and Surfaces

by Charles Chui, Johan de Villiers

Overview

Prevalent in animation movies and interactive games, subdivision methods allow users to design and implement simple but efficient schemes for rendering curves and surfaces. Adding to the current subdivision toolbox, Wavelet Subdivision Methods: GEMS for Rendering Curves and Surfaces introduces geometry editing and manipulation schemes (GEMS) and covers both subdivision and wavelet analysis for generating and editing parametric curves and surfaces of desirable geometric shapes. The authors develop a complete constructive theory and effective algorithms to derive synthesis wavelets with minimum support and any desirable order of vanishing moments, along with decomposition filters.

Through numerous examples, the book shows how to represent curves and construct convergent subdivision schemes. It comprehensively details subdivision schemes for parametric curve rendering, offering complete algorithms for implementation and theoretical development as well as detailed examples of the most commonly used schemes for rendering both open and closed curves. It also develops an existence and regularity theory for the interpolatory scaling function and extends cardinal B-splines to box splines for surface subdivision.

Keeping mathematical derivations at an elementary level without sacrificing mathematical rigor, this book shows how to apply bottom-up wavelet algorithms to curve and surface editing. It offers an accessible approach to subdivision methods that integrates the techniques and algorithms of bottom-up wavelets.

Product Details

ISBN-13:	9781439812150
Publisher:	Taylor & Francis
Publication date:	08/23/2010
Edition description:	New Edition
Pages:	480
Product dimensions:	6.12(w) x 9.19(h) x (d)

About the Author

Charles Chui is a Curators’ Professor in the Department of Mathematics and Computer Science at the University of Missouri in St. Louis, and a consulting professor of statistics at Stanford University in California. Dr. Chui’s research interests encompass applied and computational mathematics, with an emphasis on splines, wavelets, mathematics of imaging, and fast algorithms.

Johan de Villiers is a professor in the Department of Mathematical Sciences, Mathematics Division at Stellenbosch University in South Africa. Dr. de Villiers’s research interests include computational mathematics, with an emphasis on wavelet and subdivision analysis.

Table of Contents

List of Figures xi

List of Tables xv

Foreword xvii

Preface xix

Teaching and Reading Guides xxiii

1 Overview 1

1.1 Curve representation and drawing 2

1.2 Free-form parametric curves 5

1.3 From subdivision to basis functions 11

1.4 Wavelet subdivision and editing 16

1.5 Surface subdivision 29

1.6 Exercises 32

2 Basis Functions for Curve Representation 37

2.1 Refinability and scaling functions 39

2.2 Generation of smooth basis functions 46

2.3 Cardinal B-splines 52

2.4 Stable bases for integer-shift spaces 56

2.5 Splines and polynomial reproduction 62

2.6 Exercises 67

3 Curve Subdivision Schemes 75

3.1 Subdivision matrices and stencils 76

3.2 B-spline subdivision schemes 85

3.3 Closed curve rendering 95

3.4 Open curve rendering 106

3.5 Exercises 129

4 Basis Functions Generated by Subdivision Matrices 133

4.1 Subdivision operators 134

4.2 The up-sampling convolution operation 138

4.3 Scaling functions from subdivision matrices 141

4.4 Convergence of subdivision schemes 154

4.5 Uniqueness and symmetry 160

4.6 Exercises 163

5 Quasi-Interpolation 169

5.1 Sum-rule orders and discrete moments 170

5.2 Representation of polynomials 173

5.3 Characterization of sum-rule orders 178

5.4 Quasi-interpolants 182

5.5 Exercises 198

6 Convergence and Regularity Analysis 205

6.1 Cascade operators 206

6.2 Sufficient conditions for convergence 211

6.3 Hölder regularity 218

6.4 Positive refinement sequences 225

6.5 Convergence and regularity governed by two-scale symbols 233

6.6 A one-parameter family 244

6.7 Stability of the one-parameter family 255

6.8 Exercises 260

7 Algebraic Polynomial Identities 271

7.1 Fundamental existence and uniqueness theorem 272

7.2 Normalized binomial symbols 280

7.3 Behavior on the unit circle in the complex plane 288

7.4 Exercises 291

8 Interpolatory Subdivision 295

8.1 Scaling functions generated by interpolatory refinement sequences 296

8.2 Convergence, regularity, and symmetry 302

8.3 Rendering of closed and open interpolatory curves 312

8.4 A one-parameter family of interpolatory subdivision operators 322

8.5 Exercises 333

9 Wavelets for Subdivision 339

9.1 From scaling functions to synthesis wavelets 340

9.2 Synthesis wavelets with prescribed vanishing moments 351

9.3 Robust stability of synthesis wavelets 364

9.4 Spline-wavelets 370

9.5 Interpolation wavelets 385

9.6 Wavelet subdivision and editing 401

9.7 Exercises 406

10 Surface Subdivision 411

10.1 Control nets and net refinement 413

10.2 Box splines as basis functions 422

10.3 Surface subdivision masks and stencils 427

10.4 Wavelet surface subdivision 437

10.5 Exercises 442

11 Epilogue 445

Supplementary Readings 449

Index 451

What People are Saying About This

From the Publisher

The monograph contains many examples, figures, and more than 300 exercises. It is friendly written for a broad readership and very convenient for students and researchers in applied mathematics and computer science. Doubtless, this nice book will stimulate further research in modeling of curves and surfaces with wavelet subdivision methods.
—Manfred Tasche, Zentralblatt MATH 1202

All topics are treated with great care, and a lot of effort is put into stating results and proofs with a very high precision and accuracy. This makes the book so self-contained that its list of references consists of only 24 items. This is exceptional for a monograph of 450 pages and quite clearly shows the intention of the authors and the approach they have taken for their book. … the book provides everything that is useful, for example, for classroom use: examples, exercises (even with marked difficulty levels), a carefully compiled index and even a very impressive reading guide. … Its extraordinary attention to detail makes it useful to undergraduate students or researchers who want to get familiar with the fundamental techniques of stationary subdivision, who want to see "how the machine works inside".
—Tomas Sauer, Mathematical Reviews, Issue 2011k

This book is the first writing that introduces and incorporates the wavelet component of the bottom-up subdivision scheme. A complete constructive theory, together with effective algorithms, is developed to derive such synthesis wavelets and analysis wavelet filters. The book contains a large collection of carefully prepared exercises and can be used both for classroom teaching and for self study. The authors have been in the forefront for advances in wavelets and wavelet subdivision methods and I congratulate them for writing such a comprehensive text.
—From the Foreword by Tom Lyche, University of Oslo, Norway

Editorial Reviews

The monograph contains many examples, figures, and more than 300 exercises. It is friendly written for a broad readership and very convenient for students and researchers in applied mathematics and computer science. Doubtless, this nice book will stimulate further research in modeling of curves and surfaces with wavelet subdivision methods.
—Manfred Tasche, Zentralblatt MATH 1202

All topics are treated with great care, and a lot of effort is put into stating results and proofs with a very high precision and accuracy. This makes the book so self-contained that its list of references consists of only 24 items. This is exceptional for a monograph of 450 pages and quite clearly shows the intention of the authors and the approach they have taken for their book. … the book provides everything that is useful, for example, for classroom use: examples, exercises (even with marked difficulty levels), a carefully compiled index and even a very impressive reading guide. … Its extraordinary attention to detail makes it useful to undergraduate students or researchers who want to get familiar with the fundamental techniques of stationary subdivision, who want to see "how the machine works inside".
—Tomas Sauer, Mathematical Reviews, Issue 2011k

This book is the first writing that introduces and incorporates the wavelet component of the bottom-up subdivision scheme. A complete constructive theory, together with effective algorithms, is developed to derive such synthesis wavelets and analysis wavelet filters. The book contains a large collection of carefully prepared exercises and can be used both for classroom teaching and for self study. The authors have been in the forefront for advances in wavelets and wavelet subdivision methods and I congratulate them for writing such a comprehensive text.
—From the Foreword by Tom Lyche, University of Oslo, Norway

From the Publisher